home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume19 / wacco / part01 / build.C < prev    next >
C/C++ Source or Header  |  1991-05-19  |  6KB  |  312 lines
  1. // Copyright (c) 1991 by Parag Patel.  All Rights Reserved.
  2. static const char rcs_id[] = "$Header: build.C,v 1.5 91/02/22 16:07:15 hmgr Exp $";
  3.  
  4. #include "defs.h"
  5.  
  6.  
  7. static void markempty()
  8. {
  9.     symbol *sym, *s;
  10.     symnode *or, *next, *node;
  11.     int i, num;
  12.     boolean done;
  13.  
  14.     num = numsymbols();
  15.     do
  16.     {
  17.         done = TRUE;
  18.         for (i = START; i < num; i++)
  19.         {
  20.             sym = getsymbol(i);
  21.             if (sym->type != NONTERMINAL)
  22.                 continue;
  23.  
  24.             for (or = sym->node; or != NULL; or = or->or)
  25.             {
  26.                 for (node = or; node != NULL; node = node->next)
  27.                     if (node->sym->type != CODE)
  28.                         break;
  29.                 if (node == NULL)
  30.                     continue;
  31.  
  32.                 s = node->sym;
  33.                 if (s->id == EMPTY && !sym->toempty)
  34.                 {
  35.                     sym->toempty = TRUE;
  36.                     done = FALSE;
  37.                 }
  38.  
  39.                 for (next = node; next != NULL; next = next->next)
  40.                     if (next->sym->type != CODE && !next->sym->toempty)
  41.                         break;
  42.  
  43.                 if (next == NULL && !sym->toempty)
  44.                 {
  45.                     sym->toempty = TRUE;
  46.                     done = FALSE;
  47.                 }
  48.             }
  49.         }
  50.     } while (!done);
  51. }
  52.  
  53.  
  54. static void first()
  55. {
  56.     symbol *sym, *s;
  57.     symnode *or, *next, *node;
  58.     int i, num;
  59.     boolean done;
  60.  
  61.     num = numsymbols();
  62.     do
  63.     {
  64.         done = TRUE;
  65.         for (i = START; i < num; i++)
  66.         {
  67.             sym = getsymbol(i);
  68.             if (sym->type == CODE)
  69.                 continue;
  70.  
  71.             if (sym->type == TERMINAL)
  72.             {
  73.                 if (sym->first->isin(sym->id))
  74.                     continue;
  75.                 *sym->first += sym->id;
  76.                 done = FALSE;
  77.                 continue;
  78.             }
  79.  
  80.             for (or = sym->node; or != NULL; or = or->or)
  81.             {
  82.                 for (node = or; node != NULL; node = node->next)
  83.                     if (node->sym->type != CODE)
  84.                         break;
  85.                 if (node == NULL)
  86.                     continue;
  87.  
  88.                 s = node->sym;
  89.                 if (s->id == EMPTY)
  90.                 {
  91.                     if (!sym->first->isin(EMPTY))
  92.                     {
  93.                         *sym->first += EMPTY;
  94.                         done = FALSE;
  95.                     }
  96.                     continue;
  97.                 }
  98.  
  99.                 for (next = node; next != NULL; next = next->next)
  100.                 {
  101.                     s = next->sym;
  102.                     if (s->type == CODE)
  103.                         continue;
  104.  
  105.                     if (!(*s->first <= *sym->first))
  106.                     {
  107.                         *sym->first |= *s->first;
  108.                         done = FALSE;
  109.                     }
  110.                     if (!s->toempty)
  111.                         break;
  112.                 }
  113.             }
  114.         }
  115.     } while (!done);
  116. }
  117.  
  118.  
  119. static void follow()
  120. {
  121.     symbol *sym, *s;
  122.     symnode *or, *node, *next, *n;
  123.     int i, num;
  124.     boolean done;
  125.     Bitset set;
  126.  
  127.     num = numsymbols();
  128.     *startsymbol->follow += END;
  129.     do
  130.     {
  131.         done = TRUE;
  132.         for (i = START; i < num; i++)
  133.         {
  134.             sym = getsymbol(i);
  135.             if (sym->type != NONTERMINAL)
  136.                 continue;
  137.  
  138.             for (or = sym->node; or != NULL; or = or->or)
  139.             {
  140.                 for (node = or; node != NULL; node = node->next)
  141.                 {
  142.                     s = node->sym;
  143.                     if (s->type == CODE)
  144.                         continue;
  145.  
  146.                     for (next = node->next; next != NULL; next = next->next)
  147.                         if (next->sym->type != CODE)
  148.                             break;
  149.  
  150.                     for (n = next; n != NULL; n = n->next)
  151.                         if (n->sym->type != CODE && !n->sym->toempty)
  152.                             break;
  153.  
  154.                     if (n == NULL)
  155.                     {
  156.                         if (*sym->follow <= *s->follow)
  157.                             continue;
  158.                         *s->follow |= *sym->follow;
  159.                         done = FALSE;
  160.                     }
  161.  
  162.                     if (next != NULL)
  163.                     {
  164.                         set = *next->sym->first;
  165.                         set -= EMPTY;
  166.                         if (!(set <= *s->follow))
  167.                         {
  168.                             *s->follow |= set;
  169.                             done = FALSE;
  170.                         }
  171.                     }
  172.                 }
  173.             }
  174.         }
  175.     } while (!done);
  176. }
  177.  
  178.  
  179. static void mksymresync(symbol *sym)
  180. {
  181.     if (sym->list == NULL)
  182.         return;
  183.  
  184.     Bitset *set = new Bitset;
  185.  
  186.     resynclist *x;
  187.     for (resynclist *r = sym->list; r != NULL; x = r, r = r->next, delete x)
  188.     {
  189.         symbol *s;
  190.         if (r->name != NULL)
  191.         {
  192.             s = findsymbol(r->name);
  193.             if (s == NULL)
  194.             {
  195.                 error("Symbol \"%s\" doesn't exist for \"%s\" resync set",
  196.                         r->name, sym->name);
  197.                 continue;
  198.             }
  199.         }
  200.         else if (r->paren == 0)
  201.             s = getsymbol(EMPTY);
  202.         else
  203.         {
  204.             error("Cannot handle paren groups in skip-set for \"%s\"",
  205.                     sym->name);
  206.             continue;
  207.         }
  208.  
  209.         if (r->first > 0 || (r->first == 0 && r->follow == 0))
  210.             *set |= *s->first;
  211.         else if (r->first < 0)
  212.             *set -= *s->first;
  213.  
  214.         if (r->follow > 0)
  215.             *set |= *s->follow;
  216.         else if (r->follow < 0)
  217.             *set -= *s->follow;
  218.     }
  219.     sym->resync = &settab[set];
  220. }
  221.  
  222.  
  223. static void mkresync(symbol *sym, symnode *start, symnode *n)
  224. {
  225.     Bitset *set = new Bitset;
  226.  
  227.     symnode *t = n;
  228.     for (int i = 0; t != NULL && i <= 3; t = t->next, i++)
  229.         *set |= *t->sym->first;
  230.  
  231.     resynclist *x;
  232.     for (resynclist *r = n->list; r != NULL; x = r, r = r->next, delete x)
  233.     {
  234.         symbol *s;
  235.         if (r->name != NULL)
  236.         {
  237.             s = findsymbol(r->name);
  238.             if (s == NULL)
  239.             {
  240.                 for (symnode *t = start; t != NULL; t = t->next)
  241.                     if (t->alias != NULL && strcmp(t->alias, r->name) == 0)
  242.                         break;
  243.                 if (t != NULL)
  244.                     s = t->sym;
  245.             }
  246.             if (s == NULL)
  247.             {
  248.                 error("Symbol \"%s\" doesn't exist for \"%s\" resync set",
  249.                         r->name, sym->name);
  250.                 continue;
  251.             }
  252.         }
  253.         else if (r->paren == 0)
  254.             s = getsymbol(EMPTY);
  255.         else
  256.         {
  257.             for (symnode *t = start; t != NULL; t = t->next)
  258.                 if (t->sym->realname != NULL 
  259.                         && t->sym->realname != t->sym->name)
  260.                     if (--(*r).paren <= 0)
  261.                         break;
  262.             if (t == NULL)
  263.             {
  264.                 error("Paren group %d does not exist in rule for \"%s\"",
  265.                         r->paren, sym->name);
  266.                 continue;
  267.             }
  268.             s = t->sym;
  269.         }
  270.  
  271.         if (r->first > 0 || (r->first == 0 && r->follow == 0))
  272.             *set |= *s->first;
  273.         else if (r->first < 0)
  274.             *set -= *s->first;
  275.  
  276.         if (r->follow > 0)
  277.             *set |= *s->follow;
  278.         else if (r->follow < 0)
  279.             *set -= *s->follow;
  280.     }
  281.     n->resync = &settab[set];
  282. }
  283.  
  284. static void resync()
  285. {
  286.     int i;
  287.     symbol *sym;
  288.     int num = numsymbols();
  289.     symnode *or;
  290.  
  291.     for (i = START; i < num; i++)
  292.     {
  293.         sym = getsymbol(i);
  294.         if (sym->type == CODE)
  295.             continue;
  296.  
  297.         mksymresync(sym);
  298.         for (or = sym->node; or != NULL; or = or->or)
  299.             for (symnode *n = or; n != NULL; n = n->next)
  300.                 mkresync(sym, or, n);
  301.     }
  302. }
  303.  
  304.  
  305. void buildsets()
  306. {
  307.     markempty();
  308.     first();
  309.     follow();
  310.     resync();
  311. }
  312.