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