src/parse.y

   1 %code top {
   2 /*
   3  *  Parser for C declarations.
   4  *  Copyright © 2011-2012, 2021, 2023-2024 Nick Bowler
   5  *
   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.
  10  *
  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.
  15  *
  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/>.
  18  */
  19 }
  20
  21 %name-prefix "cdecl__yy"
  22 %parse-param {void *scanner}
  23 %parse-param {struct cdecl **out}
  24 %lex-param {yyscan_t scanner}
  25 %define api.pure
  26 %error-verbose
  27 %locations
  28
  29 %{
  30 #include <config.h>
  31 #include <assert.h>
  32 #include <stdbool.h>
  33
  34 #include "scan.h"
  35 #include "cdecl-internal.h"
  36 #include "errmsg.h"
  37
  38 /*
  39  * Allocate a parse tree node via cdecl__alloc_item.
  40  *
  41  * - m1 specifies the item's union member to assign to ptr, which selects the
  42  *   type of node to allocate.
  43  *
  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.
  49  *
  50  * The resulting pointer can be passed directly to free, as the union is the
  51  * first member of the parse_item structure.
  52  *
  53  * Use the wrapper macros below instead of this one.
  54  */
  55 #define ALLOC_ITEM(ptr, m1, m2) do { \
  56         struct parse_item *item; \
  57         if (!(item = cdecl__alloc_item(0))) \
  58                 YYERROR; \
  59         item->u.m1.m2 = (void *)item->u.declarator.child; \
  60         (ptr) = &item->u.m1; \
  61 } while (0)
  62
  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)
  67
  68 #define ALLOC_FUNCTION_(ptr, parameters_) do { \
  69         ALLOC_ITEM_DECLARATOR(ptr); \
  70         (ptr)->type = CDECL_DECL_FUNCTION; \
  71         (ptr)->u.function.parameters = parameters_; \
  72 } while (0)
  73
  74 #define ALLOC_FUNCTION(ptr, parameters_, variadic_) do { \
  75         ALLOC_FUNCTION_(ptr, parameters_); \
  76         (ptr)->u.function.variadic = variadic_; \
  77 } while (0)
  78
  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_; \
  84 } while (0)
  85
  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_; \
  91 } while (0)
  92
  93 #define ALLOC_DECLSPEC(ptr, type_) do { \
  94         ALLOC_ITEM_DECLSPEC(ptr); \
  95         (ptr)->type = type_; \
  96         (ptr)->ident = NULL; \
  97 } while (0)
  98
  99 #define ALLOC_DECL(ptr, specifiers_, declarators_) do { \
 100         ALLOC_ITEM_DECL(ptr); \
 101         (ptr)->specifiers = specifiers_; \
 102         (ptr)->declarators = declarators_; \
 103 } while (0)
 104
 105 /*
 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.
 109  */
 110 #define yytnamerr(a, b) ( (a) ? cdecl__strlcpy(a, b, -1) : strlen(b) )
 111 %}
 112
 113 %code requires {
 114 #include <inttypes.h>
 115 #include <stdbool.h>
 116 #include "cdecl.h"
 117 }
 118
 119 %code provides {
 120 void cdecl__free(struct cdecl *);
 121 int cdecl__yyparse(void *scanner, struct cdecl **out);
 122 const char *cdecl__token_name(unsigned token);
 123 }
 124
 125 %union {
 126         cdecl_uintmax uintval;
 127         unsigned spectype;
 128         bool boolval;
 129         struct cdecl_declspec *declspec;
 130         struct cdecl_declarator *declarator;
 131         struct cdecl *decl;
 132         struct parse_item *item;
 133 }
 134
 135 %{
 136 static void yyerror(YYLTYPE *, yyscan_t, struct cdecl **, const char *);
 137 static void free_decl(struct cdecl *);
 138
 139 static void free_declspec(struct cdecl_declspec *x)
 140 {
 141         struct cdecl_declspec *p;
 142         while (x) {
 143                 p = x->next;
 144                 free(x);
 145                 x = p;
 146         }
 147 }
 148
 149 static void free_declarator(struct cdecl_declarator *x)
 150 {
 151         struct cdecl_declarator *p;
 152
 153         while (x) {
 154                 p = x->child;
 155
 156                 switch (x->type) {
 157                 case CDECL_DECL_NULL:
 158                         x = NULL;
 159                 case CDECL_DECL_IDENT:
 160                 case CDECL_DECL_ARRAY:
 161                         break;
 162                 case CDECL_DECL_POINTER:
 163                         free_declspec(x->u.pointer.qualifiers);
 164                         break;
 165                 case CDECL_DECL_FUNCTION:
 166                         free_decl(x->u.function.parameters);
 167                         break;
 168                 default:
 169                         assert(0);
 170                 }
 171
 172                 free(x);
 173                 x = p;
 174         }
 175 }
 176
 177 static void free_decl(struct cdecl *x)
 178 {
 179         struct cdecl *p;
 180
 181         while (x) {
 182                 p = x->next;
 183
 184                 /* The specifiers may be shared by an entire chain. */
 185                 if (!p || p->specifiers != x->specifiers)
 186                         free_declspec(x->specifiers);
 187
 188                 free_declarator(x->declarators);
 189                 free(x);
 190                 x = p;
 191         }
 192 }
 193
 194 void cdecl__free(struct cdecl *decl)
 195 {
 196         free_decl(decl);
 197 }
 198
 199 /*
 200  * Join two declaration specifier lists into a single list, with "a" being the
 201  * head of the new list.
 202  *
 203  * The list "a" is assumed to be nonempty.
 204  */
 205 static void join_specs(struct cdecl_declspec *a, struct cdecl_declspec *b)
 206 {
 207         while (a->next)
 208                 a = a->next;
 209         a->next = b;
 210 }
 211
 212 /*
 213  * Join three specifier lists into a single list, and returns the head of
 214  * the new list.
 215  *
 216  * The list "b" is assumed to be a singleton list.
 217  */
 218 static struct cdecl_declspec *join_specs3(struct cdecl_declspec *a,
 219                                           struct cdecl_declspec *b,
 220                                           struct cdecl_declspec *c)
 221 {
 222         b->next = c;
 223         join_specs(b, a);
 224         return b;
 225 }
 226
 227 /*
 228  * Reverse the order of a "struct cdecl" list, and return the new first
 229  * element of the list (i.e., the last element of the original list).
 230  */
 231 static struct cdecl *reverse_decls(struct cdecl *decl)
 232 {
 233         struct cdecl *prev, *next;
 234
 235         for (prev = NULL; decl; decl = next) {
 236                 next = decl->next;
 237                 decl->next = prev;
 238                 prev = decl;
 239         }
 240
 241         return prev;
 242 }
 243
 244 /*
 245  * Alter an abstract declarator (type name) to declare an identifier instead,
 246  * used by the English parser rules to reduce "identifier as type" sequences.
 247  */
 248 static struct cdecl *
 249 insert_identifier(struct cdecl *decl, struct parse_item *ident)
 250 {
 251         struct cdecl_declarator *d, **p = &decl->declarators;
 252
 253         while ((d = *p)->child)
 254                 p = &d->child;
 255
 256         *p = &ident->u.declarator;
 257         return decl;
 258 }
 259
 260 static struct cdecl_declarator *nulldecl(void)
 261 {
 262         static const struct cdecl_declarator nulldecl = {0};
 263         return (void *)&nulldecl;
 264 }
 265 #define NULLDECL (nulldecl())
 266
 267 %}
 268
 269 %destructor { free($$); }            <item>
 270 %destructor { free_declspec($$); }   <declspec>
 271 %destructor { free_declarator($$); } <declarator>
 272 %destructor { free_decl($$); }       <decl>
 273
 274 /* Magic tokens */
 275 %token T_LEX_ERROR "@@@"
 276
 277 %token <item>    T_IDENT "identifier"
 278 %token <uintval> T_UINT  "integer constant"
 279
 280 %token T_SEMICOLON ";"
 281 %token T_ASTERISK  "*"
 282 %token T_LPAREN    "("
 283 %token T_RPAREN    ")"
 284 %token T_LBRACKET  "["
 285 %token T_RBRACKET  "]"
 286 %token T_COMMA     ","
 287 %token T_ELLIPSIS  "..."
 288
 289 %token <spectype> T_TYPEDEF   "typedef"
 290 %token <spectype> T_EXTERN    "extern"
 291 %token <spectype> T_STATIC    "static"
 292 %token <spectype> T_AUTO      "auto"
 293 %token <spectype> T_REGISTER  "register"
 294
 295 %token <spectype> T_INLINE    "inline"
 296
 297 %token <spectype> T_RESTRICT  "restrict"
 298 %token <spectype> T_VOLATILE  "volatile"
 299 %token <spectype> T_CONST     "const"
 300
 301 %token <spectype> T_VOID      "void"
 302 %token <spectype> T_CHAR      "char"
 303 %token <spectype> T_SHORT     "short"
 304 %token <spectype> T_INT       "int"
 305 %token <spectype> T_LONG      "long"
 306 %token <spectype> T_FLOAT     "float"
 307 %token <spectype> T_DOUBLE    "double"
 308 %token <spectype> T_SIGNED    "signed"
 309 %token <spectype> T_UNSIGNED  "unsigned"
 310 %token <spectype> T_BOOL      "_Bool"
 311 %token <spectype> T_COMPLEX   "_Complex"
 312 %token <spectype> T_IMAGINARY "_Imaginary"
 313
 314 %token <spectype> T_STRUCT    "struct"
 315 %token <spectype> T_UNION     "union"
 316 %token <spectype> T_ENUM      "enum"
 317
 318 /*
 319  * English keywords.
 320  */
 321 %token T_TYPE      "type"
 322 %token T_DECLARE   "declare"
 323 %token T_POINTER   "pointer"
 324 %token T_FUNCTION  "function"
 325 %token T_RETURNING "returning"
 326 %token T_ARRAY     "array"
 327 %token T_TO        "to"
 328 %token T_OF        "of"
 329 %token T_AS        "as"
 330 %token T_VLA       "variable-length"
 331
 332 %type <item>       vla_ident
 333 %type <uintval>    array_length
 334 %type <boolval>    varargs
 335 %type <spectype>   declspec_simple qualifier_simple
 336 %type <spectype>   typespec_simple typespec_tagged
 337 %type <declspec>   declspec_notype declspec_noid typespec_noid typespec
 338 %type <declspec>   qualifier qualifiers
 339 %type <declspec>   declspecs declspecs_notype declspecs_noid
 340 %type <declarator> direct_declarator declarator pointer array parens postfix
 341 %type <declarator> direct_declarator_ish declarator_ish parameter_type_list
 342 %type <decl>       cdecl declaration declarators declarator_wrap parameter
 343
 344 %type <item>       english_vla
 345 %type <declspec>   storage_func_specs post_specs
 346 %type <declspec>   type_qual_spec type_qual_specs typedef_name_qual
 347 %type <declarator> english_declarator english_array english_function
 348 %type <declarator> english_parameter_list null_decl
 349 %type <decl>       english english_declaration english_parameter
 350
 351 /* Precedence declaration to avoid conflict in english_parameter; see below. */
 352 %right T_TYPE
 353 %right T_IDENT
 354
 355 %%
 356
 357 input: cdecl { *out = $1; }
 358 cdecl: english | declaration
 359
 360 semi: | T_SEMICOLON
 361 declaration: declspecs declarators semi {
 362         $$ = reverse_decls($2);
 363         $$->specifiers = $1;
 364 };
 365
 366 /*
 367  * We support parsing declarations using arbitrary identifiers as type
 368  * specifiers (a la C typedef).  To avoid confusion with identifiers that
 369  * may also be used as declarators, note the following:
 370  *
 371  *  (a) Every valid C declaration must have at least one type specifier, and
 372  *  (b) Valid declarations with typedef names have exactly one type specifier.
 373  *
 374  * So the rule applied when parsing specifiers is: an identifier is a type
 375  * specifier only if we have not yet seen any type specifiers whatsoever
 376  * (within one declaration specifier list).
 377  *
 378  * Treating identifiers as type specifiers by default can lead to strange and
 379  * unexpected parses; libcdecl applies a simplification step to the resulting
 380  * parse tree afterwards.
 381  */
 382 declspecs: declspecs_notype typespec declspecs_noid {
 383         $$ = join_specs3($1, $2, $3);
 384 }
 385
 386 declspecs_notype: { $$ = NULL; } | declspecs_notype declspec_notype {
 387         $$ = $2;
 388         $$->next = $1;
 389 }
 390
 391 declspecs_noid: { $$ = NULL; } | declspecs_noid declspec_noid {
 392         $$ = $2;
 393         $$->next = $1;
 394 }
 395
 396 qualifiers: { $$ = NULL; } | qualifiers qualifier {
 397         $$ = $2;
 398         $$->next = $1;
 399 }
 400
 401 declarators: declarator_wrap | declarators T_COMMA declarator_wrap {
 402         $$ = $3;
 403         $$->next = $1;
 404 }
 405
 406 declarator_wrap: declarator {
 407         ALLOC_DECL($$, NULL, $1);
 408 }
 409
 410 declspec_simple: T_AUTO
 411         | T_TYPEDEF
 412         | T_EXTERN
 413         | T_STATIC
 414         | T_REGISTER
 415         | T_INLINE
 416
 417 typespec_simple: T_VOID
 418         | T_CHAR
 419         | T_SHORT
 420         | T_INT
 421         | T_LONG
 422         | T_FLOAT
 423         | T_DOUBLE
 424         | T_SIGNED
 425         | T_UNSIGNED
 426         | T_BOOL
 427         | T_COMPLEX
 428         | T_IMAGINARY
 429
 430 typespec_tagged: T_STRUCT | T_UNION | T_ENUM | { $$ = CDECL_TYPE_IDENT; }
 431
 432 qualifier_simple: T_CONST
 433         | T_RESTRICT
 434         | T_VOLATILE
 435
 436 declspec_notype: qualifier | declspec_simple { ALLOC_DECLSPEC($$, $1); }
 437 typespec_noid: typespec_simple { ALLOC_DECLSPEC($$, $1); }
 438 qualifier: qualifier_simple { ALLOC_DECLSPEC($$, $1); }
 439
 440 typespec: typespec_noid | typespec_tagged T_IDENT {
 441         /* Compiler should be able to elide this assignment. */
 442         $2->u.declspec.ident = $2->u.declarator.u.ident;
 443
 444         $$ = &$2->u.declspec;
 445         $$->type = $1;
 446 }
 447
 448 declspec_noid: declspec_notype | typespec_noid
 449
 450 vla_ident: T_IDENT | T_ASTERISK {
 451         if (!($$ = cdecl__alloc_item(1)))
 452                 YYERROR;
 453         *$$->s = 0;
 454 }
 455
 456 array: T_LBRACKET array_length T_RBRACKET {
 457         ALLOC_ARRAY($$, $2);
 458 } | T_LBRACKET vla_ident T_RBRACKET {
 459         $$ = &$2->u.declarator;
 460         $$->type = CDECL_DECL_ARRAY;
 461         $$->u.array.vla = $$->u.ident;
 462         $$->u.array.length = 0;
 463 }
 464
 465 parameter: declspecs declarator {
 466         ALLOC_DECL($$, $1, $2);
 467 }
 468
 469 varargs: { $$ = false; } | T_COMMA T_ELLIPSIS { $$ = true; }
 470
 471 parameter_type_list: parameter {
 472         ALLOC_FUNCTION_($$, $1);
 473 } | parameter_type_list T_COMMA parameter {
 474         $$ = $1;
 475         $3->next = $$->u.function.parameters;
 476         $$->u.function.parameters = $3;
 477 }
 478
 479 parens: T_LPAREN parameter_type_list varargs T_RPAREN {
 480         $2->u.function.parameters = reverse_decls($2->u.function.parameters);
 481         $2->u.function.variadic = $3;
 482         $$ = $2;
 483 } | T_LPAREN declarator_ish T_RPAREN {
 484         struct cdecl *fake_params;
 485
 486         ALLOC_DECL(fake_params, NULL, $2);
 487         ALLOC_FUNCTION_($$, fake_params);
 488 }
 489
 490 pointer: T_ASTERISK qualifiers direct_declarator {
 491         ALLOC_POINTER($$, $2, $3);
 492 } | T_ASTERISK qualifiers pointer {
 493         ALLOC_POINTER($$, $2, $3);
 494 }
 495
 496 declarator: direct_declarator | pointer
 497 declarator_ish: direct_declarator_ish | pointer
 498 postfix: array | parens
 499
 500 direct_declarator_ish: {
 501         $$ = NULLDECL;
 502 } | direct_declarator_ish postfix {
 503         $$ = $2;
 504         $$->child = $1;
 505 }
 506
 507 direct_declarator: {
 508         $$ = NULLDECL;
 509 } | T_IDENT {
 510         $$ = &$1->u.declarator;
 511 } | direct_declarator postfix {
 512         $$ = $2;
 513         $$->child = $1;
 514 }
 515
 516 english: T_DECLARE T_IDENT T_AS english_declaration {
 517         $$ = insert_identifier($4, $2);
 518 } | T_TYPE english_declaration {
 519         $$ = $2;
 520 }
 521
 522 /*
 523  * We use a precedence declaration to prefer shifting an identifier
 524  * over reducing this empty rule; see below.
 525  */
 526 storage_func_specs: %prec T_TYPE { $$ = NULL; }
 527 storage_func_specs: storage_func_specs declspec_simple {
 528         ALLOC_DECLSPEC($$, $2);
 529         $$->next = $1;
 530 }
 531
 532 type_qual_spec: typespec_noid | qualifier
 533
 534 type_qual_specs: { $$ = NULL; } | type_qual_specs type_qual_spec {
 535         $$ = $2;
 536         $$->next = $1;
 537 }
 538
 539 /*
 540  * The "qualifiers" nonterminal needs to be used here to avoid shift/reduce
 541  * conflicts with pointer declarators.  So we end up needing to stitch
 542  * together three different specifiers lists.
 543  */
 544 post_specs: qualifiers typespec type_qual_specs {
 545         $$ = join_specs3($1, $2, $3);
 546 }
 547
 548 english_declaration: storage_func_specs english_declarator post_specs {
 549         join_specs($3, $1);
 550         ALLOC_DECL($$, $3, $2);
 551 }
 552
 553 english_declarator: {
 554         $$ = NULLDECL;
 555 } | english_declarator qualifiers T_POINTER T_TO {
 556         ALLOC_POINTER($$, $2, $1);
 557 } | english_declarator english_array {
 558         $$ = $2;
 559         $$->child = $1;
 560 } | english_declarator english_function {
 561         $$ = $2;
 562         $$->child = $1;
 563 }
 564
 565 english_function: T_FUNCTION T_RETURNING {
 566         ALLOC_FUNCTION($$, NULL, false);
 567 } | T_FUNCTION T_LPAREN english_parameter_list varargs T_RPAREN T_RETURNING {
 568         $3->u.function.parameters = reverse_decls($3->u.function.parameters);
 569         $3->u.function.variadic = $4;
 570         $$ = $3;
 571 }
 572
 573 english_parameter_list: english_parameter {
 574         ALLOC_FUNCTION_($$, $1);
 575 } | english_parameter_list T_COMMA english_parameter {
 576         $$ = $1;
 577         $3->next = $$->u.function.parameters;
 578         $$->u.function.parameters = $3;
 579 }
 580
 581 typedef_name_qual: T_IDENT qualifiers {
 582         /* Compiler should be able to elide this assignment. */
 583         $1->u.declspec.ident = $1->u.declarator.u.ident;
 584
 585         $$ = &$1->u.declspec;
 586         $$->type = CDECL_TYPE_IDENT;
 587         $$->next = $2;
 588 }
 589
 590 null_decl: {
 591         $$ = NULLDECL;
 592 }
 593
 594 /*
 595  * There is a shift/reduce conflict here when an identifier appears as the
 596  * first token.  The conflict is between shifting T_IDENT, or reducing the
 597  * empty production for storage_func_specs (cf. english_declaration).
 598  *
 599  *   - In either case, if we reduce, we won't match T_IDENT T_AS since the
 600  *     stack now has the extra storage_func_specs nonterminal symbol.
 601  *   - And if we shift, we won't match english_declaration since it is
 602  *     too late to add storage_func_specs to the stack.
 603  *
 604  * The only valid input affected by the conflict is a simple type names,
 605  * possibly followed by qualifiers.  So the conflict is adequately resolved
 606  * by shifting, so long as we have a special-case reduction to handle this.
 607  */
 608 english_parameter: english_declaration | typedef_name_qual null_decl {
 609         ALLOC_DECL($$, $1, $2);
 610 } | T_IDENT T_AS english_declaration {
 611         $$ = insert_identifier($3, $1);
 612 }
 613
 614 english_array: T_VLA T_ARRAY english_vla T_OF {
 615         $$ = &$3->u.declarator;
 616         $$->type = CDECL_DECL_ARRAY;
 617         $$->u.array.vla = $$->u.ident;
 618         $$->u.array.length = 0;
 619 } | T_ARRAY array_length T_OF {
 620         ALLOC_ARRAY($$, $2);
 621 }
 622
 623 array_length: { $$ = 0; }
 624 array_length: T_UINT {
 625         if (!($$ = $1)) {
 626                 cdecl__errmsg(CDECL__EZEROARRAY);
 627                 YYERROR;
 628         }
 629 }
 630
 631 english_vla: T_IDENT | {
 632         if (!($$ = cdecl__alloc_item(1)))
 633                 YYERROR;
 634         *$$->s = 0;
 635 }
 636
 637 %%
 638
 639 /*
 640  * Expose the token string table to the rest of the library, in order to
 641  * produce strings that match parser keywords.
 642  *
 643  * In order for this to work properly, the Bison output must be postprocessed
 644  * by fix-yytname.awk to remove pointless quotation marks from the keyword
 645  * strings.
 646  */
 647 const char *cdecl__token_name(unsigned token)
 648 {
 649         return yytname[YYTRANSLATE(token)];
 650 }
 651
 652 /*
 653  * Current versions of GCC (up to 13) want to inline this function into the
 654  * parser even when optimizing for size and the results are not great, so
 655  * try to prevent such inlining.
 656  */
 657 CDECL__NOINLINE static void
 658 yyerror(YYLTYPE *loc, yyscan_t scanner, struct cdecl **out, const char *err)
 659 {
 660         if (strstr(err, yytname[YYTRANSLATE(T_LEX_ERROR)]))
 661                 return;
 662
 663         cdecl__err("%s", err);
 664 }