Home | History | Annotate | Download | only in src 
      1 /* Match rules with nonterminals for bison,
      2 
      3    Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2005 Free
      4    Software 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., 51 Franklin Street, Fifth Floor,
     21    Boston, MA 02110-1301, USA.  */
     22 
     23 #include <config.h>
     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 }
    122