src/parse.y

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