home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / BYACC.ZIP / RCS / LALR.C_V < prev    next >
Text File  |  1992-06-10  |  10KB  |  658 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. typedef
  26.   struct shorts
  27.     {
  28.       struct shorts *next;
  29.       short value;
  30.     }
  31.   shorts;
  32.  
  33. int tokensetsize;
  34. short *lookaheads;
  35. short *LAruleno;
  36. unsigned *LA;
  37. short *accessing_symbol;
  38. core **state_table;
  39. shifts **shift_table;
  40. reductions **reduction_table;
  41. short *goto_map;
  42. short *from_state;
  43. short *to_state;
  44.  
  45. short **transpose();
  46.  
  47. static int infinity;
  48. static int maxrhs;
  49. static int ngotos;
  50. static unsigned *F;
  51. static short **includes;
  52. static shorts **lookback;
  53. static short **R;
  54. static short *INDEX;
  55. static short *VERTICES;
  56. static int top;
  57.  
  58.  
  59. lalr()
  60. {
  61.     tokensetsize = WORDSIZE(ntokens);
  62.  
  63.     set_state_table();
  64.     set_accessing_symbol();
  65.     set_shift_table();
  66.     set_reduction_table();
  67.     set_maxrhs();
  68.     initialize_LA();
  69.     set_goto_map();
  70.     initialize_F();
  71.     build_relations();
  72.     compute_FOLLOWS();
  73.     compute_lookaheads();
  74. }
  75.  
  76.  
  77.  
  78. set_state_table()
  79. {
  80.     register core *sp;
  81.  
  82.     state_table = NEW2(nstates, core *);
  83.     for (sp = first_state; sp; sp = sp->next)
  84.     state_table[sp->number] = sp;
  85. }
  86.  
  87.  
  88.  
  89. set_accessing_symbol()
  90. {
  91.     register core *sp;
  92.  
  93.     accessing_symbol = NEW2(nstates, short);
  94.     for (sp = first_state; sp; sp = sp->next)
  95.     accessing_symbol[sp->number] = sp->accessing_symbol;
  96. }
  97.  
  98.  
  99.  
  100. set_shift_table()
  101. {
  102.     register shifts *sp;
  103.  
  104.     shift_table = NEW2(nstates, shifts *);
  105.     for (sp = first_shift; sp; sp = sp->next)
  106.     shift_table[sp->number] = sp;
  107. }
  108.  
  109.  
  110.  
  111. set_reduction_table()
  112. {
  113.     register reductions *rp;
  114.  
  115.     reduction_table = NEW2(nstates, reductions *);
  116.     for (rp = first_reduction; rp; rp = rp->next)
  117.     reduction_table[rp->number] = rp;
  118. }
  119.  
  120.  
  121.  
  122. set_maxrhs()
  123. {
  124.   register short *itemp;
  125.   register short *item_end;
  126.   register int length;
  127.   register int max;
  128.  
  129.   length = 0;
  130.   max = 0;
  131.   item_end = ritem + nitems;
  132.   for (itemp = ritem; itemp < item_end; itemp++)
  133.     {
  134.       if (*itemp >= 0)
  135.     {
  136.       length++;
  137.     }
  138.       else
  139.     {
  140.       if (length > max) max = length;
  141.       length = 0;
  142.     }
  143.     }
  144.  
  145.   maxrhs = max;
  146. }
  147.  
  148.  
  149.  
  150. initialize_LA()
  151. {
  152.   register int i, j, k;
  153.   register reductions *rp;
  154.  
  155.   lookaheads = NEW2(nstates + 1, short);
  156.  
  157.   k = 0;
  158.   for (i = 0; i < nstates; i++)
  159.     {
  160.       lookaheads[i] = k;
  161.       rp = reduction_table[i];
  162.       if (rp)
  163.     k += rp->nreds;
  164.     }
  165.   lookaheads[nstates] = k;
  166.  
  167.   LA = NEW2(k * tokensetsize, unsigned);
  168.   LAruleno = NEW2(k, short);
  169.   lookback = NEW2(k, shorts *);
  170.  
  171.   k = 0;
  172.   for (i = 0; i < nstates; i++)
  173.     {
  174.       rp = reduction_table[i];
  175.       if (rp)
  176.     {
  177.       for (j = 0; j < rp->nreds; j++)
  178.         {
  179.           LAruleno[k] = rp->rules[j];
  180.           k++;
  181.         }
  182.     }
  183.     }
  184. }
  185.  
  186.  
  187. set_goto_map()
  188. {
  189.   register shifts *sp;
  190.   register int i;
  191.   register int symbol;
  192.   register int k;
  193.   register short *temp_map;
  194.   register int state2;
  195.   register int state1;
  196.  
  197.   goto_map = NEW2(nvars + 1, short) - ntokens;
  198.   temp_map = NEW2(nvars + 1, short) - ntokens;
  199.  
  200.   ngotos = 0;
  201.   for (sp = first_shift; sp; sp = sp->next)
  202.     {
  203.       for (i = sp->nshifts - 1; i >= 0; i--)
  204.     {
  205.       symbol = accessing_symbol[sp->shifts[i]];
  206.  
  207.       if (ISTOKEN(symbol)) break;
  208.  
  209.       if (ngotos == MAXSHORT)
  210.         fatal("too many gotos");
  211.  
  212.       ngotos++;
  213.       goto_map[symbol]++;
  214.         }
  215.     }
  216.  
  217.   k = 0;
  218.   for (i = ntokens; i < nsyms; i++)
  219.     {
  220.       temp_map[i] = k;
  221.       k += goto_map[i];
  222.     }
  223.  
  224.   for (i = ntokens; i < nsyms; i++)
  225.     goto_map[i] = temp_map[i];
  226.  
  227.   goto_map[nsyms] = ngotos;
  228.   temp_map[nsyms] = ngotos;
  229.  
  230.   from_state = NEW2(ngotos, short);
  231.   to_state = NEW2(ngotos, short);
  232.  
  233.   for (sp = first_shift; sp; sp = sp->next)
  234.     {
  235.       state1 = sp->number;
  236.       for (i = sp->nshifts - 1; i >= 0; i--)
  237.     {
  238.       state2 = sp->shifts[i];
  239.       symbol = accessing_symbol[state2];
  240.  
  241.       if (ISTOKEN(symbol)) break;
  242.  
  243.       k = temp_map[symbol]++;
  244.       from_state[k] = state1;
  245.       to_state[k] = state2;
  246.     }
  247.     }
  248.  
  249.   FREE(temp_map + ntokens);
  250. }
  251.  
  252.  
  253.  
  254. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  255.  
  256. int
  257. map_goto(state, symbol)
  258. int state;
  259. int symbol;
  260. {
  261.     register int high;
  262.     register int low;
  263.     register int middle;
  264.     register int s;
  265.  
  266.     low = goto_map[symbol];
  267.     high = goto_map[symbol + 1];
  268.  
  269.     for (;;)
  270.     {
  271.     assert(low <= high);
  272.     middle = (low + high) >> 1;
  273.     s = from_state[middle];
  274.     if (s == state)
  275.         return (middle);
  276.     else if (s < state)
  277.         low = middle + 1;
  278.     else
  279.         high = middle - 1;
  280.     }
  281. }
  282.  
  283.  
  284.  
  285. initialize_F()
  286. {
  287.   register int i;
  288.   register int j;
  289.   register int k;
  290.   register shifts *sp;
  291.   register short *edge;
  292.   register unsigned *rowp;
  293.   register short *rp;
  294.   register short **reads;
  295.   register int nedges;
  296.   register int stateno;
  297.   register int symbol;
  298.   register int nwords;
  299.  
  300.   nwords = ngotos * tokensetsize;
  301.   F = NEW2(nwords, unsigned);
  302.  
  303.   reads = NEW2(ngotos, short *);
  304.   edge = NEW2(ngotos + 1, short);
  305.   nedges = 0;
  306.  
  307.   rowp = F;
  308.   for (i = 0; i < ngotos; i++)
  309.     {
  310.       stateno = to_state[i];
  311.       sp = shift_table[stateno];
  312.  
  313.       if (sp)
  314.     {
  315.       k = sp->nshifts;
  316.  
  317.       for (j = 0; j < k; j++)
  318.         {
  319.           symbol = accessing_symbol[sp->shifts[j]];
  320.           if (ISVAR(symbol))
  321.         break;
  322.           SETBIT(rowp, symbol);
  323.         }
  324.  
  325.       for (; j < k; j++)
  326.         {
  327.           symbol = accessing_symbol[sp->shifts[j]];
  328.           if (nullable[symbol])
  329.         edge[nedges++] = map_goto(stateno, symbol);
  330.         }
  331.     
  332.       if (nedges)
  333.         {
  334.           reads[i] = rp = NEW2(nedges + 1, short);
  335.  
  336.           for (j = 0; j < nedges; j++)
  337.         rp[j] = edge[j];
  338.  
  339.           rp[nedges] = -1;
  340.           nedges = 0;
  341.         }
  342.     }
  343.  
  344.       rowp += tokensetsize;
  345.     }
  346.  
  347.   SETBIT(F, 0);
  348.   digraph(reads);
  349.  
  350.   for (i = 0; i < ngotos; i++)
  351.     {
  352.       if (reads[i])
  353.     FREE(reads[i]);
  354.     }
  355.  
  356.   FREE(reads);
  357.   FREE(edge);
  358. }
  359.  
  360.  
  361.  
  362. build_relations()
  363. {
  364.   register int i;
  365.   register int j;
  366.   register int k;
  367.   register short *rulep;
  368.   register short *rp;
  369.   register shifts *sp;
  370.   register int length;
  371.   register int nedges;
  372.   register int done;
  373.   register int state1;
  374.   register int stateno;
  375.   register int symbol1;
  376.   register int symbol2;
  377.   register short *shortp;
  378.   register short *edge;
  379.   register short *states;
  380.   register short **new_includes;
  381.  
  382.   includes = NEW2(ngotos, short *);
  383.   edge = NEW2(ngotos + 1, short);
  384.   states = NEW2(maxrhs + 1, short);
  385.  
  386.   for (i = 0; i < ngotos; i++)
  387.     {
  388.       nedges = 0;
  389.       state1 = from_state[i];
  390.       symbol1 = accessing_symbol[to_state[i]];
  391.  
  392.       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  393.     {
  394.       length = 1;
  395.       states[0] = state1;
  396.       stateno = state1;
  397.  
  398.       for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
  399.         {
  400.           symbol2 = *rp;
  401.           sp = shift_table[stateno];
  402.           k = sp->nshifts;
  403.  
  404.           for (j = 0; j < k; j++)
  405.         {
  406.           stateno = sp->shifts[j];
  407.           if (accessing_symbol[stateno] == symbol2) break;
  408.         }
  409.  
  410.           states[length++] = stateno;
  411.         }
  412.  
  413.       add_lookback_edge(stateno, *rulep, i);
  414.  
  415.       length--;
  416.       done = 0;
  417.       while (!done)
  418.         {
  419.           done = 1;
  420.           rp--;
  421.           if (ISVAR(*rp))
  422.         {
  423.           stateno = states[--length];
  424.           edge[nedges++] = map_goto(stateno, *rp);
  425.           if (nullable[*rp] && length > 0) done = 0;
  426.         }
  427.         }
  428.     }
  429.  
  430.       if (nedges)
  431.     {
  432.       includes[i] = shortp = NEW2(nedges + 1, short);
  433.       for (j = 0; j < nedges; j++)
  434.         shortp[j] = edge[j];
  435.       shortp[nedges] = -1;
  436.     }
  437.     }
  438.  
  439.   new_includes = transpose(includes, ngotos);
  440.  
  441.   for (i = 0; i < ngotos; i++)
  442.     FREE(includes[i]);
  443.  
  444.   FREE(includes);
  445.  
  446.   includes = new_includes;
  447.  
  448.   FREE(edge);
  449.   FREE(states);
  450. }
  451.  
  452.  
  453. add_lookback_edge(stateno, ruleno, gotono)
  454. int stateno, ruleno, gotono;
  455. {
  456.     register int i, k;
  457.     register int found;
  458.     register shorts *sp;
  459.  
  460.     i = lookaheads[stateno];
  461.     k = lookaheads[stateno + 1];
  462.     found = 0;
  463.     while (!found && i < k)
  464.     {
  465.     if (LAruleno[i] == ruleno)
  466.         found = 1;
  467.     else
  468.         ++i;
  469.     }
  470.     assert(found);
  471.  
  472.     sp = NEW(shorts);
  473.     sp->next = lookback[i];
  474.     sp->value = gotono;
  475.     lookback[i] = sp;
  476. }
  477.  
  478.  
  479.  
  480. short **
  481. transpose(R, n)
  482. short **R;
  483. int n;
  484. {
  485.   register short **new_R;
  486.   register short **temp_R;
  487.   register short *nedges;
  488.   register short *sp;
  489.   register int i;
  490.   register int k;
  491.  
  492.   nedges = NEW2(n, short);
  493.  
  494.   for (i = 0; i < n; i++)
  495.     {
  496.       sp = R[i];
  497.       if (sp)
  498.     {
  499.       while (*sp >= 0)
  500.         nedges[*sp++]++;
  501.     }
  502.     }
  503.  
  504.   new_R = NEW2(n, short *);
  505.   temp_R = NEW2(n, short *);
  506.  
  507.   for (i = 0; i < n; i++)
  508.     {
  509.       k = nedges[i];
  510.       if (k > 0)
  511.     {
  512.       sp = NEW2(k + 1, short);
  513.       new_R[i] = sp;
  514.       temp_R[i] = sp;
  515.       sp[k] = -1;
  516.     }
  517.     }
  518.  
  519.   FREE(nedges);
  520.  
  521.   for (i = 0; i < n; i++)
  522.     {
  523.       sp = R[i];
  524.       if (sp)
  525.     {
  526.       while (*sp >= 0)
  527.         *temp_R[*sp++]++ = i;
  528.     }
  529.     }
  530.  
  531.   FREE(temp_R);
  532.  
  533.   return (new_R);
  534. }
  535.  
  536.  
  537.  
  538. compute_FOLLOWS()
  539. {
  540.   digraph(includes);
  541. }
  542.  
  543.  
  544. compute_lookaheads()
  545. {
  546.   register int i, n;
  547.   register unsigned *fp1, *fp2, *fp3;
  548.   register shorts *sp;
  549.   register unsigned *rowp;
  550.  
  551.   rowp = LA;
  552.   n = lookaheads[nstates];
  553.   for (i = 0; i < n; i++)
  554.     {
  555.       fp3 = rowp + tokensetsize;
  556.       for (sp = lookback[i]; sp; sp = sp->next)
  557.     {
  558.       fp1 = rowp;
  559.       fp2 = F + tokensetsize * sp->value;
  560.       while (fp1 < fp3)
  561.         *fp1++ |= *fp2++;
  562.     }
  563.       rowp = fp3;
  564.     }
  565.  
  566.   for (i = 0; i < n; i++)
  567.     for (sp = lookback[i]; sp; sp = sp->next)
  568.       FREE(sp);
  569.  
  570.   FREE(lookback);
  571.   FREE(F);
  572. }
  573.  
  574.  
  575. digraph(relation)
  576. short **relation;
  577. {
  578.   register int i;
  579.  
  580.   infinity = ngotos + 2;
  581.   INDEX = NEW2(ngotos + 1, short);
  582.   VERTICES = NEW2(ngotos + 1, short);
  583.   top = 0;
  584.  
  585.   R = relation;
  586.  
  587.   for (i = 0; i < ngotos; i++)
  588.     INDEX[i] = 0;
  589.  
  590.   for (i = 0; i < ngotos; i++)
  591.     {
  592.       if (INDEX[i] == 0 && R[i])
  593.     traverse(i);
  594.     }
  595.  
  596.   FREE(INDEX);
  597.   FREE(VERTICES);
  598. }
  599.  
  600.  
  601.  
  602. traverse(i)
  603. register int i;
  604. {
  605.   register unsigned *fp1;
  606.   register unsigned *fp2;
  607.   register unsigned *fp3;
  608.   register int j;
  609.   register short *rp;
  610.  
  611.   int height;
  612.   unsigned *base;
  613.  
  614.   VERTICES[++top] = i;
  615.   INDEX[i] = height = top;
  616.  
  617.   base = F + i * tokensetsize;
  618.   fp3 = base + tokensetsize;
  619.  
  620.   rp = R[i];
  621.   if (rp)
  622.     {
  623.       while ((j = *rp++) >= 0)
  624.     {
  625.       if (INDEX[j] == 0)
  626.         traverse(j);
  627.  
  628.       if (INDEX[i] > INDEX[j])
  629.         INDEX[i] = INDEX[j];
  630.  
  631.       fp1 = base;
  632.       fp2 = F + j * tokensetsize;
  633.  
  634.       while (fp1 < fp3)
  635.         *fp1++ |= *fp2++;
  636.     }
  637.     }
  638.  
  639.   if (INDEX[i] == height)
  640.     {
  641.       for (;;)
  642.     {
  643.       j = VERTICES[top--];
  644.       INDEX[j] = infinity;
  645.  
  646.       if (i == j)
  647.         break;
  648.  
  649.       fp1 = base;
  650.       fp2 = F + j * tokensetsize;
  651.  
  652.       while (fp1 < fp3)
  653.         *fp2++ = *fp1++;
  654.     }
  655.     }
  656. }
  657. @
  658.