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