1 /* Output the generated parsing program for Bison. 2 3 Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 4 2005, 2006 Free Software Foundation, Inc. 5 6 This file is part of Bison, the GNU Compiler Compiler. 7 8 Bison is free software; you can redistribute it and/or modify it 9 under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2, or (at your option) 11 any later version. 12 13 Bison is distributed in the hope that it will be useful, but 14 WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Bison; see the file COPYING. If not, write to the Free 20 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 21 02110-1301, USA. */ 22 23 #include <config.h> 24 #include "system.h" 25 26 #include <error.h> 27 #include <get-errno.h> 28 #include <quotearg.h> 29 #include <subpipe.h> 30 #include <timevar.h> 31 32 #include "complain.h" 33 #include "files.h" 34 #include "getargs.h" 35 #include "gram.h" 36 #include "muscle_tab.h" 37 #include "output.h" 38 #include "reader.h" 39 #include "scan-skel.h" 40 #include "symtab.h" 41 #include "tables.h" 42 43 44 static struct obstack format_obstack; 45 46 47 /*-------------------------------------------------------------------. 48 | Create a function NAME which associates to the muscle NAME the | 49 | result of formatting the FIRST and then TABLE_DATA[BEGIN..END[ (of | 50 | TYPE), and to the muscle NAME_max, the max value of the | 51 | TABLE_DATA. | 52 `-------------------------------------------------------------------*/ 53 54 55 #define GENERATE_MUSCLE_INSERT_TABLE(Name, Type) \ 56 \ 57 static void \ 58 Name (char const *name, \ 59 Type *table_data, \ 60 Type first, \ 61 int begin, \ 62 int end) \ 63 { \ 64 Type min = first; \ 65 Type max = first; \ 66 long int lmin; \ 67 long int lmax; \ 68 int i; \ 69 int j = 1; \ 70 \ 71 obstack_fgrow1 (&format_obstack, "%6d", first); \ 72 for (i = begin; i < end; ++i) \ 73 { \ 74 obstack_1grow (&format_obstack, ','); \ 75 if (j >= 10) \ 76 { \ 77 obstack_sgrow (&format_obstack, "\n "); \ 78 j = 1; \ 79 } \ 80 else \ 81 ++j; \ 82 obstack_fgrow1 (&format_obstack, "%6d", table_data[i]); \ 83 if (table_data[i] < min) \ 84 min = table_data[i]; \ 85 if (max < table_data[i]) \ 86 max = table_data[i]; \ 87 } \ 88 obstack_1grow (&format_obstack, 0); \ 89 muscle_insert (name, obstack_finish (&format_obstack)); \ 90 \ 91 lmin = min; \ 92 lmax = max; \ 93 /* Build `NAME_min' and `NAME_max' in the obstack. */ \ 94 obstack_fgrow1 (&format_obstack, "%s_min", name); \ 95 obstack_1grow (&format_obstack, 0); \ 96 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmin); \ 97 obstack_fgrow1 (&format_obstack, "%s_max", name); \ 98 obstack_1grow (&format_obstack, 0); \ 99 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmax); \ 100 } 101 102 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table, unsigned int) 103 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_int_table, int) 104 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_base_table, base_number) 105 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_rule_number_table, rule_number) 106 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table, symbol_number) 107 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_item_number_table, item_number) 108 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_state_number_table, state_number) 109 110 111 /*--------------------------------------------------------------------. 112 | Print to OUT a representation of STRING escaped both for C and M4. | 113 `--------------------------------------------------------------------*/ 114 115 static void 116 escaped_output (FILE *out, char const *string) 117 { 118 char const *p; 119 fprintf (out, "[["); 120 121 for (p = quotearg_style (c_quoting_style, string); *p; p++) 122 switch (*p) 123 { 124 case '$': fputs ("$][", out); break; 125 case '@': fputs ("@@", out); break; 126 case '[': fputs ("@{", out); break; 127 case ']': fputs ("@}", out); break; 128 default: fputc (*p, out); break; 129 } 130 131 fprintf (out, "]]"); 132 } 133 134 135 /*------------------------------------------------------------------. 136 | Prepare the muscles related to the symbols: translate, tname, and | 137 | toknum. | 138 `------------------------------------------------------------------*/ 139 140 static void 141 prepare_symbols (void) 142 { 143 MUSCLE_INSERT_BOOL ("token_table", token_table_flag); 144 MUSCLE_INSERT_INT ("tokens_number", ntokens); 145 MUSCLE_INSERT_INT ("nterms_number", nvars); 146 MUSCLE_INSERT_INT ("undef_token_number", undeftoken->number); 147 MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number); 148 149 muscle_insert_symbol_number_table ("translate", 150 token_translations, 151 token_translations[0], 152 1, max_user_token_number + 1); 153 154 /* tname -- token names. */ 155 { 156 int i; 157 /* We assume that the table will be output starting at column 2. */ 158 int j = 2; 159 for (i = 0; i < nsyms; i++) 160 { 161 char const *cp = quotearg_style (c_quoting_style, symbols[i]->tag); 162 /* Width of the next token, including the two quotes, the 163 comma and the space. */ 164 int width = strlen (cp) + 2; 165 166 if (j + width > 75) 167 { 168 obstack_sgrow (&format_obstack, "\n "); 169 j = 1; 170 } 171 172 if (i) 173 obstack_1grow (&format_obstack, ' '); 174 MUSCLE_OBSTACK_SGROW (&format_obstack, cp); 175 obstack_1grow (&format_obstack, ','); 176 j += width; 177 } 178 /* Add a NULL entry to list of tokens (well, 0, as NULL might not be 179 defined). */ 180 obstack_sgrow (&format_obstack, " 0"); 181 182 /* Finish table and store. */ 183 obstack_1grow (&format_obstack, 0); 184 muscle_insert ("tname", obstack_finish (&format_obstack)); 185 } 186 187 /* Output YYTOKNUM. */ 188 { 189 int i; 190 int *values = xnmalloc (ntokens, sizeof *values); 191 for (i = 0; i < ntokens; ++i) 192 values[i] = symbols[i]->user_token_number; 193 muscle_insert_int_table ("toknum", values, 194 values[0], 1, ntokens); 195 free (values); 196 } 197 } 198 199 200 /*-------------------------------------------------------------. 201 | Prepare the muscles related to the rules: rhs, prhs, r1, r2, | 202 | rline, dprec, merger. | 203 `-------------------------------------------------------------*/ 204 205 static void 206 prepare_rules (void) 207 { 208 rule_number r; 209 unsigned int i = 0; 210 item_number *rhs = xnmalloc (nritems, sizeof *rhs); 211 unsigned int *prhs = xnmalloc (nrules, sizeof *prhs); 212 unsigned int *rline = xnmalloc (nrules, sizeof *rline); 213 symbol_number *r1 = xnmalloc (nrules, sizeof *r1); 214 unsigned int *r2 = xnmalloc (nrules, sizeof *r2); 215 int *dprec = xnmalloc (nrules, sizeof *dprec); 216 int *merger = xnmalloc (nrules, sizeof *merger); 217 218 for (r = 0; r < nrules; ++r) 219 { 220 item_number *rhsp = NULL; 221 /* Index of rule R in RHS. */ 222 prhs[r] = i; 223 /* RHS of the rule R. */ 224 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) 225 rhs[i++] = *rhsp; 226 /* LHS of the rule R. */ 227 r1[r] = rules[r].lhs->number; 228 /* Length of rule R's RHS. */ 229 r2[r] = i - prhs[r]; 230 /* Separator in RHS. */ 231 rhs[i++] = -1; 232 /* Line where rule was defined. */ 233 rline[r] = rules[r].location.start.line; 234 /* Dynamic precedence (GLR). */ 235 dprec[r] = rules[r].dprec; 236 /* Merger-function index (GLR). */ 237 merger[r] = rules[r].merger; 238 } 239 assert (i == nritems); 240 241 muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems); 242 muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules); 243 muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules); 244 muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules); 245 muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules); 246 muscle_insert_int_table ("dprec", dprec, 0, 0, nrules); 247 muscle_insert_int_table ("merger", merger, 0, 0, nrules); 248 249 MUSCLE_INSERT_INT ("rules_number", nrules); 250 MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context); 251 252 free (rhs); 253 free (prhs); 254 free (rline); 255 free (r1); 256 free (r2); 257 free (dprec); 258 free (merger); 259 } 260 261 /*--------------------------------------------. 262 | Prepare the muscles related to the states. | 263 `--------------------------------------------*/ 264 265 static void 266 prepare_states (void) 267 { 268 state_number i; 269 symbol_number *values = xnmalloc (nstates, sizeof *values); 270 for (i = 0; i < nstates; ++i) 271 values[i] = states[i]->accessing_symbol; 272 muscle_insert_symbol_number_table ("stos", values, 273 0, 1, nstates); 274 free (values); 275 276 MUSCLE_INSERT_INT ("last", high); 277 MUSCLE_INSERT_INT ("final_state_number", final_state->number); 278 MUSCLE_INSERT_INT ("states_number", nstates); 279 } 280 281 282 283 /*---------------------------------. 284 | Output the user actions to OUT. | 285 `---------------------------------*/ 286 287 static void 288 user_actions_output (FILE *out) 289 { 290 rule_number r; 291 292 fputs ("m4_define([b4_actions], \n[[", out); 293 for (r = 0; r < nrules; ++r) 294 if (rules[r].action) 295 { 296 fprintf (out, " case %d:\n", r + 1); 297 298 fprintf (out, "]b4_syncline(%d, ", 299 rules[r].action_location.start.line); 300 escaped_output (out, rules[r].action_location.start.file); 301 fprintf (out, ")[\n"); 302 fprintf (out, " %s\n break;\n\n", 303 rules[r].action); 304 } 305 fputs ("]])\n\n", out); 306 } 307 308 /*--------------------------------------. 309 | Output the merge functions to OUT. | 310 `--------------------------------------*/ 311 312 static void 313 merger_output (FILE *out) 314 { 315 int n; 316 merger_list* p; 317 318 fputs ("m4_define([b4_mergers], \n[[", out); 319 for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next) 320 { 321 if (p->type[0] == '\0') 322 fprintf (out, " case %d: *yy0 = %s (*yy0, *yy1); break;\n", 323 n, p->name); 324 else 325 fprintf (out, " case %d: yy0->%s = %s (*yy0, *yy1); break;\n", 326 n, p->type, p->name); 327 } 328 fputs ("]])\n\n", out); 329 } 330 331 /*--------------------------------------. 332 | Output the tokens definition to OUT. | 333 `--------------------------------------*/ 334 335 static void 336 token_definitions_output (FILE *out) 337 { 338 int i; 339 char const *sep = ""; 340 341 fputs ("m4_define([b4_tokens], \n[", out); 342 for (i = 0; i < ntokens; ++i) 343 { 344 symbol *sym = symbols[i]; 345 int number = sym->user_token_number; 346 347 /* At this stage, if there are literal aliases, they are part of 348 SYMBOLS, so we should not find symbols which are the aliases 349 here. */ 350 assert (number != USER_NUMBER_ALIAS); 351 352 /* Skip error token. */ 353 if (sym == errtoken) 354 continue; 355 356 /* If this string has an alias, then it is necessarily the alias 357 which is to be output. */ 358 if (sym->alias) 359 sym = sym->alias; 360 361 /* Don't output literal chars or strings (when defined only as a 362 string). Note that must be done after the alias resolution: 363 think about `%token 'f' "f"'. */ 364 if (sym->tag[0] == '\'' || sym->tag[0] == '\"') 365 continue; 366 367 /* Don't #define nonliteral tokens whose names contain periods 368 or '$' (as does the default value of the EOF token). */ 369 if (strchr (sym->tag, '.') || strchr (sym->tag, '$')) 370 continue; 371 372 fprintf (out, "%s[[[%s]], %d]", 373 sep, sym->tag, number); 374 sep = ",\n"; 375 } 376 fputs ("])\n\n", out); 377 } 378 379 380 /*---------------------------------------. 381 | Output the symbol destructors to OUT. | 382 `---------------------------------------*/ 383 384 static void 385 symbol_destructors_output (FILE *out) 386 { 387 int i; 388 char const *sep = ""; 389 390 fputs ("m4_define([b4_symbol_destructors], \n[", out); 391 for (i = 0; i < nsyms; ++i) 392 if (symbols[i]->destructor) 393 { 394 symbol *sym = symbols[i]; 395 396 /* Filename, lineno, 397 Symbol-name, Symbol-number, 398 destructor, optional typename. */ 399 fprintf (out, "%s[", sep); 400 sep = ",\n"; 401 escaped_output (out, sym->destructor_location.start.file); 402 fprintf (out, ", %d, ", sym->destructor_location.start.line); 403 escaped_output (out, sym->tag); 404 fprintf (out, ", %d, [[%s]]", sym->number, sym->destructor); 405 if (sym->type_name) 406 fprintf (out, ", [[%s]]", sym->type_name); 407 fputc (']', out); 408 } 409 fputs ("])\n\n", out); 410 } 411 412 413 /*------------------------------------. 414 | Output the symbol printers to OUT. | 415 `------------------------------------*/ 416 417 static void 418 symbol_printers_output (FILE *out) 419 { 420 int i; 421 char const *sep = ""; 422 423 fputs ("m4_define([b4_symbol_printers], \n[", out); 424 for (i = 0; i < nsyms; ++i) 425 if (symbols[i]->printer) 426 { 427 symbol *sym = symbols[i]; 428 429 /* Filename, lineno, 430 Symbol-name, Symbol-number, 431 printer, optional typename. */ 432 fprintf (out, "%s[", sep); 433 sep = ",\n"; 434 escaped_output (out, sym->printer_location.start.file); 435 fprintf (out, ", %d, ", sym->printer_location.start.line); 436 escaped_output (out, sym->tag); 437 fprintf (out, ", %d, [[%s]]", sym->number, sym->printer); 438 if (sym->type_name) 439 fprintf (out, ", [[%s]]", sym->type_name); 440 fputc (']', out); 441 } 442 fputs ("])\n\n", out); 443 } 444 445 446 static void 447 prepare_actions (void) 448 { 449 /* Figure out the actions for the specified state, indexed by 450 look-ahead token type. */ 451 452 muscle_insert_rule_number_table ("defact", yydefact, 453 yydefact[0], 1, nstates); 454 455 /* Figure out what to do after reducing with each rule, depending on 456 the saved state from before the beginning of parsing the data 457 that matched this rule. */ 458 muscle_insert_state_number_table ("defgoto", yydefgoto, 459 yydefgoto[0], 1, nsyms - ntokens); 460 461 462 /* Output PACT. */ 463 muscle_insert_base_table ("pact", base, 464 base[0], 1, nstates); 465 MUSCLE_INSERT_INT ("pact_ninf", base_ninf); 466 467 /* Output PGOTO. */ 468 muscle_insert_base_table ("pgoto", base, 469 base[nstates], nstates + 1, nvectors); 470 471 muscle_insert_base_table ("table", table, 472 table[0], 1, high + 1); 473 MUSCLE_INSERT_INT ("table_ninf", table_ninf); 474 475 muscle_insert_base_table ("check", check, 476 check[0], 1, high + 1); 477 478 /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus 479 YYPACT) so that in states with unresolved conflicts, the default 480 reduction is not used in the conflicted entries, so that there is 481 a place to put a conflict pointer. 482 483 This means that YYCONFLP and YYCONFL are nonsense for a non-GLR 484 parser, so we could avoid accidents by not writing them out in 485 that case. Nevertheless, it seems even better to be able to use 486 the GLR skeletons even without the non-deterministic tables. */ 487 muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table, 488 conflict_table[0], 1, high + 1); 489 muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list, 490 0, 1, conflict_list_cnt); 491 } 492 493 494 /*---------------------------. 496 | Call the skeleton parser. | 497 `---------------------------*/ 498 499 static void 500 output_skeleton (void) 501 { 502 FILE *in; 503 FILE *out; 504 int filter_fd[2]; 505 char const *argv[6]; 506 pid_t pid; 507 508 /* Compute the names of the package data dir and skeleton file. 509 Test whether m4sugar.m4 is readable, to check for proper 510 installation. A faulty installation can cause deadlock, so a 511 cheap sanity check is worthwhile. */ 512 char const m4sugar[] = "m4sugar/m4sugar.m4"; 513 char *full_m4sugar; 514 char *full_skeleton; 515 char const *p; 516 char const *m4 = (p = getenv ("M4")) ? p : M4; 517 char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR; 518 size_t skeleton_size = strlen (skeleton) + 1; 519 size_t pkgdatadirlen = strlen (pkgdatadir); 520 while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/') 521 pkgdatadirlen--; 522 full_skeleton = xmalloc (pkgdatadirlen + 1 523 + (skeleton_size < sizeof m4sugar 524 ? sizeof m4sugar : skeleton_size)); 525 strcpy (full_skeleton, pkgdatadir); 526 full_skeleton[pkgdatadirlen] = '/'; 527 strcpy (full_skeleton + pkgdatadirlen + 1, m4sugar); 528 full_m4sugar = xstrdup (full_skeleton); 529 strcpy (full_skeleton + pkgdatadirlen + 1, skeleton); 530 xfclose (xfopen (full_m4sugar, "r")); 531 532 /* Create an m4 subprocess connected to us via two pipes. */ 533 534 if (trace_flag & trace_tools) 535 fprintf (stderr, "running: %s %s - %s\n", 536 m4, full_m4sugar, full_skeleton); 537 538 argv[0] = m4; 539 argv[1] = full_m4sugar; 540 argv[2] = "-"; 541 argv[3] = full_skeleton; 542 argv[4] = trace_flag & trace_m4 ? "-dV" : NULL; 543 argv[5] = NULL; 544 545 init_subpipe (); 546 pid = create_subpipe (argv, filter_fd); 547 free (full_m4sugar); 548 free (full_skeleton); 549 550 out = fdopen (filter_fd[0], "w"); 551 if (! out) 552 error (EXIT_FAILURE, get_errno (), 553 "fdopen"); 554 555 /* Output the definitions of all the muscles. */ 556 fputs ("m4_init()\n", out); 557 558 user_actions_output (out); 559 merger_output (out); 560 token_definitions_output (out); 561 symbol_destructors_output (out); 562 symbol_printers_output (out); 563 564 muscles_m4_output (out); 565 566 fputs ("m4_wrap([m4_divert_pop(0)])\n", out); 567 fputs ("m4_divert_push(0)dnl\n", out); 568 xfclose (out); 569 570 /* Read and process m4's output. */ 571 timevar_push (TV_M4); 572 end_of_output_subpipe (pid, filter_fd); 573 in = fdopen (filter_fd[1], "r"); 574 if (! in) 575 error (EXIT_FAILURE, get_errno (), 576 "fdopen"); 577 scan_skel (in); 578 xfclose (in); 579 reap_subpipe (pid, m4); 580 timevar_pop (TV_M4); 581 } 582 583 static void 584 prepare (void) 585 { 586 /* Flags. */ 587 MUSCLE_INSERT_BOOL ("debug_flag", debug_flag); 588 MUSCLE_INSERT_BOOL ("defines_flag", defines_flag); 589 MUSCLE_INSERT_BOOL ("error_verbose_flag", error_verbose); 590 MUSCLE_INSERT_BOOL ("locations_flag", locations_flag); 591 MUSCLE_INSERT_BOOL ("pure_flag", pure_parser); 592 MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag); 593 594 /* File names. */ 595 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy"); 596 #define DEFINE(Name) MUSCLE_INSERT_STRING (#Name, Name ? Name : "") 597 DEFINE (dir_prefix); 598 DEFINE (parser_file_name); 599 DEFINE (spec_defines_file); 600 DEFINE (spec_file_prefix); 601 DEFINE (spec_graph_file); 602 DEFINE (spec_name_prefix); 603 DEFINE (spec_outfile); 604 DEFINE (spec_verbose_file); 605 #undef DEFINE 606 607 /* User Code. */ 608 obstack_1grow (&pre_prologue_obstack, 0); 609 obstack_1grow (&post_prologue_obstack, 0); 610 muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack)); 611 muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack)); 612 613 /* Find the right skeleton file. */ 614 if (!skeleton) 615 { 616 if (glr_parser || nondeterministic_parser) 617 skeleton = "glr.c"; 618 else 619 skeleton = "yacc.c"; 620 } 621 622 /* About the skeletons. */ 623 { 624 char const *pkgdatadir = getenv ("BISON_PKGDATADIR"); 625 MUSCLE_INSERT_STRING ("pkgdatadir", pkgdatadir ? pkgdatadir : PKGDATADIR); 626 MUSCLE_INSERT_C_STRING ("skeleton", skeleton); 627 } 628 } 629 630 631 /*----------------------------------------------------------. 632 | Output the parsing tables and the parser code to ftable. | 633 `----------------------------------------------------------*/ 634 635 void 636 output (void) 637 { 638 obstack_init (&format_obstack); 639 640 prepare_symbols (); 641 prepare_rules (); 642 prepare_states (); 643 prepare_actions (); 644 645 prepare (); 646 647 /* Process the selected skeleton file. */ 648 output_skeleton (); 649 650 obstack_free (&format_obstack, NULL); 651 obstack_free (&pre_prologue_obstack, NULL); 652 obstack_free (&post_prologue_obstack, NULL); 653 } 654