home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / mpw-perl-byacc1.8.1.sit.hqx / mpw-perl-byacc1.8.1 / lr0.c < prev    next >
Text File  |  1992-10-20  |  10KB  |  610 lines
  1.  
  2. #include "defs.h"
  3.  
  4. extern short *itemset;
  5. extern short *itemsetend;
  6. extern unsigned *ruleset;
  7.  
  8. int nstates;
  9. core *first_state;
  10. shifts *first_shift;
  11. reductions *first_reduction;
  12.  
  13. int get_state();
  14. core *new_state();
  15.  
  16. static core **state_set;
  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.  
  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. allocate_storage()
  76. {
  77.     allocate_itemsets();
  78.     shiftset = NEW2(nsyms, short);
  79.     redset = NEW2(nrules + 1, short);
  80.     state_set = NEW2(nitems, core *);
  81. }
  82.  
  83.  
  84. append_states()
  85. {
  86.     register int i;
  87.     register int j;
  88.     register int symbol;
  89.  
  90. #ifdef    TRACE
  91.     fprintf(stderr, "Entering append_states()\n");
  92. #endif
  93.     for (i = 1; i < nshifts; i++)
  94.     {
  95.     symbol = shift_symbol[i];
  96.     j = i;
  97.  
  98.     Cooperate();
  99.  
  100.     while (j > 0 && shift_symbol[j - 1] > symbol)
  101.     {
  102.         shift_symbol[j] = shift_symbol[j - 1];
  103.         j--;
  104.     }
  105.     shift_symbol[j] = symbol;
  106.     }
  107.  
  108.     for (i = 0; i < nshifts; i++)
  109.     {
  110.     symbol = shift_symbol[i];
  111.     shiftset[i] = get_state(symbol);
  112.     }
  113. }
  114.  
  115.  
  116. free_storage()
  117. {
  118.     FREE(shift_symbol);
  119.     FREE(redset);
  120.     FREE(shiftset);
  121.     FREE(kernel_base);
  122.     FREE(kernel_end);
  123.     FREE(kernel_items);
  124.     FREE(state_set);
  125. }
  126.  
  127.  
  128.  
  129. generate_states()
  130. {
  131.     allocate_storage();
  132.     itemset = NEW2(nitems, short);
  133.     ruleset = NEW2(WORDSIZE(nrules), unsigned);
  134.     set_first_derives();
  135.     initialize_states();
  136.  
  137.     while (this_state)
  138.     {
  139.     Cooperate();
  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.     register int n;
  168.  
  169. #ifdef    TRACE
  170.     fprintf(stderr, "Entering get_state(%d)\n", symbol);
  171. #endif
  172.  
  173.     isp1 = kernel_base[symbol];
  174.     iend = kernel_end[symbol];
  175.     n = iend - isp1;
  176.  
  177.     key = *isp1;
  178.     assert(0 <= key && key < nitems);
  179.     sp = state_set[key];
  180.     if (sp)
  181.     {
  182.     found = 0;
  183.     while (!found)
  184.     {
  185.         if (sp->nitems == n)
  186.         {
  187.         found = 1;
  188.         isp1 = kernel_base[symbol];
  189.         isp2 = sp->items;
  190.  
  191.         Cooperate();
  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_set[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.         if (!ksp)
  271.         {
  272.         shift_symbol[shiftcount++] = symbol;
  273.         ksp = kernel_base[symbol];
  274.         }
  275.  
  276.         *ksp++ = i + 1;
  277.         kernel_end[symbol] = ksp;
  278.     }
  279.     }
  280.  
  281.     nshifts = shiftcount;
  282. }
  283.  
  284.  
  285.  
  286. core *
  287. new_state(symbol)
  288. int symbol;
  289. {
  290.     register int n;
  291.     register core *p;
  292.     register short *isp1;
  293.     register short *isp2;
  294.     register short *iend;
  295.  
  296. #ifdef    TRACE
  297.     fprintf(stderr, "Entering new_state(%d)\n", symbol);
  298. #endif
  299.  
  300.     if (nstates >= MAXSHORT)
  301.     fatal("too many states");
  302.  
  303.     isp1 = kernel_base[symbol];
  304.     iend = kernel_end[symbol];
  305.     n = iend - isp1;
  306.  
  307.     p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  308.     p->accessing_symbol = symbol;
  309.     p->number = nstates;
  310.     p->nitems = n;
  311.  
  312.     isp2 = p->items;
  313.     while (isp1 < iend)
  314.     *isp2++ = *isp1++;
  315.  
  316.     last_state->next = p;
  317.     last_state = p;
  318.  
  319.     nstates++;
  320.  
  321.     return (p);
  322. }
  323.  
  324.  
  325. /* show_cores is used for debugging */
  326.  
  327. show_cores()
  328. {
  329.     core *p;
  330.     int i, j, k, n;
  331.     int itemno;
  332.  
  333.     k = 0;
  334.     for (p = first_state; p; ++k, p = p->next)
  335.     {
  336.     if (k) printf("\n");
  337.     printf("state %d, number = %d, accessing symbol = %s\n",
  338.         k, p->number, symbol_name[p->accessing_symbol]);
  339.     n = p->nitems;
  340.     for (i = 0; i < n; ++i)
  341.     {
  342.         itemno = p->items[i];
  343.         printf("%4d  ", itemno);
  344.         j = itemno;
  345.         while (ritem[j] >= 0) ++j;
  346.         printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  347.         j = rrhs[-ritem[j]];
  348.         while (j < itemno)
  349.         printf(" %s", symbol_name[ritem[j++]]);
  350.         printf(" .");
  351.         while (ritem[j] >= 0)
  352.         printf(" %s", symbol_name[ritem[j++]]);
  353.         printf("\n");
  354.         fflush(stdout);
  355.     }
  356.     }
  357. }
  358.  
  359.  
  360. /* show_ritems is used for debugging */
  361.  
  362. show_ritems()
  363. {
  364.     int i;
  365.  
  366.     for (i = 0; i < nitems; ++i)
  367.     printf("ritem[%d] = %d\n", i, ritem[i]);
  368. }
  369.  
  370.  
  371. /* show_rrhs is used for debugging */
  372. show_rrhs()
  373. {
  374.     int i;
  375.  
  376.     for (i = 0; i < nrules; ++i)
  377.     printf("rrhs[%d] = %d\n", i, rrhs[i]);
  378. }
  379.  
  380.  
  381. /* show_shifts is used for debugging */
  382.  
  383. show_shifts()
  384. {
  385.     shifts *p;
  386.     int i, j, k;
  387.  
  388.     k = 0;
  389.     for (p = first_shift; p; ++k, p = p->next)
  390.     {
  391.     if (k) printf("\n");
  392.     printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  393.         p->nshifts);
  394.     j = p->nshifts;
  395.     for (i = 0; i < j; ++i)
  396.         printf("\t%d\n", p->shift[i]);
  397.     }
  398. }
  399.  
  400.  
  401. save_shifts()
  402. {
  403.     register shifts *p;
  404.     register short *sp1;
  405.     register short *sp2;
  406.     register short *send;
  407.  
  408.     p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  409.             (nshifts - 1) * sizeof(short)));
  410.  
  411.     p->number = this_state->number;
  412.     p->nshifts = nshifts;
  413.  
  414.     sp1 = shiftset;
  415.     sp2 = p->shift;
  416.     send = shiftset + nshifts;
  417.  
  418.     while (sp1 < send)
  419.     *sp2++ = *sp1++;
  420.  
  421.     if (last_shift)
  422.     {
  423.     last_shift->next = p;
  424.     last_shift = p;
  425.     }
  426.     else
  427.     {
  428.     first_shift = p;
  429.     last_shift = p;
  430.     }
  431. }
  432.  
  433.  
  434.  
  435. save_reductions()
  436. {
  437.     register short *isp;
  438.     register short *rp1;
  439.     register short *rp2;
  440.     register int item;
  441.     register int count;
  442.     register reductions *p;
  443.     register short *rend;
  444.  
  445.     count = 0;
  446.     for (isp = itemset; isp < itemsetend; isp++)
  447.     {
  448.     Cooperate();
  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.     Cooperate();
  499.     derives[lhs] = rules + k;
  500.     for (i = 0; i < nrules; i++)
  501.     {
  502.         if (rlhs[i] == lhs)
  503.         {
  504.         rules[k] = i;
  505.         k++;
  506.         }
  507.     }
  508.     rules[k] = -1;
  509.     k++;
  510.     }
  511.  
  512. #ifdef    DEBUG
  513.     print_derives();
  514. #endif
  515. }
  516.  
  517. free_derives()
  518. {
  519.     FREE(derives[start_symbol]);
  520.     FREE(derives);
  521. }
  522.  
  523. #ifdef    DEBUG
  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.     Cooperate();
  534.  
  535.     printf("%s derives ", symbol_name[i]);
  536.     for (sp = derives[i]; *sp >= 0; sp++)
  537.     {
  538.         printf("  %d", *sp);
  539.     }
  540.     putchar('\n');
  541.     }
  542.  
  543.     putchar('\n');
  544. }
  545. #endif
  546.  
  547.  
  548. set_nullable()
  549. {
  550.     register int i, j;
  551.     register int empty;
  552.     int done;
  553.  
  554.     nullable = MALLOC(nsyms);
  555.     if (nullable == 0) no_space();
  556.  
  557.     for (i = 0; i < nsyms; ++i)
  558.     nullable[i] = 0;
  559.  
  560.     done = 0;
  561.     while (!done)
  562.     {
  563.     done = 1;
  564.     for (i = 1; i < nitems; i++)
  565.     {
  566.         empty = 1;
  567.         Cooperate();
  568.         while ((j = ritem[i]) >= 0)
  569.         {
  570.         if (!nullable[j])
  571.             empty = 0;
  572.         ++i;
  573.         }
  574.         if (empty)
  575.         {
  576.         j = rlhs[-j];
  577.         if (!nullable[j])
  578.         {
  579.             nullable[j] = 1;
  580.             done = 0;
  581.         }
  582.         }
  583.     }
  584.     }
  585.  
  586. #ifdef DEBUG
  587.     for (i = 0; i < nsyms; i++)
  588.     {
  589.     if (nullable[i])
  590.         printf("%s is nullable\n", symbol_name[i]);
  591.     else
  592.         printf("%s is not nullable\n", symbol_name[i]);
  593.     }
  594. #endif
  595. }
  596.  
  597.  
  598. free_nullable()
  599. {
  600.     FREE(nullable);
  601. }
  602.  
  603.  
  604. lr0()
  605. {
  606.     set_derives();
  607.     set_nullable();
  608.     generate_states();
  609. }
  610.