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