1 | /* Calculate which nonterminals can expand into the null string for Bison. |
2 | |
3 | Copyright (C) 1984, 1989, 2000-2006, 2009-2015, 2018-2019 Free |
4 | 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 | |
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 |
24 | do so. */ |
25 | |
26 | #include <config.h> |
27 | #include "system.h" |
28 | |
29 | #include "getargs.h" |
30 | #include "gram.h" |
31 | #include "nullable.h" |
32 | #include "reduce.h" |
33 | #include "symtab.h" |
34 | |
35 | /* Linked list of rules. */ |
36 | typedef struct rule_list |
37 | { |
38 | struct rule_list *next; |
39 | rule *value; |
40 | } rule_list; |
41 | |
42 | bool *nullable = NULL; |
43 | |
44 | static void |
45 | nullable_print (FILE *out) |
46 | { |
47 | int i; |
48 | fputs ("NULLABLE\n" , out); |
49 | for (i = ntokens; i < nsyms; i++) |
50 | fprintf (out, " %s: %s\n" , symbols[i]->tag, |
51 | nullable[i - ntokens] ? "yes" : "no" ); |
52 | fputs ("\n\n" , out); |
53 | } |
54 | |
55 | void |
56 | nullable_compute (void) |
57 | { |
58 | rule_number ruleno; |
59 | symbol_number *s1; |
60 | symbol_number *s2; |
61 | rule_list *p; |
62 | |
63 | symbol_number *squeue = xnmalloc (nvars, sizeof *squeue); |
64 | size_t *rcount = xcalloc (nrules, sizeof *rcount); |
65 | /* RITEM contains all the rules, including useless productions. |
66 | Hence we must allocate room for useless nonterminals too. */ |
67 | rule_list **rsets = xcalloc (nvars, sizeof *rsets); |
68 | /* This is said to be more elements than we actually use. |
69 | Supposedly NRITEMS - NRULES is enough. But why take the risk? */ |
70 | rule_list *relts = xnmalloc (nritems + nvars + 1, sizeof *relts); |
71 | |
72 | nullable = xcalloc (nvars, sizeof *nullable); |
73 | |
74 | s1 = s2 = squeue; |
75 | p = relts; |
76 | |
77 | for (ruleno = 0; ruleno < nrules; ++ruleno) |
78 | if (rules[ruleno].useful) |
79 | { |
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 | } |
114 | } |
115 | |
116 | while (s1 < s2) |
117 | for (p = rsets[*s1++ - ntokens]; p; p = p->next) |
118 | { |
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 | } |
126 | } |
127 | |
128 | free (squeue); |
129 | free (rcount); |
130 | free (rsets); |
131 | free (relts); |
132 | |
133 | if (trace_flag & trace_sets) |
134 | nullable_print (stderr); |
135 | } |
136 | |
137 | |
138 | void |
139 | nullable_free (void) |
140 | { |
141 | free (nullable); |
142 | } |
143 | |