tests: skip C++ tests that are too demanding for some compilers
[bison.git] / src / nullable.c
CommitLineData
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 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++)
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 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 {
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
138void
bb0027a9 139nullable_free (void)
122c0aac 140{
afbb696d 141 free (nullable);
122c0aac 142}