home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnubison.zip / nullable.c < prev    next >
C/C++ Source or Header  |  1994-08-26  |  3KB  |  137 lines
  1. /* Part of the bison parser generator,
  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, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. /* set up nullable, a vector saying which nonterminals can expand into the null string.
  22.    nullable[i - ntokens] is nonzero if symbol i can do so.  */
  23.  
  24. #include <stdio.h>
  25. #include "system.h"
  26. #include "types.h"
  27. #include "gram.h"
  28. #include "new.h"
  29.  
  30.  
  31. char *nullable;
  32.  
  33.  
  34. void
  35. set_nullable()
  36. {
  37.   register short *r;
  38.   register short *s1;
  39.   register short *s2;
  40.   register int ruleno;
  41.   register int symbol;
  42.   register shorts *p;
  43.  
  44.   short *squeue;
  45.   short *rcount;
  46.   shorts **rsets;
  47.   shorts *relts;
  48.   char any_tokens;
  49.   short *r1;
  50.  
  51. #ifdef    TRACE
  52.   fprintf(stderr, "Entering set_nullable");
  53. #endif
  54.  
  55.   nullable = NEW2(nvars, char) - ntokens;
  56.  
  57.   squeue = NEW2(nvars, short);
  58.   s1 = s2 = squeue;
  59.  
  60.   rcount = NEW2(nrules + 1, short);
  61.   rsets = NEW2(nvars, shorts *) - ntokens;
  62.   /* This is said to be more elements than we actually use.
  63.      Supposedly nitems - nrules is enough.
  64.      But why take the risk?  */
  65.   relts = NEW2(nitems + nvars + 1, shorts);
  66.   p = relts;
  67.  
  68.   r = ritem;
  69.   while (*r)
  70.     {
  71.       if (*r < 0)
  72.     {
  73.       symbol = rlhs[-(*r++)];
  74.       if (symbol >= 0 && !nullable[symbol])
  75.         {
  76.           nullable[symbol] = 1;
  77.           *s2++ = symbol;
  78.         }
  79.     }
  80.       else
  81.     {
  82.       r1 = r;
  83.       any_tokens = 0;
  84.       for (symbol = *r++; symbol > 0; symbol = *r++)
  85.         {
  86.           if (ISTOKEN(symbol))
  87.         any_tokens = 1;
  88.         }
  89.  
  90.       if (!any_tokens)
  91.         {
  92.           ruleno = -symbol;
  93.           r = r1;
  94.           for (symbol = *r++; symbol > 0; symbol = *r++)
  95.         {
  96.           rcount[ruleno]++;
  97.           p->next = rsets[symbol];
  98.           p->value = ruleno;
  99.           rsets[symbol] = p;
  100.           p++;
  101.         }
  102.         }
  103.     }
  104.     }
  105.  
  106.   while (s1 < s2)
  107.     {
  108.       p = rsets[*s1++];
  109.       while (p)
  110.     {
  111.       ruleno = p->value;
  112.       p = p->next;
  113.       if (--rcount[ruleno] == 0)
  114.         {
  115.           symbol = rlhs[ruleno];
  116.           if (symbol >= 0 && !nullable[symbol])
  117.         {
  118.           nullable[symbol] = 1;
  119.           *s2++ = symbol;
  120.         }
  121.         }
  122.     }
  123.     }
  124.  
  125.   FREE(squeue);
  126.   FREE(rcount);
  127.   FREE(rsets + ntokens);
  128.   FREE(relts);
  129. }
  130.  
  131.  
  132. void
  133. free_nullable()
  134. {
  135.   FREE(nullable + ntokens);
  136. }
  137.