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