1: # include "dextern"
   2: 
   3: # include   <stdio.h>
   4: extern FILE *Fin, *Fout;
   5: 
   6: output(){ /* print the output for the states */
   7: 
   8:   int i, j, k, c;
   9: 
  10:   settab();
  11:   arrset("yyact");
  12: 
  13:   for( i=0; i<nstate; ++i ){ /* output the stuff for state i */
  14:     nolook = (tystate[i]==0);
  15:     closure(i);
  16:     /* output actions */
  17:     aryfil( temp1, nterms+1, 0 );
  18:     for( j=0; j<cwset; ++j ){ /* look at the items */
  19:       c = *( wsets[j].pitem );
  20:       if( c>0 && c<NTBASE && temp1[c]==0 ) temp1[c] = go2(i,c);
  21:       }
  22: 
  23:     if( i == 1 ) temp1[1] = ACCEPTCODE;
  24: 
  25:     /* now, we have the shifts; look at the reductions */
  26: 
  27:     lastred = 0;
  28:     for( j=0; j<cwset; ++j ){
  29:       c = *( wsets[j].pitem );
  30:       if( c<=0 ){ /* reduction */
  31:         lastred = -c;
  32:         for( k=1; k<=nterms; ++k ){
  33:           if( ((wsets[j].ws[k>>4])&(1<<(k&017))) != 0 ) {
  34:             if( temp1[k] == 0 ) temp1[k] = c;
  35:             else if( temp1[k]<0 ){ /* reduce/reduce conflict */
  36:               settty();
  37:               fprintf(Fout, "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
  38:                 i, -temp1[k], lastred, symnam(k) );
  39:               if( -temp1[k] > lastred ) temp1[k] = -lastred;
  40:               ++zzrrconf;
  41:               settab();
  42:               }
  43:             else { /* potential shift/reduce conflict */
  44:               switch( precftn( lastred, k ) ) {
  45: 
  46:             case 0: /* precedence does not apply */
  47: 
  48:                 settty();
  49:                 fprintf(Fout, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s", i,
  50:             temp1[k], lastred, symnam(k) );
  51:                 ++zzsrconf;
  52:                 settab();
  53:                 break;
  54: 
  55:             case 1: /*  reduce */
  56: 
  57:                 temp1[k] = -lastred;
  58:                 break;
  59: 
  60:             case 2: /* error, binary operator */
  61: 
  62:                 temp1[k] = ERRCODE;
  63:                 break;
  64: 
  65:             case 3: /* shift ... leave the entry alone */
  66: 
  67:                 break;
  68:                 }
  69:               }
  70:             }
  71:           }
  72:         }
  73:       }
  74:     wract(i);
  75:     }
  76: 
  77:   settab();
  78:   arrdone();
  79: 
  80:   /* now, output the pointers to the action array */
  81:   /* also output the info about reductions */
  82:   prred();
  83:   }
  84: 
  85: prred(){ /* print the information about the actions and the reductions */
  86:   int index, i;
  87: 
  88:   arrset("yypact");
  89:   index = 1;    /* position in the output table */
  90: 
  91:   for( i=0; i<nstate; ++i ){
  92:     if( tystate[i]>0 ){  /* the state is real */
  93:       temp1[i] = index;
  94:       arrval( index );
  95:       index += tystate[i];
  96:       }
  97:     else {
  98:       arrval( temp1[-tystate[i]] );
  99:       }
 100:     }
 101: 
 102:   arrdone();
 103: 
 104:   arrset("yyr1");
 105:   for( i=1; i<nprod; ++i ) arrval( *prdptr[i] - NTBASE );
 106:   arrdone();
 107: 
 108:   arrset("yyr2");
 109:   for( i=1; i<nprod; ++i ) arrval( ( prdptr[i+1]-prdptr[i]-2 ) );
 110:   arrdone();
 111: 
 112:   }
 113: 
 114: go2(i,c){ /* do a goto on the closure state, not worrying about lookaheads */
 115:   if( c<NTBASE ) return( amem[ apstate[i]+c ] );
 116:   else return( amem[ apstate[i] + c - NTBASE + nterms ] );
 117:   }
 118: 
 119: int pkdebug = 0;
 120: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
 121:   _REGISTER k, l, off;
 122:   int j;
 123: 
 124:   /* Find the spot */
 125: 
 126:   j = n;
 127:   for( off = 0; off <= j && p[off] == 0; ++off ) ;
 128:   if( off > j ){ /* no actions */
 129:     return(0);
 130:     }
 131:   j -= off;
 132:   for( k=0; k<actsiz; ++k ){
 133:     for( l=0; l<=j; ++l ){
 134:       if( p[off+l] != 0 ){
 135:         if( p[off+l] != amem[k+l] && amem[k+l] != 0 ) goto nextk;
 136:         }
 137:       }
 138:     if( pkdebug ){ settty(); fprintf(Fout, "off = %d, k = %d\n", off, k ); }
 139:     /* we have found an acceptable k */
 140:     for( l=0; l<=j; ++l ){
 141:       if( p[off+l] ){
 142:         if( k+l >= actsiz ) error("action table overflow");
 143:         if( k+l >= memact ) memact = k+l;
 144:         amem[k+l] = p[off+l];
 145:         }
 146:       }
 147:     if( pkdebug ){
 148:       for( k=0; k<memact; k+=10){
 149:         fprintf(Fout, "\t");
 150:         for( l=0; l<=9; ++l ) fprintf(Fout, "%d ", amem[k+l] );
 151:         fprintf(Fout, "\n");
 152:         }
 153:       }
 154:     return(k-off);
 155: 
 156:     nextk: ;
 157:     }
 158:   error("no space in action table");
 159:   }
 160: 
 161: go2out(){ /* output the gotos for the nontermninals */
 162:   int i, j, k, best, offset, count, cbest, times;
 163: 
 164:   settab();
 165:   arrset("yygo");
 166:   offset = 1;
 167: 
 168:   for( i=1; i<=nnonter; ++i ) {
 169:     go2gen(i);
 170: 
 171:     /* Find the best one to make default */
 172: 
 173:     temp2[i] = offset;
 174: 
 175:     best = -1;
 176:     times = 0;
 177: 
 178:     for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
 179:       if( tystate[j] == 0 ) continue;
 180:       if( tystate[j] == best ) continue;
 181: 
 182:       /* is tystate[j] the most frequent */
 183: 
 184:       count = 0;
 185:       cbest = tystate[j];
 186: 
 187:       for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
 188: 
 189:       if( count > times ){
 190:         best = cbest;
 191:         times = count;
 192:         }
 193:       }
 194: 
 195:     /* best is now the default entry */
 196: 
 197:     zzgobest += (times-1)*2;
 198:     settab();
 199:     for( j=0; j<=nstate; ++j ){
 200:       if( tystate[j] != 0 && tystate[j]!=best ){
 201:         arrval( j );
 202:         arrval( tystate[j] );
 203:         offset += 2;
 204:         zzgoent += 2;
 205:         }
 206:       }
 207: 
 208:     /* now, the default */
 209: 
 210:     zzgoent += 2;
 211:     arrval( -1 );
 212:     arrval( best );
 213:     offset += 2;
 214: 
 215:     }
 216: 
 217:   arrdone();
 218: 
 219:   arrset("yypgo");
 220:   for( i=1; i<=nnonter; ++i ) arrval( temp2[i] );
 221:   arrdone();
 222: 
 223:   }
 224: 
 225: int g2debug = 0;
 226: go2gen(c){ /* output the gotos for nonterminal c */
 227: 
 228:   int i, work, cc;
 229:   struct item *p, *q;
 230: 
 231:   /* first, Find nonterminals with gotos on c */
 232: 
 233:   aryfil( temp1, nnonter+1, 0 );
 234:   temp1[c] = 1;
 235: 
 236:   work = 1;
 237:   while( work ){
 238:     work = 0;
 239:     for( i=0; i<nprod; ++i ){
 240:       if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
 241:         if( temp1[cc] != 0 ){ /* cc has a goto on c */
 242:           cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
 243:           if( temp1[cc] == 0 ){
 244:             work = 1;
 245:             temp1[cc] = 1;
 246:             }
 247:           }
 248:         }
 249:       }
 250:     }
 251: 
 252:   /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
 253: 
 254:   if( g2debug ){
 255:     settty();
 256:     fprintf(Fout, "%s: gotos on ", nontrst[c].name );
 257:     for( i=0; i<=nnonter; ++i ) if( temp1[i]) fprintf(Fout, "%s ", nontrst[i].name);
 258:     fprintf(Fout, "\n");
 259:     }
 260: 
 261:   /* now, go through and put gotos into tystate */
 262: 
 263:   aryfil( tystate, nstate, 0 );
 264:   settty();
 265:   fprintf(Fout, "\nnonterminal %s\n", nontrst[c].name );
 266:   for( i=0; i<nstate; ++i ){
 267:     q = pstate[i+1];
 268:     for( p=pstate[i]; p<q; ++p ){
 269:       if( (cc= *p->pitem) >= NTBASE ){
 270:         if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
 271:           tystate[i] = amem[indgo[i]+c];
 272:           break;
 273:           }
 274:         }
 275:       }
 276:     if( tystate[i] ) fprintf(Fout, "\t%d\t%d\n", i, tystate[i]);
 277:     }
 278:   }
 279: 
 280: precftn(r,t){ /* decide a shift/reduce conflict by precedence.
 281: 			Returns 0 if action is 'do nothing',1 if action is reduce,
 282: 			2 if the action is 'error,binary operator'
 283: 			and 3 if the action is 'reduce'. */
 284: 
 285:     int lp,lt;
 286:     lp = levprd[r];
 287:     lt = trmlev[t];
 288:     if ((lt==0)||((lp&03)==0))return(0);
 289:     if((lt>>3) == (lp>>3)){
 290:         return(lt&03);
 291:         }
 292:     if((lt>>3) > (lp>>3)) return(3);
 293:     return(1);
 294:     }
 295: 
 296: int cdebug = 0; /* debug for common states */
 297: wract(i){ /* output state i */
 298:   /* temp1 has the actions, lastred the default */
 299:   int p, p0, p1, size;
 300:   int ntimes, tred, count, j;
 301:   struct item *q0, *q1;
 302: 
 303:   /* Find the best choice for lastred */
 304: 
 305:   lastred = 0;
 306:   ntimes = 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:       fprintf(Fout, "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 )fprintf(Fout, "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:         arrval( TESTACT+trmset[p0].value );
 375:         if( p1 < 0 ) arrval( REDUCACT - p1 );
 376:         else if( p1 == ACCEPTCODE ) arrval( ACCEPTACT );
 377:         else if( p1 == ERRCODE ) arrval( ERRACT );
 378:         else arrval( SHIFTACT + p1 );
 379:         size += 2;
 380:         }
 381:     if( lastred ) arrval( REDUCACT + lastred );
 382:     else arrval( ERRACT );
 383:     tystate[i] = size+1; /* store entry size in tystate */
 384:     zzacent += (size+1);
 385:     return;
 386:   }
 387: 
 388: wrstate(i){ /* writes state i */
 389:     int j0,j1,s;
 390:         struct item *pp, *qq;
 391:     settty();
 392:     fprintf(Fout, "\nstate %d\n",i);
 393:     qq = pstate[i+1];
 394:     for( pp=pstate[i]; pp<qq; ++pp) fprintf(Fout, "\t%s\n", writem(pp));
 395: 
 396:         /* check for state equal to another */
 397: 
 398:         if( tystate[i] <= 0 ){
 399:           fprintf(Fout, "\n\tsame as %d\n\n", -tystate[i] );
 400:           return;
 401:           }
 402: 
 403:     for( j0=1; j0<=nterms; ++j0 ) if( (j1=temp1[j0]) != 0 ){
 404:     fprintf(Fout, "\n\t%s  ", symnam(j0) );
 405:              if( j1>0 ){ /* shift, error, or accept */
 406:                if( j1 == ACCEPTCODE ) fprintf(Fout,  "accept" );
 407:                else if( j1 == ERRCODE ) fprintf(Fout,  "error" );
 408:                else fprintf(Fout,  "shift %d", j1 );
 409:                }
 410:            else fprintf(Fout, "reduce %d",-j1 );
 411:        }
 412: 
 413:     /* output the Final production */
 414: 
 415:     if( lastred ) fprintf(Fout, "\n\t.  reduce %d\n\n", lastred );
 416:     else fprintf(Fout, "\n\t.  error\n\n" );
 417: 
 418: ret:
 419:     settab();
 420:     }

Defined functions

apack defined in line 120; used 2 times
go2 defined in line 114; used 1 times
  • in line 20
go2gen defined in line 226; used 1 times
go2out defined in line 161; used 1 times
output defined in line 6; used 1 times
precftn defined in line 280; used 1 times
  • in line 44
prred defined in line 85; used 1 times
  • in line 82
wract defined in line 297; used 1 times
  • in line 74
wrstate defined in line 388; used 2 times

Defined variables

cdebug defined in line 296; used 2 times
g2debug defined in line 225; used 1 times
pkdebug defined in line 119; used 2 times
Last modified: 1995-02-18
Generated: 2016-12-26
Generated by src2html V0.67
page hit count: 3333
Valid CSS Valid XHTML 1.0 Strict