home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 200-299 / ff299.lzh / Yacc / lr0.c < prev    next >
C/C++ Source or Header  |  1989-12-30  |  10KB  |  606 lines
  1. #include "defs.h"
  2.  
  3. extern short *itemset;
  4. extern short *itemsetend;
  5. extern unsigned *ruleset;
  6.  
  7. int nstates;
  8. core *first_state;
  9. shifts *first_shift;
  10. reductions *first_reduction;
  11.  
  12. int get_state();
  13. core *new_state();
  14.  
  15. static core *this_state;
  16. static core *last_state;
  17. static shifts *last_shift;
  18. static reductions *last_reduction;
  19.  
  20. static int nshifts;
  21. static short *shift_symbol;
  22.  
  23. static short *redset;
  24. static short *shiftset;
  25.  
  26. static short **kernel_base;
  27. static short **kernel_end;
  28. static short *kernel_items;
  29.  
  30. static core **state_table;
  31.  
  32.  
  33. allocate_itemsets()
  34. {
  35.   register short *itemp;
  36.   register short *item_end;
  37.   register int symbol;
  38.   register int i;
  39.   register int count;
  40.   register int max;
  41.   register short *symbol_count;
  42.  
  43.   count = 0;
  44.   symbol_count = NEW2(nsyms, short);
  45.  
  46.   item_end = ritem + nitems;
  47.   for (itemp = ritem; itemp < item_end; itemp++)
  48.     {
  49.       symbol = *itemp;
  50.       if (symbol >= 0)
  51.     {
  52.       count++;
  53.       symbol_count[symbol]++;
  54.     }
  55.     }
  56.  
  57.   kernel_base = NEW2(nsyms, short *);
  58.   kernel_items = NEW2(count, short);
  59.  
  60.   count = 0;
  61.   max = 0;
  62.   for (i = 0; i < nsyms; i++)
  63.     {
  64.       kernel_base[i] = kernel_items + count;
  65.       count += symbol_count[i];
  66.       if (max < symbol_count[i])
  67.     max = symbol_count[i];
  68.     }
  69.  
  70.   shift_symbol = symbol_count;
  71.   kernel_end = NEW2(nsyms, short *);
  72. }
  73.  
  74.  
  75.  
  76. allocate_storage()
  77. {
  78.   allocate_itemsets();
  79.  
  80.   shiftset = NEW2(nsyms, short);
  81.   redset = NEW2(nrules + 1, short);
  82.   state_table = NEW2(nitems, core *);
  83. }
  84.  
  85.  
  86.  
  87. append_states()
  88. {
  89.   register int i;
  90.   register int j;
  91.   register int symbol;
  92.  
  93. #ifdef    TRACE
  94.   fprintf(stderr, "Entering append_states\n");
  95. #endif
  96.  
  97.   for (i = 1; i < nshifts; i++)
  98.     {
  99.       symbol = shift_symbol[i];
  100.       j = i;
  101.       while (j > 0 && shift_symbol[j - 1] > symbol)
  102.     {
  103.       shift_symbol[j] = shift_symbol[j - 1];
  104.       j--;
  105.     }
  106.       shift_symbol[j] = symbol;
  107.     }
  108.  
  109.   for (i = 0; i < nshifts; i++)
  110.     {
  111.       symbol = shift_symbol[i];
  112.       shiftset[i] = get_state(symbol);
  113.     }
  114. }
  115.  
  116.  
  117. free_storage()
  118. {
  119.   FREE(shift_symbol);
  120.   FREE(redset);
  121.   FREE(shiftset);
  122.   FREE(kernel_base);
  123.   FREE(kernel_end);
  124.   FREE(kernel_items);
  125.   FREE(state_table);
  126. }
  127.  
  128.  
  129.  
  130. generate_states()
  131. {
  132.   allocate_storage();
  133.   itemset = NEW2(nitems, short);
  134.   ruleset = NEW2(WORDSIZE(nrules), unsigned);
  135.   set_first_derives();
  136.   initialize_states();
  137.  
  138.   while (this_state)
  139.     {
  140.       closure(this_state->items, this_state->nitems);
  141.       save_reductions();
  142.       new_itemsets();
  143.       append_states();
  144.  
  145.       if (nshifts > 0)
  146.         save_shifts();
  147.  
  148.       this_state = this_state->next;
  149.     }
  150.  
  151.   finalize_closure();
  152.   free_storage();
  153. }
  154.  
  155.  
  156.  
  157. int
  158. get_state(symbol)
  159. int symbol;
  160. {
  161.   register int key;
  162.   register short *isp1;
  163.   register short *isp2;
  164.   register short *iend;
  165.   register core *sp;
  166.   register int found;
  167.  
  168.   int n;
  169.  
  170. #ifdef    TRACE
  171.   fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
  172. #endif
  173.  
  174.   isp1 = kernel_base[symbol];
  175.   iend = kernel_end[symbol];
  176.   n = iend - isp1;
  177.  
  178.   key = *isp1;
  179.   assert(0 <= key && key < nitems);
  180.   sp = state_table[key];
  181.   if (sp)
  182.     {
  183.       found = 0;
  184.       while (!found)
  185.     {
  186.       if (sp->nitems == n)
  187.         {
  188.           found = 1;
  189.           isp1 = kernel_base[symbol];
  190.           isp2 = sp->items;
  191.  
  192.           while (found && isp1 < iend)
  193.         {
  194.           if (*isp1++ != *isp2++)
  195.             found = 0;
  196.         }
  197.         }
  198.  
  199.       if (!found)
  200.         {
  201.           if (sp->link)
  202.         {
  203.           sp = sp->link;
  204.         }
  205.           else
  206.         {
  207.           sp = sp->link = new_state(symbol);
  208.           found = 1;
  209.         }
  210.         }
  211.     }
  212.     }
  213.   else
  214.     {
  215.       state_table[key] = sp = new_state(symbol);
  216.     }
  217.  
  218.   return (sp->number);
  219. }
  220.  
  221.  
  222.  
  223. initialize_states()
  224. {
  225.     register int i;
  226.     register short *start_derives;
  227.     register core *p;
  228.  
  229.     start_derives = derives[start_symbol];
  230.     for (i = 0; start_derives[i] >= 0; ++i)
  231.     continue;
  232.  
  233.     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  234.     if (p == 0) no_space();
  235.  
  236.     p->next = 0;
  237.     p->link = 0;
  238.     p->number = 0;
  239.     p->accessing_symbol = 0;
  240.     p->nitems = i;
  241.  
  242.     for (i = 0;  start_derives[i] >= 0; ++i)
  243.     p->items[i] = rrhs[start_derives[i]];
  244.  
  245.     first_state = last_state = this_state = p;
  246.     nstates = 1;
  247. }
  248.  
  249.  
  250. new_itemsets()
  251. {
  252.   register int i;
  253.   register int shiftcount;
  254.   register short *isp;
  255.   register short *ksp;
  256.   register int symbol;
  257.  
  258.   for (i = 0; i < nsyms; i++)
  259.     kernel_end[i] = 0;
  260.  
  261.   shiftcount = 0;
  262.   isp = itemset;
  263.   while (isp < itemsetend)
  264.     {
  265.       i = *isp++;
  266.       symbol = ritem[i];
  267.       if (symbol > 0)
  268.     {
  269.           ksp = kernel_end[symbol];
  270.  
  271.           if (!ksp)
  272.         {
  273.           shift_symbol[shiftcount++] = symbol;
  274.           ksp = kernel_base[symbol];
  275.         }
  276.  
  277.           *ksp++ = i + 1;
  278.           kernel_end[symbol] = ksp;
  279.     }
  280.     }
  281.  
  282.   nshifts = shiftcount;
  283. }
  284.  
  285.  
  286.  
  287. core *
  288. new_state(symbol)
  289. int symbol;
  290. {
  291.   register int 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. show_cores()
  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. show_ritems()
  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. show_rrhs()
  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. show_shifts()
  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. save_shifts()
  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. save_reductions()
  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. set_derives()
  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. free_derives()
  517. {
  518.   FREE(derives[start_symbol]);
  519.   FREE(derives);
  520. }
  521.  
  522. #ifdef    DEBUG
  523. print_derives()
  524. {
  525.   register int i;
  526.   register short *sp;
  527.  
  528.   printf("\nDERIVES\n\n");
  529.  
  530.   for (i = start_symbol; i < nsyms; i++)
  531.     {
  532.       printf("%s derives ", symbol_name[i]);
  533.       for (sp = derives[i]; *sp >= 0; sp++)
  534.     {
  535.       printf("  %d", *sp);
  536.     }
  537.       putchar('\n');
  538.     }
  539.  
  540.   putchar('\n');
  541. }
  542. #endif
  543.  
  544.  
  545. set_nullable()
  546. {
  547.     register int i, j;
  548.     register int empty;
  549.     int done;
  550.  
  551.     nullable = MALLOC(nsyms);
  552.     if (nullable == 0) no_space();
  553.  
  554.     for (i = 0; i < nsyms; ++i)
  555.     nullable[i] = 0;
  556.  
  557.     done = 0;
  558.     while (!done)
  559.     {
  560.     done = 1;
  561.     for (i = 1; i < nitems; i++)
  562.     {
  563.         empty = 1;
  564.         while ((j = ritem[i]) >= 0)
  565.         {
  566.         if (!nullable[j])
  567.             empty = 0;
  568.         ++i;
  569.         }
  570.         if (empty)
  571.         {
  572.         j = rlhs[-j];
  573.         if (!nullable[j])
  574.         {
  575.             nullable[j] = 1;
  576.             done = 0;
  577.         }
  578.         }
  579.     }
  580.     }
  581.  
  582. #ifdef DEBUG
  583.     for (i = 0; i < nsyms; i++)
  584.     {
  585.     if (nullable[i])
  586.         printf("%s is nullable\n", symbol_name[i]);
  587.     else
  588.         printf("%s is not nullable\n", symbol_name[i]);
  589.     }
  590. #endif
  591. }
  592.  
  593.  
  594. free_nullable()
  595. {
  596.   FREE(nullable);
  597. }
  598.  
  599.  
  600. lr0()
  601. {
  602.     set_derives();
  603.     set_nullable();
  604.     generate_states();
  605. }
  606.