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