home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / utility / bison / conflict.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-07-11  |  14.2 KB  |  583 lines
  1. /* Find and resolve or report look-ahead conflicts for bison,
  2.    Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
  3.  
  4. BISON is distributed in the hope that it will be useful, but WITHOUT ANY
  5. WARRANTY.  No author or distributor accepts responsibility to anyone
  6. for the consequences of using it or for whether it serves any
  7. particular purpose or works at all, unless he says so in writing.
  8. Refer to the BISON General Public License for full details.
  9.  
  10. Everyone is granted permission to copy, modify and redistribute BISON,
  11. but only under the conditions described in the BISON General Public
  12. License.  A copy of this license is supposed to have been given to you
  13. along with BISON so you can know your rights and responsibilities.  It
  14. should be in a file named COPYING.  Among other things, the copyright
  15. notice and this notice must be preserved on all copies.
  16.  
  17.  In other words, you are welcome to use, share and improve this program.
  18.  You are forbidden to forbid anyone else to use, share and improve
  19.  what you give them.   Help stamp out software-hoarding!  */
  20.  
  21. #include <stdio.h>
  22. #include "machine.h"
  23. #include "new.h"
  24. #include "files.h"
  25. #include "gram.h"
  26. #include "state.h"
  27.  
  28.  
  29. extern char **tags;
  30. extern int tokensetsize;
  31. extern char *consistent;
  32. extern short *accessing_symbol;
  33. extern shifts **shift_table;
  34. extern unsigned *LA;
  35. extern short *LAruleno;
  36. extern short *lookaheads;
  37. extern int verboseflag;
  38.  
  39. char any_conflicts;
  40. char *conflicts;
  41. errs **err_table;
  42. int expected_conflicts;
  43.  
  44.  
  45. static unsigned *shiftset;
  46. static unsigned *lookaheadset;
  47. static int src_total;
  48. static int rrc_total;
  49. static int src_count;
  50. static int rrc_count;
  51.  
  52.  
  53.  
  54. initialize_conflicts()
  55. {
  56.   register int i;
  57. /*  register errs *sp; JF unused */
  58.  
  59.   conflicts = NEW2(nstates, char);
  60.   shiftset = NEW2(tokensetsize, unsigned);
  61.   lookaheadset = NEW2(tokensetsize, unsigned);
  62.  
  63.   err_table = NEW2(nstates, errs *);
  64.  
  65.   any_conflicts = 0;
  66.  
  67.   for (i = 0; i < nstates; i++)
  68.     set_conflicts(i);
  69. }
  70.  
  71.  
  72.  
  73. set_conflicts(state)
  74. int state;
  75. {
  76.   register int i;
  77.   register int k;
  78.   register shifts *shiftp;
  79.   register unsigned *fp2;
  80.   register unsigned *fp3;
  81.   register unsigned *fp4;
  82.   register unsigned *fp1;
  83.   register int symbol;
  84.  
  85.   if (consistent[state]) return;
  86.  
  87.   for (i = 0; i < tokensetsize; i++)
  88.     lookaheadset[i] = 0;
  89.  
  90.   shiftp = shift_table[state];
  91.   if (shiftp)
  92.     {
  93.       k = shiftp->nshifts;
  94.       for (i = 0; i < k; i++)
  95.     {
  96.       symbol = accessing_symbol[shiftp->shifts[i]];
  97.       if (ISVAR(symbol)) break;
  98.       SETBIT(lookaheadset, symbol);
  99.     }
  100.     }
  101.  
  102.   k = lookaheads[state + 1];
  103.   fp4 = lookaheadset + tokensetsize;
  104.  
  105.   /* loop over all rules which require lookahead in this state */
  106.   /* first check for shift-reduce conflict, and try to resolve using precedence  */
  107.  
  108.   for (i = lookaheads[state]; i < k; i++)
  109.     if (rprec[LAruleno[i]])
  110.       {
  111.     fp1 = LA + i * tokensetsize;
  112.     fp2 = fp1;
  113.     fp3 = lookaheadset;
  114.   
  115.     while (fp3 < fp4)
  116.       {
  117.         if (*fp2++ & *fp3++)
  118.           {
  119.         resolve_sr_conflict(state, i);
  120.         break;
  121.           }
  122.       }
  123.       }
  124.  
  125.   /* loop over all rules which require lookahead in this state */
  126.   /* Check for conflicts not resolved above.  */
  127.  
  128.   for (i = lookaheads[state]; i < k; i++)
  129.     {
  130.       fp1 = LA + i * tokensetsize;
  131.       fp2 = fp1;
  132.       fp3 = lookaheadset;
  133.  
  134.       while (fp3 < fp4)
  135.     {
  136.       if (*fp2++ & *fp3++)
  137.         {
  138.           conflicts[state] = 1;
  139.           any_conflicts = 1;
  140.         }
  141.     }
  142.  
  143.       fp2 = fp1;
  144.       fp3 = lookaheadset;
  145.  
  146.       while (fp3 < fp4)
  147.     *fp3++ |= *fp2++;
  148.     }
  149. }
  150.  
  151.  
  152.  
  153. /* Attempt to resolve shift-reduce conflict for one rule
  154. by means of precedence declarations.
  155. It has already been checked that the rule has a precedence.
  156. A conflict is resolved by modifying the shift or reduce tables
  157. so that there is no longer a conflict.  */
  158.  
  159. resolve_sr_conflict(state, lookaheadnum)
  160. int state;
  161. int lookaheadnum;
  162. {
  163.   register int i;
  164.   register int mask;
  165.   register unsigned *fp1;
  166.   register unsigned *fp2;
  167.   register int redprec;
  168.   errs *errp = (errs *) alloca (sizeof(errs) + ntokens * sizeof(short));
  169.   short *errtokens = errp->errs;
  170.  
  171.   /* find the rule to reduce by to get precedence of reduction  */
  172.   redprec = rprec[LAruleno[lookaheadnum]];
  173.  
  174.   mask = 1;
  175.   fp1 = LA + lookaheadnum * tokensetsize;
  176.   fp2 = lookaheadset;
  177.   for (i = 0; i < ntokens; i++)
  178.     {
  179.       if ((mask & *fp2 & *fp1) && sprec[i])
  180.     /* shift-reduce conflict occurs for token number i and it has a precision.
  181.        The precedence of shifting is that of token i.  */
  182.     {
  183.       if (sprec[i] < redprec)
  184.         {
  185.           if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  186.           *fp2 &= ~mask;  /* flush the shift for this token */
  187.           flush_shift(state, i);
  188.         }
  189.       else if (sprec[i] > redprec)
  190.         {
  191.           if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  192.           *fp1 &= ~mask;  /* flush the reduce for this token */
  193.         }
  194.       else
  195.         {
  196.           /* Matching precedence levels.
  197.          For left association, keep only the reduction.
  198.          For right association, keep only the shift.
  199.          For nonassociation, keep neither.  */
  200.  
  201.           switch (sassoc[i])
  202.         {
  203.  
  204.         case RIGHT_ASSOC:
  205.               if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  206.           break;
  207.  
  208.         case LEFT_ASSOC:
  209.               if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  210.           break;
  211.  
  212.         case NON_ASSOC:
  213.               if (verboseflag) log_resolution(state, lookaheadnum, i, "an error");
  214.           break;
  215.         }
  216.  
  217.           if (sassoc[i] != RIGHT_ASSOC)
  218.         {
  219.           *fp2 &= ~mask;  /* flush the shift for this token */
  220.           flush_shift(state, i);
  221.         }
  222.           if (sassoc[i] != LEFT_ASSOC)
  223.             {
  224.           *fp1 &= ~mask;  /* flush the reduce for this token */
  225.         }
  226.           if (sassoc[i] ssoc[i] ssoc[i] ssoc[i] ssoc[i] ÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷÷== 1)
  227.     fprintf(stderr, " 1 shift/reduce conflict");
  228.   else if (src_total > 1)
  229.     fprintf(stderr, " %d shift/reduce conflicts", src_total);
  230.  
  231.   if (src_total > 0 && rrc_total > 0)
  232.     fprintf(stderr, " and");
  233.  
  234.   if (rrc_total == 1)
  235.     fprintf(stderr, " 1 reduce/reduce conflict");
  236.   else if (rrc_total > 1)
  237.     fprintf(stderr, " %d reduce/reduce conflicts", rrc_total);
  238.  
  239.   putc('.', stderr);
  240.   putc('\n', stderr);
  241. }
  242.  
  243.  
  244.  
  245. count_sr_conflicts(state)
  246. int state;
  247. {
  248.   register int i;
  249.   register int k;
  250.   register int mask;
  251.   register shifts *shiftp;
  252.   register unsigned *fp1;
  253.   register unsigned *fp2;
  254.   register unsigned *fp3;
  255.   register int symbol;
  256.  
  257.   src_count = 0;
  258.  
  259.   shiftp = shift_table[state];
  260.   if (!shiftp) return;
  261.  
  262.   for (i = 0; i < tokensetsize; i++)
  263.     {
  264.       shiftset[i] = 0;
  265.       lookaheadset[i] = 0;
  266.     }
  267.  
  268.   k = shiftp->nshifts;
  269.   for (i = 0; i < k; i++)
  270.     {
  271.       if (! shiftp->shifts[i]) continue;
  272.       symbol = accessing_symbol[shiftp->shifts[i]];
  273.       if (ISVAR(symbol)) break;
  274.       SETBIT(shiftset, symbol);
  275.     }
  276.  
  277.   k = lookaheads[state + 1];
  278.   fp3 = lookaheadset + tokensetsize;
  279.  
  280.   for (i = lookaheads[state]; i < k; i++)
  281.     {
  282.       fp1 = LA + i * tokensetsize;
  283.       fp2 = lookaheadset;
  284.  
  285.       while (fp2 < fp3)
  286.     *fp2++ |= *fp1++;
  287.     }
  288.  
  289.   fp1 = shiftset;
  290.   fp2 = lookaheadset;
  291.  
  292.   while (fp2 < fp3)
  293.     *fp2++ &= *fp1++;
  294.  
  295.   mask = 1;
  296.   fp2 = lookaheadset;
  297.   for (i = 0; i < ntokens; i++)
  298.     {
  299.       if (mask & *fp2)
  300.     src_count++;
  301.  
  302.       mask <<= 1;
  303.       if (mask == 0)
  304.     {
  305.       mask = 1;
  306.       fp2++;
  307.     }
  308.     }
  309. }
  310.  
  311.  
  312.  
  313. count_rr_conflicts(state)
  314. int state;
  315. {
  316.   register int i;
  317.   register int j;
  318.   register int count;
  319.   register unsigned mask;
  320.   register unsigned *baseword;
  321.   register unsigned *wordp;
  322.   register int m;
  323.   register int n;
  324.  
  325.   rrc_count = 0;
  326.  
  327.   m = lookaheads[state];
  328.   n = lookaheads[state + 1];
  329.  
  330.   if (n - m < 2) return;
  331.  
  332.   mask = 1;
  333.   baseword = LA + m * tokensetsize;
  334.   for (i = 0; i < ntokens; i++)
  335.     {
  336.       wordp = baseword;
  337.  
  338.       count = 0;
  339.       for (j = m; j < n; j++)
  340.     {
  341.       if (mask & *wordp)
  342.         count++;
  343.  
  344.       wordp += tokensetsize;
  345.     }
  346.  
  347.       if (count >= 2) rrc_count++;
  348.  
  349.       mask <<= 1;
  350.       if (mask == 0)
  351.     {
  352.       mask = 1;
  353.       baseword++;
  354.     }
  355.     }
  356. }
  357.  
  358.  
  359.  
  360. print_reductions(state)
  361. int state;
  362. {
  363.   register int i;
  364.   register int j;
  365.   register int k;
  366.   register unsigned *fp1;
  367.   register unsigned *fp2;
  368.   register unsigned *fp3;
  369.   register unsigned *fp4;
  370.   register int rule;
  371.   register int symbol;
  372.   register unsigned mask;
  373.   register int m;
  374.   register int n;
  375.   register int default_LA;
  376.   register int default_rule;
  377.   register int cmax;
  378.   register int count;
  379.   register shifts *shiftp;
  380.   register errs *errp;
  381.   int nodefault = 0;
  382.  
  383.   for (i = 0; i < tokensetsize; i++)
  384.     shiftset[i] = 0;
  385.  
  386.   shiftp = shift_table[state];
  387.   if (shiftp)
  388.     {
  389.       k = shiftp->nshifts;
  390.       for (i = 0; i < k; i++)
  391.     {
  392.       if (! shiftp->shifts[i]) continue;
  393.       symbol = accessing_symbol[shiftp->shifts[i]];
  394.       if (ISVAR(symbol)) break;
  395.       /* if this state has a shift for the error token,
  396.          don't use a default rule.  */
  397.       if (symbol == error_token_number) nodefault = 1;
  398.       SETBIT(shiftset, symbol);
  399.     }
  400.     }
  401.  
  402.   errp = err_table[state];
  403.   if (errp)
  404.     {
  405.       k = errp->nerrs;
  406.       for (i = 0; i < k; i++)
  407.     {
  408.       if (! errp->errs[i]) continue;
  409.       symbol = errp->errs[i];
  410.       SETBIT(shiftset, symbol);
  411.     }
  412.     }
  413.  
  414.   m = lookaheads[state];
  415.   n = lookaheads[state + 1];
  416.  
  417.   if (n - m == 1 && ! nodefault)
  418.     {
  419.       default_rule = LAruleno[m];
  420.  
  421.       fp1 = LA + m * tokensetsize;
  422.       fp2 = shiftset;
  423.       fp3 = lookaheadset;
  424.       fp4 = lookaheadset + tokensetsize;
  425.  
  426.       while (fp3 < fp4)
  427.     *fp3++ = *fp1++ & *fp2++;
  428.  
  429.       mask = 1;
  430.       fp3 = lookaheadset;
  431.  
  432.       for (i = 0; i < ntokens; i++)
  433.     {
  434.       if (mask & *fp3)
  435.         fprintf(foutput, "    %-4s\t[reduce  %d  (%s)]\n",
  436.             tags[i], default_rule, tags[rlhs[default_rule]]);
  437.  
  438.       mask <<= 1;
  439.       if (mask == 0)
  440.         {
  441.           mask = 1;
  442.           fp3++;
  443.         }
  444.     }
  445.  
  446.       fprintf(foutput, "    $default\treduce  %d  (%s)\n\n",
  447.           default_rule, tags[rlhs[default_rule]]);
  448.     }
  449.   else if (n - m >= 1)
  450.     {
  451.       cmax = 0;
  452.       default_LA = -1;
  453.       fp4 = lookaheadset + tokensetsize;
  454.  
  455.       if (! nodefault)
  456.     for (i = m; i < n; i++)
  457.       {
  458.         fp1 = LA + i * tokensetsize;
  459.         fp2 = shiftset;
  460.         fp3 = lookaheadset;
  461.   
  462.         while (fp3 < fp4)
  463.           *fp3++ = *fp1++ & ( ~ (*fp2++));
  464.   
  465.         count = 0;
  466.         mask = 1;
  467.         fp3 = lookaheadset;
  468.         for (j = 0; j < ntokens; j++)
  469.           {
  470.         if (mask & *fp3)
  471.           count++;
  472.   
  473.         mask <<= 1;
  474.         if (mask == 0)
  475.           {
  476.             mask = 1;
  477.             fp3++;
  478.           }
  479.           }
  480.   
  481.         if (count > cmax)
  482.           {
  483.         cmax = count;
  484.         default_LA = i;
  485.         default_rule = LAruleno[i];
  486.           }
  487.   
  488.         fp2 = shiftset;
  489.         fp3 = lookaheadset;
  490.   
  491.         while (fp3 < fp4)
  492.           *fp2++ |= *fp3++;
  493.       }
  494.  
  495.       for (i = 0; i < tokensetsize; i++)
  496.         shiftset[i] = 0;
  497.  
  498.       if (shiftp)
  499.         {
  500.           k = shiftp->nshifts;
  501.           for (i = 0; i < k; i++)
  502.         {
  503.           if (! shiftp->shifts[i]) continue;
  504.           symbol = accessing_symbol[shiftp->shifts[i]];
  505.           if (ISVAR(symbol)) break;
  506.           SETBIT(shiftset, symbol);
  507.         }
  508.         }
  509.  
  510.       mask = 1;
  511.       fp1 = LA + m * tokensetsize;
  512.       fp2 = shiftset;
  513.       for (i = 0; i < ntokens; i++)
  514.     {
  515.       int defaulted = 0;
  516.  
  517.       if (mask & *fp2)
  518.         count = 1;
  519.       else
  520.         count = 0;
  521.  
  522.       fp3 = fp1;
  523.       for (j = m; j < n; j++)
  524.         {
  525.           if (mask & *fp3)
  526.         {
  527.           if (count == 0)
  528.             {
  529.               if (j != default_LA)
  530.             {
  531.               rule = LAruleno[j];
  532.               fprintf(foutput, "    %-4s\treduce  %d  (%s)\n",
  533.                   tags[i], rule, tags[rlhs[rule]]);
  534.             }
  535.               else defaulted = 1;
  536.  
  537.               count++;
  538.             }
  539.           else
  540.             {
  541.               if (defaulted)
  542.             {
  543.               rule = LAruleno[default_LA];
  544.               fprintf(foutput, "    %-4s\treduce  %d  (%s)\n",
  545.                   tags[i], rule, tags[rlhs[rule]]);
  546.               defaulted = 0;
  547.             }
  548.               rule = LAruleno[j];
  549.               fprintf(foutput, "    %-4s\t[reduce  %d  (%s)]\n",
  550.                   tags[i], rule, tags[rlhs[rule]]);
  551.             }
  552.         }
  553.  
  554.           fp3 += tokensetsize;
  555.         }
  556.  
  557.       mask <<= 1;
  558.       if (mask == 0)
  559.         {
  560.           mask = 1;
  561.           fp1++;
  562.         }
  563.     }
  564.  
  565.       if (default_LA >= 0)
  566.     {
  567.       fprintf(foutput, "    $default\treduce  %d  (%s)\n",
  568.           default_rule, tags[rlhs[default_rule]]);
  569.     }
  570.  
  571.       putc('\n', foutput);
  572.     }
  573. }
  574.  
  575.  
  576.  
  577. finalize_conflicts()
  578. {
  579.   FREE(conflicts);
  580.   FREE(shiftset);
  581.   FREE(lookaheadset);
  582. }
  583.