src/derives.c

   1 /* Match rules with nonterminals for bison,
   2    Copyright 1984, 1989, 2000, 2001, 2002  Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "getargs.h"
  24 #include "symtab.h"
  25 #include "types.h"
  26 #include "reader.h"
  27 #include "gram.h"
  28 #include "derives.h"
  29
  30 /* Linked list of rule numbers.  */
  31 typedef struct rule_list_s
  32 {
  33   struct rule_list_s *next;
  34   rule_number_t value;
  35 } rule_list_t;
  36
  37 rule_number_t **derives = NULL;
  38
  39 static void
  40 print_derives (void)
  41 {
  42   int i;
  43
  44   fputs ("DERIVES\n", stderr);
  45
  46   for (i = ntokens; i < nsyms; i++)
  47     {
  48       rule_number_t *rp;
  49       fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
  50       for (rp = derives[i]; *rp > 0; rp++)
  51         {
  52           fprintf (stderr, "\t\t%3d ", *rp - 1);
  53           rule_rhs_print (&rules[*rp], stderr);
  54         }
  55     }
  56
  57   fputs ("\n\n", stderr);
  58 }
  59
  60
  61 void
  62 set_derives (void)
  63 {
  64   symbol_number_t i;
  65   rule_number_t r;
  66   rule_number_t *q;
  67
  68   /* DSET[NTERM] -- A linked list of the numbers of the rules whose
  69      LHS is NTERM.  */
  70   rule_list_t **dset = XCALLOC (rule_list_t *, nvars) - ntokens;
  71
  72   /* DELTS[RULE] -- There are NRULES rule number to attach to nterms.
  73      Instead of performing NRULES allocations for each, have an array
  74      indexed by rule numbers.  */
  75   rule_list_t *delts = XCALLOC (rule_list_t, nrules + 1);
  76
  77   for (r = nrules; r > 0; r--)
  78     {
  79       symbol_number_t lhs = rules[r].lhs->number;
  80       rule_list_t *p = &delts[r];
  81       /* A new LHS is found.  */
  82       p->next = dset[lhs];
  83       p->value = r;
  84       dset[lhs] = p;
  85     }
  86
  87   /* DSET contains what we need under the form of a linked list.  Make
  88      it a single array.  */
  89
  90   derives = XCALLOC (rule_number_t *, nvars) - ntokens;
  91   q = XCALLOC (rule_number_t, nvars + int_of_rule_number (nrules));
  92
  93   for (i = ntokens; i < nsyms; i++)
  94     {
  95       rule_list_t *p = dset[i];
  96       derives[i] = q;
  97       while (p)
  98         {
  99           *q++ = p->value;
 100           p = p->next;
 101         }
 102       *q++ = -1;
 103     }
 104
 105   if (trace_flag)
 106     print_derives ();
 107
 108   free (dset + ntokens);
 109   free (delts);
 110 }
 111
 112
 113 void
 114 free_derives (void)
 115 {
 116   XFREE (derives[ntokens]);
 117   XFREE (derives + ntokens);
 118 }