# 2.11BSD#431 - /usr/src/ucb/PORT/pascal/eyacc/ey4.c

##### Functions

    apack             X
    go2               X
    go2gen            X
    go2out            X
    output            X
    precftn           X
    prred             X
    wract             X
    wrstate           X

##### Variables

    cdebug            X
    g2debug           X
    pkdebug           X

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

#### Defined functions

apack defined in line 129; used 2 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey3.c line 252-253(2)

go2 defined in line 123; used 1 times

- in line 27

go2gen defined in line 235; used 1 times

- in line 178

go2out defined in line 170; used 1 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey1.c line 89

output defined in line 13; used 1 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey1.c line 88

precftn defined in line 289; used 1 times

- in line 51

prred defined in line 94; used 1 times

- in line 91

wract defined in line 306; used 1 times

- in line 83

wrstate defined in line 459; used 2 times

- in line 406, 417

#### Defined variables

cdebug defined in line 305; used 4 times

- in line 356, 367, 399, 428

g2debug defined in line 234; used 1 times

- in line 263

pkdebug defined in line 128; used 2 times

- in line 147, 156

sccsid defined in line 8; never used

Last modified: 1985-04-30 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1923 |