home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Bison.sit.hqx / Bison / Source / nullable.c < prev    next >
Text File  |  1992-08-21  |  3KB  |  148 lines
  1. /***********************************************************
  2.  *
  3.  * Macintosh/MPW version of GNU Bison 1.18
  4.  * Please read the README_MPW file for more information
  5.  *
  6.  ***********************************************************/
  7.  
  8. /* Part of the bison parser generator,
  9.    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
  10.  
  11. This file is part of Bison, the GNU Compiler Compiler.
  12.  
  13. Bison is free software; you can redistribute it and/or modify
  14. it under the terms of the GNU General Public License as published by
  15. the Free Software Foundation; either version 2, or (at your option)
  16. any later version.
  17.  
  18. Bison is distributed in the hope that it will be useful,
  19. but WITHOUT ANY WARRANTY; without even the implied warranty of
  20. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21. GNU General Public License for more details.
  22.  
  23. You should have received a copy of the GNU General Public License
  24. along with Bison; see the file COPYING.  If not, write to
  25. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  26.  
  27.  
  28. /* set up nullable, a vector saying which nonterminals can expand into the null string.
  29.    nullable[i - ntokens] is nonzero if symbol i can do so.  */
  30.  
  31. #include <stdio.h>
  32. #include "system.h"
  33. #include "types.h"
  34. #include "gram.h"
  35. #include "new.h"
  36.  
  37. #ifdef macintosh
  38. #pragma segment bison
  39. #endif
  40.  
  41.  
  42. char *nullable;
  43.  
  44.  
  45. void
  46. set_nullable()
  47. {
  48.   register short *r;
  49.   register short *s1;
  50.   register short *s2;
  51.   register int ruleno;
  52.   register int symbol;
  53.   register shorts *p;
  54.  
  55.   short *squeue;
  56.   short *rcount;
  57.   shorts **rsets;
  58.   shorts *relts;
  59.   char any_tokens;
  60.   short *r1;
  61.  
  62. #ifdef    TRACE
  63.   fprintf(stderr, "Entering set_nullable");
  64. #endif
  65.  
  66.   nullable = NEW2(nvars, char) - ntokens;
  67.  
  68.   squeue = NEW2(nvars, short);
  69.   s1 = s2 = squeue;
  70.  
  71.   rcount = NEW2(nrules + 1, short);
  72.   rsets = NEW2(nvars, shorts *) - ntokens;
  73.   /* This is said to be more elements than we actually use.
  74.      Supposedly nitems - nrules is enough.
  75.      But why take the risk?  */
  76.   relts = NEW2(nitems + nvars + 1, shorts);
  77.   p = relts;
  78.  
  79.   r = ritem;
  80.   while (*r)
  81.     {
  82.       if (*r < 0)
  83.     {
  84.       symbol = rlhs[-(*r++)];
  85.       if (symbol >= 0 && !nullable[symbol])
  86.         {
  87.           nullable[symbol] = 1;
  88.           *s2++ = symbol;
  89.         }
  90.     }
  91.       else
  92.     {
  93.       r1 = r;
  94.       any_tokens = 0;
  95.       for (symbol = *r++; symbol > 0; symbol = *r++)
  96.         {
  97.           if (ISTOKEN(symbol))
  98.         any_tokens = 1;
  99.         }
  100.  
  101.       if (!any_tokens)
  102.         {
  103.           ruleno = -symbol;
  104.           r = r1;
  105.           for (symbol = *r++; symbol > 0; symbol = *r++)
  106.         {
  107.           rcount[ruleno]++;
  108.           p->next = rsets[symbol];
  109.           p->value = ruleno;
  110.           rsets[symbol] = p;
  111.           p++;
  112.         }
  113.         }
  114.     }
  115.     }
  116.  
  117.   while (s1 < s2)
  118.     {
  119.       p = rsets[*s1++];
  120.       while (p)
  121.     {
  122.       ruleno = p->value;
  123.       p = p->next;
  124.       if (--rcount[ruleno] == 0)
  125.         {
  126.           symbol = rlhs[ruleno];
  127.           if (symbol >= 0 && !nullable[symbol])
  128.         {
  129.           nullable[symbol] = 1;
  130.           *s2++ = symbol;
  131.         }
  132.         }
  133.     }
  134.     }
  135.  
  136.   FREE(squeue);
  137.   FREE(rcount);
  138.   FREE(rsets + ntokens);
  139.   FREE(relts);
  140. }
  141.  
  142.  
  143. void
  144. free_nullable()
  145. {
  146.   FREE(nullable + ntokens);
  147. }
  148.