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