Commit | Line | Data |
---|---|---|
09939714 PE |
1 | /* Calculate which nonterminals can expand into the null string for Bison. |
2 | ||
7d6bad19 | 3 | Copyright (C) 1984, 1989, 2000-2006, 2009-2013 Free Software |
575619af | 4 | Foundation, Inc. |
122c0aac | 5 | |
3519ec76 | 6 | This file is part of Bison, the GNU Compiler Compiler. |
122c0aac | 7 | |
f16b0819 | 8 | This program is free software: you can redistribute it and/or modify |
3519ec76 | 9 | it under the terms of the GNU General Public License as published by |
f16b0819 PE |
10 | the Free Software Foundation, either version 3 of the License, or |
11 | (at your option) any later version. | |
122c0aac | 12 | |
f16b0819 | 13 | This program is distributed in the hope that it will be useful, |
3519ec76 AD |
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. | |
122c0aac | 17 | |
3519ec76 | 18 | You should have received a copy of the GNU General Public License |
f16b0819 | 19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
122c0aac RS |
20 | |
21 | ||
3519ec76 AD |
22 | /* Set up NULLABLE, a vector saying which nonterminals can expand into |
23 | the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can | |
ceed8467 | 24 | do so. */ |
122c0aac | 25 | |
2cec9080 | 26 | #include <config.h> |
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 | 36 | typedef struct rule_list |
e68e0410 | 37 | { |
a0b76449 PE |
38 | struct rule_list *next; |
39 | rule *value; | |
40 | } rule_list; | |
e68e0410 | 41 | |
bb0027a9 | 42 | bool *nullable = NULL; |
122c0aac | 43 | |
6bb1878b AD |
44 | static void |
45 | nullable_print (FILE *out) | |
46 | { | |
47 | int i; | |
48 | fputs ("NULLABLE\n", out); | |
49 | for (i = ntokens; i < nsyms; i++) | |
5cd907c4 | 50 | fprintf (out, " %s: %s\n", symbols[i]->tag, |
e9690142 | 51 | nullable[i - ntokens] ? "yes" : "no"); |
6bb1878b AD |
52 | fputs ("\n\n", out); |
53 | } | |
54 | ||
122c0aac | 55 | void |
bb0027a9 | 56 | nullable_compute (void) |
122c0aac | 57 | { |
a0b76449 PE |
58 | rule_number ruleno; |
59 | symbol_number *s1; | |
60 | symbol_number *s2; | |
61 | rule_list *p; | |
122c0aac | 62 | |
da2a7671 | 63 | symbol_number *squeue = xnmalloc (nvars, sizeof *squeue); |
f6fbd3da | 64 | size_t *rcount = xcalloc (nrules, sizeof *rcount); |
ed8e1f68 AD |
65 | /* RITEM contains all the rules, including useless productions. |
66 | Hence we must allocate room for useless nonterminals too. */ | |
da2a7671 | 67 | rule_list **rsets = xcalloc (nvars, sizeof *rsets); |
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? */ |
da2a7671 | 70 | rule_list *relts = xnmalloc (nritems + nvars + 1, sizeof *relts); |
122c0aac | 71 | |
da2a7671 | 72 | nullable = xcalloc (nvars, sizeof *nullable); |
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 | { |
e9690142 JD |
80 | rule *rules_ruleno = &rules[ruleno]; |
81 | if (rules_ruleno->rhs[0] >= 0) | |
82 | { | |
83 | /* This rule has a non empty RHS. */ | |
84 | item_number *rp = NULL; | |
85 | bool any_tokens = false; | |
86 | for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) | |
87 | if (ISTOKEN (*rp)) | |
88 | any_tokens = true; | |
89 | ||
90 | /* This rule has only nonterminals: schedule it for the second | |
91 | pass. */ | |
92 | if (!any_tokens) | |
93 | for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) | |
94 | { | |
95 | rcount[ruleno]++; | |
96 | p->next = rsets[*rp - ntokens]; | |
97 | p->value = rules_ruleno; | |
98 | rsets[*rp - ntokens] = p; | |
99 | p++; | |
100 | } | |
101 | } | |
102 | else | |
103 | { | |
104 | /* This rule has an empty RHS. */ | |
105 | aver (item_number_as_rule_number (rules_ruleno->rhs[0]) | |
106 | == ruleno); | |
107 | if (rules_ruleno->useful | |
108 | && ! nullable[rules_ruleno->lhs->number - ntokens]) | |
109 | { | |
110 | nullable[rules_ruleno->lhs->number - ntokens] = true; | |
111 | *s2++ = rules_ruleno->lhs->number; | |
112 | } | |
113 | } | |
ed8e1f68 | 114 | } |
122c0aac RS |
115 | |
116 | while (s1 < s2) | |
09939714 | 117 | for (p = rsets[*s1++ - ntokens]; p; p = p->next) |
e3e4e814 | 118 | { |
e9690142 JD |
119 | rule *r = p->value; |
120 | if (--rcount[r->number] == 0) | |
121 | if (r->useful && ! nullable[r->lhs->number - ntokens]) | |
122 | { | |
123 | nullable[r->lhs->number - ntokens] = true; | |
124 | *s2++ = r->lhs->number; | |
125 | } | |
e3e4e814 | 126 | } |
122c0aac | 127 | |
afbb696d PE |
128 | free (squeue); |
129 | free (rcount); | |
130 | free (rsets); | |
131 | free (relts); | |
6bb1878b | 132 | |
273a74fa | 133 | if (trace_flag & trace_sets) |
6bb1878b | 134 | nullable_print (stderr); |
122c0aac RS |
135 | } |
136 | ||
137 | ||
138 | void | |
bb0027a9 | 139 | nullable_free (void) |
122c0aac | 140 | { |
afbb696d | 141 | free (nullable); |
122c0aac | 142 | } |