3 * Parser for C declarations.
4 * Copyright © 2011-2012, 2021, 2023-2024 Nick Bowler
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
21 %name-prefix "cdecl__yy"
22 %parse-param {void *scanner}
23 %parse-param {struct cdecl **out}
24 %lex-param {yyscan_t scanner}
35 #include "cdecl-internal.h"
39 * Allocate a parse tree node via cdecl__alloc_item.
41 * - m1 specifies the item's union member to assign to ptr, which selects the
42 * type of node to allocate.
44 * - m2 specifies the "next" or "child" member, which is initialized to a null
45 * pointer. The cdecl__alloc_item function sets the declarator.child member
46 * to null; we explicitly copy this null pointer to the returned union member
47 * to avoid type punning. It is hoped that compilers will notice that these
48 * pointers are at the same offset therefore the assignment can be elided.
50 * The resulting pointer can be passed directly to free, as the union is the
51 * first member of the parse_item structure.
53 * Use the wrapper macros below instead of this one.
55 #define ALLOC_ITEM(ptr, m1, m2) do { \
56 struct parse_item *item; \
57 if (!(item = cdecl__alloc_item(0))) \
59 item->u.m1.m2 = (void *)item->u.declarator.child; \
60 (ptr) = &item->u.m1; \
63 /* Wrappers for ALLOC_ITEM to allocate various kinds of parser structures. */
64 #define ALLOC_ITEM_DECLARATOR(ptr) ALLOC_ITEM(ptr, declarator, child)
65 #define ALLOC_ITEM_DECLSPEC(ptr) ALLOC_ITEM(ptr, declspec, next)
66 #define ALLOC_ITEM_DECL(ptr) ALLOC_ITEM(ptr, decl, next)
68 #define ALLOC_FUNCTION_(ptr, parameters_) do { \
69 ALLOC_ITEM_DECLARATOR(ptr); \
70 (ptr)->type = CDECL_DECL_FUNCTION; \
71 (ptr)->u.function.parameters = parameters_; \
74 #define ALLOC_FUNCTION(ptr, parameters_, variadic_) do { \
75 ALLOC_FUNCTION_(ptr, parameters_); \
76 (ptr)->u.function.variadic = variadic_; \
79 #define ALLOC_ARRAY(ptr, length_) do { \
80 ALLOC_ITEM_DECLARATOR(ptr); \
81 (ptr)->type = CDECL_DECL_ARRAY; \
82 (ptr)->u.array.vla = NULL; \
83 (ptr)->u.array.length = length_; \
86 #define ALLOC_POINTER(ptr, qualifiers_, child_) do { \
87 ALLOC_ITEM_DECLARATOR(ptr); \
88 (ptr)->child = child_; \
89 (ptr)->type = CDECL_DECL_POINTER; \
90 (ptr)->u.pointer.qualifiers = qualifiers_; \
93 #define ALLOC_DECLSPEC(ptr, type_) do { \
94 ALLOC_ITEM_DECLSPEC(ptr); \
95 (ptr)->type = type_; \
96 (ptr)->ident = NULL; \
99 #define ALLOC_DECL(ptr, specifiers_, declarators_) do { \
100 ALLOC_ITEM_DECL(ptr); \
101 (ptr)->specifiers = specifiers_; \
102 (ptr)->declarators = declarators_; \
106 * With the postprocessing performed by fix-yytname.awk, all the symbol
107 * name strings can be used directly in error messages and there is no
108 * need for any string processing.
110 #define yytnamerr(a, b) ( (a) ? yytnamerr_copy(a, b) \
113 static size_t yytnamerr_copy(char *dst, const char *src)
115 return cdecl__strlcpy(dst, src, strlen(src)+1);
120 #include <inttypes.h>
126 void cdecl__free(struct cdecl *);
127 int cdecl__yyparse(void *scanner, struct cdecl **out);
128 const char *cdecl__token_name(unsigned token);
132 cdecl_uintmax uintval;
135 struct cdecl_declspec *declspec;
136 struct cdecl_declarator *declarator;
138 struct parse_item *item;
142 static void yyerror(YYLTYPE *, yyscan_t, struct cdecl **, const char *);
143 static void free_decl(struct cdecl *);
145 static void free_declspec(struct cdecl_declspec *x)
147 struct cdecl_declspec *p;
155 static void free_declarator(struct cdecl_declarator *x)
157 struct cdecl_declarator *p;
163 case CDECL_DECL_NULL:
165 case CDECL_DECL_IDENT:
166 case CDECL_DECL_ARRAY:
168 case CDECL_DECL_POINTER:
169 free_declspec(x->u.pointer.qualifiers);
171 case CDECL_DECL_FUNCTION:
172 free_decl(x->u.function.parameters);
183 static void free_decl(struct cdecl *x)
190 /* The specifiers may be shared by an entire chain. */
191 if (!p || p->specifiers != x->specifiers)
192 free_declspec(x->specifiers);
194 free_declarator(x->declarators);
200 void cdecl__free(struct cdecl *decl)
206 * Join two declaration specifier lists into a single list, with "a" being the
207 * head of the new list.
209 * The list "a" is assumed to be nonempty.
211 static void join_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
219 * Join three specifier lists into a single list, and returns the head of
222 * The list "b" is assumed to be a singleton list.
224 static struct cdecl_declspec *join_specs3(struct cdecl_declspec *a,
225 struct cdecl_declspec *b,
226 struct cdecl_declspec *c)
234 * Reverse the order of a "struct cdecl" list, and return the new first
235 * element of the list (i.e., the last element of the original list).
237 static struct cdecl *reverse_decls(struct cdecl *decl)
239 struct cdecl *prev, *next;
241 for (prev = NULL; decl; decl = next) {
251 * Alter an abstract declarator (type name) to declare an identifier instead,
252 * used by the English parser rules to reduce "identifier as type" sequences.
254 static struct cdecl *
255 insert_identifier(struct cdecl *decl, struct parse_item *ident)
257 struct cdecl_declarator *d, **p = &decl->declarators;
259 while ((d = *p)->child)
262 *p = &ident->u.declarator;
266 static struct cdecl_declarator *nulldecl(void)
268 static const struct cdecl_declarator nulldecl = {0};
269 return (void *)&nulldecl;
271 #define NULLDECL (nulldecl())
275 %destructor { free($$); } <item>
276 %destructor { free_declspec($$); } <declspec>
277 %destructor { free_declarator($$); } <declarator>
278 %destructor { free_decl($$); } <decl>
283 %token <item> T_IDENT "identifier"
284 %token <uintval> T_UINT "integer constant"
286 %token T_SEMICOLON ";"
287 %token T_ASTERISK "*"
290 %token T_LBRACKET "["
291 %token T_RBRACKET "]"
293 %token T_ELLIPSIS "..."
295 %token <spectype> T_TYPEDEF "typedef"
296 %token <spectype> T_EXTERN "extern"
297 %token <spectype> T_STATIC "static"
298 %token <spectype> T_AUTO "auto"
299 %token <spectype> T_REGISTER "register"
301 %token <spectype> T_INLINE "inline"
303 %token <spectype> T_RESTRICT "restrict"
304 %token <spectype> T_VOLATILE "volatile"
305 %token <spectype> T_CONST "const"
307 %token <spectype> T_VOID "void"
308 %token <spectype> T_CHAR "char"
309 %token <spectype> T_SHORT "short"
310 %token <spectype> T_INT "int"
311 %token <spectype> T_LONG "long"
312 %token <spectype> T_FLOAT "float"
313 %token <spectype> T_DOUBLE "double"
314 %token <spectype> T_SIGNED "signed"
315 %token <spectype> T_UNSIGNED "unsigned"
316 %token <spectype> T_BOOL "_Bool"
317 %token <spectype> T_COMPLEX "_Complex"
318 %token <spectype> T_IMAGINARY "_Imaginary"
320 %token <spectype> T_STRUCT "struct"
321 %token <spectype> T_UNION "union"
322 %token <spectype> T_ENUM "enum"
328 %token T_DECLARE "declare"
329 %token T_POINTER "pointer"
330 %token T_FUNCTION "function"
331 %token T_RETURNING "returning"
332 %token T_ARRAY "array"
336 %token T_VLA "variable-length"
338 %type <item> vla_ident
339 %type <uintval> array_length
340 %type <boolval> varargs
341 %type <spectype> declspec_simple qualifier_simple
342 %type <spectype> typespec_simple typespec_tagged
343 %type <declspec> declspec_notype declspec_noid typespec_noid typespec
344 %type <declspec> qualifier qualifiers
345 %type <declspec> declspecs declspecs_notype declspecs_noid
346 %type <declarator> direct_declarator declarator pointer array parens postfix
347 %type <declarator> direct_declarator_ish declarator_ish parameter_type_list
348 %type <decl> cdecl declaration declarators declarator_wrap parameter
350 %type <item> english_vla
351 %type <declspec> storage_func_specs post_specs
352 %type <declspec> type_qual_spec type_qual_specs typedef_name_qual
353 %type <declarator> english_declarator english_array english_function
354 %type <declarator> english_parameter_list null_decl
355 %type <decl> english english_declaration english_parameter
357 /* Precedence declaration to avoid conflict in english_parameter; see below. */
363 input: cdecl { *out = $1; }
364 cdecl: english | declaration
367 declaration: declspecs declarators semi {
368 $$ = reverse_decls($2);
373 * We support parsing declarations using arbitrary identifiers as type
374 * specifiers (a la C typedef). To avoid confusion with identifiers that
375 * may also be used as declarators, note the following:
377 * (a) Every valid C declaration must have at least one type specifier, and
378 * (b) Valid declarations with typedef names have exactly one type specifier.
380 * So the rule applied when parsing specifiers is: an identifier is a type
381 * specifier only if we have not yet seen any type specifiers whatsoever
382 * (within one declaration specifier list).
384 * Treating identifiers as type specifiers by default can lead to strange and
385 * unexpected parses; libcdecl applies a simplification step to the resulting
386 * parse tree afterwards.
388 declspecs: declspecs_notype typespec declspecs_noid {
389 $$ = join_specs3($1, $2, $3);
392 declspecs_notype: { $$ = NULL; } | declspecs_notype declspec_notype {
397 declspecs_noid: { $$ = NULL; } | declspecs_noid declspec_noid {
402 qualifiers: { $$ = NULL; } | qualifiers qualifier {
407 declarators: declarator_wrap | declarators T_COMMA declarator_wrap {
412 declarator_wrap: declarator {
413 ALLOC_DECL($$, NULL, $1);
416 declspec_simple: T_AUTO
423 typespec_simple: T_VOID
436 typespec_tagged: T_STRUCT | T_UNION | T_ENUM | { $$ = CDECL_TYPE_IDENT; }
438 qualifier_simple: T_CONST
442 declspec_notype: qualifier | declspec_simple { ALLOC_DECLSPEC($$, $1); }
443 typespec_noid: typespec_simple { ALLOC_DECLSPEC($$, $1); }
444 qualifier: qualifier_simple { ALLOC_DECLSPEC($$, $1); }
446 typespec: typespec_noid | typespec_tagged T_IDENT {
447 /* Compiler should be able to elide this assignment. */
448 $2->u.declspec.ident = $2->u.declarator.u.ident;
450 $$ = &$2->u.declspec;
454 declspec_noid: declspec_notype | typespec_noid
456 vla_ident: T_IDENT | T_ASTERISK {
457 if (!($$ = cdecl__alloc_item(1)))
462 array: T_LBRACKET array_length T_RBRACKET {
464 } | T_LBRACKET vla_ident T_RBRACKET {
465 $$ = &$2->u.declarator;
466 $$->type = CDECL_DECL_ARRAY;
467 $$->u.array.vla = $$->u.ident;
468 $$->u.array.length = 0;
471 parameter: declspecs declarator {
472 ALLOC_DECL($$, $1, $2);
475 varargs: { $$ = false; } | T_COMMA T_ELLIPSIS { $$ = true; }
477 parameter_type_list: parameter {
478 ALLOC_FUNCTION_($$, $1);
479 } | parameter_type_list T_COMMA parameter {
481 $3->next = $$->u.function.parameters;
482 $$->u.function.parameters = $3;
485 parens: T_LPAREN parameter_type_list varargs T_RPAREN {
486 $2->u.function.parameters = reverse_decls($2->u.function.parameters);
487 $2->u.function.variadic = $3;
489 } | T_LPAREN declarator_ish T_RPAREN {
490 struct cdecl *fake_params;
492 ALLOC_DECL(fake_params, NULL, $2);
493 ALLOC_FUNCTION_($$, fake_params);
496 pointer: T_ASTERISK qualifiers direct_declarator {
497 ALLOC_POINTER($$, $2, $3);
498 } | T_ASTERISK qualifiers pointer {
499 ALLOC_POINTER($$, $2, $3);
502 declarator: direct_declarator | pointer
503 declarator_ish: direct_declarator_ish | pointer
504 postfix: array | parens
506 direct_declarator_ish: {
508 } | direct_declarator_ish postfix {
516 $$ = &$1->u.declarator;
517 } | direct_declarator postfix {
522 english: T_DECLARE T_IDENT T_AS english_declaration {
523 $$ = insert_identifier($4, $2);
524 } | T_TYPE english_declaration {
529 * We use a precedence declaration to prefer shifting an identifier
530 * over reducing this empty rule; see below.
532 storage_func_specs: %prec T_TYPE { $$ = NULL; }
533 storage_func_specs: storage_func_specs declspec_simple {
534 ALLOC_DECLSPEC($$, $2);
538 type_qual_spec: typespec_noid | qualifier
540 type_qual_specs: { $$ = NULL; } | type_qual_specs type_qual_spec {
546 * The "qualifiers" nonterminal needs to be used here to avoid shift/reduce
547 * conflicts with pointer declarators. So we end up needing to stitch
548 * together three different specifiers lists.
550 post_specs: qualifiers typespec type_qual_specs {
551 $$ = join_specs3($1, $2, $3);
554 english_declaration: storage_func_specs english_declarator post_specs {
556 ALLOC_DECL($$, $3, $2);
559 english_declarator: {
561 } | english_declarator qualifiers T_POINTER T_TO {
562 ALLOC_POINTER($$, $2, $1);
563 } | english_declarator english_array {
566 } | english_declarator english_function {
571 english_function: T_FUNCTION T_RETURNING {
572 ALLOC_FUNCTION($$, NULL, false);
573 } | T_FUNCTION T_LPAREN english_parameter_list varargs T_RPAREN T_RETURNING {
574 $3->u.function.parameters = reverse_decls($3->u.function.parameters);
575 $3->u.function.variadic = $4;
579 english_parameter_list: english_parameter {
580 ALLOC_FUNCTION_($$, $1);
581 } | english_parameter_list T_COMMA english_parameter {
583 $3->next = $$->u.function.parameters;
584 $$->u.function.parameters = $3;
587 typedef_name_qual: T_IDENT qualifiers {
588 /* Compiler should be able to elide this assignment. */
589 $1->u.declspec.ident = $1->u.declarator.u.ident;
591 $$ = &$1->u.declspec;
592 $$->type = CDECL_TYPE_IDENT;
601 * There is a shift/reduce conflict here when an identifier appears as the
602 * first token. The conflict is between shifting T_IDENT, or reducing the
603 * empty production for storage_func_specs (cf. english_declaration).
605 * - In either case, if we reduce, we won't match T_IDENT T_AS since the
606 * stack now has the extra storage_func_specs nonterminal symbol.
607 * - And if we shift, we won't match english_declaration since it is
608 * too late to add storage_func_specs to the stack.
610 * The only valid input affected by the conflict is a simple type names,
611 * possibly followed by qualifiers. So the conflict is adequately resolved
612 * by shifting, so long as we have a special-case reduction to handle this.
614 english_parameter: english_declaration | typedef_name_qual null_decl {
615 ALLOC_DECL($$, $1, $2);
616 } | T_IDENT T_AS english_declaration {
617 $$ = insert_identifier($3, $1);
620 english_array: T_VLA T_ARRAY english_vla T_OF {
621 $$ = &$3->u.declarator;
622 $$->type = CDECL_DECL_ARRAY;
623 $$->u.array.vla = $$->u.ident;
624 $$->u.array.length = 0;
625 } | T_ARRAY array_length T_OF {
629 array_length: { $$ = 0; }
630 array_length: T_UINT {
632 cdecl__errmsg(CDECL__EZEROARRAY);
637 english_vla: T_IDENT | {
638 if (!($$ = cdecl__alloc_item(1)))
646 * Expose the token string table to the rest of the library, in order to
647 * produce strings that match parser keywords.
649 * In order for this to work properly, the Bison output must be postprocessed
650 * by fix-yytname.awk to remove pointless quotation marks from the keyword
653 const char *cdecl__token_name(unsigned token)
655 return yytname[YYTRANSLATE(token)];
659 * Current versions of GCC (up to 13) want to inline this function into the
660 * parser even when optimizing for size and the results are not great, so
661 * try to prevent such inlining.
663 CDECL__NOINLINE static void
664 yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err)
666 if (strstr(err, yytname[YYTRANSLATE(T_LEX_ERROR)]))
669 cdecl__err("%s", err);