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