src/reader.c

   1 /* Input parser for bison
   2    Copyright (C) 1984, 1986, 1989, 1992, 1998, 2000, 2001, 2002
   3    Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    Bison 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, or (at your option)
  10    any later version.
  11
  12    Bison 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 Bison; see the file COPYING.  If not, write to
  19    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20    Boston, MA 02111-1307, USA.  */
  21
  22
  23 #include "system.h"
  24 #include "quotearg.h"
  25 #include "quote.h"
  26 #include "getargs.h"
  27 #include "files.h"
  28 #include "symtab.h"
  29 #include "options.h"
  30 #include "gram.h"
  31 #include "complain.h"
  32 #include "output.h"
  33 #include "reader.h"
  34 #include "conflicts.h"
  35 #include "muscle_tab.h"
  36
  37 int lineno;
  38 static symbol_list *grammar = NULL;
  39 static int start_flag = 0;
  40
  41 /* Nonzero if %union has been seen.  */
  42 int typed = 0;
  43
  44 symbol_list *
  45 symbol_list_new (symbol_t *sym, location_t location)
  46 {
  47   symbol_list *res = XMALLOC (symbol_list, 1);
  48   res->next = NULL;
  49   res->sym = sym;
  50   res->location = location;
  51   res->action = NULL;
  52   res->ruleprec = NULL;
  53   return res;
  54 }
  55
  56 symbol_list *
  57 symbol_list_prepend (symbol_list *list, symbol_t *symbol, location_t location)
  58 {
  59   symbol_list *res = symbol_list_new (symbol, location);
  60   res->next = list;
  61   return res;
  62 }
  63
  64 \f
  65 /*--------------------------------------------------------------.
  66 | Get the data type (alternative in the union) of the value for |
  67 | symbol N in rule RULE.                                        |
  68 `--------------------------------------------------------------*/
  69
  70 char *
  71 get_type_name (int n, symbol_list *rule)
  72 {
  73   int i;
  74   symbol_list *rp;
  75
  76   if (n < 0)
  77     {
  78       complain (_("invalid $ value"));
  79       return NULL;
  80     }
  81
  82   rp = rule;
  83   i = 0;
  84
  85   while (i < n)
  86     {
  87       rp = rp->next;
  88       if (rp == NULL || rp->sym == NULL)
  89         {
  90           complain (_("invalid $ value"));
  91           return NULL;
  92         }
  93       ++i;
  94     }
  95
  96   return rp->sym->type_name;
  97 }
  98
  99
 100 /*-----------------------.
 101 | Set the start symbol.  |
 102 `-----------------------*/
 103
 104 void
 105 grammar_start_symbol_set (symbol_t *s, location_t l)
 106 {
 107   if (start_flag)
 108     complain (_("multiple %s declarations"), "%start");
 109   else
 110     {
 111       start_flag = 1;
 112       startsymbol = s;
 113       startsymbol_location = l;
 114     }
 115 }
 116
 117
 118 /*----------------------------------------------------------------.
 119 | There are two prologues: one before %union, one after.  Augment |
 120 | the current one.                                                |
 121 `----------------------------------------------------------------*/
 122
 123 void
 124 prologue_augment (const char *prologue, location_t location)
 125 {
 126   struct obstack *oout =
 127     !typed ? &pre_prologue_obstack : &post_prologue_obstack;
 128
 129   if (!no_lines_flag)
 130     {
 131       obstack_fgrow2 (oout, muscle_find ("linef"),
 132                       location.first_line,
 133                       quotearg_style (c_quoting_style,
 134                                       muscle_find ("filename")));
 135     }
 136   obstack_sgrow (oout, prologue);
 137 }
 138
 139
 140
 141
 142 /*----------------------.
 143 | Handle the epilogue.  |
 144 `----------------------*/
 145
 146 void
 147 epilogue_set (const char *epilogue, location_t location)
 148 {
 149   if (!no_lines_flag)
 150     {
 151       obstack_fgrow2 (&muscle_obstack, muscle_find ("linef"),
 152                       location.first_line,
 153                       quotearg_style (c_quoting_style,
 154                                       muscle_find ("filename")));
 155     }
 156   obstack_sgrow (&muscle_obstack, epilogue);
 157   obstack_1grow (&muscle_obstack, 0);
 158   muscle_insert ("epilogue", obstack_finish (&muscle_obstack));
 159 }
 160
 161
 162 \f
 163
 164 /*-------------------------------------------------------------------.
 165 | Generate a dummy symbol, a nonterminal, whose name cannot conflict |
 166 | with the user's names.                                             |
 167 `-------------------------------------------------------------------*/
 168
 169 static symbol_t *
 170 gensym (location_t location)
 171 {
 172   /* Incremented for each generated symbol */
 173   static int gensym_count = 0;
 174   static char buf[256];
 175
 176   symbol_t *sym;
 177
 178   sprintf (buf, "@%d", ++gensym_count);
 179   sym = getsym (buf, location);
 180   sym->class = nterm_sym;
 181   sym->number = nvars++;
 182   return sym;
 183 }
 184 \f
 185 /*-------------------------------------------------------------------.
 186 | Parse the input grammar into a one symbol_list structure.  Each    |
 187 | rule is represented by a sequence of symbols: the left hand side   |
 188 | followed by the contents of the right hand side, followed by a     |
 189 | null pointer instead of a symbol to terminate the rule.  The next  |
 190 | symbol is the lhs of the following rule.                           |
 191 |                                                                    |
 192 | All actions are copied out, labelled by the rule number they apply |
 193 | to.                                                                |
 194 |                                                                    |
 195 | Bison used to allow some %directives in the rules sections, but    |
 196 | this is no longer consider appropriate: (i) the documented grammar |
 197 | doesn't claim it, (ii), it would promote bad style, (iii), error   |
 198 | recovery for %directives consists in skipping the junk until a `%' |
 199 | is seen and helrp synchronizing.  This scheme is definitely wrong  |
 200 | in the rules section.                                              |
 201 `-------------------------------------------------------------------*/
 202
 203 /* The (currently) last symbol of GRAMMAR. */
 204 symbol_list *grammar_end = NULL;
 205
 206 /* Append S to the GRAMMAR. */
 207 void
 208 grammar_symbol_append (symbol_t *symbol, location_t location)
 209 {
 210   symbol_list *p = symbol_list_new (symbol, location);
 211
 212   if (grammar_end)
 213     grammar_end->next = p;
 214   else
 215     grammar = p;
 216
 217   grammar_end = p;
 218 }
 219
 220 /* The rule currently being defined, and the previous rule.
 221    CURRENT_RULE points to the first LHS of the current rule, while
 222    PREVIOUS_RULE_END points to the *end* of the previous rule (NULL).  */
 223 symbol_list *current_rule = NULL;
 224 symbol_list *previous_rule_end = NULL;
 225
 226
 227 /*----------------------------------------------.
 228 | Create a new rule for LHS in to the GRAMMAR.  |
 229 `----------------------------------------------*/
 230
 231 void
 232 grammar_rule_begin (symbol_t *lhs, location_t location)
 233 {
 234   if (!start_flag)
 235     {
 236       startsymbol = lhs;
 237       startsymbol_location = location;
 238       start_flag = 1;
 239     }
 240
 241   /* Start a new rule and record its lhs.  */
 242   ++nrules;
 243   ++nritems;
 244
 245   previous_rule_end = grammar_end;
 246   grammar_symbol_append (lhs, location);
 247   current_rule = grammar_end;
 248
 249   /* Mark the rule's lhs as a nonterminal if not already so.  */
 250
 251   if (lhs->class == unknown_sym)
 252     {
 253       lhs->class = nterm_sym;
 254       lhs->number = nvars;
 255       ++nvars;
 256     }
 257   else if (lhs->class == token_sym)
 258     complain (_("rule given for %s, which is a token"), lhs->tag);
 259 }
 260
 261 /* Check that the last rule (CURRENT_RULE) is properly defined.  For
 262    instance, there should be no type clash on the default action.  */
 263
 264 static void
 265 grammar_current_rule_check (void)
 266 {
 267   symbol_t *lhs = current_rule->sym;
 268   symbol_t *first_rhs = current_rule->next->sym;
 269
 270   /* If there is an action, then there is nothing we can do: the user
 271      is allowed to shoot in her foot.  */
 272   if (current_rule->action)
 273     return;
 274
 275   /* If $$ is being set in default way, report if any type mismatch.
 276      */
 277   if (first_rhs)
 278     {
 279       const char *lhs_type = lhs->type_name       ? lhs->type_name       : "";
 280       const char *rhs_type = first_rhs->type_name ? first_rhs->type_name : "";
 281       if (strcmp (lhs_type, rhs_type))
 282         complain (_("type clash (`%s' `%s') on default action"),
 283                   lhs_type, rhs_type);
 284     }
 285   /* Warn if there is no default for $$ but we need one.  */
 286   else
 287     {
 288       if (lhs->type_name)
 289         complain (_("empty rule for typed nonterminal, and no action"));
 290     }
 291 }
 292
 293
 294 /*-------------------------------------.
 295 | End the currently being grown rule.  |
 296 `-------------------------------------*/
 297
 298 void
 299 grammar_rule_end (location_t location)
 300 {
 301   /* Put an empty link in the list to mark the end of this rule  */
 302   grammar_symbol_append (NULL, grammar_end->location);
 303   current_rule->location = location;
 304   grammar_current_rule_check ();
 305 }
 306
 307
 308 /*-------------------------------------------------------------------.
 309 | The previous action turns out the be a mid-rule action.  Attach it |
 310 | to the current rule, i.e., create a dummy symbol, attach it this   |
 311 | mid-rule action, and append this dummy nonterminal to the current  |
 312 | rule.                                                              |
 313 `-------------------------------------------------------------------*/
 314
 315 void
 316 grammar_midrule_action (void)
 317 {
 318   /* Since the action was written out with this rule's number, we must
 319      give the new rule this number by inserting the new rule before
 320      it.  */
 321
 322   /* Make a DUMMY nonterminal, whose location is that of the midrule
 323      action.  Create the MIDRULE.  */
 324   location_t dummy_location = current_rule->action_location;
 325   symbol_t *dummy = gensym (dummy_location);
 326   symbol_list *midrule = symbol_list_new (dummy, dummy_location);
 327
 328   /* Make a new rule, whose body is empty, before the current one, so
 329      that the action just read can belong to it.  */
 330   ++nrules;
 331   ++nritems;
 332   /* Attach its location and actions to that of the DUMMY.  */
 333   midrule->location = dummy_location;
 334   midrule->action = current_rule->action;
 335   midrule->action_location = dummy_location;
 336   current_rule->action = NULL;
 337
 338   if (previous_rule_end)
 339     previous_rule_end->next = midrule;
 340   else
 341     grammar = midrule;
 342
 343   /* End the dummy's rule.  */
 344   previous_rule_end = symbol_list_new (NULL, dummy_location);
 345   previous_rule_end->next = current_rule;
 346
 347   midrule->next = previous_rule_end;
 348
 349   /* Insert the dummy nonterminal replacing the midrule action into
 350      the current rule.  */
 351   grammar_current_rule_symbol_append (dummy, dummy_location);
 352 }
 353
 354 /* Set the precedence symbol of the current rule to PRECSYM. */
 355
 356 void
 357 grammar_current_rule_prec_set (symbol_t *precsym)
 358 {
 359   if (current_rule->ruleprec)
 360     complain (_("two @prec's in a row"));
 361   current_rule->ruleprec = precsym;
 362 }
 363
 364 /* Attach a SYMBOL to the current rule.  If needed, move the previous
 365    action as a mid-rule action.  */
 366
 367 void
 368 grammar_current_rule_symbol_append (symbol_t *symbol, location_t location)
 369 {
 370   if (current_rule->action)
 371     grammar_midrule_action ();
 372   ++nritems;
 373   grammar_symbol_append (symbol, location);
 374 }
 375
 376
 377 /* Attach an ACTION to the current rule.  If needed, move the previous
 378    action as a mid-rule action.  */
 379
 380 void
 381 grammar_current_rule_action_append (const char *action, location_t location)
 382 {
 383   if (current_rule->action)
 384     grammar_midrule_action ();
 385   current_rule->action = action;
 386   current_rule->action_location = location;
 387 }
 388
 389 \f
 390 /*---------------------------------------------------------------.
 391 | Convert the rules into the representation using RRHS, RLHS and |
 392 | RITEM.                                                         |
 393 `---------------------------------------------------------------*/
 394
 395 static void
 396 packgram (void)
 397 {
 398   unsigned int itemno;
 399   int ruleno;
 400   symbol_list *p;
 401
 402   ritem = XCALLOC (item_number_t, nritems);
 403   rules = XCALLOC (rule_t, nrules) - 1;
 404
 405   itemno = 0;
 406   ruleno = 1;
 407
 408   p = grammar;
 409   while (p)
 410     {
 411       symbol_t *ruleprec = p->ruleprec;
 412       rules[ruleno].user_number = ruleno;
 413       rules[ruleno].number = ruleno;
 414       rules[ruleno].lhs = p->sym;
 415       rules[ruleno].rhs = ritem + itemno;
 416       rules[ruleno].location = p->location;
 417       rules[ruleno].useful = TRUE;
 418       rules[ruleno].action = p->action;
 419       rules[ruleno].action_location = p->action_location;
 420
 421       p = p->next;
 422       while (p && p->sym)
 423         {
 424           /* item_number_t = symbol_number_t.
 425              But the former needs to contain more: negative rule numbers. */
 426           ritem[itemno++] = symbol_number_as_item_number (p->sym->number);
 427           /* A rule gets by default the precedence and associativity
 428              of the last token in it.  */
 429           if (p->sym->class == token_sym)
 430             rules[ruleno].prec = p->sym;
 431           if (p)
 432             p = p->next;
 433         }
 434
 435       /* If this rule has a %prec,
 436          the specified symbol's precedence replaces the default.  */
 437       if (ruleprec)
 438         {
 439           rules[ruleno].precsym = ruleprec;
 440           rules[ruleno].prec = ruleprec;
 441         }
 442       ritem[itemno++] = -ruleno;
 443       ++ruleno;
 444
 445       if (p)
 446         p = p->next;
 447     }
 448
 449   assert (itemno == nritems);
 450
 451   if (trace_flag)
 452     ritem_print (stderr);
 453 }
 454 \f
 455 /*------------------------------------------------------------------.
 456 | Read in the grammar specification and record it in the format     |
 457 | described in gram.h.  All actions are copied into ACTION_OBSTACK, |
 458 | in each case forming the body of a C function (YYACTION) which    |
 459 | contains a switch statement to decide which action to execute.    |
 460 `------------------------------------------------------------------*/
 461
 462 void
 463 reader (void)
 464 {
 465   gram_control_t gram_control;
 466   lineno = 1;
 467
 468   /* Initialize the symbol table.  */
 469   symbols_new ();
 470
 471   /* Construct the axiom symbol. */
 472   axiom = getsym ("$axiom", empty_location);
 473   axiom->class = nterm_sym;
 474   axiom->number = nvars++;
 475
 476   /* Construct the error token */
 477   errtoken = getsym ("error", empty_location);
 478   errtoken->class = token_sym;
 479   errtoken->number = ntokens++;
 480
 481   /* Construct a token that represents all undefined literal tokens.
 482      It is always token number 2.  */
 483   undeftoken = getsym ("$undefined.", empty_location);
 484   undeftoken->class = token_sym;
 485   undeftoken->number = ntokens++;
 486
 487   /* Initialize the obstacks. */
 488   obstack_init (&pre_prologue_obstack);
 489   obstack_init (&post_prologue_obstack);
 490
 491   finput = xfopen (infile, "r");
 492   gram_in = finput;
 493
 494   gram_debug = !!getenv ("parse");
 495   gram__flex_debug = !!getenv ("scan");
 496   scanner_initialize ();
 497   gram_parse (&gram_control);
 498
 499   /* Grammar has been read.  Do some checking */
 500   if (nrules == 0)
 501     fatal (_("no rules in the input grammar"));
 502
 503   /* Report any undefined symbols and consider them nonterminals.  */
 504   symbols_check_defined ();
 505
 506   /* If the user did not define her EOFTOKEN, do it now. */
 507   if (!eoftoken)
 508     {
 509       eoftoken = getsym ("$", empty_location);
 510       eoftoken->class = token_sym;
 511       eoftoken->number = 0;
 512       /* Value specified by POSIX.  */
 513       eoftoken->user_token_number = 0;
 514     }
 515
 516   /* Insert the initial rule, which line is that of the first rule
 517      (not that of the start symbol):
 518
 519      axiom: %start EOF.  */
 520   {
 521     symbol_list *p = symbol_list_new (axiom, empty_location);
 522     p->location = grammar->location;
 523     p->next = symbol_list_new (startsymbol, empty_location);
 524     p->next->next = symbol_list_new (eoftoken, empty_location);
 525     p->next->next->next = symbol_list_new (NULL, empty_location);
 526     p->next->next->next->next = grammar;
 527     nrules += 1;
 528     nritems += 3;
 529     grammar = p;
 530   }
 531
 532   if (nsyms > SHRT_MAX)
 533     fatal (_("too many symbols (tokens plus nonterminals); maximum %d"),
 534           SHRT_MAX);
 535
 536   assert (nsyms == ntokens + nvars);
 537
 538   xfclose (finput);
 539
 540   /* Assign the symbols their symbol numbers.  Write #defines for the
 541      token symbols into FDEFINES if requested.  */
 542   symbols_pack ();
 543
 544   /* Convert the grammar into the format described in gram.h.  */
 545   packgram ();
 546
 547   /* The grammar as a symbol_list is no longer needed. */
 548   LIST_FREE (symbol_list, grammar);
 549 }