home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Distributions / ucb / spencer_2bsd.tar.gz / 2bsd.tar / src / eyacc / ey4.c < prev    next >
Text File  |  1980-02-17  |  10KB  |  424 lines
  1. /* (c) 1979 Regents of the University of California */
  2. # include "ey.h"
  3.  
  4. output(){ /* print the output for the states */
  5.  
  6.   int i, j, k, c;
  7.  
  8.   settab();
  9.   arrset("yyact");
  10.  
  11.   for( i=0; i<nstate; ++i ){ /* output the stuff for state i */
  12.     nolook = (tystate[i]==0);
  13.     closure(i);
  14.     /* output actions */
  15.     aryfil( temp1, nterms+1, 0 );
  16.     for( j=0; j<cwset; ++j ){ /* look at the items */
  17.       c = *( wsets[j].pitem );
  18.       if( c>0 && c<NTBASE && temp1[c]==0 ) temp1[c] = go2(i,c);
  19.       }
  20.  
  21.     if( i == 1 ) temp1[1] = ACCEPTCODE;
  22.  
  23.     /* now, we have the shifts; look at the reductions */
  24.  
  25.     lastred = 0;
  26.     for( j=0; j<cwset; ++j ){
  27.       c = *( wsets[j].pitem );
  28.       if( c<=0 ){ /* reduction */
  29.         lastred = -c;
  30.         for( k=1; k<=nterms; ++k ){
  31.           if( ((wsets[j].ws[k>>4])&(1<<(k&017))) != 0 ) {
  32.             if( temp1[k] == 0 ) temp1[k] = c;
  33.             else if( temp1[k]<0 ){ /* reduce/reduce conflict */
  34.               settty();
  35.               printf("\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
  36.                 i, -temp1[k], lastred, symnam(k) );
  37.               if( -temp1[k] > lastred ) temp1[k] = -lastred;
  38.               ++zzrrconf;
  39.               settab();
  40.               }
  41.             else { /* potential shift/reduce conflict */
  42.               switch( precftn( lastred, k ) ) {
  43.  
  44.             case 0: /* precedence does not apply */
  45.  
  46.                 settty();
  47.                 printf("\n%d: shift/reduce conflict (shift %d, red'n %d) on %s", i,
  48.             temp1[k], lastred, symnam(k) );
  49.                 ++zzsrconf;
  50.                 settab();
  51.                 break;
  52.  
  53.             case 1: /*  reduce */
  54.  
  55.                 temp1[k] = -lastred;
  56.                 break;
  57.  
  58.             case 2: /* error, binary operator */
  59.  
  60.                 temp1[k] = ERRCODE;
  61.                 break;
  62.  
  63.             case 3: /* shift ... leave the entry alone */
  64.  
  65.                 break;
  66.                 }
  67.               }
  68.             }
  69.           }
  70.         }
  71.       }
  72.     wract(i);
  73.     }
  74.  
  75.   settab();
  76.   arrdone();
  77.  
  78.   /* now, output the pointers to the action array */
  79.   /* also output the info about reductions */
  80.   prred();
  81.   }
  82.  
  83. prred(){ /* print the information about the actions and the reductions */
  84.   int index, i;
  85.  
  86.   arrset("yypact");
  87.   index = 1;    /* position in the output table */
  88.  
  89.   for( i=0; i<nstate; ++i ){
  90.     if( tystate[i]>0 ){  /* the state is real */
  91.       temp1[i] = index;
  92.       arrval( index );
  93.       index =+ tystate[i];
  94.       }
  95.     else {
  96.       arrval( temp1[-tystate[i]] );
  97.       }
  98.     }
  99.  
  100.   arrdone();
  101.  
  102.   arrset("yyr1");
  103.   for( i=1; i<nprod; ++i ) arrval( *prdptr[i] - NTBASE );
  104.   arrdone();
  105.  
  106.   arrset("yyr2");
  107.   for( i=1; i<nprod; ++i ) arrval( ( prdptr[i+1]-prdptr[i]-2 ) );
  108.   arrdone();
  109.  
  110.   }
  111.  
  112. go2(i,c){ /* do a goto on the closure state, not worrying about lookaheads */
  113.   if( c<NTBASE ) return( amem[ apstate[i]+c ] );
  114.   else return( amem[ apstate[i] + c - NTBASE + nterms ] );
  115.   }
  116.  
  117. int pkdebug 0;
  118. apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
  119.   _REGISTER k, l, off;
  120.   int j;
  121.  
  122.   /* find the spot */
  123.  
  124.   j = n;
  125.   for( off = 0; off <= j && p[off] == 0; ++off ) ;
  126.   if( off > j ){ /* no actions */
  127.     return(0);
  128.     }
  129.   j =- off;
  130.   for( k=0; k<actsiz; ++k ){
  131.     for( l=0; l<=j; ++l ){
  132.       if( p[off+l] != 0 ){
  133.         if( p[off+l] != amem[k+l] && amem[k+l] != 0 ) goto nextk;
  134.         }
  135.       }
  136.     if( pkdebug ){ settty(); printf("off = %d, k = %d\n", off, k ); }
  137.     /* we have found an acceptable k */
  138.     for( l=0; l<=j; ++l ){
  139.       if( p[off+l] ){
  140.         if( k+l >= actsiz ) error("action table overflow");
  141.         if( k+l >= memact ) memact = k+l;
  142.         amem[k+l] = p[off+l];
  143.         }
  144.       }
  145.     if( pkdebug ){
  146.       for( k=0; k<memact; k=+10){
  147.         printf("\t");
  148.         for( l=0; l<=9; ++l ) printf("%d ", amem[k+l] );
  149.         printf("\n");
  150.         }
  151.       }
  152.     return(k-off);
  153.  
  154.     nextk: ;
  155.     }
  156.   error("no space in action table");
  157.   }
  158.  
  159. go2out(){ /* output the gotos for the nontermninals */
  160.   int i, j, k, best, offset, count, cbest, times;
  161.  
  162.   settab();
  163.   arrset("yygo");
  164.   offset = 1;
  165.  
  166.   for( i=1; i<=nnonter; ++i ) {
  167.     go2gen(i);
  168.  
  169.     /* find the best one to make default */
  170.  
  171.     temp2[i] = offset;
  172.  
  173.     best = -1;
  174.     times = 0;
  175.  
  176.     for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
  177.       if( tystate[j] == 0 ) continue;
  178.       if( tystate[j] == best ) continue;
  179.  
  180.       /* is tystate[j] the most frequent */
  181.  
  182.       count = 0;
  183.       cbest = tystate[j];
  184.  
  185.       for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
  186.  
  187.       if( count > times ){
  188.         best = cbest;
  189.         times = count;
  190.         }
  191.       }
  192.  
  193.     /* best is now the default entry */
  194.  
  195.     zzgobest =+ (times-1)*2;
  196.     settab();
  197.     for( j=0; j<=nstate; ++j ){
  198.       if( tystate[j] != 0 && tystate[j]!=best ){
  199.         arrval( j );
  200.         arrval( tystate[j] );
  201.         offset =+ 2;
  202.         zzgoent =+ 2;
  203.         }
  204.       }
  205.  
  206.     /* now, the default */
  207.  
  208.     zzgoent =+ 2;
  209.     arrval( -1 );
  210.     arrval( best );
  211.     offset =+ 2;
  212.  
  213.     }
  214.  
  215.   arrdone();
  216.  
  217.   arrset("yypgo");
  218.   for( i=1; i<=nnonter; ++i ) arrval( temp2[i] );
  219.   arrdone();
  220.  
  221.   }
  222.  
  223. int g2debug 0;
  224. go2gen(c){ /* output the gotos for nonterminal c */
  225.  
  226.   int i, work, cc;
  227.   struct item *p, *q;
  228.  
  229.   /* first, find nonterminals with gotos on c */
  230.  
  231.   aryfil( temp1, nnonter+1, 0 );
  232.   temp1[c] = 1;
  233.  
  234.   work = 1;
  235.   while( work ){
  236.     work = 0;
  237.     for( i=0; i<nprod; ++i ){
  238.       if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
  239.         if( temp1[cc] != 0 ){ /* cc has a goto on c */
  240.           cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
  241.           if( temp1[cc] == 0 ){
  242.             work = 1;
  243.             temp1[cc] = 1;
  244.             }
  245.           }
  246.         }
  247.       }
  248.     }
  249.  
  250.   /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
  251.  
  252.   if( g2debug ){
  253.     settty();
  254.     printf("%s: gotos on ", nontrst[c].name );
  255.     for( i=0; i<=nnonter; ++i ) if( temp1[i]) printf("%s ", nontrst[i].name);
  256.     printf("\n");
  257.     }
  258.  
  259.   /* now, go through and put gotos into tystate */
  260.  
  261.   aryfil( tystate, nstate, 0 );
  262.   settty();
  263.   printf("\nnonterminal %s\n", nontrst[c].name );
  264.   for( i=0; i<nstate; ++i ){
  265.     q = pstate[i+1];
  266.     for( p=pstate[i]; p<q; ++p ){
  267.       if( (cc= *p->pitem) >= NTBASE ){
  268.         if( temp1[cc =- NTBASE] ){ /* goto on c is possible */
  269.           tystate[i] = amem[indgo[i]+c];
  270.           break;
  271.           }
  272.         }
  273.       }
  274.     if( tystate[i] ) printf("\t%d\t%d\n", i, tystate[i]);
  275.     }
  276.   }
  277.  
  278. precftn(r,t){ /* decide a shift/reduce conflict by precedence.
  279.             Returns 0 if action is 'do nothing',1 if action is reduce,
  280.             2 if the action is 'error,binary operator'
  281.             and 3 if the action is 'reduce'. */
  282.  
  283.     int lp,lt;
  284.     lp = levprd[r];
  285.     lt = trmlev[t];
  286.     if ((lt==0)||((lp&03)==0))return(0);
  287.     if((lt>>3) == (lp>>3)){
  288.         return(lt&03);
  289.         }
  290.     if((lt>>3) > (lp>>3)) return(3);
  291.     return(1);
  292.     }
  293.  
  294. int cdebug 0; /* debug for common states */
  295. wract(i){ /* output state i */
  296.   /* temp1 has the actions, lastred the default */
  297.   int p, p0, p1, size;
  298.   int ntimes, tred, count, j;
  299.   struct item *q0, *q1;
  300.  
  301.   /* find the best choice for lastred */
  302.  
  303.   lastred = 0;
  304.   ntimes = 0;
  305.   /***** UCB MOD - full state spec if shift on error *****/
  306.   if (temp1[2] <= 0)
  307.   for( j=1; j<=nterms; ++j ){
  308.     if( temp1[j] >= 0 ) continue;
  309.     if( temp1[j]+lastred == 0 ) continue;
  310.     /* count the number of appearances of temp1[j] */
  311.     count = 0;
  312.     tred = -temp1[j];
  313.     for( p=1; p<=nterms; ++p ){
  314.       if( temp1[p]+tred == 0 ) ++count;
  315.       }
  316.     if( count >ntimes ){
  317.       lastred = tred;
  318.       ntimes = count;
  319.       }
  320.     }
  321.  
  322.     /* clear out entries in temp1 which equal lastred */
  323.     for( p=1; p<= nterms; ++p ) if( temp1[p]+lastred == 0 )temp1[p]=0;
  324.  
  325.     /* write out the state */
  326.  
  327.     /* first, check for equality with another state */
  328.     /* see if there is a nonterminal with all dots before it. */
  329.  
  330.     p0 = 0;
  331.     q1 = pstate[i+1];
  332.     for( q0=pstate[i]; q0<q1; ++q0 ){
  333.       if( (p1= *(q0->pitem) ) < NTBASE ) goto standard;
  334.       if( p0 == 0 ) p0 = p1;
  335.       else if( p0 != p1 ) goto standard;
  336.       }
  337.  
  338.     /* now, all items have dots before p0 */
  339.     if( cdebug ){
  340.       settty();
  341.       printf("state %d, pre-nonterminal %s\n",i,nontrst[p0-NTBASE].name);
  342.       }
  343.  
  344.     for( j=0; j<i; ++j ){
  345.       if( apstate[i] != apstate[j] ) continue;
  346.  
  347.       /* equal positions -- check items */
  348.  
  349.       if( cdebug )printf("states %d and %d have equal positions\n",i,j);
  350.       q1 = pstate[j+1];
  351.       for( q0=pstate[j]; q0<q1; ++q0 ){
  352.         if( *(q0->pitem) != p0 ) goto nextj;
  353.         }
  354.  
  355.       /* we have a match with state j ! */
  356.  
  357.       tystate[i] = -j;
  358.       zzacsave =+ tystate[j];
  359.       zznsave++;
  360.       wrstate(i);
  361.       return;
  362.  
  363.     nextj:  ;
  364.       }
  365.  
  366.  
  367.   standard:
  368.     tystate[i] = 2;
  369.     wrstate(i);
  370.  
  371.     size = 0;
  372.     for( p0=1; p0<=nterms; ++p0 )
  373.       if( (p1=temp1[p0])!=0 ) {
  374.     /***** UCB MOD - test actions are negative of symbol to be tested
  375.              this speeds up the parser as it is easy to check for
  376.      *****/
  377.         arrval( -trmset[p0].value );
  378.         if( p1 < 0 ) arrval( REDUCACT - p1 );
  379.         else if( p1 == ACCEPTCODE ) arrval( ACCEPTACT );
  380.         else if( p1 == ERRCODE ) arrval( ERRACT );
  381.         else arrval( SHIFTACT + p1 );
  382.         size =+ 2;
  383.         }
  384.     if( lastred ) arrval( REDUCACT + lastred );
  385.     else arrval( ERRACT );
  386.     tystate[i] = size+1; /* store entry size in tystate */
  387.     zzacent =+ (size+1);
  388.     return;
  389.   }
  390.  
  391. wrstate(i){ /* writes state i */
  392.     int j0,j1,s;
  393.         struct item *pp, *qq;
  394.     settty();
  395.     printf("\nstate %d\n",i);
  396.     qq = pstate[i+1];
  397.     for( pp=pstate[i]; pp<qq; ++pp) printf("\t%s\n", writem(pp));
  398.  
  399.         /* check for state equal to another */
  400.  
  401.         if( tystate[i] <= 0 ){
  402.           printf("\n\tsame as %d\n\n", -tystate[i] );
  403.           return;
  404.           }
  405.  
  406.     for( j0=1; j0<=nterms; ++j0 ) if( (j1=temp1[j0]) != 0 ){
  407.     printf("\n\t%s  ", symnam(j0) );
  408.              if( j1>0 ){ /* shift, error, or accept */
  409.                if( j1 == ACCEPTCODE ) printf( "accept" );
  410.                else if( j1 == ERRCODE ) printf( "error" );
  411.                else printf( "shift %d", j1 );
  412.                }
  413.            else printf("reduce %d",-j1 );
  414.        }
  415.  
  416.     /* output the final production */
  417.  
  418.     if( lastred ) printf("\n\t.  reduce %d\n\n", lastred );
  419.     else printf("\n\t.  error\n\n" );
  420.  
  421. ret:
  422.     settab();
  423.     }
  424.