1 /*- 2 * Copyright (c) 1979, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.proprietary.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)ey3.c 8.1 (Berkeley) 06/06/93"; 10 #endif /* not lint */ 11 12 # include "ey.h" 13 14 cpres(){ /* conpute an array with the beginnings of productions yielding given nonterminals 15 The array pres points to these lists */ 16 int i,j,c; 17 pres = (int ***)yalloc(nnonter+1); 18 for(i=0;i<=nnonter;i++){ 19 c = i+NTBASE; 20 pres[i] = (int **)mem; 21 fatfl = 0; /* make undefined symbols nonfatal */ 22 for(j=0;j<nprod;j++) 23 if (*prdptr[j] == c) *mem++ = (int)(prdptr[j]+1); 24 if(pres[i] == (int **)mem){ 25 error("nonterminal %s not defined!", nontrst[i].name); 26 } 27 } 28 pres[i] = (int **)mem; 29 fatfl = 1; 30 if( nerrors ){ 31 summary(); 32 cexit(1); 33 } 34 } 35 36 int indebug = 0; 37 cpfir() { 38 /* compute an array with the first of nonterminals */ 39 int i, ch, **s, **t, changes, *p; 40 41 pfirst = (struct looksets **)yalloc(nnonter+1); 42 for (i=0;i<=nnonter;i++) { 43 aryfil( wsets[i].ws, tbitset, 0 ); 44 t = pres[i+1]; 45 for( s=pres[i]; s<t; ++s ){ /* initially fill the sets */ 46 for( p = *s; (ch = *p) > 0 ; ++p ) { 47 if( ch < NTBASE ) { 48 wsets[i].ws[ch>>4] |= (1 << (ch&017) ); 49 break; 50 } 51 else if( !pempty[ch-NTBASE] ) break; 52 } 53 } 54 } 55 56 /* now, reflect transitivity */ 57 58 changes = 1; 59 while( changes ){ 60 changes = 0; 61 for( i=0; i<=nnonter; ++i ){ 62 t = pres[i+1]; 63 for( s=pres[i]; s<t; ++s ){ 64 for( p = *s; ( ch = (*p-NTBASE) ) >= 0; ++p ) { 65 changes |= UNION( wsets[i].ws, wsets[i].ws, wsets[ch].ws ); 66 if( !pempty[ch] ) break; 67 } 68 } 69 } 70 } 71 72 for( i=0; i<=nnonter; i++ ) pfirst[i] = flset( wsets[i].ws ); 73 if( !indebug ) return; 74 settty(); 75 for( i=0; i<=nnonter; i++ ){ 76 fprintf( cout , "\n%s: ", nontrst[i].name ); 77 prlook( pfirst[i] ); 78 fprintf( cout , " %d\n", pempty[i] ); 79 } 80 } 81 82 state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */ 83 int *s,size1,size2; 84 struct looksets *lp; 85 _REGISTER i; 86 struct item *p1, *p2, *k, *l, *q1, *q2; 87 p1 = pstate[nstate]; 88 p2 = pstate[nstate+1]; 89 if(p1==p2) return(0); /* null state */ 90 /* sort the items */ 91 for(k=p2-1;k>p1;k--) { /* make k the biggest */ 92 for(l=k-1;l>=p1;--l)if( l->pitem > k->pitem ){ 93 s = k->pitem; 94 k->pitem = l->pitem; 95 l->pitem = s; 96 lp = k->look; 97 k->look = l->look; 98 l->look = lp; 99 } 100 } 101 size1 = p2 - p1; /* size of state */ 102 103 for( i= (c>=NTBASE)?ntstates[c-NTBASE]:tstates[c]; i != 0; i = mstates[i] ) { 104 /* get ith state */ 105 q1 = pstate[i]; 106 q2 = pstate[i+1]; 107 size2 = q2 - q1; 108 if (size1 != size2) continue; 109 k=p1; 110 for(l=q1;l<q2;l++) { 111 if( l->pitem != k->pitem ) break; 112 ++k; 113 } 114 if (l != q2) continue; 115 /* found it */ 116 pstate[nstate+1] = pstate[nstate]; /* delete last state */ 117 /* fix up lookaheads */ 118 k=p1; 119 for( l=q1; l<q2; ++l ){ 120 if( UNION( clset.lset, l->look->lset, k->look->lset ) ) { 121 tystate[i] = 1; 122 /* register the new set */ 123 l->look = flset( &clset ); 124 } 125 ++k; 126 } 127 return (i); 128 } 129 /* state is new */ 130 pstate[nstate+2] = p2; 131 if(nstate+1 >= stsize) error("too many states"); 132 if( c >= NTBASE ){ 133 mstates[ nstate ] = ntstates[ c-NTBASE ]; 134 ntstates[ c-NTBASE ] = nstate; 135 } 136 else { 137 mstates[ nstate ] = tstates[ c ]; 138 tstates[ c ] = nstate; 139 } 140 tystate[nstate]=1; 141 return(nstate++); 142 } 143 144 int pidebug = 0; /* debugging flag for putitem */ 145 putitem ( ptr, lptr ) int *ptr; struct looksets *lptr;{ 146 int *jip, k; 147 struct item *i, *j; 148 149 if( pidebug ) { 150 settty(); 151 fprintf( cout , "putitem(%s), state %d\n", writem(&ptr), nstate ); 152 } 153 /* see if it's there */ 154 j = pstate[nstate+1]; 155 for( i=pstate[nstate]; i<j; ++i ) 156 if(i->pitem == ptr) { 157 error("yacc error--duplicate item"); 158 } 159 /* not there */ 160 j->pitem = ptr; 161 j->look = flset( lptr ); 162 pstate[nstate+1] = ++j; 163 jip = (int *)j; 164 if(jip-mem0 >= memsiz) error("out of state space"); 165 } 166 167 cempty(){ /* mark nonterminals which derive the empty string */ 168 169 int i, *p; 170 171 /* set pempty to 0 */ 172 pempty = (char *)yalloc( nnonter / sizeof(int) + 1 ); 173 aryfil( pempty, nnonter+1, 0 ); 174 for( i=1; i<nprod; ++i ) /* loop over productions */ 175 if( prdptr[i][1] <= 0 ) /* i is empty production */ 176 pempty[ *prdptr[i]-NTBASE ] = 1; 177 178 /* now, all explicitly empty nonterminals marked with pempty = 1 */ 179 180 /* loop as long as we keep finding nontrivial empty nonterminals */ 181 182 again: 183 for( i=1; i<nprod; ++i ){ 184 if( pempty[ *prdptr[i]-NTBASE ]==0 ){ /* not known to be empty */ 185 for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]!=0 ; ++p ) ; 186 if( *p < 0 ){ /* we have a nontrivially empty nonterminal */ 187 pempty[*prdptr[i]-NTBASE] = 1; 188 goto again; /* got one ... try for another */ 189 } 190 } 191 } 192 } 193 194 int gsdebug = 0; 195 stagen(){ /* generate the states */ 196 197 int i, j, k, c; 198 199 /* initialize */ 200 201 nstate = 0; 202 pstate[0] = pstate[1] = (struct item *)mem; 203 aryfil( clset.lset, tbitset, 0 ); 204 putitem( prdptr[0]+1, &clset ); 205 tystate[0] = 1; 206 nstate = 1; 207 pstate[2] = pstate[1]; 208 209 memact = 0; 210 aryfil( amem, actsiz, 0 ); 211 212 /* now, the main state generation loop */ 213 214 more: 215 for( i=0; i<nstate; ++i ){ 216 /* if tystate == 2, set to zero */ 217 if( tystate[i] != 1 ) continue; 218 tystate[i] = 0; 219 aryfil( temp1, nterms+nnonter+1, 0 ); 220 /* take state i, close it, and do gotos */ 221 closure(i); 222 for( j=0; j<cwset; ++j ){ /* generate gotos */ 223 if( wsets[j].flag ) continue; 224 wsets[j].flag = 1; 225 c = *(wsets[j].pitem); 226 /* if no symbols after the dot (ie empty rule) */ 227 if( c <= 1 ) { 228 /* if not in kernel then tystate = 2 unless not done with it */ 229 if( pstate[i+1]-pstate[i] <= j ) tystate[i] = (tystate[i]==1)?1:2; 230 continue; 231 } 232 /* do a goto on c */ 233 for( k=j; k<cwset; ++k ){ 234 if( c == *(wsets[k].pitem) ){ /* this item contributes to the goto */ 235 putitem( wsets[k].pitem + 1, wsets[k].ws ); 236 wsets[k].flag = 1; 237 } 238 } 239 if( c < NTBASE ) temp1[c] = state(c); 240 else temp1[c-NTBASE+nterms] = state(c); 241 } 242 if( gsdebug ){ 243 settty(); 244 fprintf( cout , "%d: ", i ); 245 for( j=1; j<=nterms; ++j ){ 246 if( temp1[j] != 0 ) fprintf( cout , "%s %d, ", symnam(j), temp1[j]); 247 } 248 for( j=1; j<=nnonter; ++j ){ 249 if( temp1[j+nterms] ) fprintf( cout , "%s %d, ", nontrst[j].name, temp1[j+nterms] ); 250 } 251 fprintf( cout , "\n"); 252 } 253 apstate[i] = apack( &temp1[0], nterms ); 254 indgo[i] = apack( &temp1[nterms+1], nnonter-1 ) - 1; 255 goto more; /* we have done one goto; do some more */ 256 } 257 /* no more to do... stop */ 258 } 259 260 int cldebug = 0; /* debugging flag for closure */ 261 closure(i){ /* generate the closure of state i */ 262 263 int c, ch, work; 264 _REGISTER j, k; 265 int *pi; 266 int **s, **t; 267 struct item *q; 268 _REGISTER struct item *p; 269 270 ++zzclose; 271 272 /* first, copy kernel of state i to wsets */ 273 274 lambdarule = -1; 275 cwset = 0; 276 q = pstate[i+1]; 277 /* for every item in the kernel */ 278 for( p=pstate[i]; p<q; ++p ){ 279 wsets[cwset].pitem = p->pitem; 280 wsets[cwset].flag = 1; /* this item must get closed */ 281 for( k=0; k<tbitset; ++k ) wsets[cwset].ws[k] = p->look->lset[k]; 282 ++cwset; 283 } 284 285 /* now, go through the loop, closing each item */ 286 287 work = 1; 288 while( work ){ 289 work = 0; 290 for( j=0; j<cwset; ++j ){ 291 292 /* for every item in state, if terminal after dot, flag = 0 */ 293 if( wsets[j].flag == 0 ) continue; 294 /* dot is before c, since pitem of X -> A.B is B */ 295 c = *(wsets[j].pitem); 296 297 if( c < NTBASE ){ 298 wsets[j].flag = 0; 299 continue; /* only interesting case is where . is before nonterminal */ 300 } 301 302 /* compute the lookahead */ 303 aryfil( clset.lset, tbitset, 0 ); 304 305 /* find items involving c */ 306 307 /* for all the rest of the items in the state */ 308 for( k=j; k<cwset; ++k ){ 309 if( wsets[k].flag == 1 && *(pi=wsets[k].pitem) == c ){ 310 wsets[k].flag = 0; 311 if( nolook ) continue; 312 while( (ch= *++pi)>0 ){ 313 if( ch < NTBASE ){ /* terminal symbol */ 314 /* put ch in clset */ 315 clset.lset[ch>>4] |= (1<<(ch&017)); 316 break; 317 } 318 /* nonterminal symbol */ 319 /* clset <- clset U first(ch) */ 320 UNION( clset.lset, clset.lset, pfirst[ch-NTBASE] ); 321 /* if ch cannot derive lambda we are done */ 322 if( !pempty[ch-NTBASE] ) break; 323 } 324 /* if end of rule the clset <- clset U (lookahead for LHS) */ 325 if( ch<=0 ) UNION( clset.lset, clset.lset, wsets[k].ws ); 326 } 327 } 328 329 /* now loop over productions derived from c */ 330 331 c -= NTBASE; /* c is now nonterminal number */ 332 333 t = pres[c+1]; 334 /* for each rule that c derives */ 335 for( s=pres[c]; s<t; ++s ){ 336 /* put these items into the closure */ 337 for( k=0; k<cwset; ++k ){ /* is the item there */ 338 if( wsets[k].pitem == *s ){ /* yes, it is there */ 339 if( nolook ) goto nexts; 340 /* if something new in ws, set flag = 1 */ 341 if( UNION( wsets[k].ws, wsets[k].ws, clset.lset ) ) 342 wsets[k].flag = work = 1; 343 goto nexts; 344 } 345 } 346 347 /* not there; make a new entry */ 348 if( cwset+1 >= wssize ) error( "working set overflow" ); 349 wsets[cwset].pitem = *s; 350 wsets[cwset].flag = 1; 351 if (**s < 0) 352 lambdarule = cwset; 353 if( nolook ){ 354 cwset++; 355 goto nexts; 356 } 357 work = 1; 358 for( k=0; k<tbitset; ++k ) wsets[cwset].ws[k] = clset.lset[k]; 359 cwset++; 360 361 nexts: ; 362 } 363 364 } 365 } 366 367 /* have computed closure; flags are reset; return */ 368 369 if( cwset > zzcwset ) zzcwset = cwset; 370 if( !cldebug ) return; 371 settty(); 372 fprintf( cout , "\nState %d, nolook = %d\n", i, nolook ); 373 for( j=0; j<cwset; ++j ){ 374 if( wsets[j].flag ) fprintf( cout , "flag set!\n"); 375 wsets[j].flag = 0; 376 fprintf( cout , "\t%s", writem(&wsets[j].pitem)); 377 prlook( wsets[j].ws ); 378 fprintf( cout , "\n" ); 379 } 380 381 } 382 383 struct looksets *flset( p ) 384 struct looksets *p; 385 { 386 /* decide if the lookahead set pointed to by p is known */ 387 /* return pointer to a perminent location for the set */ 388 389 int j, *w; 390 _REGISTER *u, *v, i; 391 392 for( i=0; i<nlset; ++i ){ 393 u = p->lset; 394 v = lkst[i].lset; 395 w = & v[tbitset]; 396 while( v<w) if( *u++ != *v++ ) goto more; 397 /* we have matched */ 398 return( & lkst[i] ); 399 more: ; 400 } 401 /* add a new one */ 402 if( nlset+1 >= lsetsz )error("too many lookahead sets"); 403 for( j=0; j<tbitset; ++j ){ 404 lkst[nlset].lset[j] = p->lset[j]; 405 } 406 return( & lkst[nlset++]); 407 } 408