src/derives.c

   1 /* Match rules with nonterminals for bison,
   2
   3    Copyright (C) 1984, 1989, 2000-2003, 2005, 2009-2010 Free Software
   4    Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program 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 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include "getargs.h"
  25
  26 #include "derives.h"
  27 #include "gram.h"
  28 #include "reader.h"
  29 #include "symtab.h"
  30
  31 /* Linked list of rule numbers.  */
  32 typedef struct rule_list
  33 {
  34   struct rule_list *next;
  35   rule *value;
  36 } rule_list;
  37
  38 rule ***derives;
  39
  40 static void
  41 print_derives (void)
  42 {
  43   int i;
  44
  45   fputs ("DERIVES\n", stderr);
  46
  47   for (i = ntokens; i < nsyms; i++)
  48     {
  49       rule **rp;
  50       fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
  51       for (rp = derives[i - ntokens]; *rp; ++rp)
  52         {
  53           fprintf (stderr, "\t\t%3d ", (*rp)->user_number);
  54           rule_rhs_print (*rp, stderr);
  55         }
  56     }
  57
  58   fputs ("\n\n", stderr);
  59 }
  60
  61
  62 void
  63 derives_compute (void)
  64 {
  65   symbol_number i;
  66   rule_number r;
  67   rule **q;
  68
  69   /* DSET[NTERM - NTOKENS] -- A linked list of the numbers of the rules
  70      whose LHS is NTERM.  */
  71   rule_list **dset = xcalloc (nvars, sizeof *dset);
  72
  73   /* DELTS[RULE] -- There are NRULES rule number to attach to nterms.
  74      Instead of performing NRULES allocations for each, have an array
  75      indexed by rule numbers.  */
  76   rule_list *delts = xnmalloc (nrules, sizeof *delts);
  77
  78   for (r = nrules - 1; r >= 0; --r)
  79     {
  80       symbol_number lhs = rules[r].lhs->number;
  81       rule_list *p = &delts[r];
  82       /* A new LHS is found.  */
  83       p->next = dset[lhs - ntokens];
  84       p->value = &rules[r];
  85       dset[lhs - ntokens] = p;
  86     }
  87
  88   /* DSET contains what we need under the form of a linked list.  Make
  89      it a single array.  */
  90
  91   derives = xnmalloc (nvars, sizeof *derives);
  92   q = xnmalloc (nvars + nrules, sizeof *q);
  93
  94   for (i = ntokens; i < nsyms; i++)
  95     {
  96       rule_list *p = dset[i - ntokens];
  97       derives[i - ntokens] = q;
  98       while (p)
  99         {
 100           *q++ = p->value;
 101           p = p->next;
 102         }
 103       *q++ = NULL;
 104     }
 105
 106   if (trace_flag & trace_sets)
 107     print_derives ();
 108
 109   free (dset);
 110   free (delts);
 111 }
 112
 113
 114 void
 115 derives_free (void)
 116 {
 117   free (derives[0]);
 118   free (derives);
 119 }