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 Bison 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 2, or (at your option) 11 any later version. 12 13 Bison 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 Bison; see the file COPYING. If not, write to 20 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 21 Boston, MA 02110-1301, USA. */ 22 23 24 /* Set up NULLABLE, a vector saying which nonterminals can expand into 25 the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can 26 do so. */ 27 28 #include <config.h> 29 #include "system.h" 30 31 #include "getargs.h" 32 #include "gram.h" 33 #include "nullable.h" 34 #include "reduce.h" 35 #include "symtab.h" 36 37 /* Linked list of rules. */ 38 typedef struct rule_list 39 { 40 struct rule_list *next; 41 rule *value; 42 } rule_list; 43 44 bool *nullable = NULL; 45 46 static void 47 nullable_print (FILE *out) 48 { 49 int i; 50 fputs ("NULLABLE\n", out); 51 for (i = ntokens; i < nsyms; i++) 52 fprintf (out, "\t%s: %s\n", symbols[i]->tag, 53 nullable[i - ntokens] ? "yes" : "no"); 54 fputs ("\n\n", out); 55 } 56 57 void 58 nullable_compute (void) 59 { 60 rule_number ruleno; 61 symbol_number *s1; 62 symbol_number *s2; 63 rule_list *p; 64 65 symbol_number *squeue = xnmalloc (nvars, sizeof *squeue); 66 size_t *rcount = xcalloc (nrules, sizeof *rcount); 67 /* RITEM contains all the rules, including useless productions. 68 Hence we must allocate room for useless nonterminals too. */ 69 rule_list **rsets = xcalloc (nvars, sizeof *rsets); 70 /* This is said to be more elements than we actually use. 71 Supposedly NRITEMS - NRULES is enough. But why take the risk? */ 72 rule_list *relts = xnmalloc (nritems + nvars + 1, sizeof *relts); 73 74 nullable = xcalloc (nvars, sizeof *nullable); 75 76 s1 = s2 = squeue; 77 p = relts; 78 79 for (ruleno = 0; ruleno < nrules; ++ruleno) 80 if (rules[ruleno].useful) 81 { 82 rule *rules_ruleno = &rules[ruleno]; 83 if (rules_ruleno->rhs[0] >= 0) 84 { 85 /* This rule has a non empty RHS. */ 86 item_number *rp = NULL; 87 bool any_tokens = false; 88 for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) 89 if (ISTOKEN (*rp)) 90 any_tokens = true; 91 92 /* This rule has only nonterminals: schedule it for the second 93 pass. */ 94 if (!any_tokens) 95 for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) 96 { 97 rcount[ruleno]++; 98 p->next = rsets[*rp - ntokens]; 99 p->value = rules_ruleno; 100 rsets[*rp - ntokens] = p; 101 p++; 102 } 103 } 104 else 105 { 106 /* This rule has an empty RHS. */ 107 assert (item_number_as_rule_number (rules_ruleno->rhs[0]) 108 == ruleno); 109 if (rules_ruleno->useful 110 && ! nullable[rules_ruleno->lhs->number - ntokens]) 111 { 112 nullable[rules_ruleno->lhs->number - ntokens] = true; 113 *s2++ = rules_ruleno->lhs->number; 114 } 115 } 116 } 117 118 while (s1 < s2) 119 for (p = rsets[*s1++ - ntokens]; p; p = p->next) 120 { 121 rule *r = p->value; 122 if (--rcount[r->number] == 0) 123 if (r->useful && ! nullable[r->lhs->number - ntokens]) 124 { 125 nullable[r->lhs->number - ntokens] = true; 126 *s2++ = r->lhs->number; 127 } 128 } 129 130 free (squeue); 131 free (rcount); 132 free (rsets); 133 free (relts); 134 135 if (trace_flag & trace_sets) 136 nullable_print (stderr); 137 } 138 139 140 void 141 nullable_free (void) 142 { 143 free (nullable); 144 } 145
