src/derives.c

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