1 /* Calculate which nonterminals can expand into the null string for Bison.
2
3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2006
4 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
9 it 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,
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 Bison; see the file COPYING. If not, write to
20 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
22
23
24 /* Set up NULLABLE, a vector saying which nonterminals can expand into
25 the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can
26 do so. */
27
28 #include <config.h>
29 #include "system.h"
30
31 #include "getargs.h"
32 #include "gram.h"
33 #include "nullable.h"
34 #include "reduce.h"
35 #include "symtab.h"
36
37 /* Linked list of rules. */
38 typedef struct rule_list
39 {
40 struct rule_list *next;
41 rule *value;
42 } rule_list;
43
44 bool *nullable = NULL;
45
46 static void
nullable_print(FILE * out)47 nullable_print (FILE *out)
48 {
49 int i;
50 fputs ("NULLABLE\n", out);
51 for (i = ntokens; i < nsyms; i++)
52 fprintf (out, "\t%s: %s\n", symbols[i]->tag,
53 nullable[i - ntokens] ? "yes" : "no");
54 fputs ("\n\n", out);
55 }
56
57 void
nullable_compute(void)58 nullable_compute (void)
59 {
60 rule_number ruleno;
61 symbol_number *s1;
62 symbol_number *s2;
63 rule_list *p;
64
65 symbol_number *squeue = xnmalloc (nvars, sizeof *squeue);
66 size_t *rcount = xcalloc (nrules, sizeof *rcount);
67 /* RITEM contains all the rules, including useless productions.
68 Hence we must allocate room for useless nonterminals too. */
69 rule_list **rsets = xcalloc (nvars, sizeof *rsets);
70 /* This is said to be more elements than we actually use.
71 Supposedly NRITEMS - NRULES is enough. But why take the risk? */
72 rule_list *relts = xnmalloc (nritems + nvars + 1, sizeof *relts);
73
74 nullable = xcalloc (nvars, sizeof *nullable);
75
76 s1 = s2 = squeue;
77 p = relts;
78
79 for (ruleno = 0; ruleno < nrules; ++ruleno)
80 if (rules[ruleno].useful)
81 {
82 rule *rules_ruleno = &rules[ruleno];
83 if (rules_ruleno->rhs[0] >= 0)
84 {
85 /* This rule has a non empty RHS. */
86 item_number *rp = NULL;
87 bool any_tokens = false;
88 for (rp = rules_ruleno->rhs; *rp >= 0; ++rp)
89 if (ISTOKEN (*rp))
90 any_tokens = true;
91
92 /* This rule has only nonterminals: schedule it for the second
93 pass. */
94 if (!any_tokens)
95 for (rp = rules_ruleno->rhs; *rp >= 0; ++rp)
96 {
97 rcount[ruleno]++;
98 p->next = rsets[*rp - ntokens];
99 p->value = rules_ruleno;
100 rsets[*rp - ntokens] = p;
101 p++;
102 }
103 }
104 else
105 {
106 /* This rule has an empty RHS. */
107 assert (item_number_as_rule_number (rules_ruleno->rhs[0])
108 == ruleno);
109 if (rules_ruleno->useful
110 && ! nullable[rules_ruleno->lhs->number - ntokens])
111 {
112 nullable[rules_ruleno->lhs->number - ntokens] = true;
113 *s2++ = rules_ruleno->lhs->number;
114 }
115 }
116 }
117
118 while (s1 < s2)
119 for (p = rsets[*s1++ - ntokens]; p; p = p->next)
120 {
121 rule *r = p->value;
122 if (--rcount[r->number] == 0)
123 if (r->useful && ! nullable[r->lhs->number - ntokens])
124 {
125 nullable[r->lhs->number - ntokens] = true;
126 *s2++ = r->lhs->number;
127 }
128 }
129
130 free (squeue);
131 free (rcount);
132 free (rsets);
133 free (relts);
134
135 if (trace_flag & trace_sets)
136 nullable_print (stderr);
137 }
138
139
140 void
nullable_free(void)141 nullable_free (void)
142 {
143 free (nullable);
144 }
145