From: Richard M. Stallman Date: Wed, 18 Dec 1991 04:06:36 +0000 (+0000) Subject: entered into RCS X-Git-Tag: GNU_ORIG~125 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/122c0aacef4088dccca6fce5559fb3617aa25e81 entered into RCS --- diff --git a/src/derives.c b/src/derives.c new file mode 100644 index 00000000..f7dfaf73 --- /dev/null +++ b/src/derives.c @@ -0,0 +1,118 @@ +/* Match rules with nonterminals for bison, + Copyright (C) 1984, 1989 Free Software Foundation, Inc. + +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 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. */ + + +/* set_derives finds, for each variable (nonterminal), which rules can derive it. + It sets up the value of derives so that + derives[i - ntokens] points to a vector of rule numbers, + terminated with -1. */ + +#include +#include "system.h" +#include "new.h" +#include "types.h" +#include "gram.h" + + +short **derives; + +void +set_derives() +{ + register int i; + register int lhs; + register shorts *p; + register short *q; + register shorts **dset; + register shorts *delts; + + dset = NEW2(nvars, shorts *) - ntokens; + delts = NEW2(nrules + 1, shorts); + + p = delts; + for (i = nrules; i > 0; i--) + { + lhs = rlhs[i]; + if (lhs >= 0) + { + p->next = dset[lhs]; + p->value = i; + dset[lhs] = p; + p++; + } + } + + derives = NEW2(nvars, short *) - ntokens; + q = NEW2(nvars + nrules, short); + + for (i = ntokens; i < nsyms; i++) + { + derives[i] = q; + p = dset[i]; + while (p) + { + *q++ = p->value; + p = p->next; + } + *q++ = -1; + } + +#ifdef DEBUG + print_derives(); +#endif + + FREE(dset + ntokens); + FREE(delts); +} + +void +free_derives() +{ + FREE(derives[ntokens]); + FREE(derives + ntokens); +} + + + +#ifdef DEBUG + +print_derives() +{ + register int i; + register short *sp; + + extern char **tags; + + printf("\n\n\nDERIVES\n\n"); + + for (i = ntokens; i < nsyms; i++) + { + printf("%s derives", tags[i]); + for (sp = derives[i]; *sp > 0; sp++) + { + printf(" %d", *sp); + } + putchar('\n'); + } + + putchar('\n'); +} + +#endif + diff --git a/src/nullable.c b/src/nullable.c new file mode 100644 index 00000000..b85dec61 --- /dev/null +++ b/src/nullable.c @@ -0,0 +1,136 @@ +/* Part of the bison parser generator, + Copyright (C) 1984, 1989 Free Software Foundation, Inc. + +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 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. */ + + +/* 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 "types.h" +#include "gram.h" +#include "new.h" + + +char *nullable; + + +void +set_nullable() +{ + 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; + /* 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); + 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)) + 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++; + } + } + } + } + + while (s1 < s2) + { + p = rsets[*s1++]; + while (p) + { + ruleno = p->value; + p = p->next; + if (--rcount[ruleno] == 0) + { + symbol = rlhs[ruleno]; + if (symbol >= 0 && !nullable[symbol]) + { + nullable[symbol] = 1; + *s2++ = symbol; + } + } + } + } + + FREE(squeue); + FREE(rcount); + FREE(rsets + ntokens); + FREE(relts); +} + + +void +free_nullable() +{ + FREE(nullable + ntokens); +}