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