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