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