home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / BYACC.ZIP / LR0.C < prev    next >
C/C++ Source or Header  |  1992-03-16  |  10KB  |  607 lines
  1. #include <stdlib.h>
  2. #include <stddef.h>
  3. #include "byacc.h"
  4.  
  5. extern short *itemset;
  6. extern short *itemsetend;
  7. extern unsigned *ruleset;
  8.  
  9. int nstates;
  10. core *first_state;
  11. shifts *first_shift;
  12. reductions *first_reduction;
  13.  
  14. int get_state();
  15. core *new_state();
  16.  
  17. static core *this_state;
  18. static core *last_state;
  19. static shifts *last_shift;
  20. static reductions *last_reduction;
  21.  
  22. static int nshifts;
  23. static short *shift_symbol;
  24.  
  25. static short *redset;
  26. static short *shiftset;
  27.  
  28. static short **kernel_base;
  29. static short **kernel_end;
  30. static short *kernel_items;
  31.  
  32. extern core **state_table;
  33.  
  34.  
  35. void allocate_itemsets(void)
  36. {
  37.   register short *itemp;
  38.   register short *item_end;
  39.   register int symbol;
  40.   register int i;
  41.   register int count;
  42.   register int max;
  43.   register short *symbol_count;
  44.  
  45.   count = 0;
  46.   symbol_count = NEW2(nsyms, short);
  47.  
  48.   item_end = ritem + nitems;
  49.   for (itemp = ritem; itemp < item_end; itemp++)
  50.     {
  51.       symbol = *itemp;
  52.       if (symbol >= 0)
  53.     {
  54.       count++;
  55.       symbol_count[symbol]++;
  56.     }
  57.     }
  58.  
  59.   kernel_base = NEW2(nsyms, short *);
  60.   kernel_items = NEW2(count, short);
  61.  
  62.   count = 0;
  63.   max = 0;
  64.   for (i = 0; i < nsyms; i++)
  65.     {
  66.       kernel_base[i] = kernel_items + count;
  67.       count += symbol_count[i];
  68.       if (max < symbol_count[i])
  69.     max = symbol_count[i];
  70.     }
  71.  
  72.   shift_symbol = symbol_count;
  73.   kernel_end = NEW2(nsyms, short *);
  74. }
  75.  
  76.  
  77.  
  78. void allocate_storage(void)
  79. {
  80.   allocate_itemsets();
  81.  
  82.   shiftset = NEW2(nsyms, short);
  83.   redset = NEW2(nrules + 1, short);
  84.   state_table = NEW2(nitems, core *);
  85. }
  86.  
  87.  
  88.  
  89. void append_states(void)
  90. {
  91.   register int i;
  92.   register int j;
  93.   register int symbol;
  94.  
  95. #ifdef    TRACE
  96.   fprintf(stderr, "Entering append_states\n");
  97. #endif
  98.  
  99.   for (i = 1; i < nshifts; i++)
  100.     {
  101.       symbol = shift_symbol[i];
  102.       j = i;
  103.       while (j > 0 && shift_symbol[j - 1] > symbol)
  104.     {
  105.       shift_symbol[j] = shift_symbol[j - 1];
  106.       j--;
  107.     }
  108.       shift_symbol[j] = symbol;
  109.     }
  110.  
  111.   for (i = 0; i < nshifts; i++)
  112.     {
  113.       symbol = shift_symbol[i];
  114.       shiftset[i] = get_state(symbol);
  115.     }
  116. }
  117.  
  118.  
  119. void free_storage(void)
  120. {
  121.   FREE(shift_symbol);
  122.   FREE(redset);
  123.   FREE(shiftset);
  124.   FREE(kernel_base);
  125.   FREE(kernel_end);
  126.   FREE(kernel_items);
  127.   FREE(state_table);
  128. }
  129.  
  130.  
  131.  
  132. void generate_states(void)
  133. {
  134.   allocate_storage();
  135.   itemset = NEW2(nitems, short);
  136.   ruleset = NEW2(WORDSIZE(nrules), unsigned);
  137.   set_first_derives();
  138.   initialize_states();
  139.  
  140.   while (this_state)
  141.     {
  142.       closure(this_state->items, this_state->nitems);
  143.       save_reductions();
  144.       new_itemsets();
  145.       append_states();
  146.  
  147.       if (nshifts > 0)
  148.     save_shifts();
  149.  
  150.       this_state = this_state->next;
  151.     }
  152.  
  153.   finalize_closure();
  154.   free_storage();
  155. }
  156.  
  157.  
  158.  
  159. int
  160. get_state(int symbol)
  161. {
  162.   register int key;
  163.   register short *isp1;
  164.   register short *isp2;
  165.   register short *iend;
  166.   register core *sp;
  167.   register int found;
  168.  
  169.   ptrdiff_t n;
  170.  
  171. #ifdef    TRACE
  172.   fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
  173. #endif
  174.  
  175.   isp1 = kernel_base[symbol];
  176.   iend = kernel_end[symbol];
  177.   n = iend - isp1;
  178.  
  179.   key = *isp1;
  180.   assert(0 <= key && key < nitems);
  181.   sp = state_table[key];
  182.   if (sp)
  183.     {
  184.       found = 0;
  185.       while (!found)
  186.     {
  187.       if (sp->nitems == n)
  188.         {
  189.           found = 1;
  190.           isp1 = kernel_base[symbol];
  191.           isp2 = sp->items;
  192.  
  193.           while (found && isp1 < iend)
  194.         {
  195.           if (*isp1++ != *isp2++)
  196.             found = 0;
  197.         }
  198.         }
  199.  
  200.       if (!found)
  201.         {
  202.           if (sp->link)
  203.         {
  204.           sp = sp->link;
  205.         }
  206.           else
  207.         {
  208.           sp = sp->link = new_state(symbol);
  209.           found = 1;
  210.         }
  211.         }
  212.     }
  213.     }
  214.   else
  215.     {
  216.       state_table[key] = sp = new_state(symbol);
  217.     }
  218.  
  219.   return (sp->number);
  220. }
  221.  
  222.  
  223.  
  224. void initialize_states(void)
  225. {
  226.     register int i;
  227.     register short *start_derives;
  228.     register core *p;
  229.  
  230.     start_derives = derives[start_symbol];
  231.     for (i = 0; start_derives[i] >= 0; ++i)
  232.     continue;
  233.  
  234.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  235.     if (p == 0) no_space();
  236.  
  237.     p->next = 0;
  238.     p->link = 0;
  239.     p->number = 0;
  240.     p->accessing_symbol = 0;
  241.     p->nitems = i;
  242.  
  243.     for (i = 0;  start_derives[i] >= 0; ++i)
  244.     p->items[i] = rrhs[start_derives[i]];
  245.  
  246.     first_state = last_state = this_state = p;
  247.     nstates = 1;
  248. }
  249.  
  250.  
  251. void new_itemsets(void)
  252. {
  253.   register int i;
  254.   register int shiftcount;
  255.   register short *isp;
  256.   register short *ksp;
  257.   register int symbol;
  258.  
  259.   for (i = 0; i < nsyms; i++)
  260.     kernel_end[i] = 0;
  261.  
  262.   shiftcount = 0;
  263.   isp = itemset;
  264.   while (isp < itemsetend)
  265.     {
  266.       i = *isp++;
  267.       symbol = ritem[i];
  268.       if (symbol > 0)
  269.     {
  270.           ksp = kernel_end[symbol];
  271.  
  272.           if (!ksp)
  273.         {
  274.           shift_symbol[shiftcount++] = symbol;
  275.           ksp = kernel_base[symbol];
  276.         }
  277.  
  278.       *ksp++ = i + 1;
  279.           kernel_end[symbol] = ksp;
  280.     }
  281.     }
  282.  
  283.   nshifts = shiftcount;
  284. }
  285.  
  286.  
  287.  
  288. core *
  289. new_state(int symbol)
  290. {
  291.   register ptrdiff_t n;
  292.   register core *p;
  293.   register short *isp1;
  294.   register short *isp2;
  295.   register short *iend;
  296.  
  297. #ifdef    TRACE
  298.   fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
  299. #endif
  300.  
  301.   if (nstates >= MAXSHORT)
  302.     fatal("too many states");
  303.  
  304.   isp1 = kernel_base[symbol];
  305.   iend = kernel_end[symbol];
  306.   n = iend - isp1;
  307.  
  308.   p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  309.   p->accessing_symbol = symbol;
  310.   p->number = nstates;
  311.   p->nitems = n;
  312.  
  313.   isp2 = p->items;
  314.   while (isp1 < iend)
  315.     *isp2++ = *isp1++;
  316.  
  317.   last_state->next = p;
  318.   last_state = p;
  319.  
  320.   nstates++;
  321.  
  322.   return (p);
  323. }
  324.  
  325.  
  326. /* show_cores is used for debugging */
  327.  
  328. void show_cores(void)
  329. {
  330.     core *p;
  331.     int i, j, k, n;
  332.     int itemno;
  333.  
  334.     k = 0;
  335.     for (p = first_state; p; ++k, p = p->next)
  336.     {
  337.     if (k) printf("\n");
  338.     printf("state %d, number = %d, accessing symbol = %s\n",
  339.         k, p->number, symbol_name[p->accessing_symbol]);
  340.     n = p->nitems;
  341.     for (i = 0; i < n; ++i)
  342.     {
  343.         itemno = p->items[i];
  344.         printf("%4d  ", itemno);
  345.         j = itemno;
  346.         while (ritem[j] >= 0) ++j;
  347.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  348.         j = rrhs[-ritem[j]];
  349.         while (j < itemno)
  350.         printf(" %s", symbol_name[ritem[j++]]);
  351.         printf(" .");
  352.         while (ritem[j] >= 0)
  353.         printf(" %s", symbol_name[ritem[j++]]);
  354.         printf("\n");
  355.         fflush(stdout);
  356.     }
  357.     }
  358. }
  359.  
  360.  
  361. /* show_ritems is used for debugging */
  362.  
  363. void show_ritems(void)
  364. {
  365.     int i;
  366.  
  367.     for (i = 0; i < nitems; ++i)
  368.     printf("ritem[%d] = %d\n", i, ritem[i]);
  369. }
  370.  
  371.  
  372. /* show_rrhs is used for debugging */
  373. void show_rrhs(void)
  374. {
  375.     int i;
  376.  
  377.     for (i = 0; i < nrules; ++i)
  378.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  379. }
  380.  
  381.  
  382. /* show_shifts is used for debugging */
  383.  
  384. void show_shifts(void)
  385. {
  386.     shifts *p;
  387.     int i, j, k;
  388.  
  389.     k = 0;
  390.     for (p = first_shift; p; ++k, p = p->next)
  391.     {
  392.     if (k) printf("\n");
  393.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  394.         p->nshifts);
  395.     j = p->nshifts;
  396.     for (i = 0; i < j; ++i)
  397.         printf("\t%d\n", p->shifts[i]);
  398.     }
  399. }
  400.  
  401.  
  402. void save_shifts(void)
  403. {
  404.   register shifts *p;
  405.   register short *sp1;
  406.   register short *sp2;
  407.   register short *send;
  408.  
  409.   p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  410.             (nshifts - 1) * sizeof(short)));
  411.  
  412.   p->number = this_state->number;
  413.   p->nshifts = nshifts;
  414.  
  415.   sp1 = shiftset;
  416.   sp2 = p->shifts;
  417.   send = shiftset + nshifts;
  418.  
  419.   while (sp1 < send)
  420.     *sp2++ = *sp1++;
  421.  
  422.   if (last_shift)
  423.     {
  424.       last_shift->next = p;
  425.       last_shift = p;
  426.     }
  427.   else
  428.     {
  429.       first_shift = p;
  430.       last_shift = p;
  431.     }
  432. }
  433.  
  434.  
  435.  
  436. void save_reductions(void)
  437. {
  438.   register short *isp;
  439.   register short *rp1;
  440.   register short *rp2;
  441.   register int item;
  442.   register int count;
  443.   register reductions *p;
  444.  
  445.   short *rend;
  446.  
  447.   count = 0;
  448.   for (isp = itemset; isp < itemsetend; isp++)
  449.     {
  450.       item = ritem[*isp];
  451.       if (item < 0)
  452.     {
  453.       redset[count++] = -item;
  454.     }
  455.     }
  456.  
  457.   if (count)
  458.     {
  459.       p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  460.                     (count - 1) * sizeof(short)));
  461.  
  462.       p->number = this_state->number;
  463.       p->nreds = count;
  464.  
  465.       rp1 = redset;
  466.       rp2 = p->rules;
  467.       rend = rp1 + count;
  468.  
  469.       while (rp1 < rend)
  470.     *rp2++ = *rp1++;
  471.  
  472.       if (last_reduction)
  473.     {
  474.       last_reduction->next = p;
  475.       last_reduction = p;
  476.     }
  477.       else
  478.     {
  479.       first_reduction = p;
  480.       last_reduction = p;
  481.     }
  482.     }
  483. }
  484.  
  485.  
  486. void set_derives(void)
  487. {
  488.   register int i, k;
  489.   register int lhs;
  490.   register short *rules;
  491.  
  492.   derives = NEW2(nsyms, short *);
  493.   rules = NEW2(nvars + nrules, short);
  494.  
  495.   k = 0;
  496.   for (lhs = start_symbol; lhs < nsyms; lhs++)
  497.     {
  498.       derives[lhs] = rules + k;
  499.       for (i = 0; i < nrules; i++)
  500.     {
  501.       if (rlhs[i] == lhs)
  502.         {
  503.           rules[k] = i;
  504.           k++;
  505.         }
  506.     }
  507.       rules[k] = -1;
  508.       k++;
  509.     }
  510.  
  511. #ifdef    DEBUG
  512.   print_derives();
  513. #endif
  514. }
  515.  
  516. void free_derives(void)
  517. {
  518.   FREE(derives[start_symbol]);
  519.   FREE(derives);
  520. }
  521.  
  522. #ifdef    DEBUG
  523. void
  524. print_derives()
  525. {
  526.   register int i;
  527.   register short *sp;
  528.  
  529.   printf("\nDERIVES\n\n");
  530.  
  531.   for (i = start_symbol; i < nsyms; i++)
  532.     {
  533.       printf("%s derives ", symbol_name[i]);
  534.       for (sp = derives[i]; *sp >= 0; sp++)
  535.     {
  536.       printf("  %d", *sp);
  537.     }
  538.       putchar('\n');
  539.     }
  540.  
  541.   putchar('\n');
  542. }
  543. #endif
  544.  
  545.  
  546. void set_nullable(void)
  547. {
  548.     register int i, j;
  549.     register int empty;
  550.     int done;
  551.  
  552.     nullable = MALLOC(nsyms);
  553.     if (nullable == 0) no_space();
  554.  
  555.     for (i = 0; i < nsyms; ++i)
  556.     nullable[i] = 0;
  557.  
  558.     done = 0;
  559.     while (!done)
  560.     {
  561.     done = 1;
  562.     for (i = 1; i < nitems; i++)
  563.     {
  564.         empty = 1;
  565.         while ((j = ritem[i]) >= 0)
  566.         {
  567.         if (!nullable[j])
  568.             empty = 0;
  569.         ++i;
  570.         }
  571.         if (empty)
  572.         {
  573.         j = rlhs[-j];
  574.         if (!nullable[j])
  575.         {
  576.             nullable[j] = 1;
  577.             done = 0;
  578.         }
  579.         }
  580.     }
  581.     }
  582.  
  583. #ifdef DEBUG
  584.     for (i = 0; i < nsyms; i++)
  585.     {
  586.     if (nullable[i])
  587.         printf("%s is nullable\n", symbol_name[i]);
  588.     else
  589.         printf("%s is not nullable\n", symbol_name[i]);
  590.     }
  591. #endif
  592. }
  593.  
  594.  
  595. void free_nullable(void)
  596. {
  597.   FREE(nullable);
  598. }
  599.  
  600.  
  601. void lr0(void)
  602. {
  603.     set_derives();
  604.     set_nullable();
  605.     generate_states();
  606. }
  607.