Commit | Line | Data |
---|---|---|
c854545e KB |
1 | /* |
2 | * Copyright (c) 1989 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Robert Paul Corbett. | |
7 | * | |
6ecf3d85 | 8 | * %sccs.include.redist.c% |
c854545e KB |
9 | */ |
10 | ||
11 | #ifndef lint | |
6ecf3d85 | 12 | static char sccsid[] = "@(#)lalr.c 5.3 (Berkeley) %G%"; |
c854545e KB |
13 | #endif /* not lint */ |
14 | ||
15 | #include "defs.h" | |
16 | ||
17 | typedef | |
18 | struct shorts | |
19 | { | |
20 | struct shorts *next; | |
21 | short value; | |
22 | } | |
23 | shorts; | |
24 | ||
25 | int tokensetsize; | |
26 | short *lookaheads; | |
27 | short *LAruleno; | |
28 | unsigned *LA; | |
29 | short *accessing_symbol; | |
30 | core **state_table; | |
31 | shifts **shift_table; | |
32 | reductions **reduction_table; | |
33 | short *goto_map; | |
34 | short *from_state; | |
35 | short *to_state; | |
36 | ||
37 | short **transpose(); | |
38 | ||
39 | static int infinity; | |
40 | static int maxrhs; | |
41 | static int ngotos; | |
42 | static unsigned *F; | |
43 | static short **includes; | |
44 | static shorts **lookback; | |
45 | static short **R; | |
46 | static short *INDEX; | |
47 | static short *VERTICES; | |
48 | static int top; | |
49 | ||
50 | ||
51 | lalr() | |
52 | { | |
53 | tokensetsize = WORDSIZE(ntokens); | |
54 | ||
55 | set_state_table(); | |
56 | set_accessing_symbol(); | |
57 | set_shift_table(); | |
58 | set_reduction_table(); | |
59 | set_maxrhs(); | |
60 | initialize_LA(); | |
61 | set_goto_map(); | |
62 | initialize_F(); | |
63 | build_relations(); | |
64 | compute_FOLLOWS(); | |
65 | compute_lookaheads(); | |
66 | } | |
67 | ||
68 | ||
69 | ||
70 | set_state_table() | |
71 | { | |
72 | register core *sp; | |
73 | ||
74 | state_table = NEW2(nstates, core *); | |
75 | for (sp = first_state; sp; sp = sp->next) | |
76 | state_table[sp->number] = sp; | |
77 | } | |
78 | ||
79 | ||
80 | ||
81 | set_accessing_symbol() | |
82 | { | |
83 | register core *sp; | |
84 | ||
85 | accessing_symbol = NEW2(nstates, short); | |
86 | for (sp = first_state; sp; sp = sp->next) | |
87 | accessing_symbol[sp->number] = sp->accessing_symbol; | |
88 | } | |
89 | ||
90 | ||
91 | ||
92 | set_shift_table() | |
93 | { | |
94 | register shifts *sp; | |
95 | ||
96 | shift_table = NEW2(nstates, shifts *); | |
97 | for (sp = first_shift; sp; sp = sp->next) | |
98 | shift_table[sp->number] = sp; | |
99 | } | |
100 | ||
101 | ||
102 | ||
103 | set_reduction_table() | |
104 | { | |
105 | register reductions *rp; | |
106 | ||
107 | reduction_table = NEW2(nstates, reductions *); | |
108 | for (rp = first_reduction; rp; rp = rp->next) | |
109 | reduction_table[rp->number] = rp; | |
110 | } | |
111 | ||
112 | ||
113 | ||
114 | set_maxrhs() | |
115 | { | |
116 | register short *itemp; | |
117 | register short *item_end; | |
118 | register int length; | |
119 | register int max; | |
120 | ||
121 | length = 0; | |
122 | max = 0; | |
123 | item_end = ritem + nitems; | |
124 | for (itemp = ritem; itemp < item_end; itemp++) | |
125 | { | |
126 | if (*itemp >= 0) | |
127 | { | |
128 | length++; | |
129 | } | |
130 | else | |
131 | { | |
132 | if (length > max) max = length; | |
133 | length = 0; | |
134 | } | |
135 | } | |
136 | ||
137 | maxrhs = max; | |
138 | } | |
139 | ||
140 | ||
141 | ||
142 | initialize_LA() | |
143 | { | |
144 | register int i, j, k; | |
145 | register reductions *rp; | |
146 | ||
147 | lookaheads = NEW2(nstates + 1, short); | |
148 | ||
149 | k = 0; | |
150 | for (i = 0; i < nstates; i++) | |
151 | { | |
152 | lookaheads[i] = k; | |
153 | rp = reduction_table[i]; | |
154 | if (rp) | |
155 | k += rp->nreds; | |
156 | } | |
157 | lookaheads[nstates] = k; | |
158 | ||
159 | LA = NEW2(k * tokensetsize, unsigned); | |
160 | LAruleno = NEW2(k, short); | |
161 | lookback = NEW2(k, shorts *); | |
162 | ||
163 | k = 0; | |
164 | for (i = 0; i < nstates; i++) | |
165 | { | |
166 | rp = reduction_table[i]; | |
167 | if (rp) | |
168 | { | |
169 | for (j = 0; j < rp->nreds; j++) | |
170 | { | |
171 | LAruleno[k] = rp->rules[j]; | |
172 | k++; | |
173 | } | |
174 | } | |
175 | } | |
176 | } | |
177 | ||
178 | ||
179 | set_goto_map() | |
180 | { | |
181 | register shifts *sp; | |
182 | register int i; | |
183 | register int symbol; | |
184 | register int k; | |
185 | register short *temp_map; | |
186 | register int state2; | |
187 | register int state1; | |
188 | ||
189 | goto_map = NEW2(nvars + 1, short) - ntokens; | |
190 | temp_map = NEW2(nvars + 1, short) - ntokens; | |
191 | ||
192 | ngotos = 0; | |
193 | for (sp = first_shift; sp; sp = sp->next) | |
194 | { | |
195 | for (i = sp->nshifts - 1; i >= 0; i--) | |
196 | { | |
197 | symbol = accessing_symbol[sp->shift[i]]; | |
198 | ||
199 | if (ISTOKEN(symbol)) break; | |
200 | ||
201 | if (ngotos == MAXSHORT) | |
202 | fatal("too many gotos"); | |
203 | ||
204 | ngotos++; | |
205 | goto_map[symbol]++; | |
206 | } | |
207 | } | |
208 | ||
209 | k = 0; | |
210 | for (i = ntokens; i < nsyms; i++) | |
211 | { | |
212 | temp_map[i] = k; | |
213 | k += goto_map[i]; | |
214 | } | |
215 | ||
216 | for (i = ntokens; i < nsyms; i++) | |
217 | goto_map[i] = temp_map[i]; | |
218 | ||
219 | goto_map[nsyms] = ngotos; | |
220 | temp_map[nsyms] = ngotos; | |
221 | ||
222 | from_state = NEW2(ngotos, short); | |
223 | to_state = NEW2(ngotos, short); | |
224 | ||
225 | for (sp = first_shift; sp; sp = sp->next) | |
226 | { | |
227 | state1 = sp->number; | |
228 | for (i = sp->nshifts - 1; i >= 0; i--) | |
229 | { | |
230 | state2 = sp->shift[i]; | |
231 | symbol = accessing_symbol[state2]; | |
232 | ||
233 | if (ISTOKEN(symbol)) break; | |
234 | ||
235 | k = temp_map[symbol]++; | |
236 | from_state[k] = state1; | |
237 | to_state[k] = state2; | |
238 | } | |
239 | } | |
240 | ||
241 | FREE(temp_map + ntokens); | |
242 | } | |
243 | ||
244 | ||
245 | ||
246 | /* Map_goto maps a state/symbol pair into its numeric representation. */ | |
247 | ||
248 | int | |
249 | map_goto(state, symbol) | |
250 | int state; | |
251 | int symbol; | |
252 | { | |
253 | register int high; | |
254 | register int low; | |
255 | register int middle; | |
256 | register int s; | |
257 | ||
258 | low = goto_map[symbol]; | |
259 | high = goto_map[symbol + 1]; | |
260 | ||
261 | for (;;) | |
262 | { | |
263 | assert(low <= high); | |
264 | middle = (low + high) >> 1; | |
265 | s = from_state[middle]; | |
266 | if (s == state) | |
267 | return (middle); | |
268 | else if (s < state) | |
269 | low = middle + 1; | |
270 | else | |
271 | high = middle - 1; | |
272 | } | |
273 | } | |
274 | ||
275 | ||
276 | ||
277 | initialize_F() | |
278 | { | |
279 | register int i; | |
280 | register int j; | |
281 | register int k; | |
282 | register shifts *sp; | |
283 | register short *edge; | |
284 | register unsigned *rowp; | |
285 | register short *rp; | |
286 | register short **reads; | |
287 | register int nedges; | |
288 | register int stateno; | |
289 | register int symbol; | |
290 | register int nwords; | |
291 | ||
292 | nwords = ngotos * tokensetsize; | |
293 | F = NEW2(nwords, unsigned); | |
294 | ||
295 | reads = NEW2(ngotos, short *); | |
296 | edge = NEW2(ngotos + 1, short); | |
297 | nedges = 0; | |
298 | ||
299 | rowp = F; | |
300 | for (i = 0; i < ngotos; i++) | |
301 | { | |
302 | stateno = to_state[i]; | |
303 | sp = shift_table[stateno]; | |
304 | ||
305 | if (sp) | |
306 | { | |
307 | k = sp->nshifts; | |
308 | ||
309 | for (j = 0; j < k; j++) | |
310 | { | |
311 | symbol = accessing_symbol[sp->shift[j]]; | |
312 | if (ISVAR(symbol)) | |
313 | break; | |
314 | SETBIT(rowp, symbol); | |
315 | } | |
316 | ||
317 | for (; j < k; j++) | |
318 | { | |
319 | symbol = accessing_symbol[sp->shift[j]]; | |
320 | if (nullable[symbol]) | |
321 | edge[nedges++] = map_goto(stateno, symbol); | |
322 | } | |
323 | ||
324 | if (nedges) | |
325 | { | |
326 | reads[i] = rp = NEW2(nedges + 1, short); | |
327 | ||
328 | for (j = 0; j < nedges; j++) | |
329 | rp[j] = edge[j]; | |
330 | ||
331 | rp[nedges] = -1; | |
332 | nedges = 0; | |
333 | } | |
334 | } | |
335 | ||
336 | rowp += tokensetsize; | |
337 | } | |
338 | ||
339 | SETBIT(F, 0); | |
340 | digraph(reads); | |
341 | ||
342 | for (i = 0; i < ngotos; i++) | |
343 | { | |
344 | if (reads[i]) | |
345 | FREE(reads[i]); | |
346 | } | |
347 | ||
348 | FREE(reads); | |
349 | FREE(edge); | |
350 | } | |
351 | ||
352 | ||
353 | ||
354 | build_relations() | |
355 | { | |
356 | register int i; | |
357 | register int j; | |
358 | register int k; | |
359 | register short *rulep; | |
360 | register short *rp; | |
361 | register shifts *sp; | |
362 | register int length; | |
363 | register int nedges; | |
364 | register int done; | |
365 | register int state1; | |
366 | register int stateno; | |
367 | register int symbol1; | |
368 | register int symbol2; | |
369 | register short *shortp; | |
370 | register short *edge; | |
371 | register short *states; | |
372 | register short **new_includes; | |
373 | ||
374 | includes = NEW2(ngotos, short *); | |
375 | edge = NEW2(ngotos + 1, short); | |
376 | states = NEW2(maxrhs + 1, short); | |
377 | ||
378 | for (i = 0; i < ngotos; i++) | |
379 | { | |
380 | nedges = 0; | |
381 | state1 = from_state[i]; | |
382 | symbol1 = accessing_symbol[to_state[i]]; | |
383 | ||
384 | for (rulep = derives[symbol1]; *rulep >= 0; rulep++) | |
385 | { | |
386 | length = 1; | |
387 | states[0] = state1; | |
388 | stateno = state1; | |
389 | ||
390 | for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) | |
391 | { | |
392 | symbol2 = *rp; | |
393 | sp = shift_table[stateno]; | |
394 | k = sp->nshifts; | |
395 | ||
396 | for (j = 0; j < k; j++) | |
397 | { | |
398 | stateno = sp->shift[j]; | |
399 | if (accessing_symbol[stateno] == symbol2) break; | |
400 | } | |
401 | ||
402 | states[length++] = stateno; | |
403 | } | |
404 | ||
405 | add_lookback_edge(stateno, *rulep, i); | |
406 | ||
407 | length--; | |
408 | done = 0; | |
409 | while (!done) | |
410 | { | |
411 | done = 1; | |
412 | rp--; | |
413 | if (ISVAR(*rp)) | |
414 | { | |
415 | stateno = states[--length]; | |
416 | edge[nedges++] = map_goto(stateno, *rp); | |
417 | if (nullable[*rp] && length > 0) done = 0; | |
418 | } | |
419 | } | |
420 | } | |
421 | ||
422 | if (nedges) | |
423 | { | |
424 | includes[i] = shortp = NEW2(nedges + 1, short); | |
425 | for (j = 0; j < nedges; j++) | |
426 | shortp[j] = edge[j]; | |
427 | shortp[nedges] = -1; | |
428 | } | |
429 | } | |
430 | ||
431 | new_includes = transpose(includes, ngotos); | |
432 | ||
433 | for (i = 0; i < ngotos; i++) | |
3e83b7de KB |
434 | if (includes[i]) |
435 | FREE(includes[i]); | |
c854545e KB |
436 | |
437 | FREE(includes); | |
438 | ||
439 | includes = new_includes; | |
440 | ||
441 | FREE(edge); | |
442 | FREE(states); | |
443 | } | |
444 | ||
445 | ||
446 | add_lookback_edge(stateno, ruleno, gotono) | |
447 | int stateno, ruleno, gotono; | |
448 | { | |
449 | register int i, k; | |
450 | register int found; | |
451 | register shorts *sp; | |
452 | ||
453 | i = lookaheads[stateno]; | |
454 | k = lookaheads[stateno + 1]; | |
455 | found = 0; | |
456 | while (!found && i < k) | |
457 | { | |
458 | if (LAruleno[i] == ruleno) | |
459 | found = 1; | |
460 | else | |
461 | ++i; | |
462 | } | |
463 | assert(found); | |
464 | ||
465 | sp = NEW(shorts); | |
466 | sp->next = lookback[i]; | |
467 | sp->value = gotono; | |
468 | lookback[i] = sp; | |
469 | } | |
470 | ||
471 | ||
472 | ||
473 | short ** | |
474 | transpose(R, n) | |
475 | short **R; | |
476 | int n; | |
477 | { | |
478 | register short **new_R; | |
479 | register short **temp_R; | |
480 | register short *nedges; | |
481 | register short *sp; | |
482 | register int i; | |
483 | register int k; | |
484 | ||
485 | nedges = NEW2(n, short); | |
486 | ||
487 | for (i = 0; i < n; i++) | |
488 | { | |
489 | sp = R[i]; | |
490 | if (sp) | |
491 | { | |
492 | while (*sp >= 0) | |
493 | nedges[*sp++]++; | |
494 | } | |
495 | } | |
496 | ||
497 | new_R = NEW2(n, short *); | |
498 | temp_R = NEW2(n, short *); | |
499 | ||
500 | for (i = 0; i < n; i++) | |
501 | { | |
502 | k = nedges[i]; | |
503 | if (k > 0) | |
504 | { | |
505 | sp = NEW2(k + 1, short); | |
506 | new_R[i] = sp; | |
507 | temp_R[i] = sp; | |
508 | sp[k] = -1; | |
509 | } | |
510 | } | |
511 | ||
512 | FREE(nedges); | |
513 | ||
514 | for (i = 0; i < n; i++) | |
515 | { | |
516 | sp = R[i]; | |
517 | if (sp) | |
518 | { | |
519 | while (*sp >= 0) | |
520 | *temp_R[*sp++]++ = i; | |
521 | } | |
522 | } | |
523 | ||
524 | FREE(temp_R); | |
525 | ||
526 | return (new_R); | |
527 | } | |
528 | ||
529 | ||
530 | ||
531 | compute_FOLLOWS() | |
532 | { | |
533 | digraph(includes); | |
534 | } | |
535 | ||
536 | ||
537 | compute_lookaheads() | |
538 | { | |
539 | register int i, n; | |
540 | register unsigned *fp1, *fp2, *fp3; | |
3e83b7de | 541 | register shorts *sp, *next; |
c854545e KB |
542 | register unsigned *rowp; |
543 | ||
544 | rowp = LA; | |
545 | n = lookaheads[nstates]; | |
546 | for (i = 0; i < n; i++) | |
547 | { | |
548 | fp3 = rowp + tokensetsize; | |
549 | for (sp = lookback[i]; sp; sp = sp->next) | |
550 | { | |
551 | fp1 = rowp; | |
552 | fp2 = F + tokensetsize * sp->value; | |
553 | while (fp1 < fp3) | |
554 | *fp1++ |= *fp2++; | |
555 | } | |
556 | rowp = fp3; | |
557 | } | |
558 | ||
559 | for (i = 0; i < n; i++) | |
3e83b7de KB |
560 | for (sp = lookback[i]; sp; sp = next) |
561 | { | |
562 | next = sp->next; | |
563 | FREE(sp); | |
564 | } | |
c854545e KB |
565 | |
566 | FREE(lookback); | |
567 | FREE(F); | |
568 | } | |
569 | ||
570 | ||
571 | digraph(relation) | |
572 | short **relation; | |
573 | { | |
574 | register int i; | |
575 | ||
576 | infinity = ngotos + 2; | |
577 | INDEX = NEW2(ngotos + 1, short); | |
578 | VERTICES = NEW2(ngotos + 1, short); | |
579 | top = 0; | |
580 | ||
581 | R = relation; | |
582 | ||
583 | for (i = 0; i < ngotos; i++) | |
584 | INDEX[i] = 0; | |
585 | ||
586 | for (i = 0; i < ngotos; i++) | |
587 | { | |
588 | if (INDEX[i] == 0 && R[i]) | |
589 | traverse(i); | |
590 | } | |
591 | ||
592 | FREE(INDEX); | |
593 | FREE(VERTICES); | |
594 | } | |
595 | ||
596 | ||
597 | ||
598 | traverse(i) | |
599 | register int i; | |
600 | { | |
601 | register unsigned *fp1; | |
602 | register unsigned *fp2; | |
603 | register unsigned *fp3; | |
604 | register int j; | |
605 | register short *rp; | |
606 | ||
607 | int height; | |
608 | unsigned *base; | |
609 | ||
610 | VERTICES[++top] = i; | |
611 | INDEX[i] = height = top; | |
612 | ||
613 | base = F + i * tokensetsize; | |
614 | fp3 = base + tokensetsize; | |
615 | ||
616 | rp = R[i]; | |
617 | if (rp) | |
618 | { | |
619 | while ((j = *rp++) >= 0) | |
620 | { | |
621 | if (INDEX[j] == 0) | |
622 | traverse(j); | |
623 | ||
624 | if (INDEX[i] > INDEX[j]) | |
625 | INDEX[i] = INDEX[j]; | |
626 | ||
627 | fp1 = base; | |
628 | fp2 = F + j * tokensetsize; | |
629 | ||
630 | while (fp1 < fp3) | |
631 | *fp1++ |= *fp2++; | |
632 | } | |
633 | } | |
634 | ||
635 | if (INDEX[i] == height) | |
636 | { | |
637 | for (;;) | |
638 | { | |
639 | j = VERTICES[top--]; | |
640 | INDEX[j] = infinity; | |
641 | ||
642 | if (i == j) | |
643 | break; | |
644 | ||
645 | fp1 = base; | |
646 | fp2 = F + j * tokensetsize; | |
647 | ||
648 | while (fp1 < fp3) | |
649 | *fp2++ = *fp1++; | |
650 | } | |
651 | } | |
652 | } |