src/derives.c

   1 /* Match rules with nonterminals for bison,
   2    Copyright (C) 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 "reader.h"
  26 #include "gram.h"
  27 #include "derives.h"
  28
  29 /* Linked list of rule numbers.  */
  30 typedef struct rule_list_s
  31 {
  32   struct rule_list_s *next;
  33   rule_t *value;
  34 } rule_list_t;
  35
  36 rule_t ***derives = NULL;
  37
  38 static void
  39 print_derives (void)
  40 {
  41   int i;
  42
  43   fputs ("DERIVES\n", stderr);
  44
  45   for (i = ntokens; i < nsyms; i++)
  46     {
  47       rule_t **rp;
  48       fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
  49       for (rp = derives[i]; *rp; ++rp)
  50         {
  51           fprintf (stderr, "\t\t%3d ", (*rp)->user_number);
  52           rule_rhs_print (*rp, stderr);
  53         }
  54     }
  55
  56   fputs ("\n\n", stderr);
  57 }
  58
  59
  60 void
  61 derives_compute (void)
  62 {
  63   symbol_number_t i;
  64   int r;
  65   rule_t **q;
  66
  67   /* DSET[NTERM] -- A linked list of the numbers of the rules whose
  68      LHS is NTERM.  */
  69   rule_list_t **dset = XCALLOC (rule_list_t *, nvars) - ntokens;
  70
  71   /* DELTS[RULE] -- There are NRULES rule number to attach to nterms.
  72      Instead of performing NRULES allocations for each, have an array
  73      indexed by rule numbers.  */
  74   rule_list_t *delts = XCALLOC (rule_list_t, nrules);
  75
  76   for (r = nrules - 1; r >= 0; --r)
  77     {
  78       symbol_number_t lhs = rules[r].lhs->number;
  79       rule_list_t *p = &delts[r];
  80       /* A new LHS is found.  */
  81       p->next = dset[lhs];
  82       p->value = &rules[r];
  83       dset[lhs] = p;
  84     }
  85
  86   /* DSET contains what we need under the form of a linked list.  Make
  87      it a single array.  */
  88
  89   derives = XCALLOC (rule_t **, nvars) - ntokens;
  90   q = XCALLOC (rule_t *, nvars + int_of_rule_number (nrules));
  91
  92   for (i = ntokens; i < nsyms; i++)
  93     {
  94       rule_list_t *p = dset[i];
  95       derives[i] = q;
  96       while (p)
  97         {
  98           *q++ = p->value;
  99           p = p->next;
 100         }
 101       *q++ = NULL;
 102     }
 103
 104   if (trace_flag & trace_sets)
 105     print_derives ();
 106
 107   free (dset + ntokens);
 108   free (delts);
 109 }
 110
 111
 112 void
 113 derives_free (void)
 114 {
 115   XFREE (derives[ntokens]);
 116   XFREE (derives + ntokens);
 117 }