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