1 /* Calculate which nonterminals can expand into the null string for Bison.
3 Copyright (C) 1984, 1989, 2000-2006, 2009-2012 Free Software
6 This file is part of Bison, the GNU Compiler Compiler.
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.
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.
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/>. */
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
35 /* Linked list of rules. */
36 typedef struct rule_list
38 struct rule_list
*next
;
42 bool *nullable
= NULL
;
45 nullable_print (FILE *out
)
48 fputs ("NULLABLE\n", out
);
49 for (i
= ntokens
; i
< nsyms
; i
++)
50 fprintf (out
, "\t%s: %s\n", symbols
[i
]->tag
,
51 nullable
[i
- ntokens
] ? "yes" : "no");
56 nullable_compute (void)
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
);
72 nullable
= xcalloc (nvars
, sizeof *nullable
);
77 for (ruleno
= 0; ruleno
< nrules
; ++ruleno
)
78 if (rules
[ruleno
].useful
)
80 rule
*rules_ruleno
= &rules
[ruleno
];
81 if (rules_ruleno
->rhs
[0] >= 0)
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
)
90 /* This rule has only nonterminals: schedule it for the second
93 for (rp
= rules_ruleno
->rhs
; *rp
>= 0; ++rp
)
96 p
->next
= rsets
[*rp
- ntokens
];
97 p
->value
= rules_ruleno
;
98 rsets
[*rp
- ntokens
] = p
;
104 /* This rule has an empty RHS. */
105 aver (item_number_as_rule_number (rules_ruleno
->rhs
[0])
107 if (rules_ruleno
->useful
108 && ! nullable
[rules_ruleno
->lhs
->number
- ntokens
])
110 nullable
[rules_ruleno
->lhs
->number
- ntokens
] = true;
111 *s2
++ = rules_ruleno
->lhs
->number
;
117 for (p
= rsets
[*s1
++ - ntokens
]; p
; p
= p
->next
)
120 if (--rcount
[r
->number
] == 0)
121 if (r
->useful
&& ! nullable
[r
->lhs
->number
- ntokens
])
123 nullable
[r
->lhs
->number
- ntokens
] = true;
124 *s2
++ = r
->lhs
->number
;
133 if (trace_flag
& trace_sets
)
134 nullable_print (stderr
);