OLD | NEW |
(Empty) | |
| 1 /* Calculate which nonterminals can expand into the null string for Bison. |
| 2 |
| 3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2006 |
| 4 Free Software Foundation, Inc. |
| 5 |
| 6 This file is part of Bison, the GNU Compiler Compiler. |
| 7 |
| 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. |
| 12 |
| 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. |
| 17 |
| 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/>. */ |
| 20 |
| 21 |
| 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 |
| 24 do so. */ |
| 25 |
| 26 #include <config.h> |
| 27 #include "system.h" |
| 28 |
| 29 #include "getargs.h" |
| 30 #include "gram.h" |
| 31 #include "nullable.h" |
| 32 #include "reduce.h" |
| 33 #include "symtab.h" |
| 34 |
| 35 /* Linked list of rules. */ |
| 36 typedef struct rule_list |
| 37 { |
| 38 struct rule_list *next; |
| 39 rule *value; |
| 40 } rule_list; |
| 41 |
| 42 bool *nullable = NULL; |
| 43 |
| 44 static void |
| 45 nullable_print (FILE *out) |
| 46 { |
| 47 int i; |
| 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"); |
| 52 fputs ("\n\n", out); |
| 53 } |
| 54 |
| 55 void |
| 56 nullable_compute (void) |
| 57 { |
| 58 rule_number ruleno; |
| 59 symbol_number *s1; |
| 60 symbol_number *s2; |
| 61 rule_list *p; |
| 62 |
| 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); |
| 71 |
| 72 nullable = xcalloc (nvars, sizeof *nullable); |
| 73 |
| 74 s1 = s2 = squeue; |
| 75 p = relts; |
| 76 |
| 77 for (ruleno = 0; ruleno < nrules; ++ruleno) |
| 78 if (rules[ruleno].useful) |
| 79 { |
| 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 } |
| 114 } |
| 115 |
| 116 while (s1 < s2) |
| 117 for (p = rsets[*s1++ - ntokens]; p; p = p->next) |
| 118 { |
| 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 } |
| 126 } |
| 127 |
| 128 free (squeue); |
| 129 free (rcount); |
| 130 free (rsets); |
| 131 free (relts); |
| 132 |
| 133 if (trace_flag & trace_sets) |
| 134 nullable_print (stderr); |
| 135 } |
| 136 |
| 137 |
| 138 void |
| 139 nullable_free (void) |
| 140 { |
| 141 free (nullable); |
| 142 } |
OLD | NEW |