1 /* Calculate which nonterminals can expand into the null string for Bison. 2 3 Copyright (C) 1984, 1989, 2000-2006, 2009-2012 Free Software 4 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 } 143
