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