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