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