X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/9bfe901c33190b9726bddabf8f192ad0c3a25500..1c4ad777cb220ea669dc934c9b600a25a824a658:/src/derives.c diff --git a/src/derives.c b/src/derives.c index 7b862d82..2d60fd85 100644 --- a/src/derives.c +++ b/src/derives.c @@ -1,110 +1,119 @@ /* Match rules with nonterminals for bison, - Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. + + Copyright (C) 1984, 1989, 2000-2003, 2005, 2009-2010 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 + This program 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. + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - Bison is distributed in the hope that it will be useful, + This program 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. */ - - -/* 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. - */ + along with this program. If not, see . */ +#include #include "system.h" + #include "getargs.h" -#include "types.h" -#include "reader.h" -#include "gram.h" + #include "derives.h" +#include "gram.h" +#include "reader.h" +#include "symtab.h" -short **derives; +/* Linked list of rule numbers. */ +typedef struct rule_list +{ + struct rule_list *next; + rule *value; +} rule_list; +rule ***derives; static void print_derives (void) { int i; - short *sp; - fputs ("\n\n\nDERIVES\n\n", stderr); + fputs ("DERIVES\n", stderr); for (i = ntokens; i < nsyms; i++) { - fprintf (stderr, "%s derives", tags[i]); - for (sp = derives[i]; *sp > 0; sp++) - fprintf (stderr, " %d", *sp); - putc ('\n', stderr); + rule **rp; + fprintf (stderr, "\t%s derives\n", symbols[i]->tag); + for (rp = derives[i - ntokens]; *rp; ++rp) + { + fprintf (stderr, "\t\t%3d ", (*rp)->user_number); + rule_rhs_print (*rp, stderr); + } } - putc ('\n', stderr); + fputs ("\n\n", stderr); } void -set_derives (void) +derives_compute (void) { - int i; - int lhs; - shorts *p; - short *q; - shorts **dset; - shorts *delts; + symbol_number i; + rule_number r; + rule **q; + + /* DSET[NTERM - NTOKENS] -- A linked list of the numbers of the rules + whose LHS is NTERM. */ + rule_list **dset = xcalloc (nvars, sizeof *dset); - dset = XCALLOC (shorts *, nvars) - ntokens; - delts = XCALLOC (shorts, nrules + 1); + /* DELTS[RULE] -- There are NRULES rule number to attach to nterms. + Instead of performing NRULES allocations for each, have an array + indexed by rule numbers. */ + rule_list *delts = xnmalloc (nrules, sizeof *delts); - p = delts; - for (i = nrules; i > 0; i--) + for (r = nrules - 1; r >= 0; --r) { - lhs = rule_table[i].lhs; - if (lhs >= 0) - { - p->next = dset[lhs]; - p->value = i; - dset[lhs] = p; - p++; - } + symbol_number lhs = rules[r].lhs->number; + rule_list *p = &delts[r]; + /* A new LHS is found. */ + p->next = dset[lhs - ntokens]; + p->value = &rules[r]; + dset[lhs - ntokens] = p; } - derives = XCALLOC (short *, nvars) - ntokens; - q = XCALLOC (short, nvars + nrules); + /* DSET contains what we need under the form of a linked list. Make + it a single array. */ + + derives = xnmalloc (nvars, sizeof *derives); + q = xnmalloc (nvars + nrules, sizeof *q); for (i = ntokens; i < nsyms; i++) { - derives[i] = q; - p = dset[i]; + rule_list *p = dset[i - ntokens]; + derives[i - ntokens] = q; while (p) { *q++ = p->value; p = p->next; } - *q++ = -1; + *q++ = NULL; } - if (trace_flag) + if (trace_flag & trace_sets) print_derives (); - XFREE (dset + ntokens); - XFREE (delts); + free (dset); + free (delts); } + void -free_derives (void) +derives_free (void) { - XFREE (derives[ntokens]); - XFREE (derives + ntokens); + free (derives[0]); + free (derives); }