Commit | Line | Data |
---|---|---|
7878f925 KB |
1 | /*- |
2 | * Copyright (c) 1979 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * %sccs.include.proprietary.c% | |
0b1076e3 KM |
6 | */ |
7 | ||
8 | #ifndef lint | |
7878f925 KB |
9 | static char sccsid[] = "@(#)ey3.c 5.2 (Berkeley) %G%"; |
10 | #endif /* not lint */ | |
0b1076e3 KM |
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 | } |