util/LLgen/src/reach.c

   1 /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
   2  * For full copyright and restrictions on use see the file COPYING in the top
   3  * level of the LLgen tree.
   4  */
   5
   6 /*
   7  *  L L G E N
   8  *
   9  *  An Extended LL(1) Parser Generator
  10  *
  11  *  Author : Ceriel J.H. Jacobs
  12  */
  13
  14 /*
  15  * reach.c
  16  * Determine which nonterminals are reachable, and also check that they
  17  * are all defined.
  18  */
  19
  20 # include "types.h"
  21 # include "extern.h"
  22 # include "io.h"
  23 # include "assert.h"
  24
  25 # ifndef NORCSID
  26 static string rcsid8 = "$Id: reach.c,v 2.12 1995/07/31 09:17:00 ceriel Exp $";
  27 # endif
  28
  29 /* In this file the following routines are defined: */
  30 extern co_reach();
  31 STATIC reachable();
  32 STATIC reachwalk();
  33
  34 co_reach() {
  35         /*
  36          * Check for undefined or unreachable nonterminals.
  37          */
  38         register p_nont         p;
  39         register p_token        t;
  40         register p_start        st;
  41         register p_file         x;
  42         register int            s;
  43
  44         /* Check for undefined nonterminals */
  45         for (p = nonterms; p < maxnt; p++) {
  46                 if (! p->n_rule) {      /* undefined */
  47                         f_input = p->n_string;
  48                         error(p->n_lineno,"Nonterminal %s not defined",
  49                                 p->n_name);
  50                 }
  51         }
  52
  53         /*
  54          * Walk the grammar rules, starting with the startsymbols
  55          * Mark the nonterminals that are encountered with the flag
  56          * REACHABLE, and walk their rules, if not done before
  57          */
  58         for (st = start; st; st = st->ff_next) {
  59                 reachable(&nonterms[st->ff_nont]);
  60         }
  61         /*
  62          * Now check for unreachable nonterminals
  63          */
  64         for (x = files; x < maxfiles; x++) {
  65             f_input = x->f_name;
  66             for (s = x->f_nonterminals; s != -1; s = p->n_next) {
  67                 p = &nonterms[s];
  68                 if (! (p->n_flags & REACHABLE)) {
  69                         warning(p->n_lineno,"nonterminal %s unreachable",
  70                                 p->n_name);
  71                 }
  72             }
  73             for (s = x->f_terminals; s != -1; s = t->t_next) {
  74                 t = &tokens[s];
  75                 if (! (t->t_flags & REACHABLE)) {
  76                         warning(t->t_lineno,"terminal %s not used",
  77                                 t->t_string);
  78                 }
  79             }
  80         }
  81 }
  82
  83 STATIC
  84 reachable(p) register p_nont p; {
  85         /*
  86          * Enter the fact that p is reachable, and look for implications
  87          */
  88         if (! (p->n_flags & REACHABLE)) {
  89                 p->n_flags |= REACHABLE;
  90                 /*
  91                  * Now walk its grammar rule
  92                  */
  93                 if (p->n_rule) reachwalk(p->n_rule);
  94         }
  95 }
  96
  97 STATIC
  98 reachwalk(p) register p_gram p; {
  99         /*
 100          * Walk through rule p, looking for nonterminals.
 101          * The nonterminals found are entered as reachable
 102          */
 103
 104         for (;;) {
 105                 switch(g_gettype(p)) {
 106                   case ALTERNATION :
 107                         reachwalk(g_getlink(p)->l_rule);
 108                         break;
 109                   case TERM :
 110                         reachwalk(g_getterm(p)->t_rule);
 111                         break;
 112                   case NONTERM : {
 113                         register p_nont n = &nonterms[g_getcont(p)];
 114
 115                         reachable(n);
 116                         if (n->n_rule && g_gettype(n->n_rule) == EORULE &&
 117                             ! g_getnpar(p) && (getntparams(n) == 0)) {
 118                                 register p_gram np = p;
 119                                 do {
 120                                         *np = *(np + 1);
 121                                         np++;
 122                                 } while (g_gettype(np) != EORULE);
 123                                 continue;
 124                         }
 125                         break;
 126                   }
 127                   case TERMINAL:
 128                         tokens[g_getcont(p)].t_flags |= REACHABLE;
 129                         break;
 130                   case EORULE :
 131                         return;
 132                 }
 133                 p++;
 134         }
 135 }