Do not let the scan-skel token buffer grow unboundedly in the usual case.
[bison.git] / src / nullable.c
CommitLineData
09939714
PE
1/* Calculate which nonterminals can expand into the null string for Bison.
2
e68e0410 3 Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software Foundation, Inc.
122c0aac 4
3519ec76 5 This file is part of Bison, the GNU Compiler Compiler.
122c0aac 6
3519ec76
AD
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.
122c0aac 11
3519ec76
AD
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.
122c0aac 16
3519ec76
AD
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. */
122c0aac
RS
21
22
3519ec76
AD
23/* Set up NULLABLE, a vector saying which nonterminals can expand into
24 the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can
ceed8467 25 do so. */
122c0aac 26
122c0aac 27#include "system.h"
a0b76449 28
9bfe901c 29#include "getargs.h"
122c0aac 30#include "gram.h"
3519ec76 31#include "nullable.h"
a0b76449
PE
32#include "reduce.h"
33#include "symtab.h"
122c0aac 34
bb0027a9 35/* Linked list of rules. */
a0b76449 36typedef struct rule_list
e68e0410 37{
a0b76449
PE
38 struct rule_list *next;
39 rule *value;
40} rule_list;
e68e0410 41
bb0027a9 42bool *nullable = NULL;
122c0aac 43
6bb1878b
AD
44static void
45nullable_print (FILE *out)
46{
47 int i;
48 fputs ("NULLABLE\n", out);
49 for (i = ntokens; i < nsyms; i++)
09939714
PE
50 fprintf (out, "\t%s: %s\n", symbols[i]->tag,
51 nullable[i - ntokens] ? "yes" : "no");
6bb1878b
AD
52 fputs ("\n\n", out);
53}
54
122c0aac 55void
bb0027a9 56nullable_compute (void)
122c0aac 57{
a0b76449
PE
58 rule_number ruleno;
59 symbol_number *s1;
60 symbol_number *s2;
61 rule_list *p;
122c0aac 62
09939714
PE
63 symbol_number *squeue = CALLOC (squeue, nvars);
64 short *rcount = CALLOC (rcount, nrules);
ed8e1f68
AD
65 /* RITEM contains all the rules, including useless productions.
66 Hence we must allocate room for useless nonterminals too. */
09939714 67 rule_list **rsets = CALLOC (rsets, nvars);
ed8e1f68 68 /* This is said to be more elements than we actually use.
9e7f6bbd 69 Supposedly NRITEMS - NRULES is enough. But why take the risk? */
09939714 70 rule_list *relts = CALLOC (relts, nritems + nvars + 1);
122c0aac 71
09939714 72 CALLOC (nullable, nvars);
122c0aac 73
122c0aac 74 s1 = s2 = squeue;
122c0aac
RS
75 p = relts;
76
4b3d3a8e 77 for (ruleno = 0; ruleno < nrules; ++ruleno)
1a2b5d37 78 if (rules[ruleno].useful)
ed8e1f68 79 {
a0b76449
PE
80 rule *rules_ruleno = &rules[ruleno];
81 if (rules_ruleno->rhs[0] >= 0)
9c2c67e6
AD
82 {
83 /* This rule has a non empty RHS. */
a0b76449 84 item_number *r = NULL;
9c2c67e6 85 int any_tokens = 0;
a0b76449 86 for (r = rules_ruleno->rhs; *r >= 0; ++r)
9c2c67e6
AD
87 if (ISTOKEN (*r))
88 any_tokens = 1;
89
90 /* This rule has only nonterminals: schedule it for the second
91 pass. */
92 if (!any_tokens)
a0b76449 93 for (r = rules_ruleno->rhs; *r >= 0; ++r)
9c2c67e6
AD
94 {
95 rcount[ruleno]++;
09939714 96 p->next = rsets[*r - ntokens];
a0b76449 97 p->value = rules_ruleno;
09939714 98 rsets[*r - ntokens] = p;
9c2c67e6
AD
99 p++;
100 }
101 }
102 else
81b51460 103 {
9c2c67e6 104 /* This rule has an empty RHS. */
a0b76449 105 if (item_number_as_rule_number (rules_ruleno->rhs[0]) != ruleno)
b475e0cc 106 abort ();
09939714
PE
107 if (rules_ruleno->useful
108 && ! nullable[rules_ruleno->lhs->number - ntokens])
9c2c67e6 109 {
09939714 110 nullable[rules_ruleno->lhs->number - ntokens] = 1;
a0b76449 111 *s2++ = rules_ruleno->lhs->number;
9c2c67e6 112 }
81b51460 113 }
ed8e1f68 114 }
122c0aac
RS
115
116 while (s1 < s2)
09939714 117 for (p = rsets[*s1++ - ntokens]; p; p = p->next)
e3e4e814 118 {
a0b76449
PE
119 rule *r = p->value;
120 if (--rcount[r->number] == 0)
09939714 121 if (r->useful && ! nullable[r->lhs->number - ntokens])
122c0aac 122 {
09939714 123 nullable[r->lhs->number - ntokens] = 1;
a0b76449 124 *s2++ = r->lhs->number;
122c0aac 125 }
e3e4e814 126 }
122c0aac 127
d7913476
AD
128 XFREE (squeue);
129 XFREE (rcount);
09939714 130 XFREE (rsets);
d7913476 131 XFREE (relts);
6bb1878b 132
273a74fa 133 if (trace_flag & trace_sets)
6bb1878b 134 nullable_print (stderr);
122c0aac
RS
135}
136
137
138void
bb0027a9 139nullable_free (void)
122c0aac 140{
09939714 141 XFREE (nullable);
122c0aac 142}