home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Bison.sit.hqx / Bison / Source / lalr.c < prev    next >
Text File  |  1992-08-21  |  14KB  |  782 lines
  1. /***********************************************************
  2.  *
  3.  * Macintosh/MPW version of GNU Bison 1.18
  4.  * Please read the README_MPW file for more information
  5.  *
  6.  ***********************************************************/
  7.  
  8. /* Compute look-ahead criteria for bison,
  9.    Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
  10.  
  11. This file is part of Bison, the GNU Compiler Compiler.
  12.  
  13. Bison is free software; you can redistribute it and/or modify
  14. it under the terms of the GNU General Public License as published by
  15. the Free Software Foundation; either version 2, or (at your option)
  16. any later version.
  17.  
  18. Bison is distributed in the hope that it will be useful,
  19. but WITHOUT ANY WARRANTY; without even the implied warranty of
  20. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21. GNU General Public License for more details.
  22.  
  23. You should have received a copy of the GNU General Public License
  24. along with Bison; see the file COPYING.  If not, write to
  25. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  26.  
  27.  
  28. /* Compute how to make the finite state machine deterministic;
  29.  find which rules need lookahead in each state, and which lookahead tokens they accept.
  30.  
  31. lalr(), the entry point, builds these data structures:
  32.  
  33. goto_map, from_state and to_state 
  34.  record each shift transition which accepts a variable (a nonterminal).
  35. ngotos is the number of such transitions.
  36. from_state[t] is the state number which a transition leads from
  37. and to_state[t] is the state number it leads to.
  38. All the transitions that accept a particular variable are grouped together and
  39. goto_map[i - ntokens] is the index in from_state and to_state of the first of them.
  40.  
  41. consistent[s] is nonzero if no lookahead is needed to decide what to do in state s.
  42.  
  43. LAruleno is a vector which records the rules that need lookahead in various states.
  44. The elements of LAruleno that apply to state s are those from
  45.  lookaheads[s] through lookaheads[s+1]-1.
  46. Each element of LAruleno is a rule number.
  47.  
  48. If lr is the length of LAruleno, then a number from 0 to lr-1 
  49. can specify both a rule and a state where the rule might be applied.
  50.  
  51. LA is a lr by ntokens matrix of bits.
  52. LA[l, i] is 1 if the rule LAruleno[l] is applicable in the appropriate state
  53.  when the next token is symbol i.
  54. If LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict.
  55. */
  56.  
  57. #include <stdio.h>
  58. #include "system.h"
  59. #include "machine.h"
  60. #include "types.h"
  61. #include "state.h"
  62. #include "new.h"
  63. #include "gram.h"
  64.  
  65. #ifdef macintosh
  66. #pragma segment bison
  67. #endif
  68.  
  69.  
  70. extern short **derives;
  71. extern char *nullable;
  72.  
  73.  
  74. int tokensetsize;
  75. short *lookaheads;
  76. short *LAruleno;
  77. unsigned *LA;
  78. short *accessing_symbol;
  79. char *consistent;
  80. core **state_table;
  81. shifts **shift_table;
  82. reductions **reduction_table;
  83. short *goto_map;
  84. short *from_state;
  85. short *to_state;
  86.  
  87. short **transpose();
  88. void set_state_table();
  89. void set_accessing_symbol();
  90. void set_shift_table();
  91. void set_reduction_table();
  92. void set_maxrhs();
  93. void initialize_LA();
  94. void set_goto_map();
  95. void initialize_F();
  96. void build_relations();
  97. void add_lookback_edge();
  98. void compute_FOLLOWS();
  99. void compute_lookaheads();
  100. void digraph();
  101. void traverse();
  102.  
  103. extern void toomany();
  104. extern void berror();
  105.  
  106. static int infinity;
  107. static int maxrhs;
  108. static int ngotos;
  109. static unsigned *F;
  110. static short **includes;
  111. static shorts **lookback;
  112. static short **R;
  113. static short *INDEX;
  114. static short *VERTICES;
  115. static int top;
  116.  
  117.  
  118. void
  119. lalr()
  120. {
  121.   tokensetsize = WORDSIZE(ntokens);
  122.  
  123.   set_state_table();
  124.   set_accessing_symbol();
  125.   set_shift_table();
  126.   set_reduction_table();
  127.   set_maxrhs();
  128.   initialize_LA();
  129.   set_goto_map();
  130.   initialize_F();
  131.   build_relations();
  132.   compute_FOLLOWS();
  133.   compute_lookaheads();
  134. }
  135.  
  136.  
  137. void
  138. set_state_table()
  139. {
  140.   register core *sp;
  141.  
  142.   state_table = NEW2(nstates, core *);
  143.  
  144.   for (sp = first_state; sp; sp = sp->next)
  145.     state_table[sp->number] = sp;
  146. }
  147.  
  148.  
  149. void
  150. set_accessing_symbol()
  151. {
  152.   register core *sp;
  153.  
  154.   accessing_symbol = NEW2(nstates, short);
  155.  
  156.   for (sp = first_state; sp; sp = sp->next)
  157.     accessing_symbol[sp->number] = sp->accessing_symbol;
  158. }
  159.  
  160.  
  161. void
  162. set_shift_table()
  163. {
  164.   register shifts *sp;
  165.  
  166.   shift_table = NEW2(nstates, shifts *);
  167.  
  168.   for (sp = first_shift; sp; sp = sp->next)
  169.     shift_table[sp->number] = sp;
  170. }
  171.  
  172.  
  173. void
  174. set_reduction_table()
  175. {
  176.   register reductions *rp;
  177.  
  178.   reduction_table = NEW2(nstates, reductions *);
  179.  
  180.   for (rp = first_reduction; rp; rp = rp->next)
  181.     reduction_table[rp->number] = rp;
  182. }
  183.  
  184.  
  185. void
  186. set_maxrhs()
  187. {
  188.   register short *itemp;
  189.   register int length;
  190.   register int max;
  191.  
  192.   length = 0;
  193.   max = 0;
  194.   for (itemp = ritem; *itemp; itemp++)
  195.     {
  196.       if (*itemp > 0)
  197.     {
  198.       length++;
  199.     }
  200.       else
  201.     {
  202.       if (length > max) max = length;
  203.       length = 0;
  204.     }
  205.     }
  206.  
  207.   maxrhs = max;
  208. }
  209.  
  210.  
  211. void
  212. initialize_LA()
  213. {
  214.   register int i;
  215.   register int j;
  216.   register int count;
  217.   register reductions *rp;
  218.   register shifts *sp;
  219.   register short *np;
  220.  
  221.   consistent = NEW2(nstates, char);
  222.   lookaheads = NEW2(nstates + 1, short);
  223.  
  224.   count = 0;
  225.   for (i = 0; i < nstates; i++)
  226.     {
  227.       register int k;
  228.  
  229.       lookaheads[i] = count;
  230.  
  231.       rp = reduction_table[i];
  232.       sp = shift_table[i];
  233.       if (rp && (rp->nreds > 1
  234.           || (sp && ! ISVAR(accessing_symbol[sp->shifts[0]]))))
  235.     count += rp->nreds;
  236.       else
  237.     consistent[i] = 1;
  238.  
  239.       if (sp)
  240.     for (k = 0; k < sp->nshifts; k++)
  241.       {
  242.         if (accessing_symbol[sp->shifts[k]] == error_token_number)
  243.           {
  244.         consistent[i] = 0;
  245.         break;
  246.           }
  247.       }
  248.     }
  249.  
  250.   lookaheads[nstates] = count;
  251.  
  252.   if (count == 0)
  253.     {
  254.       LA = NEW2(1 * tokensetsize, unsigned);
  255.       LAruleno = NEW2(1, short);
  256.       lookback = NEW2(1, shorts *);
  257.     }
  258.   else
  259.     {
  260.       LA = NEW2(count * tokensetsize, unsigned);
  261.       LAruleno = NEW2(count, short);
  262.       lookback = NEW2(count, shorts *);
  263.     }
  264.  
  265.   np = LAruleno;
  266.   for (i = 0; i < nstates; i++)
  267.     {
  268.       if (!consistent[i])
  269.     {
  270.       if (rp = reduction_table[i])
  271.         for (j = 0; j < rp->nreds; j++)
  272.           *np++ = rp->rules[j];
  273.     }
  274.     }
  275. }
  276.  
  277.  
  278. void
  279. set_goto_map()
  280. {
  281.   register shifts *sp;
  282.   register int i;
  283.   register int symbol;
  284.   register int k;
  285.   register short *temp_map;
  286.   register int state2;
  287.   register int state1;
  288.  
  289.   goto_map = NEW2(nvars + 1, short) - ntokens;
  290.   temp_map = NEW2(nvars + 1, short) - ntokens;
  291.  
  292.   ngotos = 0;
  293.   for (sp = first_shift; sp; sp = sp->next)
  294.     {
  295.       for (i = sp->nshifts - 1; i >= 0; i--)
  296.     {
  297.       symbol = accessing_symbol[sp->shifts[i]];
  298.  
  299.       if (ISTOKEN(symbol)) break;
  300.  
  301.       if (ngotos == MAXSHORT)
  302.         toomany("gotos");
  303.  
  304.       ngotos++;
  305.       goto_map[symbol]++;
  306.         }
  307.     }
  308.  
  309.   k = 0;
  310.   for (i = ntokens; i < nsyms; i++)
  311.     {
  312.       temp_map[i] = k;
  313.       k += goto_map[i];
  314.     }
  315.  
  316.   for (i = ntokens; i < nsyms; i++)
  317.     goto_map[i] = temp_map[i];
  318.  
  319.   goto_map[nsyms] = ngotos;
  320.   temp_map[nsyms] = ngotos;
  321.  
  322.   from_state = NEW2(ngotos, short);
  323.   to_state = NEW2(ngotos, short);
  324.  
  325.   for (sp = first_shift; sp; sp = sp->next)
  326.     {
  327.       state1 = sp->number;
  328.       for (i = sp->nshifts - 1; i >= 0; i--)
  329.     {
  330.       state2 = sp->shifts[i];
  331.       symbol = accessing_symbol[state2];
  332.  
  333.       if (ISTOKEN(symbol)) break;
  334.  
  335.       k = temp_map[symbol]++;
  336.       from_state[k] = state1;
  337.       to_state[k] = state2;
  338.     }
  339.     }
  340.  
  341.   FREE(temp_map + ntokens);
  342. }
  343.  
  344.  
  345.  
  346. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  347.  
  348. int
  349. map_goto(state, symbol)
  350. int state;
  351. int symbol;
  352. {
  353.   register int high;
  354.   register int low;
  355.   register int middle;
  356.   register int s;
  357.  
  358.   low = goto_map[symbol];
  359.   high = goto_map[symbol + 1] - 1;
  360.  
  361.   while (low <= high)
  362.     {
  363.       middle = (low + high) / 2;
  364.       s = from_state[middle];
  365.       if (s == state)
  366.     return (middle);
  367.       else if (s < state)
  368.     low = middle + 1;
  369.       else
  370.     high = middle - 1;
  371.     }
  372.  
  373.   berror("map_goto");
  374. /* NOTREACHED */
  375.   return 0;
  376. }
  377.  
  378.  
  379. void
  380. initialize_F()
  381. {
  382.   register int i;
  383.   register int j;
  384.   register int k;
  385.   register shifts *sp;
  386.   register short *edge;
  387.   register unsigned *rowp;
  388.   register short *rp;
  389.   register short **reads;
  390.   register int nedges;
  391.   register int stateno;
  392.   register int symbol;
  393.   register int nwords;
  394.  
  395.   nwords = ngotos * tokensetsize;
  396.   F = NEW2(nwords, unsigned);
  397.  
  398.   reads = NEW2(ngotos, short *);
  399.   edge = NEW2(ngotos + 1, short);
  400.   nedges = 0;
  401.  
  402.   rowp = F;
  403.   for (i = 0; i < ngotos; i++)
  404.     {
  405.       stateno = to_state[i];
  406.       sp = shift_table[stateno];
  407.  
  408.       if (sp)
  409.     {
  410.       k = sp->nshifts;
  411.  
  412.       for (j = 0; j < k; j++)
  413.         {
  414.           symbol = accessing_symbol[sp->shifts[j]];
  415.           if (ISVAR(symbol))
  416.         break;
  417.           SETBIT(rowp, symbol);
  418.         }
  419.  
  420.       for (; j < k; j++)
  421.         {
  422.           symbol = accessing_symbol[sp->shifts[j]];
  423.           if (nullable[symbol])
  424.         edge[nedges++] = map_goto(stateno, symbol);
  425.         }
  426.     
  427.       if (nedges)
  428.         {
  429.           reads[i] = rp = NEW2(nedges + 1, short);
  430.  
  431.           for (j = 0; j < nedges; j++)
  432.         rp[j] = edge[j];
  433.  
  434.           rp[nedges] = -1;
  435.           nedges = 0;
  436.         }
  437.     }
  438.  
  439.       rowp += tokensetsize;
  440.     }
  441.  
  442.   digraph(reads);
  443.  
  444.   for (i = 0; i < ngotos; i++)
  445.     {
  446.       if (reads[i])
  447.     FREE(reads[i]);
  448.     }
  449.  
  450.   FREE(reads);
  451.   FREE(edge);
  452. }
  453.  
  454.  
  455. void
  456. build_relations()
  457. {
  458.   register int i;
  459.   register int j;
  460.   register int k;
  461.   register short *rulep;
  462.   register short *rp;
  463.   register shifts *sp;
  464.   register int length;
  465.   register int nedges;
  466.   register int done;
  467.   register int state1;
  468.   register int stateno;
  469.   register int symbol1;
  470.   register int symbol2;
  471.   register short *shortp;
  472.   register short *edge;
  473.   register short *states;
  474.   register short **new_includes;
  475.  
  476.   includes = NEW2(ngotos, short *);
  477.   edge = NEW2(ngotos + 1, short);
  478.   states = NEW2(maxrhs + 1, short);
  479.  
  480.   for (i = 0; i < ngotos; i++)
  481.     {
  482.       nedges = 0;
  483.       state1 = from_state[i];
  484.       symbol1 = accessing_symbol[to_state[i]];
  485.  
  486.       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
  487.     {
  488.       length = 1;
  489.       states[0] = state1;
  490.       stateno = state1;
  491.  
  492.       for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
  493.         {
  494.           symbol2 = *rp;
  495.           sp = shift_table[stateno];
  496.           k = sp->nshifts;
  497.  
  498.           for (j = 0; j < k; j++)
  499.         {
  500.           stateno = sp->shifts[j];
  501.           if (accessing_symbol[stateno] == symbol2) break;
  502.         }
  503.  
  504.           states[length++] = stateno;
  505.         }
  506.  
  507.       if (!consistent[stateno])
  508.         add_lookback_edge(stateno, *rulep, i);
  509.  
  510.       length--;
  511.       done = 0;
  512.       while (!done)
  513.         {
  514.           done = 1;
  515.           rp--;
  516.             /* JF added rp>=ritem &&   I hope to god its right! */
  517.           if (rp>=ritem && ISVAR(*rp))
  518.         {
  519.           stateno = states[--length];
  520.           edge[nedges++] = map_goto(stateno, *rp);
  521.           if (nullable[*rp]) done = 0;
  522.         }
  523.         }
  524.     }
  525.  
  526.       if (nedges)
  527.     {
  528.       includes[i] = shortp = NEW2(nedges + 1, short);
  529.       for (j = 0; j < nedges; j++)
  530.         shortp[j] = edge[j];
  531.       shortp[nedges] = -1;
  532.     }
  533.     }
  534.  
  535.   new_includes = transpose(includes, ngotos);
  536.  
  537.   for (i = 0; i < ngotos; i++)
  538.     if (includes[i])
  539.       FREE(includes[i]);
  540.  
  541.   FREE(includes);
  542.  
  543.   includes = new_includes;
  544.  
  545.   FREE(edge);
  546.   FREE(states);
  547. }
  548.  
  549.  
  550. void
  551. add_lookback_edge(stateno, ruleno, gotono)
  552. int stateno;
  553. int ruleno;
  554. int gotono;
  555. {
  556.   register int i;
  557.   register int k;
  558.   register int found;
  559.   register shorts *sp;
  560.  
  561.   i = lookaheads[stateno];
  562.   k = lookaheads[stateno + 1];
  563.   found = 0;
  564.   while (!found && i < k)
  565.     {
  566.       if (LAruleno[i] == ruleno)
  567.     found = 1;
  568.       else
  569.     i++;
  570.     }
  571.  
  572.   if (found == 0)
  573.     berror("add_lookback_edge");
  574.  
  575.   sp = NEW(shorts);
  576.   sp->next = lookback[i];
  577.   sp->value = gotono;
  578.   lookback[i] = sp;
  579. }
  580.  
  581.  
  582.  
  583. short **
  584. transpose(R_arg, n)
  585. short **R_arg;
  586. int n;
  587. {
  588.   register short **new_R;
  589.   register short **temp_R;
  590.   register short *nedges;
  591.   register short *sp;
  592.   register int i;
  593.   register int k;
  594.  
  595.   nedges = NEW2(n, short);
  596.  
  597.   for (i = 0; i < n; i++)
  598.     {
  599.       sp = R_arg[i];
  600.       if (sp)
  601.     {
  602.       while (*sp >= 0)
  603.         nedges[*sp++]++;
  604.     }
  605.     }
  606.  
  607.   new_R = NEW2(n, short *);
  608.   temp_R = NEW2(n, short *);
  609.  
  610.   for (i = 0; i < n; i++)
  611.     {
  612.       k = nedges[i];
  613.       if (k > 0)
  614.     {
  615.       sp = NEW2(k + 1, short);
  616.       new_R[i] = sp;
  617.       temp_R[i] = sp;
  618.       sp[k] = -1;
  619.     }
  620.     }
  621.  
  622.   FREE(nedges);
  623.  
  624.   for (i = 0; i < n; i++)
  625.     {
  626.       sp = R_arg[i];
  627.       if (sp)
  628.     {
  629.       while (*sp >= 0)
  630.         *temp_R[*sp++]++ = i;
  631.     }
  632.     }
  633.  
  634.   FREE(temp_R);
  635.  
  636.   return (new_R);
  637. }
  638.  
  639.  
  640. void
  641. compute_FOLLOWS()
  642. {
  643.   register int i;
  644.  
  645.   digraph(includes);
  646.  
  647.   for (i = 0; i < ngotos; i++)
  648.     {
  649.       if (includes[i]) FREE(includes[i]);
  650.     }
  651.  
  652.   FREE(includes);
  653. }
  654.  
  655.  
  656. void
  657. compute_lookaheads()
  658. {
  659.   register int i;
  660.   register int n;
  661.   register unsigned *fp1;
  662.   register unsigned *fp2;
  663.   register unsigned *fp3;
  664.   register shorts *sp;
  665.   register unsigned *rowp;
  666. /*   register short *rulep; JF unused */
  667. /*  register int count; JF unused */
  668.   register shorts *sptmp;/* JF */
  669.  
  670.   rowp = LA;
  671.   n = lookaheads[nstates];
  672.   for (i = 0; i < n; i++)
  673.     {
  674.       fp3 = rowp + tokensetsize;
  675.       for (sp = lookback[i]; sp; sp = sp->next)
  676.     {
  677.       fp1 = rowp;
  678.       fp2 = F + tokensetsize * sp->value;
  679.       while (fp1 < fp3)
  680.         *fp1++ |= *fp2++;
  681.     }
  682.  
  683.       rowp = fp3;
  684.     }
  685.  
  686.   for (i = 0; i < n; i++)
  687.     {/* JF removed ref to freed storage */
  688.       for (sp = lookback[i]; sp; sp = sptmp) {
  689.     sptmp=sp->next;
  690.     FREE(sp);
  691.       }
  692.     }
  693.  
  694.   FREE(lookback);
  695.   FREE(F);
  696. }
  697.  
  698.  
  699. void
  700. digraph(relation)
  701. short **relation;
  702. {
  703.   register int i;
  704.  
  705.   infinity = ngotos + 2;
  706.   INDEX = NEW2(ngotos + 1, short);
  707.   VERTICES = NEW2(ngotos + 1, short);
  708.   top = 0;
  709.  
  710.   R = relation;
  711.  
  712.   for (i = 0; i < ngotos; i++)
  713.     INDEX[i] = 0;
  714.  
  715.   for (i = 0; i < ngotos; i++)
  716.     {
  717.       if (INDEX[i] == 0 && R[i])
  718.     traverse(i);
  719.     }
  720.  
  721.   FREE(INDEX);
  722.   FREE(VERTICES);
  723. }
  724.  
  725.  
  726. void
  727. traverse(i)
  728. register int i;
  729. {
  730.   register unsigned *fp1;
  731.   register unsigned *fp2;
  732.   register unsigned *fp3;
  733.   register int j;
  734.   register short *rp;
  735.  
  736.   int height;
  737.   unsigned *base;
  738.  
  739.   VERTICES[++top] = i;
  740.   INDEX[i] = height = top;
  741.  
  742.   base = F + i * tokensetsize;
  743.   fp3 = base + tokensetsize;
  744.  
  745.   rp = R[i];
  746.   if (rp)
  747.     {
  748.       while ((j = *rp++) >= 0)
  749.     {
  750.       if (INDEX[j] == 0)
  751.         traverse(j);
  752.  
  753.       if (INDEX[i] > INDEX[j])
  754.         INDEX[i] = INDEX[j];
  755.  
  756.       fp1 = base;
  757.       fp2 = F + j * tokensetsize;
  758.  
  759.       while (fp1 < fp3)
  760.         *fp1++ |= *fp2++;
  761.     }
  762.     }
  763.  
  764.   if (INDEX[i] == height)
  765.     {
  766.       for (;;)
  767.     {
  768.       j = VERTICES[top--];
  769.       INDEX[j] = infinity;
  770.  
  771.       if (i == j)
  772.         break;
  773.  
  774.       fp1 = base;
  775.       fp2 = F + j * tokensetsize;
  776.  
  777.       while (fp1 < fp3)
  778.         *fp2++ = *fp1++;
  779.     }
  780.     }
  781. }
  782.