src/derives.c

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