1 %{/* Bison Grammar Parser -*- C -*- 2 3 Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 4 5 This file is part of Bison, the GNU Compiler Compiler. 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301 USA 21 */ 22 23 #include <config.h> 24 #include "system.h" 25 26 #include "complain.h" 27 #include "conflicts.h" 28 #include "files.h" 29 #include "getargs.h" 30 #include "gram.h" 31 #include "muscle_tab.h" 32 #include "quotearg.h" 33 #include "reader.h" 34 #include "symlist.h" 35 #include "strverscmp.h" 36 37 #define YYLLOC_DEFAULT(Current, Rhs, N) (Current) = lloc_default (Rhs, N) 38 static YYLTYPE lloc_default (YYLTYPE const *, int); 39 40 #define YY_LOCATION_PRINT(File, Loc) \ 41 location_print (File, Loc) 42 43 static void version_check (location const *loc, char const *version); 44 45 /* Request detailed syntax error messages, and pass them to GRAM_ERROR. 46 FIXME: depends on the undocumented availability of YYLLOC. */ 47 #undef yyerror 48 #define yyerror(Msg) \ 49 gram_error (&yylloc, Msg) 50 static void gram_error (location const *, char const *); 51 52 static void add_param (char const *, char *, location); 53 54 static symbol_class current_class = unknown_sym; 55 static uniqstr current_type = 0; 56 static symbol *current_lhs; 57 static location current_lhs_location; 58 static int current_prec = 0; 59 60 #ifdef UINT_FAST8_MAX 61 # define YYTYPE_UINT8 uint_fast8_t 62 #endif 63 #ifdef INT_FAST8_MAX 64 # define YYTYPE_INT8 int_fast8_t 65 #endif 66 #ifdef UINT_FAST16_MAX 67 # define YYTYPE_UINT16 uint_fast16_t 68 #endif 69 #ifdef INT_FAST16_MAX 70 # define YYTYPE_INT16 int_fast16_t 71 #endif 72 %} 73 74 %debug 75 %verbose 76 %defines 77 %locations 78 %pure-parser 79 %error-verbose 80 %defines 81 %name-prefix="gram_" 82 83 %initial-action 84 { 85 /* Bison's grammar can initial empty locations, hence a default 86 location is needed. */ 87 @$.start.file = @$.end.file = current_file; 88 @$.start.line = @$.end.line = 1; 89 @$.start.column = @$.end.column = 0; 90 } 91 92 /* Only NUMBERS have a value. */ 93 %union 94 { 95 symbol *symbol; 96 symbol_list *list; 97 int integer; 98 char *chars; 99 assoc assoc; 100 uniqstr uniqstr; 101 }; 102 103 /* Define the tokens together with their human representation. */ 104 %token GRAM_EOF 0 "end of file" 105 %token STRING "string" 106 %token INT "integer" 107 108 %token PERCENT_TOKEN "%token" 109 %token PERCENT_NTERM "%nterm" 110 111 %token PERCENT_TYPE "%type" 112 %token PERCENT_DESTRUCTOR "%destructor {...}" 113 %token PERCENT_PRINTER "%printer {...}" 114 115 %token PERCENT_UNION "%union {...}" 116 117 %token PERCENT_LEFT "%left" 118 %token PERCENT_RIGHT "%right" 119 %token PERCENT_NONASSOC "%nonassoc" 120 121 %token PERCENT_PREC "%prec" 122 %token PERCENT_DPREC "%dprec" 123 %token PERCENT_MERGE "%merge" 124 125 126 /*----------------------. 127 | Global Declarations. | 128 `----------------------*/ 129 130 %token 131 PERCENT_DEBUG "%debug" 132 PERCENT_DEFAULT_PREC "%default-prec" 133 PERCENT_DEFINE "%define" 134 PERCENT_DEFINES "%defines" 135 PERCENT_ERROR_VERBOSE "%error-verbose" 136 PERCENT_EXPECT "%expect" 137 PERCENT_EXPECT_RR "%expect-rr" 138 PERCENT_FILE_PREFIX "%file-prefix" 139 PERCENT_GLR_PARSER "%glr-parser" 140 PERCENT_INITIAL_ACTION "%initial-action {...}" 141 PERCENT_LEX_PARAM "%lex-param {...}" 142 PERCENT_LOCATIONS "%locations" 143 PERCENT_NAME_PREFIX "%name-prefix" 144 PERCENT_NO_DEFAULT_PREC "%no-default-prec" 145 PERCENT_NO_LINES "%no-lines" 146 PERCENT_NONDETERMINISTIC_PARSER 147 "%nondeterministic-parser" 148 PERCENT_OUTPUT "%output" 149 PERCENT_PARSE_PARAM "%parse-param {...}" 150 PERCENT_PURE_PARSER "%pure-parser" 151 PERCENT_REQUIRE "%require" 152 PERCENT_SKELETON "%skeleton" 153 PERCENT_START "%start" 154 PERCENT_TOKEN_TABLE "%token-table" 155 PERCENT_VERBOSE "%verbose" 156 PERCENT_YACC "%yacc" 157 ; 158 159 %token TYPE "type" 160 %token EQUAL "=" 161 %token SEMICOLON ";" 162 %token PIPE "|" 163 %token ID "identifier" 164 %token ID_COLON "identifier:" 165 %token PERCENT_PERCENT "%%" 166 %token PROLOGUE "%{...%}" 167 %token EPILOGUE "epilogue" 168 %token BRACED_CODE "{...}" 169 170 171 %type <chars> STRING string_content 172 "%destructor {...}" 173 "%initial-action {...}" 174 "%lex-param {...}" 175 "%parse-param {...}" 176 "%printer {...}" 177 "%union {...}" 178 PROLOGUE EPILOGUE 179 %printer { fprintf (stderr, "\"%s\"", $$); } 180 STRING string_content 181 %printer { fprintf (stderr, "{\n%s\n}", $$); } 182 "%destructor {...}" 183 "%initial-action {...}" 184 "%lex-param {...}" 185 "%parse-param {...}" 186 "%printer {...}" 187 "%union {...}" 188 PROLOGUE EPILOGUE 189 %type <uniqstr> TYPE 190 %printer { fprintf (stderr, "<%s>", $$); } TYPE 191 %type <integer> INT 192 %printer { fprintf (stderr, "%d", $$); } INT 193 %type <symbol> ID symbol string_as_id 194 %printer { fprintf (stderr, "%s", $$->tag); } ID symbol string_as_id 195 %type <symbol> ID_COLON 196 %printer { fprintf (stderr, "%s:", $$->tag); } ID_COLON 197 %type <assoc> precedence_declarator 198 %type <list> symbols.1 199 %% 200 201 input: 202 declarations "%%" grammar epilogue.opt 203 ; 204 205 206 /*------------------------------------. 207 | Declarations: before the first %%. | 208 `------------------------------------*/ 209 210 declarations: 211 /* Nothing */ 212 | declarations declaration 213 ; 214 215 declaration: 216 grammar_declaration 217 | PROLOGUE { prologue_augment ($1, @1); } 218 | "%debug" { debug_flag = true; } 219 | "%define" string_content 220 { 221 static char one[] = "1"; 222 muscle_insert ($2, one); 223 } 224 | "%define" string_content string_content { muscle_insert ($2, $3); } 225 | "%defines" { defines_flag = true; } 226 | "%error-verbose" { error_verbose = true; } 227 | "%expect" INT { expected_sr_conflicts = $2; } 228 | "%expect-rr" INT { expected_rr_conflicts = $2; } 229 | "%file-prefix" "=" string_content { spec_file_prefix = $3; } 230 | "%glr-parser" 231 { 232 nondeterministic_parser = true; 233 glr_parser = true; 234 } 235 | "%initial-action {...}" 236 { 237 muscle_code_grow ("initial_action", $1, @1); 238 } 239 | "%lex-param {...}" { add_param ("lex_param", $1, @1); } 240 | "%locations" { locations_flag = true; } 241 | "%name-prefix" "=" string_content { spec_name_prefix = $3; } 242 | "%no-lines" { no_lines_flag = true; } 243 | "%nondeterministic-parser" { nondeterministic_parser = true; } 244 | "%output" "=" string_content { spec_outfile = $3; } 245 | "%parse-param {...}" { add_param ("parse_param", $1, @1); } 246 | "%pure-parser" { pure_parser = true; } 247 | "%require" string_content { version_check (&@2, $2); } 248 | "%skeleton" string_content { skeleton = $2; } 249 | "%token-table" { token_table_flag = true; } 250 | "%verbose" { report_flag = report_states; } 251 | "%yacc" { yacc_flag = true; } 252 | /*FIXME: Err? What is this horror doing here? */ ";" 253 ; 254 255 grammar_declaration: 256 precedence_declaration 257 | symbol_declaration 258 | "%start" symbol 259 { 260 grammar_start_symbol_set ($2, @2); 261 } 262 | "%union {...}" 263 { 264 char const *body = $1; 265 266 if (typed) 267 { 268 /* Concatenate the union bodies, turning the first one's 269 trailing '}' into '\n', and omitting the second one's '{'. */ 270 char *code = muscle_find ("stype"); 271 code[strlen (code) - 1] = '\n'; 272 body++; 273 } 274 275 typed = true; 276 muscle_code_grow ("stype", body, @1); 277 } 278 | "%destructor {...}" symbols.1 279 { 280 symbol_list *list; 281 for (list = $2; list; list = list->next) 282 symbol_destructor_set (list->sym, $1, @1); 283 symbol_list_free ($2); 284 } 285 | "%printer {...}" symbols.1 286 { 287 symbol_list *list; 288 for (list = $2; list; list = list->next) 289 symbol_printer_set (list->sym, $1, @1); 290 symbol_list_free ($2); 291 } 292 | "%default-prec" 293 { 294 default_prec = true; 295 } 296 | "%no-default-prec" 297 { 298 default_prec = false; 299 } 300 ; 301 302 symbol_declaration: 303 "%nterm" { current_class = nterm_sym; } symbol_defs.1 304 { 305 current_class = unknown_sym; 306 current_type = NULL; 307 } 308 | "%token" { current_class = token_sym; } symbol_defs.1 309 { 310 current_class = unknown_sym; 311 current_type = NULL; 312 } 313 | "%type" TYPE symbols.1 314 { 315 symbol_list *list; 316 for (list = $3; list; list = list->next) 317 symbol_type_set (list->sym, $2, @2); 318 symbol_list_free ($3); 319 } 320 ; 321 322 precedence_declaration: 323 precedence_declarator type.opt symbols.1 324 { 325 symbol_list *list; 326 ++current_prec; 327 for (list = $3; list; list = list->next) 328 { 329 symbol_type_set (list->sym, current_type, @2); 330 symbol_precedence_set (list->sym, current_prec, $1, @1); 331 } 332 symbol_list_free ($3); 333 current_type = NULL; 334 } 335 ; 336 337 precedence_declarator: 338 "%left" { $$ = left_assoc; } 339 | "%right" { $$ = right_assoc; } 340 | "%nonassoc" { $$ = non_assoc; } 341 ; 342 343 type.opt: 344 /* Nothing. */ { current_type = NULL; } 345 | TYPE { current_type = $1; } 346 ; 347 348 /* One or more nonterminals to be %typed. */ 349 350 symbols.1: 351 symbol { $$ = symbol_list_new ($1, @1); } 352 | symbols.1 symbol { $$ = symbol_list_prepend ($1, $2, @2); } 353 ; 354 355 /* One token definition. */ 356 symbol_def: 357 TYPE 358 { 359 current_type = $1; 360 } 361 | ID 362 { 363 symbol_class_set ($1, current_class, @1, true); 364 symbol_type_set ($1, current_type, @1); 365 } 366 | ID INT 367 { 368 symbol_class_set ($1, current_class, @1, true); 369 symbol_type_set ($1, current_type, @1); 370 symbol_user_token_number_set ($1, $2, @2); 371 } 372 | ID string_as_id 373 { 374 symbol_class_set ($1, current_class, @1, true); 375 symbol_type_set ($1, current_type, @1); 376 symbol_make_alias ($1, $2, @$); 377 } 378 | ID INT string_as_id 379 { 380 symbol_class_set ($1, current_class, @1, true); 381 symbol_type_set ($1, current_type, @1); 382 symbol_user_token_number_set ($1, $2, @2); 383 symbol_make_alias ($1, $3, @$); 384 } 385 ; 386 387 /* One or more symbol definitions. */ 388 symbol_defs.1: 389 symbol_def 390 | symbol_defs.1 symbol_def 391 ; 392 393 394 /*------------------------------------------. 395 | The grammar section: between the two %%. | 396 `------------------------------------------*/ 397 398 grammar: 399 rules_or_grammar_declaration 400 | grammar rules_or_grammar_declaration 401 ; 402 403 /* As a Bison extension, one can use the grammar declarations in the 404 body of the grammar. */ 405 rules_or_grammar_declaration: 406 rules 407 | grammar_declaration ";" 408 | error ";" 409 { 410 yyerrok; 411 } 412 ; 413 414 rules: 415 ID_COLON { current_lhs = $1; current_lhs_location = @1; } rhses.1 416 ; 417 418 rhses.1: 419 rhs { grammar_current_rule_end (@1); } 420 | rhses.1 "|" rhs { grammar_current_rule_end (@3); } 421 | rhses.1 ";" 422 ; 423 424 rhs: 425 /* Nothing. */ 426 { grammar_current_rule_begin (current_lhs, current_lhs_location); } 427 | rhs symbol 428 { grammar_current_rule_symbol_append ($2, @2); } 429 | rhs action 430 | rhs "%prec" symbol 431 { grammar_current_rule_prec_set ($3, @3); } 432 | rhs "%dprec" INT 433 { grammar_current_rule_dprec_set ($3, @3); } 434 | rhs "%merge" TYPE 435 { grammar_current_rule_merge_set ($3, @3); } 436 ; 437 438 symbol: 439 ID { $$ = $1; } 440 | string_as_id { $$ = $1; } 441 ; 442 443 /* Handle the semantics of an action specially, with a mid-rule 444 action, so that grammar_current_rule_action_append is invoked 445 immediately after the braced code is read by the scanner. 446 447 This implementation relies on the LALR(1) parsing algorithm. 448 If grammar_current_rule_action_append were executed in a normal 449 action for this rule, then when the input grammar contains two 450 successive actions, the scanner would have to read both actions 451 before reducing this rule. That wouldn't work, since the scanner 452 relies on all preceding input actions being processed by 453 grammar_current_rule_action_append before it scans the next 454 action. */ 455 action: 456 { grammar_current_rule_action_append (last_string, last_braced_code_loc); } 457 BRACED_CODE 458 ; 459 460 /* A string used as an ID: quote it. */ 461 string_as_id: 462 STRING 463 { 464 $$ = symbol_get (quotearg_style (c_quoting_style, $1), @1); 465 symbol_class_set ($$, token_sym, @1, false); 466 } 467 ; 468 469 /* A string used for its contents. Don't quote it. */ 470 string_content: 471 STRING 472 { $$ = $1; } 473 ; 474 475 476 epilogue.opt: 477 /* Nothing. */ 478 | "%%" EPILOGUE 479 { 480 muscle_code_grow ("epilogue", $2, @2); 481 scanner_last_string_free (); 482 } 483 ; 484 485 %% 486 487 488 /* Return the location of the left-hand side of a rule whose 489 right-hand side is RHS[1] ... RHS[N]. Ignore empty nonterminals in 490 the right-hand side, and return an empty location equal to the end 491 boundary of RHS[0] if the right-hand side is empty. */ 492 493 static YYLTYPE 494 lloc_default (YYLTYPE const *rhs, int n) 495 { 496 int i; 497 YYLTYPE loc; 498 499 /* SGI MIPSpro 7.4.1m miscompiles "loc.start = loc.end = rhs[n].end;". 500 The bug is fixed in 7.4.2m, but play it safe for now. */ 501 loc.start = rhs[n].end; 502 loc.end = rhs[n].end; 503 504 /* Ignore empty nonterminals the start of the the right-hand side. 505 Do not bother to ignore them at the end of the right-hand side, 506 since empty nonterminals have the same end as their predecessors. */ 507 for (i = 1; i <= n; i++) 508 if (! equal_boundaries (rhs[i].start, rhs[i].end)) 509 { 510 loc.start = rhs[i].start; 511 break; 512 } 513 514 return loc; 515 } 516 517 518 /* Add a lex-param or a parse-param (depending on TYPE) with 519 declaration DECL and location LOC. */ 520 521 static void 522 add_param (char const *type, char *decl, location loc) 523 { 524 static char const alphanum[26 + 26 + 1 + 10] = 525 "abcdefghijklmnopqrstuvwxyz" 526 "ABCDEFGHIJKLMNOPQRSTUVWXYZ" 527 "_" 528 "0123456789"; 529 char const *name_start = NULL; 530 char *p; 531 532 /* Stop on last actual character. */ 533 for (p = decl; p[1]; p++) 534 if ((p == decl 535 || ! memchr (alphanum, p[-1], sizeof alphanum)) 536 && memchr (alphanum, p[0], sizeof alphanum - 10)) 537 name_start = p; 538 539 /* Strip the surrounding '{' and '}', and any blanks just inside 540 the braces. */ 541 while (*--p == ' ' || *p == '\t') 542 continue; 543 p[1] = '\0'; 544 while (*++decl == ' ' || *decl == '\t') 545 continue; 546 547 if (! name_start) 548 complain_at (loc, _("missing identifier in parameter declaration")); 549 else 550 { 551 char *name; 552 size_t name_len; 553 554 for (name_len = 1; 555 memchr (alphanum, name_start[name_len], sizeof alphanum); 556 name_len++) 557 continue; 558 559 name = xmalloc (name_len + 1); 560 memcpy (name, name_start, name_len); 561 name[name_len] = '\0'; 562 muscle_pair_list_grow (type, decl, name); 563 free (name); 564 } 565 566 scanner_last_string_free (); 567 } 568 569 static void 570 version_check (location const *loc, char const *version) 571 { 572 if (strverscmp (version, PACKAGE_VERSION) > 0) 573 { 574 complain_at (*loc, "require bison %s, but have %s", 575 version, PACKAGE_VERSION); 576 exit (63); 577 } 578 } 579 580 static void 581 gram_error (location const *loc, char const *msg) 582 { 583 complain_at (*loc, "%s", msg); 584 } 585 586 char const * 587 token_name (int type) 588 { 589 return yytname[YYTRANSLATE (type)]; 590 } 591
