1 /* Calculate which nonterminals can expand into the null string for Bison.
3 Copyright (C) 1984, 1989, 2000-2006, 2009-2015, 2018-2020 Free
4 Software Foundation, Inc.
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
)
47 fputs ("NULLABLE\n", out
);
48 for (int i
= ntokens
; i
< nsyms
; i
++)
49 fprintf (out
, " %s: %s\n", symbols
[i
]->tag
,
50 nullable
[i
- ntokens
] ? "yes" : "no");
55 nullable_compute (void)
57 nullable
= xcalloc (nnterms
, sizeof *nullable
);
59 size_t *rcount
= xcalloc (nrules
, sizeof *rcount
);
60 /* RITEM contains all the rules, including useless productions.
61 Hence we must allocate room for useless nonterminals too. */
62 rule_list
**rsets
= xcalloc (nnterms
, sizeof *rsets
);
63 /* This is said to be more elements than we actually use.
64 Supposedly NRITEMS - NRULES is enough. But why take the risk? */
65 rule_list
*relts
= xnmalloc (nritems
+ nnterms
+ 1, sizeof *relts
);
67 symbol_number
*squeue
= xnmalloc (nnterms
, sizeof *squeue
);
68 symbol_number
*s2
= squeue
;
71 for (rule_number ruleno
= 0; ruleno
< nrules
; ++ruleno
)
72 if (rules
[ruleno
].useful
)
74 const rule
*r
= &rules
[ruleno
];
77 /* This rule has a non empty RHS. */
78 bool any_tokens
= false;
79 for (item_number
*rp
= r
->rhs
; *rp
>= 0; ++rp
)
83 /* This rule has only nonterminals: schedule it for the second
86 for (item_number
*rp
= r
->rhs
; *rp
>= 0; ++rp
)
89 p
->next
= rsets
[*rp
- ntokens
];
91 rsets
[*rp
- ntokens
] = p
;
97 /* This rule has an empty RHS. */
99 && ! nullable
[r
->lhs
->number
- ntokens
])
101 nullable
[r
->lhs
->number
- ntokens
] = true;
102 *s2
++ = r
->lhs
->number
;
108 symbol_number
*s1
= squeue
;
110 for (rule_list
*p
= rsets
[*s1
++ - ntokens
]; p
; p
= p
->next
)
112 const rule
*r
= p
->value
;
113 if (--rcount
[r
->number
] == 0)
114 if (r
->useful
&& ! nullable
[r
->lhs
->number
- ntokens
])
116 nullable
[r
->lhs
->number
- ntokens
] = true;
117 *s2
++ = r
->lhs
->number
;
126 if (trace_flag
& trace_sets
)
127 nullable_print (stderr
);