src/derives.c

   1 /* Match rules with nonterminals for bison,
   2    Copyright (C) 1984, 1989, 2000 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 /* set_derives finds, for each variable (nonterminal), which rules can
  23    derive it.  It sets up the value of derives so that derives[i -
  24    ntokens] points to a vector of rule numbers, terminated with -1.
  25    */
  26
  27 #include "system.h"
  28 #include "alloc.h"
  29 #include "types.h"
  30 #include "gram.h"
  31 #include "derives.h"
  32
  33 #if DEBUG
  34 extern char **tags;
  35
  36 static void
  37 print_derives (void)
  38 {
  39   register int i;
  40   register short *sp;
  41
  42   printf (_("\n\n\nDERIVES\n\n"));
  43
  44   for (i = ntokens; i < nsyms; i++)
  45     {
  46       printf (_("%s derives"), tags[i]);
  47       for (sp = derives[i]; *sp > 0; sp++)
  48         {
  49           printf ("  %d", *sp);
  50         }
  51       putchar ('\n');
  52     }
  53
  54   putchar ('\n');
  55 }
  56
  57 #endif
  58
  59 short **derives;
  60
  61 void
  62 set_derives (void)
  63 {
  64   register int i;
  65   register int lhs;
  66   register shorts *p;
  67   register short *q;
  68   register shorts **dset;
  69   register shorts *delts;
  70
  71   dset = NEW2 (nvars, shorts *) - ntokens;
  72   delts = NEW2 (nrules + 1, shorts);
  73
  74   p = delts;
  75   for (i = nrules; i > 0; i--)
  76     {
  77       lhs = rlhs[i];
  78       if (lhs >= 0)
  79         {
  80           p->next = dset[lhs];
  81           p->value = i;
  82           dset[lhs] = p;
  83           p++;
  84         }
  85     }
  86
  87   derives = NEW2 (nvars, short *) - ntokens;
  88   q = NEW2 (nvars + nrules, short);
  89
  90   for (i = ntokens; i < nsyms; i++)
  91     {
  92       derives[i] = q;
  93       p = dset[i];
  94       while (p)
  95         {
  96           *q++ = p->value;
  97           p = p->next;
  98         }
  99       *q++ = -1;
 100     }
 101
 102 #if DEBUG
 103   print_derives ();
 104 #endif
 105
 106   FREE (dset + ntokens);
 107   FREE (delts);
 108 }
 109
 110 void
 111 free_derives (void)
 112 {
 113   FREE (derives[ntokens]);
 114   FREE (derives + ntokens);
 115 }