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