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