Home | History | Annotate | Download | only in src 
      1 /* Match rules with nonterminals for bison,
      2 
      3    Copyright (C) 1984, 1989, 2000-2003, 2005, 2009-2012 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 }
    120