X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d2729d44ab05f89e96d199ad6b10e127c1cb0a38..e9f87b5b7df2e328d2e4196d276c0d96594c906b:/src/nullable.c diff --git a/src/nullable.c b/src/nullable.c index f931f4a9..f8c9b32e 100644 --- a/src/nullable.c +++ b/src/nullable.c @@ -1,138 +1,133 @@ /* 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, 675 Mass Ave, Cambridge, MA 02139, 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 "symtab.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", symbols[i]->tag, 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 *squeue; - short *rcount; - shorts **rsets; - shorts *relts; - char any_tokens; - short *r1; - -#ifdef TRACE - fprintf(stderr, _("Entering set_nullable")); -#endif - - nullable = NEW2(nvars, char) - ntokens; - - squeue = NEW2(nvars, short); - s1 = s2 = squeue; - - rcount = NEW2(nrules + 1, short); - rsets = NEW2(nvars, shorts *) - ntokens; + int ruleno; + short *s1; + short *s2; + shorts *p; + + short *squeue = XCALLOC (short, nvars); + short *rcount = XCALLOC (short, nrules + 1); + /* RITEM contains all the rules, including useless productions. + Hence we must allocate room for useless nonterminals too. */ + shorts **rsets = XCALLOC (shorts *, nvars) - 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); + Supposedly NRITEMS - NRULES is enough. But why take the risk? */ + shorts *relts = XCALLOC (shorts, nritems + nvars + 1); + + if (trace_flag) + fprintf (stderr, "Entering set_nullable\n"); + + nullable = XCALLOC (char, nvars) - ntokens; + + s1 = s2 = squeue; p = relts; - r = ritem; - while (*r) - { - if (*r < 0) - { - 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)) + for (ruleno = 1; ruleno < nrules + 1; ++ruleno) + if (rules[ruleno].useful) + { + if (ritem[rules[ruleno].rhs] >= 0) + { + /* This rule has a non empty RHS. */ + short *r; + int any_tokens = 0; + for (r = &ritem[rules[ruleno].rhs]; *r >= 0; ++r) + if (ISTOKEN (*r)) any_tokens = 1; - } - if (!any_tokens) - { - ruleno = -symbol; - r = r1; - for (symbol = *r++; symbol > 0; symbol = *r++) + /* This rule has only nonterminals: schedule it for the second + pass. */ + if (!any_tokens) + for (r = &ritem[rules[ruleno].rhs]; *r >= 0; ++r) { rcount[ruleno]++; - p->next = rsets[symbol]; + p->next = rsets[*r]; p->value = ruleno; - rsets[symbol] = p; + rsets[*r] = p; p++; } - } - } - } + } + else + { + /* This rule has an empty RHS. */ + assert (ritem[rules[ruleno].rhs] == -ruleno); + if (rules[ruleno].useful && !nullable[rules[ruleno].lhs]) + { + nullable[rules[ruleno].lhs] = 1; + *s2++ = rules[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) + { + ruleno = p->value; + if (--rcount[ruleno] == 0) + if (rules[ruleno].useful && !nullable[rules[ruleno].lhs]) { - symbol = rlhs[ruleno]; - if (symbol >= 0 && !nullable[symbol]) - { - nullable[symbol] = 1; - *s2++ = symbol; - } + nullable[rules[ruleno].lhs] = 1; + *s2++ = rules[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); }