Commit | Line | Data |
---|---|---|
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 | 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++) | |
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 | 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 | |
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 | ||
138 | void | |
bb0027a9 | 139 | nullable_free (void) |
122c0aac | 140 | { |
09939714 | 141 | XFREE (nullable); |
122c0aac | 142 | } |