X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/c49a8e71cec845d32366432b824a9317e4a80160..80e25d4d46e2f0745eea5658fa675a05a77dc68a:/src/nullable.c diff --git a/src/nullable.c b/src/nullable.c index de4551a8..8e8809e2 100644 --- a/src/nullable.c +++ b/src/nullable.c @@ -1,139 +1,135 @@ /* Part of the bison parser generator, - Copyright (C) 1984, 1989 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. -This file is part of Bison, the GNU Compiler Compiler. + This file is part of Bison, the GNU Compiler Compiler. -Bison is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. + Bison is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. -Bison is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + Bison is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with Bison; see the file COPYING. If not, write to -the Free Software Foundation, Inc., 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ + You should have received a copy of the GNU General Public License + along with Bison; see the file COPYING. If not, write to + the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. */ -/* set up nullable, a vector saying which nonterminals can expand into the null string. - nullable[i - ntokens] is nonzero if symbol i can do so. */ +/* Set up NULLABLE, a vector saying which nonterminals can expand into + the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can + do so. */ -#include #include "system.h" +#include "getargs.h" +#include "reader.h" #include "types.h" #include "gram.h" -#include "alloc.h" +#include "reduce.h" +#include "nullable.h" +char *nullable = NULL; -char *nullable; - -void free_nullable PARAMS((void)); -void set_nullable PARAMS((void)); +static void +nullable_print (FILE *out) +{ + int i; + fputs ("NULLABLE\n", out); + for (i = ntokens; i < nsyms; i++) + fprintf (out, "\t%s: %s\n", tags[i], nullable[i] ? "yes" : "no"); + fputs ("\n\n", out); +} void set_nullable (void) { - register short *r; - register short *s1; - register short *s2; - register int ruleno; - register int symbol; - register shorts *p; + short *r; + short *s1; + short *s2; + shorts *p; short *squeue; short *rcount; shorts **rsets; shorts *relts; - char any_tokens; - short *r1; -#ifdef TRACE - fprintf(stderr, _("Entering set_nullable")); -#endif + if (trace_flag) + fprintf (stderr, "Entering set_nullable\n"); - nullable = NEW2(nvars, char) - ntokens; + nullable = XCALLOC (char, nvars) - ntokens; - squeue = NEW2(nvars, short); + squeue = XCALLOC (short, nvars); s1 = s2 = squeue; - rcount = NEW2(nrules + 1, short); - rsets = NEW2(nvars, shorts *) - ntokens; + rcount = XCALLOC (short, nrules + 1); + + /* RITEM contains all the rules, including useless productions. + Hence we must allocate room for useless nonterminals too. */ + rsets = XCALLOC (shorts *, nvars + nuseless_nonterminals) - ntokens; /* This is said to be more elements than we actually use. Supposedly nitems - nrules is enough. But why take the risk? */ - relts = NEW2(nitems + nvars + 1, shorts); + relts = XCALLOC (shorts, nitems + nvars + nuseless_nonterminals + 1); p = relts; - r = ritem; - while (*r) + for (r = ritem; *r; ++r) { - if (*r < 0) + /* Walk RITEM to find (i), if there are any tokens in the + RHS, and (ii), to find RULENO. */ + int ruleno; + int any_tokens = 0; + short *r1; + for (r1 = r; *r1 > 0; ++r1) + if (ISTOKEN (*r1)) + any_tokens = 1; + ruleno = -*r1; + + /* Examine the RHS of the rule. */ + if (!any_tokens) + for (/* Nothing. */; *r > 0; ++r) + { + rcount[ruleno]++; + p->next = rsets[*r]; + p->value = ruleno; + rsets[*r] = p; + p++; + } + + /* Examine its LHS. */ + if (rule_table[ruleno].useful && !nullable[rule_table[ruleno].lhs]) { - symbol = rlhs[-(*r++)]; - if (symbol >= 0 && !nullable[symbol]) - { - nullable[symbol] = 1; - *s2++ = symbol; - } - } - else - { - r1 = r; - any_tokens = 0; - for (symbol = *r++; symbol > 0; symbol = *r++) - { - if (ISTOKEN(symbol)) - any_tokens = 1; - } - - if (!any_tokens) - { - ruleno = -symbol; - r = r1; - for (symbol = *r++; symbol > 0; symbol = *r++) - { - rcount[ruleno]++; - p->next = rsets[symbol]; - p->value = ruleno; - rsets[symbol] = p; - p++; - } - } - } + nullable[rule_table[ruleno].lhs] = 1; + *s2++ = rule_table[ruleno].lhs; + } } while (s1 < s2) - { - p = rsets[*s1++]; - while (p) - { - ruleno = p->value; - p = p->next; - if (--rcount[ruleno] == 0) + for (p = rsets[*s1++]; p; p = p->next) + { + int ruleno = p->value; + if (--rcount[ruleno] == 0) + if (rule_table[ruleno].useful && !nullable[rule_table[ruleno].lhs]) { - symbol = rlhs[ruleno]; - if (symbol >= 0 && !nullable[symbol]) - { - nullable[symbol] = 1; - *s2++ = symbol; - } + nullable[rule_table[ruleno].lhs] = 1; + *s2++ = rule_table[ruleno].lhs; } - } - } + } + + XFREE (squeue); + XFREE (rcount); + XFREE (rsets + ntokens); + XFREE (relts); - FREE(squeue); - FREE(rcount); - FREE(rsets + ntokens); - FREE(relts); + if (trace_flag) + nullable_print (stderr); } void free_nullable (void) { - FREE(nullable + ntokens); + XFREE (nullable + ntokens); }