Return to ey4.c CVS log

Up to [CSRG BSD Unix] / 43BSD / ucb / pascal / eyacc

Annotation of 43BSD/ucb/pascal/eyacc/ey4.c, revision 1.1

1.1     ! root        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:        }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.