1/* Input parser for Bison
2
3   Copyright (C) 1984, 1986, 1989, 1992, 1998, 2000-2003, 2005-2007,
4   2009-2012 Free Software Foundation, Inc.
5
6   This file is part of Bison, the GNU Compiler Compiler.
7
8   This program is free software: you can redistribute it and/or modify
9   it under the terms of the GNU General Public License as published by
10   the Free Software Foundation, either version 3 of the License, or
11   (at your option) any later version.
12
13   This program is distributed in the hope that it will be useful,
14   but WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16   GNU General Public License for more details.
17
18   You should have received a copy of the GNU General Public License
19   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
20
21#include <config.h>
22#include "system.h"
23
24#include <quote.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 "reader.h"
33#include "symlist.h"
34#include "symtab.h"
35#include "scan-gram.h"
36#include "scan-code.h"
37
38static void prepare_percent_define_front_end_variables (void);
39static void check_and_convert_grammar (void);
40
41static symbol_list *grammar = NULL;
42static bool start_flag = false;
43merger_list *merge_functions;
44
45/* Was %union seen?  */
46bool union_seen = false;
47
48/* Was a tag seen?  */
49bool tag_seen = false;
50
51/* Should rules have a default precedence?  */
52bool default_prec = true;
53
54/*-----------------------.
55| Set the start symbol.  |
56`-----------------------*/
57
58void
59grammar_start_symbol_set (symbol *sym, location loc)
60{
61  if (start_flag)
62    complain_at (loc, _("multiple %s declarations"), "%start");
63  else
64    {
65      start_flag = true;
66      startsymbol = sym;
67      startsymbol_location = loc;
68    }
69}
70
71
72
73/*------------------------------------------------------------------------.
74| Return the merger index for a merging function named NAME.  Records the |
75| function, if new, in MERGER_LIST.                                       |
76`------------------------------------------------------------------------*/
77
78static int
79get_merge_function (uniqstr name)
80{
81  merger_list *syms;
82  merger_list head;
83  int n;
84
85  if (! glr_parser)
86    return 0;
87
88  head.next = merge_functions;
89  for (syms = &head, n = 1; syms->next; syms = syms->next, n += 1)
90    if (UNIQSTR_EQ (name, syms->next->name))
91      break;
92  if (syms->next == NULL)
93    {
94      syms->next = xmalloc (sizeof syms->next[0]);
95      syms->next->name = uniqstr_new (name);
96      /* After all symbol type declarations have been parsed, packgram invokes
97	 record_merge_function_type to set the type.  */
98      syms->next->type = NULL;
99      syms->next->next = NULL;
100      merge_functions = head.next;
101    }
102  return n;
103}
104
105/*-------------------------------------------------------------------------.
106| For the existing merging function with index MERGER, record the result   |
107| type as TYPE as required by the lhs of the rule whose %merge declaration |
108| is at DECLARATION_LOC.                                                   |
109`-------------------------------------------------------------------------*/
110
111static void
112record_merge_function_type (int merger, uniqstr type, location declaration_loc)
113{
114  int merger_find;
115  merger_list *merge_function;
116
117  if (merger <= 0)
118    return;
119
120  if (type == NULL)
121    type = uniqstr_new ("");
122
123  merger_find = 1;
124  for (merge_function = merge_functions;
125       merge_function != NULL && merger_find != merger;
126       merge_function = merge_function->next)
127    merger_find += 1;
128  aver (merge_function != NULL && merger_find == merger);
129  if (merge_function->type != NULL && !UNIQSTR_EQ (merge_function->type, type))
130    {
131      unsigned indent = 0;
132      complain_at_indent (declaration_loc, &indent,
133                          _("result type clash on merge function %s: "
134                            "<%s> != <%s>"),
135                          quote (merge_function->name), type,
136                          merge_function->type);
137      indent += SUB_INDENT;
138      complain_at_indent (merge_function->type_declaration_location, &indent,
139                          _("previous declaration"));
140   }
141  merge_function->type = uniqstr_new (type);
142  merge_function->type_declaration_location = declaration_loc;
143}
144
145/*--------------------------------------.
146| Free all merge-function definitions.	|
147`--------------------------------------*/
148
149void
150free_merger_functions (void)
151{
152  merger_list *L0 = merge_functions;
153  while (L0)
154    {
155      merger_list *L1 = L0->next;
156      free (L0);
157      L0 = L1;
158    }
159}
160
161
162/*-------------------------------------------------------------------.
163| Parse the input grammar into a one symbol_list structure.  Each    |
164| rule is represented by a sequence of symbols: the left hand side   |
165| followed by the contents of the right hand side, followed by a     |
166| null pointer instead of a symbol to terminate the rule.  The next  |
167| symbol is the lhs of the following rule.                           |
168|                                                                    |
169| All actions are copied out, labelled by the rule number they apply |
170| to.                                                                |
171`-------------------------------------------------------------------*/
172
173/* The (currently) last symbol of GRAMMAR. */
174static symbol_list *grammar_end = NULL;
175
176/* Append SYM to the grammar.  */
177static symbol_list *
178grammar_symbol_append (symbol *sym, location loc)
179{
180  symbol_list *p = symbol_list_sym_new (sym, loc);
181
182  if (grammar_end)
183    grammar_end->next = p;
184  else
185    grammar = p;
186
187  grammar_end = p;
188
189  /* A null SYM stands for an end of rule; it is not an actual
190     part of it.  */
191  if (sym)
192    ++nritems;
193
194  return p;
195}
196
197static void
198assign_named_ref (symbol_list *p, named_ref *name)
199{
200  symbol *sym = p->content.sym;
201
202  if (name->id == sym->tag)
203    {
204      warn_at (name->loc,
205	       _("duplicated symbol name for %s ignored"),
206	       quote (sym->tag));
207      named_ref_free (name);
208    }
209  else
210    p->named_ref = name;
211}
212
213
214/* The rule currently being defined, and the previous rule.
215   CURRENT_RULE points to the first LHS of the current rule, while
216   PREVIOUS_RULE_END points to the *end* of the previous rule (NULL).  */
217static symbol_list *current_rule = NULL;
218static symbol_list *previous_rule_end = NULL;
219
220
221/*----------------------------------------------.
222| Create a new rule for LHS in to the GRAMMAR.  |
223`----------------------------------------------*/
224
225void
226grammar_current_rule_begin (symbol *lhs, location loc,
227			    named_ref *lhs_name)
228{
229  symbol_list* p;
230
231  /* Start a new rule and record its lhs.  */
232  ++nrules;
233  previous_rule_end = grammar_end;
234
235  p = grammar_symbol_append (lhs, loc);
236  if (lhs_name)
237    assign_named_ref (p, named_ref_copy (lhs_name));
238
239  current_rule = grammar_end;
240
241  /* Mark the rule's lhs as a nonterminal if not already so.  */
242  if (lhs->class == unknown_sym)
243    {
244      lhs->class = nterm_sym;
245      lhs->number = nvars;
246      ++nvars;
247    }
248  else if (lhs->class == token_sym)
249    complain_at (loc, _("rule given for %s, which is a token"), lhs->tag);
250}
251
252
253/*----------------------------------------------------------------------.
254| A symbol should be used if either:                                    |
255|   1. It has a destructor.                                             |
256|   2. The symbol is a mid-rule symbol (i.e., the generated LHS         |
257|      replacing a mid-rule action) that was assigned to or used, as in |
258|      "exp: { $$ = 1; } { $$ = $1; }".                                 |
259`----------------------------------------------------------------------*/
260
261static bool
262symbol_should_be_used (symbol_list const *s, bool *midrule_warning)
263{
264  if (symbol_destructor_get (s->content.sym)->code)
265    return true;
266  if ((s->midrule && s->midrule->action_props.is_value_used)
267      || (s->midrule_parent_rule
268          && symbol_list_n_get (s->midrule_parent_rule,
269                                s->midrule_parent_rhs_index)
270               ->action_props.is_value_used))
271    {
272      *midrule_warning = true;
273      return true;
274    }
275  return false;
276}
277
278/*----------------------------------------------------------------.
279| Check that the rule R is properly defined.  For instance, there |
280| should be no type clash on the default action.                  |
281`----------------------------------------------------------------*/
282
283static void
284grammar_rule_check (const symbol_list *r)
285{
286  /* Type check.
287
288     If there is an action, then there is nothing we can do: the user
289     is allowed to shoot herself in the foot.
290
291     Don't worry about the default action if $$ is untyped, since $$'s
292     value can't be used.  */
293  if (!r->action_props.code && r->content.sym->type_name)
294    {
295      symbol *first_rhs = r->next->content.sym;
296      /* If $$ is being set in default way, report if any type mismatch.  */
297      if (first_rhs)
298	{
299	  char const *lhs_type = r->content.sym->type_name;
300	  const char *rhs_type =
301	    first_rhs->type_name ? first_rhs->type_name : "";
302	  if (!UNIQSTR_EQ (lhs_type, rhs_type))
303	    warn_at (r->location,
304		     _("type clash on default action: <%s> != <%s>"),
305		     lhs_type, rhs_type);
306	}
307      /* Warn if there is no default for $$ but we need one.  */
308      else
309	warn_at (r->location,
310		 _("empty rule for typed nonterminal, and no action"));
311    }
312
313  /* Check that symbol values that should be used are in fact used.  */
314  {
315    symbol_list const *l = r;
316    int n = 0;
317    for (; l && l->content.sym; l = l->next, ++n)
318      {
319        bool midrule_warning = false;
320        if (!l->action_props.is_value_used
321            && symbol_should_be_used (l, &midrule_warning)
322            /* The default action, $$ = $1, `uses' both.  */
323            && (r->action_props.code || (n != 0 && n != 1)))
324          {
325            void (*warn_at_ptr)(location, char const*, ...) =
326              midrule_warning ? midrule_value_at : warn_at;
327            if (n)
328              warn_at_ptr (l->location, _("unused value: $%d"), n);
329            else
330              warn_at_ptr (l->location, _("unset value: $$"));
331          }
332      }
333  }
334
335  /* See comments in grammar_current_rule_prec_set for how POSIX
336     mandates this complaint.  It's only for identifiers, so skip
337     it for char literals and strings, which are always tokens.  */
338  if (r->ruleprec
339      && r->ruleprec->tag[0] != '\'' && r->ruleprec->tag[0] != '"'
340      && !r->ruleprec->declared && !r->ruleprec->prec)
341    warn_at (r->location, _("token for %%prec is not defined: %s"),
342             r->ruleprec->tag);
343}
344
345
346/*-------------------------------------.
347| End the currently being grown rule.  |
348`-------------------------------------*/
349
350void
351grammar_current_rule_end (location loc)
352{
353  /* Put an empty link in the list to mark the end of this rule  */
354  grammar_symbol_append (NULL, grammar_end->location);
355  current_rule->location = loc;
356}
357
358
359/*-------------------------------------------------------------------.
360| The previous action turns out the be a mid-rule action.  Attach it |
361| to the current rule, i.e., create a dummy symbol, attach it this   |
362| mid-rule action, and append this dummy nonterminal to the current  |
363| rule.                                                              |
364`-------------------------------------------------------------------*/
365
366void
367grammar_midrule_action (void)
368{
369  /* Since the action was written out with this rule's number, we must
370     give the new rule this number by inserting the new rule before
371     it.  */
372
373  /* Make a DUMMY nonterminal, whose location is that of the midrule
374     action.  Create the MIDRULE.  */
375  location dummy_location = current_rule->action_props.location;
376  symbol *dummy = dummy_symbol_get (dummy_location);
377  symbol_list *midrule = symbol_list_sym_new (dummy, dummy_location);
378
379  /* Remember named_ref of previous action. */
380  named_ref *action_name = current_rule->action_props.named_ref;
381
382  /* Make a new rule, whose body is empty, before the current one, so
383     that the action just read can belong to it.  */
384  ++nrules;
385  ++nritems;
386  /* Attach its location and actions to that of the DUMMY.  */
387  midrule->location = dummy_location;
388  code_props_rule_action_init (&midrule->action_props,
389                               current_rule->action_props.code,
390                               current_rule->action_props.location,
391                               midrule, 0);
392  code_props_none_init (&current_rule->action_props);
393
394  if (previous_rule_end)
395    previous_rule_end->next = midrule;
396  else
397    grammar = midrule;
398
399  /* End the dummy's rule.  */
400  midrule->next = symbol_list_sym_new (NULL, dummy_location);
401  midrule->next->next = current_rule;
402
403  previous_rule_end = midrule->next;
404
405  /* Insert the dummy nonterminal replacing the midrule action into
406     the current rule.  Bind it to its dedicated rule.  */
407  grammar_current_rule_symbol_append (dummy, dummy_location,
408                                      action_name);
409  grammar_end->midrule = midrule;
410  midrule->midrule_parent_rule = current_rule;
411  midrule->midrule_parent_rhs_index = symbol_list_length (current_rule->next);
412}
413
414/* Set the precedence symbol of the current rule to PRECSYM. */
415
416void
417grammar_current_rule_prec_set (symbol *precsym, location loc)
418{
419  /* POSIX says that any identifier is a nonterminal if it does not
420     appear on the LHS of a grammar rule and is not defined by %token
421     or by one of the directives that assigns precedence to a token.  We
422     ignore this here because the only kind of identifier that POSIX
423     allows to follow a %prec is a token and because assuming it's a
424     token now can produce more logical error messages.  Nevertheless,
425     grammar_rule_check does obey what we believe is the real intent of
426     POSIX here: that an error be reported for any identifier that
427     appears after %prec but that is not defined separately as a
428     token.  */
429  symbol_class_set (precsym, token_sym, loc, false);
430  if (current_rule->ruleprec)
431    complain_at (loc, _("only one %s allowed per rule"), "%prec");
432  current_rule->ruleprec = precsym;
433}
434
435/* Attach dynamic precedence DPREC to the current rule. */
436
437void
438grammar_current_rule_dprec_set (int dprec, location loc)
439{
440  if (! glr_parser)
441    warn_at (loc, _("%s affects only GLR parsers"), "%dprec");
442  if (dprec <= 0)
443    complain_at (loc, _("%s must be followed by positive number"), "%dprec");
444  else if (current_rule->dprec != 0)
445    complain_at (loc, _("only one %s allowed per rule"), "%dprec");
446  current_rule->dprec = dprec;
447}
448
449/* Attach a merge function NAME with argument type TYPE to current
450   rule. */
451
452void
453grammar_current_rule_merge_set (uniqstr name, location loc)
454{
455  if (! glr_parser)
456    warn_at (loc, _("%s affects only GLR parsers"), "%merge");
457  if (current_rule->merger != 0)
458    complain_at (loc, _("only one %s allowed per rule"), "%merge");
459  current_rule->merger = get_merge_function (name);
460  current_rule->merger_declaration_location = loc;
461}
462
463/* Attach SYM to the current rule.  If needed, move the previous
464   action as a mid-rule action.  */
465
466void
467grammar_current_rule_symbol_append (symbol *sym, location loc,
468				    named_ref *name)
469{
470  symbol_list *p;
471  if (current_rule->action_props.code)
472    grammar_midrule_action ();
473  p = grammar_symbol_append (sym, loc);
474  if (name)
475    assign_named_ref(p, name);
476}
477
478/* Attach an ACTION to the current rule.  */
479
480void
481grammar_current_rule_action_append (const char *action, location loc,
482				    named_ref *name)
483{
484  if (current_rule->action_props.code)
485    grammar_midrule_action ();
486  /* After all symbol declarations have been parsed, packgram invokes
487     code_props_translate_code.  */
488  code_props_rule_action_init (&current_rule->action_props, action, loc,
489                               current_rule, name);
490}
491
492
493/*---------------------------------------------------------------.
494| Convert the rules into the representation using RRHS, RLHS and |
495| RITEM.                                                         |
496`---------------------------------------------------------------*/
497
498static void
499packgram (void)
500{
501  unsigned int itemno = 0;
502  rule_number ruleno = 0;
503  symbol_list *p = grammar;
504
505  ritem = xnmalloc (nritems + 1, sizeof *ritem);
506
507  /* This sentinel is used by build_relations in gram.c.  */
508  *ritem++ = 0;
509
510  rules = xnmalloc (nrules, sizeof *rules);
511
512  while (p)
513    {
514      int rule_length = 0;
515      symbol *ruleprec = p->ruleprec;
516      record_merge_function_type (p->merger, p->content.sym->type_name,
517				  p->merger_declaration_location);
518      rules[ruleno].user_number = ruleno;
519      rules[ruleno].number = ruleno;
520      rules[ruleno].lhs = p->content.sym;
521      rules[ruleno].rhs = ritem + itemno;
522      rules[ruleno].prec = NULL;
523      rules[ruleno].dprec = p->dprec;
524      rules[ruleno].merger = p->merger;
525      rules[ruleno].precsym = NULL;
526      rules[ruleno].location = p->location;
527      rules[ruleno].useful = true;
528      rules[ruleno].action = p->action_props.code;
529      rules[ruleno].action_location = p->action_props.location;
530
531      /* If the midrule's $$ is set or its $n is used, remove the `$' from the
532	 symbol name so that it's a user-defined symbol so that the default
533	 %destructor and %printer apply.  */
534      if (p->midrule_parent_rule
535          && (p->action_props.is_value_used
536	      || symbol_list_n_get (p->midrule_parent_rule,
537				    p->midrule_parent_rhs_index)
538                   ->action_props.is_value_used))
539	p->content.sym->tag += 1;
540
541      /* Don't check the generated rule 0.  It has no action, so some rhs
542	 symbols may appear unused, but the parsing algorithm ensures that
543	 %destructor's are invoked appropriately.  */
544      if (p != grammar)
545	grammar_rule_check (p);
546
547      for (p = p->next; p && p->content.sym; p = p->next)
548	{
549	  ++rule_length;
550
551	  /* Don't allow rule_length == INT_MAX, since that might
552	     cause confusion with strtol if INT_MAX == LONG_MAX.  */
553	  if (rule_length == INT_MAX)
554	      fatal_at (rules[ruleno].location, _("rule is too long"));
555
556	  /* item_number = symbol_number.
557	     But the former needs to contain more: negative rule numbers. */
558	  ritem[itemno++] =
559            symbol_number_as_item_number (p->content.sym->number);
560	  /* A rule gets by default the precedence and associativity
561	     of its last token.  */
562	  if (p->content.sym->class == token_sym && default_prec)
563	    rules[ruleno].prec = p->content.sym;
564	}
565
566      /* If this rule has a %prec,
567         the specified symbol's precedence replaces the default.  */
568      if (ruleprec)
569	{
570	  rules[ruleno].precsym = ruleprec;
571	  rules[ruleno].prec = ruleprec;
572	}
573      /* An item ends by the rule number (negated).  */
574      ritem[itemno++] = rule_number_as_item_number (ruleno);
575      aver (itemno < ITEM_NUMBER_MAX);
576      ++ruleno;
577      aver (ruleno < RULE_NUMBER_MAX);
578
579      if (p)
580	p = p->next;
581    }
582
583  aver (itemno == nritems);
584
585  if (trace_flag & trace_sets)
586    ritem_print (stderr);
587}
588
589/*------------------------------------------------------------------.
590| Read in the grammar specification and record it in the format     |
591| described in gram.h.  All actions are copied into ACTION_OBSTACK, |
592| in each case forming the body of a C function (YYACTION) which    |
593| contains a switch statement to decide which action to execute.    |
594`------------------------------------------------------------------*/
595
596void
597reader (void)
598{
599  /* Initialize the symbol table.  */
600  symbols_new ();
601
602  /* Construct the accept symbol. */
603  accept = symbol_get ("$accept", empty_location);
604  accept->class = nterm_sym;
605  accept->number = nvars++;
606
607  /* Construct the error token */
608  errtoken = symbol_get ("error", empty_location);
609  errtoken->class = token_sym;
610  errtoken->number = ntokens++;
611
612  /* Construct a token that represents all undefined literal tokens.
613     It is always token number 2.  */
614  undeftoken = symbol_get ("$undefined", empty_location);
615  undeftoken->class = token_sym;
616  undeftoken->number = ntokens++;
617
618  gram_in = xfopen (grammar_file, "r");
619
620  gram__flex_debug = trace_flag & trace_scan;
621  gram_debug = trace_flag & trace_parse;
622  gram_scanner_initialize ();
623  gram_parse ();
624  prepare_percent_define_front_end_variables ();
625
626  if (! complaint_issued)
627    check_and_convert_grammar ();
628
629  xfclose (gram_in);
630}
631
632static void
633prepare_percent_define_front_end_variables (void)
634{
635  /* Set %define front-end variable defaults.  */
636  muscle_percent_define_default ("lr.keep-unreachable-states", "false");
637  {
638    char *lr_type;
639    /* IELR would be a better default, but LALR is historically the
640       default.  */
641    muscle_percent_define_default ("lr.type", "lalr");
642    lr_type = muscle_percent_define_get ("lr.type");
643    if (0 != strcmp (lr_type, "canonical-lr"))
644      muscle_percent_define_default ("lr.default-reductions", "most");
645    else
646      muscle_percent_define_default ("lr.default-reductions", "accepting");
647    free (lr_type);
648  }
649
650  /* Check %define front-end variables.  */
651  {
652    static char const * const values[] = {
653      "lr.type", "lalr", "ielr", "canonical-lr", NULL,
654      "lr.default-reductions", "most", "consistent", "accepting", NULL,
655      NULL
656    };
657    muscle_percent_define_check_values (values);
658  }
659}
660
661
662/*-------------------------------------------------------------.
663| Check the grammar that has just been read, and convert it to |
664| internal form.					       |
665`-------------------------------------------------------------*/
666
667static void
668check_and_convert_grammar (void)
669{
670  /* Grammar has been read.  Do some checking.  */
671  if (nrules == 0)
672    fatal (_("no rules in the input grammar"));
673
674  /* If the user did not define her ENDTOKEN, do it now. */
675  if (!endtoken)
676    {
677      endtoken = symbol_get ("$end", empty_location);
678      endtoken->class = token_sym;
679      endtoken->number = 0;
680      /* Value specified by POSIX.  */
681      endtoken->user_token_number = 0;
682    }
683
684  /* Report any undefined symbols and consider them nonterminals.  */
685  symbols_check_defined ();
686
687  /* Find the start symbol if no %start.  */
688  if (!start_flag)
689    {
690      symbol_list *node;
691      for (node = grammar;
692           node != NULL && symbol_is_dummy (node->content.sym);
693           node = node->next)
694        {
695          for (node = node->next;
696               node != NULL && node->content.sym != NULL;
697               node = node->next)
698            ;
699        }
700      aver (node != NULL);
701      grammar_start_symbol_set (node->content.sym,
702                                node->content.sym->location);
703    }
704
705  /* Insert the initial rule, whose line is that of the first rule
706     (not that of the start symbol):
707
708     accept: %start EOF.  */
709  {
710    symbol_list *p = symbol_list_sym_new (accept, empty_location);
711    p->location = grammar->location;
712    p->next = symbol_list_sym_new (startsymbol, empty_location);
713    p->next->next = symbol_list_sym_new (endtoken, empty_location);
714    p->next->next->next = symbol_list_sym_new (NULL, empty_location);
715    p->next->next->next->next = grammar;
716    nrules += 1;
717    nritems += 3;
718    grammar = p;
719  }
720
721  aver (nsyms <= SYMBOL_NUMBER_MAXIMUM && nsyms == ntokens + nvars);
722
723  /* Assign the symbols their symbol numbers.  Write #defines for the
724     token symbols into FDEFINES if requested.  */
725  symbols_pack ();
726
727  /* Scan rule actions after invoking symbol_check_alias_consistency (in
728     symbols_pack above) so that token types are set correctly before the rule
729     action type checking.
730
731     Before invoking grammar_rule_check (in packgram below) on any rule, make
732     sure all actions have already been scanned in order to set `used' flags.
733     Otherwise, checking that a midrule's $$ should be set will not always work
734     properly because the check must forward-reference the midrule's parent
735     rule.  For the same reason, all the `used' flags must be set before
736     checking whether to remove `$' from any midrule symbol name (also in
737     packgram).  */
738  {
739    symbol_list *sym;
740    for (sym = grammar; sym; sym = sym->next)
741      code_props_translate_code (&sym->action_props);
742  }
743
744  /* Convert the grammar into the format described in gram.h.  */
745  packgram ();
746
747  /* The grammar as a symbol_list is no longer needed. */
748  symbol_list_free (grammar);
749}
750