]> git.saurik.com Git - bison.git/blame - src/nullable.c
tests: syntax-check
[bison.git] / src / nullable.c
CommitLineData
09939714
PE
1/* Calculate which nonterminals can expand into the null string for Bison.
2
c932d613 3 Copyright (C) 1984, 1989, 2000-2006, 2009-2012 Free Software
ea0a7676 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 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
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 {
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. */
a737b216 84 item_number *rp = NULL;
d0829076 85 bool any_tokens = false;
a737b216
PE
86 for (rp = rules_ruleno->rhs; *rp >= 0; ++rp)
87 if (ISTOKEN (*rp))
d0829076 88 any_tokens = true;
9c2c67e6
AD
89
90 /* This rule has only nonterminals: schedule it for the second
91 pass. */
92 if (!any_tokens)
a737b216 93 for (rp = rules_ruleno->rhs; *rp >= 0; ++rp)
9c2c67e6
AD
94 {
95 rcount[ruleno]++;
a737b216 96 p->next = rsets[*rp - ntokens];
a0b76449 97 p->value = rules_ruleno;
a737b216 98 rsets[*rp - ntokens] = p;
9c2c67e6
AD
99 p++;
100 }
101 }
102 else
81b51460 103 {
9c2c67e6 104 /* This rule has an empty RHS. */
4f82b42a
PE
105 aver (item_number_as_rule_number (rules_ruleno->rhs[0])
106 == ruleno);
09939714
PE
107 if (rules_ruleno->useful
108 && ! nullable[rules_ruleno->lhs->number - ntokens])
9c2c67e6 109 {
d0829076 110 nullable[rules_ruleno->lhs->number - ntokens] = true;
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 {
d0829076 123 nullable[r->lhs->number - ntokens] = true;
a0b76449 124 *s2++ = r->lhs->number;
122c0aac 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
138void
bb0027a9 139nullable_free (void)
122c0aac 140{
afbb696d 141 free (nullable);
122c0aac 142}