X-Git-Url: https://git.draconx.ca/gitweb/cdecl99.git/blobdiff_plain/5b6fc836137be0073e1a15895c6375429762c147..72aedaedd7afa666f7c69dfe7ef4b7ec3dbc2458:/src/parse.y diff --git a/src/parse.y b/src/parse.y index 86091f9..14d593e 100644 --- a/src/parse.y +++ b/src/parse.y @@ -1,6 +1,7 @@ +%code top { /* * Parser for C declarations. - * Copyright © 2011 Nick Bowler + * Copyright © 2011-2012, 2021, 2023 Nick Bowler * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -15,33 +16,106 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see . */ +} +%name-prefix "cdecl__yy" +%parse-param {void *scanner} %parse-param {struct cdecl **out} +%lex-param {yyscan_t scanner} %define api.pure %error-verbose %locations %{ +#include #include +#include #include "scan.h" #include "cdecl.h" +#include "cdecl-internal.h" +#include "errmsg.h" #define FAIL(msg) do { \ - yyerror(&yylloc, NULL, msg); \ + yyerror(&yylloc, NULL, NULL, msg); \ YYERROR; \ } while (0) -#define ALLOC(ptr, size) do { \ - (ptr) = malloc(size); \ - if (!(ptr)) \ - FAIL("failed to allocate memory"); \ +/* + * Allocate a parse tree node via cdecl__alloc_item. + * + * - m1 specifies the item's union member to assign to ptr, which selects the + * type of node to allocate. + * + * - m2 specifies the "next" or "child" member, which is initialized to a null + * pointer. The cdecl__alloc_item function sets the declarator.child member + * to null; we explicitly copy this null pointer to the returned union member + * to avoid type punning. It is hoped that compilers will notice that these + * pointers are at the same offset therefore the assignment can be elided. + * + * The resulting pointer can be passed directly to free, as the union is the + * first member of the parse_item structure. + * + * Use the wrapper macros below instead of this one. + */ +#define ALLOC_ITEM(ptr, m1, m2) do { \ + struct parse_item *item; \ + if (!(item = cdecl__alloc_item(0))) \ + YYERROR; \ + item->u.m1.m2 = (void *)item->u.declarator.child; \ + (ptr) = &item->u.m1; \ +} while (0) + +/* Wrappers for ALLOC_ITEM to allocate various kinds of parser structures. */ +#define ALLOC_ITEM_DECLARATOR(ptr) ALLOC_ITEM(ptr, declarator, child) +#define ALLOC_ITEM_DECLSPEC(ptr) ALLOC_ITEM(ptr, declspec, next) +#define ALLOC_ITEM_DECL(ptr) ALLOC_ITEM(ptr, decl, next) + +#define ALLOC_FUNCTION(ptr, parameters_, variadic_) do { \ + ALLOC_ITEM_DECLARATOR(ptr); \ + (ptr)->type = CDECL_DECL_FUNCTION; \ + (ptr)->u.function.parameters = parameters_; \ + (ptr)->u.function.variadic = variadic_; \ +} while (0) + +#define ALLOC_ARRAY(ptr, length_) do { \ + ALLOC_ITEM_DECLARATOR(ptr); \ + (ptr)->type = CDECL_DECL_ARRAY; \ + (ptr)->u.array.vla = NULL; \ + (ptr)->u.array.length = length_; \ +} while (0) + +#define ALLOC_POINTER(ptr, qualifiers_, child_) do { \ + ALLOC_ITEM_DECLARATOR(ptr); \ + (ptr)->child = child_; \ + (ptr)->type = CDECL_DECL_POINTER; \ + (ptr)->u.pointer.qualifiers = qualifiers_; \ +} while (0) + +#define ALLOC_DECLSPEC(ptr, type_) do { \ + ALLOC_ITEM_DECLSPEC(ptr); \ + (ptr)->type = type_; \ + (ptr)->ident = NULL; \ } while (0) -#define ALLOC_STRUCT(ptr, type, ...) do { \ - ALLOC(ptr, sizeof (type)); \ - *(ptr) = (type) { __VA_ARGS__ }; \ +#define ALLOC_DECL(ptr, specifiers_, declarators_) do { \ + ALLOC_ITEM_DECL(ptr); \ + (ptr)->specifiers = specifiers_; \ + (ptr)->declarators = declarators_; \ } while (0) + +/* + * With the postprocessing performed by fix-yytname.awk, all the symbol + * name strings can be used directly in error messages and there is no + * need for any string processing. + */ +#define yytnamerr(a, b) ( (a) ? yytnamerr_copy(a, b) \ + : strlen(b) ) + +static size_t yytnamerr_copy(char *dst, const char *src) +{ + return cdecl__strlcpy(dst, src, strlen(src)+1); +} %} %code requires { @@ -49,25 +123,30 @@ } %code provides { -void yyerror(YYLTYPE *, struct cdecl **, const char *); -int yyparse(struct cdecl **out); +void cdecl__free(struct cdecl *); +int cdecl__yyparse(void *scanner, struct cdecl **out); +const char *cdecl__token_name(unsigned token); } %union { uintmax_t uintval; - char *strval; + unsigned spectype; + _Bool boolval; struct cdecl_declspec *declspec; struct cdecl_declarator *declarator; struct cdecl *decl; + struct parse_item *item; } %{ +static void yyerror(YYLTYPE *, yyscan_t, struct cdecl **, const char *); +static void free_decl(struct cdecl *); + static void free_declspec(struct cdecl_declspec *x) { struct cdecl_declspec *p; while (x) { p = x->next; - free(x->ident); free(x); x = p; } @@ -82,15 +161,15 @@ static void free_declarator(struct cdecl_declarator *x) switch (x->type) { case CDECL_DECL_NULL: - break; + x = NULL; case CDECL_DECL_IDENT: - free(x->u.ident); + case CDECL_DECL_ARRAY: break; case CDECL_DECL_POINTER: free_declspec(x->u.pointer.qualifiers); break; - case CDECL_DECL_ARRAY: - free(x->u.array.vla); + case CDECL_DECL_FUNCTION: + free_decl(x->u.function.parameters); break; default: assert(0); @@ -118,21 +197,58 @@ static void free_decl(struct cdecl *x) } } -void cdecl_free(struct cdecl *decl) +void cdecl__free(struct cdecl *decl) { free_decl(decl); } + +/* + * Join two declaration specifier lists into a single list, with "a" being the + * head of the new list. + * + * The list "a" is assumed to be nonempty. + */ +static void join_specs(struct cdecl_declspec *a, struct cdecl_declspec *b) +{ + while (a->next) + a = a->next; + a->next = b; +} + +/* + * Alter an abstract declarator (type name) to declare an identifier instead, + * used by the English parser rules to reduce "identifier as type" sequences. + */ +static struct cdecl *insert_identifier(struct cdecl *decl, struct parse_item *ident) +{ + struct cdecl_declarator *d, **p = &decl->declarators; + + while ((d = *p)->child) + p = &d->child; + + *p = &ident->u.declarator; + return decl; +} + +static struct cdecl_declarator *nulldecl(void) +{ + static const struct cdecl_declarator nulldecl = {0}; + return (void *)&nulldecl; +} +#define NULLDECL (nulldecl()) + %} -%destructor { free($$); } +%destructor { free($$); } %destructor { free_declspec($$); } %destructor { free_declarator($$); } %destructor { free_decl($$); } +/* Magic tokens */ %token T_LEX_ERROR -%token T_IDENT "identifier" -%token T_UINT "integer constant" +%token T_IDENT "identifier" +%token T_UINT "integer constant" %token T_SEMICOLON ";" %token T_ASTERISK "*" @@ -141,56 +257,101 @@ void cdecl_free(struct cdecl *decl) %token T_LBRACKET "[" %token T_RBRACKET "]" %token T_COMMA "," +%token T_ELLIPSIS "..." + +%token T_TYPEDEF "typedef" +%token T_EXTERN "extern" +%token T_STATIC "static" +%token T_AUTO "auto" +%token T_REGISTER "register" + +%token T_INLINE "inline" + +%token T_RESTRICT "restrict" +%token T_VOLATILE "volatile" +%token T_CONST "const" + +%token T_VOID "void" +%token T_CHAR "char" +%token T_SHORT "short" +%token T_INT "int" +%token T_LONG "long" +%token T_FLOAT "float" +%token T_DOUBLE "double" +%token T_SIGNED "signed" +%token T_UNSIGNED "unsigned" +%token T_BOOL "_Bool" +%token T_COMPLEX "_Complex" +%token T_IMAGINARY "_Imaginary" + +%token T_STRUCT "struct" +%token T_UNION "union" +%token T_ENUM "enum" -%token T_TYPEDEF "typedef" -%token T_EXTERN "extern" -%token T_STATIC "static" -%token T_AUTO "auto" -%token T_REGISTER "register" - -%token T_INLINE "inline" - -%token T_RESTRICT "restrict" -%token T_VOLATILE "volatile" -%token T_CONST "const" - -%token T_VOID "void" -%token T_CHAR "char" -%token T_SHORT "short" -%token T_INT "int" -%token T_LONG "long" -%token T_FLOAT "float" -%token T_DOUBLE "double" -%token T_SIGNED "signed" -%token T_UNSIGNED "unsigned" -%token T_BOOL "_Bool" -%token T_COMPLEX "_Complex" - -%token T_STRUCT "struct" -%token T_UNION "union" -%token T_ENUM "enum" - -%type vla_ident -%type declspec_simple typespec_simple qualifier_simple +/* + * English keywords. + */ +%token T_TYPE "type" +%token T_DECLARE "declare" +%token T_POINTER "pointer" +%token T_FUNCTION "function" +%token T_RETURNING "returning" +%token T_ARRAY "array" +%token T_TO "to" +%token T_OF "of" +%token T_AS "as" +%token T_VLA "variable-length" + +%type vla_ident +%type array_length +%type varargs +%type declspec_simple qualifier_simple +%type typespec_simple typespec_tagged %type declspec_notype declspec_noid typespec_noid typespec %type qualifier qualifiers %type declspecs declspecs_noid -%type direct_declarator declarator pointer array -%type declaration declarators declarator_wrap +%type direct_declarator declarator pointer array parens postfix +%type direct_declarator_ish declarator_ish parameter_type_list +%type cdecl declaration declarators declarator_wrap parameter + +%type english_vla +%type storage_func_specs post_specs +%type type_qual_spec type_qual_specs typedef_name_qual +%type english_declarator english_array english_function +%type english_parameter_list null_decl +%type english english_declaration english_parameter + +/* Precedence declaration to avoid conflict in english_parameter; see below. */ +%right T_TYPE +%right T_IDENT %% -input: declaration { - *out = $1; -}; +input: cdecl { *out = $1; } +cdecl: english | declaration -declaration: declspecs declarators T_SEMICOLON { +semi: | T_SEMICOLON +declaration: declspecs declarators semi { $$ = $2; - - for (struct cdecl *i = $$; i; i = i->next) - i->specifiers = $1; + $$->specifiers = $1; }; +/* + * We support parsing declarations using arbitrary identifiers as type + * specifiers (a la C typedef). To avoid confusion with identifiers that + * may also be used as declarators, note the following: + * + * (a) Every valid C declaration must have at least one type specifier, and + * (b) Valid declarations with typedef names have exactly one type specifier. + * + * So the rule applied when parsing specifiers is: an identifier is a type + * specifier only if we have not yet seen any type specifiers whatsoever + * (within one declaration specifier list). + * + * Treating identifiers as type specifiers by default can lead to strange and + * unexpected parses; libcdecl applies a simplification step to the resulting + * parse tree afterwards. + */ declspecs: declspec_notype declspecs { $$ = $1; $$->next = $2; @@ -215,118 +376,252 @@ declarators: declarator_wrap | declarator_wrap T_COMMA declarators { } declarator_wrap: declarator { - ALLOC_STRUCT($$, struct cdecl, .declarators = $1); -} - -declspec_simple: T_AUTO { $$ = CDECL_STOR_AUTO; } - | T_TYPEDEF { $$ = CDECL_STOR_TYPEDEF; } - | T_EXTERN { $$ = CDECL_STOR_EXTERN; } - | T_STATIC { $$ = CDECL_STOR_STATIC; } - | T_REGISTER { $$ = CDECL_STOR_REGISTER; } - | T_INLINE { $$ = CDECL_FUNC_INLINE; } - -typespec_simple: T_VOID { $$ = CDECL_TYPE_VOID; } - | T_CHAR { $$ = CDECL_TYPE_CHAR; } - | T_SHORT { $$ = CDECL_TYPE_SHORT; } - | T_INT { $$ = CDECL_TYPE_INT; } - | T_LONG { $$ = CDECL_TYPE_LONG; } - | T_FLOAT { $$ = CDECL_TYPE_FLOAT; } - | T_DOUBLE { $$ = CDECL_TYPE_DOUBLE; } - | T_SIGNED { $$ = CDECL_TYPE_SIGNED; } - | T_UNSIGNED { $$ = CDECL_TYPE_UNSIGNED; } - | T_BOOL { $$ = CDECL_TYPE_BOOL; } - | T_COMPLEX { $$ = CDECL_TYPE_COMPLEX; } - -qualifier_simple: T_CONST { $$ = CDECL_QUAL_CONST; } - | T_RESTRICT { $$ = CDECL_QUAL_RESTRICT; } - | T_VOLATILE { $$ = CDECL_QUAL_VOLATILE; } - -declspec_notype: qualifier | declspec_simple { - ALLOC_STRUCT($$, struct cdecl_declspec, .type = $1); -} - -typespec_noid: typespec_simple { - ALLOC_STRUCT($$, struct cdecl_declspec, .type = $1); -} - -qualifier: qualifier_simple { - ALLOC_STRUCT($$, struct cdecl_declspec, .type = $1); -} - -typespec: typespec_noid | T_STRUCT T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = CDECL_TYPE_STRUCT, - .ident = $2); -} | T_UNION T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = CDECL_TYPE_UNION, - .ident = $2); -} | T_ENUM T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = CDECL_TYPE_ENUM, - .ident = $2); -} | T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declspec, - .type = CDECL_TYPE_IDENT, - .ident = $1); + ALLOC_DECL($$, NULL, $1); +} + +declspec_simple: T_AUTO + | T_TYPEDEF + | T_EXTERN + | T_STATIC + | T_REGISTER + | T_INLINE + +typespec_simple: T_VOID + | T_CHAR + | T_SHORT + | T_INT + | T_LONG + | T_FLOAT + | T_DOUBLE + | T_SIGNED + | T_UNSIGNED + | T_BOOL + | T_COMPLEX + | T_IMAGINARY + +typespec_tagged: T_STRUCT | T_UNION | T_ENUM | { $$ = CDECL_TYPE_IDENT; } + +qualifier_simple: T_CONST + | T_RESTRICT + | T_VOLATILE + +declspec_notype: qualifier | declspec_simple { ALLOC_DECLSPEC($$, $1); } +typespec_noid: typespec_simple { ALLOC_DECLSPEC($$, $1); } +qualifier: qualifier_simple { ALLOC_DECLSPEC($$, $1); } + +typespec: typespec_noid | typespec_tagged T_IDENT { + /* Compiler should be able to elide this assignment. */ + $2->u.declspec.ident = $2->u.declarator.u.ident; + + $$ = &$2->u.declspec; + $$->type = $1; } declspec_noid: declspec_notype | typespec_noid vla_ident: T_IDENT | T_ASTERISK { - ALLOC($$, sizeof ""); - strcpy($$, ""); + if (!($$ = cdecl__alloc_item(1))) + YYERROR; + *$$->s = 0; } -array: T_LBRACKET T_UINT T_RBRACKET { - if ($2 == 0) - FAIL("array length must be positive"); - - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.length = $2); +array: T_LBRACKET array_length T_RBRACKET { + ALLOC_ARRAY($$, $2); } | T_LBRACKET vla_ident T_RBRACKET { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY, - .u.array.vla = $2); -} | T_LBRACKET T_RBRACKET { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_ARRAY); + $$ = &$2->u.declarator; + $$->type = CDECL_DECL_ARRAY; + $$->u.array.vla = $$->u.ident; + $$->u.array.length = 0; +} + +parameter: declspecs declarator { + ALLOC_DECL($$, $1, $2); +} + +varargs: { $$ = false; } | T_COMMA T_ELLIPSIS { $$ = true; } + +parameter_type_list: parameter varargs { + ALLOC_FUNCTION($$, $1, $2); +} | parameter T_COMMA parameter_type_list { + $$ = $3; + $1->next = $$->u.function.parameters; + $$->u.function.parameters = $1; +} + +parens: T_LPAREN parameter_type_list T_RPAREN { + $$ = $2; +} | T_LPAREN declarator_ish T_RPAREN { + struct cdecl *fake_params; + + ALLOC_DECL(fake_params, NULL, $2); + ALLOC_FUNCTION($$, fake_params, false); } pointer: T_ASTERISK qualifiers direct_declarator { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_POINTER, - .u.pointer.qualifiers = $2, - .child = $3); + ALLOC_POINTER($$, $2, $3); } | T_ASTERISK qualifiers pointer { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_POINTER, - .u.pointer.qualifiers = $2, - .child = $3); + ALLOC_POINTER($$, $2, $3); } declarator: direct_declarator | pointer +declarator_ish: direct_declarator_ish | pointer +postfix: array | parens + +direct_declarator_ish: { + $$ = NULLDECL; +} | direct_declarator_ish postfix { + $$ = $2; + $$->child = $1; +} direct_declarator: { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_NULL); + $$ = NULLDECL; } | T_IDENT { - ALLOC_STRUCT($$, struct cdecl_declarator, - .type = CDECL_DECL_IDENT, - .u.ident = $1); -} | direct_declarator array { + $$ = &$1->u.declarator; +} | direct_declarator postfix { $$ = $2; $$->child = $1; -} | T_LPAREN declarator T_RPAREN { +} + +english: T_DECLARE T_IDENT T_AS english_declaration { + $$ = insert_identifier($4, $2); +} | T_TYPE english_declaration { $$ = $2; -}; +} + +/* + * We use a precedence declaration to prefer shifting an identifier + * over reducing this empty rule; see below. + */ +storage_func_specs: %prec T_TYPE { $$ = NULL; } +storage_func_specs: declspec_simple storage_func_specs { + ALLOC_DECLSPEC($$, $1); + $$->next = $2; +} + +type_qual_spec: typespec_noid | qualifier + +type_qual_specs: { $$ = NULL; } | type_qual_spec type_qual_specs { + $$ = $1; + $$->next = $2; +} + +/* + * The "qualifiers" nonterminal needs to be used here to avoid shift/reduce + * conflicts with pointer declarators. So we end up needing to stitch + * together three different specifiers lists. + */ +post_specs: qualifiers typespec type_qual_specs { + $2->next = $3; + join_specs($2, $1); + $$ = $2; +} + +english_declaration: storage_func_specs english_declarator post_specs { + join_specs($3, $1); + ALLOC_DECL($$, $3, $2); +} + +english_declarator: { + $$ = NULLDECL; +} | english_declarator qualifiers T_POINTER T_TO { + ALLOC_POINTER($$, $2, $1); +} | english_declarator english_array { + $$ = $2; + $$->child = $1; +} | english_declarator english_function { + $$ = $2; + $$->child = $1; +} + +english_function: T_FUNCTION T_RETURNING { + ALLOC_FUNCTION($$, NULL, false); +} | T_FUNCTION T_LPAREN english_parameter_list T_RPAREN T_RETURNING { + $$ = $3; +} + +english_parameter_list: english_parameter varargs { + ALLOC_FUNCTION($$, $1, $2); +} | english_parameter T_COMMA english_parameter_list { + $$ = $3; + $1->next = $$->u.function.parameters; + $$->u.function.parameters = $1; +} + +typedef_name_qual: T_IDENT qualifiers { + /* Compiler should be able to elide this assignment. */ + $1->u.declspec.ident = $1->u.declarator.u.ident; + + $$ = &$1->u.declspec; + $$->type = CDECL_TYPE_IDENT; + $$->next = $2; +} + +null_decl: { + $$ = NULLDECL; +} + +/* + * There is a shift/reduce conflict here when an identifier appears as the + * first token. The conflict is between shifting T_IDENT, or reducing the + * empty production for storage_func_specs (cf. english_declaration). + * + * - In either case, if we reduce, we won't match T_IDENT T_AS since the + * stack now has the extra storage_func_specs nonterminal symbol. + * - And if we shift, we won't match english_declaration since it is + * too late to add storage_func_specs to the stack. + * + * The only valid input affected by the conflict is a simple type names, + * possibly followed by qualifiers. So the conflict is adequately resolved + * by shifting, so long as we have a special-case reduction to handle this. + */ +english_parameter: english_declaration | typedef_name_qual null_decl { + ALLOC_DECL($$, $1, $2); +} | T_IDENT T_AS english_declaration { + $$ = insert_identifier($3, $1); +} + +english_array: T_VLA T_ARRAY english_vla T_OF { + $$ = &$3->u.declarator; + $$->type = CDECL_DECL_ARRAY; + $$->u.array.vla = $$->u.ident; + $$->u.array.length = 0; +} | T_ARRAY array_length T_OF { + ALLOC_ARRAY($$, $2); +} + +array_length: { $$ = 0; } +array_length: T_UINT { + if (!($$ = $1)) + FAIL(_("array length must be positive")); +} + +english_vla: T_IDENT | { + if (!($$ = cdecl__alloc_item(1))) + YYERROR; + *$$->s = 0; +} %% -void yyerror(YYLTYPE *loc, struct cdecl **out, const char *err) + +/* + * Expose the token string table to the rest of the library, in order to + * produce strings that match parser keywords. + * + * In order for this to work properly, the Bison output must be postprocessed + * by fix-yytname.awk to remove pointless quotation marks from the keyword + * strings. + */ +const char *cdecl__token_name(unsigned token) +{ + return yytname[YYTRANSLATE(token)]; +} + +static void +yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err) { - if (strstr(err, "T_LEX_ERROR")) + if (strstr(err, yytname[YYTRANSLATE(T_LEX_ERROR)])) return; - fprintf(stderr, "%s\n", err); + cdecl__err(CDECL_ENOPARSE, "%s", err); }