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