1 /* $Id: lalr.c,v 1.12 2016/06/07 00:28:03 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 int 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 Value_t state1;
187
188 goto_base = NEW2(nvars + 1, Value_t);
189 temp_base = NEW2(nvars + 1, Value_t);
190
191 goto_map = goto_base - ntokens;
192 temp_map = temp_base - ntokens;
193
194 ngotos = 0;
195 for (sp = first_shift; sp; sp = sp->next)
196 {
197 for (i = sp->nshifts - 1; i >= 0; i--)
198 {
199 symbol = accessing_symbol[sp->shift[i]];
200
201 if (ISTOKEN(symbol))
202 break;
203
204 if (ngotos == MAXYYINT)
205 fatal("too many gotos");
206
207 ngotos++;
208 goto_map[symbol]++;
209 }
210 }
211
212 k = 0;
213 for (i = ntokens; i < nsyms; i++)
214 {
215 temp_map[i] = (Value_t)k;
216 k += goto_map[i];
217 }
218
219 for (i = ntokens; i < nsyms; i++)
220 goto_map[i] = temp_map[i];
221
222 goto_map[nsyms] = (Value_t)ngotos;
223 temp_map[nsyms] = (Value_t)ngotos;
224
225 from_state = NEW2(ngotos, Value_t);
226 to_state = NEW2(ngotos, Value_t);
227
228 for (sp = first_shift; sp; sp = sp->next)
229 {
230 state1 = sp->number;
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 high;
254 int low;
255 int middle;
256 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 (Value_t)(middle);
268 else if (s < state)
269 low = middle + 1;
270 else
271 high = middle - 1;
272 }
273 }
274
275 static void
initialize_F(void)276 initialize_F(void)
277 {
278 int i;
279 int j;
280 int k;
281 shifts *sp;
282 Value_t *edge;
283 unsigned *rowp;
284 Value_t *rp;
285 Value_t **reads;
286 int nedges;
287 int stateno;
288 int symbol;
289 int nwords;
290
291 nwords = ngotos * tokensetsize;
292 F = NEW2(nwords, unsigned);
293
294 reads = NEW2(ngotos, Value_t *);
295 edge = NEW2(ngotos + 1, Value_t);
296 nedges = 0;
297
298 rowp = F;
299 for (i = 0; i < ngotos; i++)
300 {
301 stateno = to_state[i];
302 sp = shift_table[stateno];
303
304 if (sp)
305 {
306 k = sp->nshifts;
307
308 for (j = 0; j < k; j++)
309 {
310 symbol = accessing_symbol[sp->shift[j]];
311 if (ISVAR(symbol))
312 break;
313 SETBIT(rowp, symbol);
314 }
315
316 for (; j < k; j++)
317 {
318 symbol = accessing_symbol[sp->shift[j]];
319 if (nullable[symbol])
320 edge[nedges++] = map_goto(stateno, symbol);
321 }
322
323 if (nedges)
324 {
325 reads[i] = rp = NEW2(nedges + 1, Value_t);
326
327 for (j = 0; j < nedges; j++)
328 rp[j] = edge[j];
329
330 rp[nedges] = -1;
331 nedges = 0;
332 }
333 }
334
335 rowp += tokensetsize;
336 }
337
338 SETBIT(F, 0);
339 digraph(reads);
340
341 for (i = 0; i < ngotos; i++)
342 {
343 if (reads[i])
344 FREE(reads[i]);
345 }
346
347 FREE(reads);
348 FREE(edge);
349 }
350
351 static void
build_relations(void)352 build_relations(void)
353 {
354 int i;
355 int j;
356 int k;
357 Value_t *rulep;
358 Value_t *rp;
359 shifts *sp;
360 int length;
361 int nedges;
362 int done_flag;
363 Value_t state1;
364 Value_t stateno;
365 int symbol1;
366 int symbol2;
367 Value_t *shortp;
368 Value_t *edge;
369 Value_t *states;
370 Value_t **new_includes;
371
372 includes = NEW2(ngotos, Value_t *);
373 edge = NEW2(ngotos + 1, Value_t);
374 states = NEW2(maxrhs + 1, Value_t);
375
376 for (i = 0; i < ngotos; i++)
377 {
378 nedges = 0;
379 state1 = from_state[i];
380 symbol1 = accessing_symbol[to_state[i]];
381
382 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
383 {
384 length = 1;
385 states[0] = state1;
386 stateno = state1;
387
388 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
389 {
390 symbol2 = *rp;
391 sp = shift_table[stateno];
392 k = sp->nshifts;
393
394 for (j = 0; j < k; j++)
395 {
396 stateno = sp->shift[j];
397 if (accessing_symbol[stateno] == symbol2)
398 break;
399 }
400
401 states[length++] = stateno;
402 }
403
404 add_lookback_edge(stateno, *rulep, i);
405
406 length--;
407 done_flag = 0;
408 while (!done_flag)
409 {
410 done_flag = 1;
411 rp--;
412 if (ISVAR(*rp))
413 {
414 stateno = states[--length];
415 edge[nedges++] = map_goto(stateno, *rp);
416 if (nullable[*rp] && length > 0)
417 done_flag = 0;
418 }
419 }
420 }
421
422 if (nedges)
423 {
424 includes[i] = shortp = NEW2(nedges + 1, Value_t);
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++)
434 if (includes[i])
435 FREE(includes[i]);
436
437 FREE(includes);
438
439 includes = new_includes;
440
441 FREE(edge);
442 FREE(states);
443 }
444
445 static void
add_lookback_edge(int stateno,int ruleno,int gotono)446 add_lookback_edge(int stateno, int ruleno, int gotono)
447 {
448 int i, k;
449 int found;
450 shorts *sp;
451
452 i = lookaheads[stateno];
453 k = lookaheads[stateno + 1];
454 found = 0;
455 while (!found && i < k)
456 {
457 if (LAruleno[i] == ruleno)
458 found = 1;
459 else
460 ++i;
461 }
462 assert(found);
463
464 sp = NEW(shorts);
465 sp->next = lookback[i];
466 sp->value = (Value_t)gotono;
467 lookback[i] = sp;
468 }
469
470 static Value_t **
transpose(Value_t ** R2,int n)471 transpose(Value_t **R2, int n)
472 {
473 Value_t **new_R;
474 Value_t **temp_R;
475 Value_t *nedges;
476 Value_t *sp;
477 int i;
478 int k;
479
480 nedges = NEW2(n, Value_t);
481
482 for (i = 0; i < n; i++)
483 {
484 sp = R2[i];
485 if (sp)
486 {
487 while (*sp >= 0)
488 nedges[*sp++]++;
489 }
490 }
491
492 new_R = NEW2(n, Value_t *);
493 temp_R = NEW2(n, Value_t *);
494
495 for (i = 0; i < n; i++)
496 {
497 k = nedges[i];
498 if (k > 0)
499 {
500 sp = NEW2(k + 1, Value_t);
501 new_R[i] = sp;
502 temp_R[i] = sp;
503 sp[k] = -1;
504 }
505 }
506
507 FREE(nedges);
508
509 for (i = 0; i < n; i++)
510 {
511 sp = R2[i];
512 if (sp)
513 {
514 while (*sp >= 0)
515 *temp_R[*sp++]++ = (Value_t)i;
516 }
517 }
518
519 FREE(temp_R);
520
521 return (new_R);
522 }
523
524 static void
compute_FOLLOWS(void)525 compute_FOLLOWS(void)
526 {
527 digraph(includes);
528 }
529
530 static void
compute_lookaheads(void)531 compute_lookaheads(void)
532 {
533 int i, n;
534 unsigned *fp1, *fp2, *fp3;
535 shorts *sp, *next;
536 unsigned *rowp;
537
538 rowp = LA;
539 n = lookaheads[nstates];
540 for (i = 0; i < n; i++)
541 {
542 fp3 = rowp + tokensetsize;
543 for (sp = lookback[i]; sp; sp = sp->next)
544 {
545 fp1 = rowp;
546 fp2 = F + tokensetsize * sp->value;
547 while (fp1 < fp3)
548 *fp1++ |= *fp2++;
549 }
550 rowp = fp3;
551 }
552
553 for (i = 0; i < n; i++)
554 for (sp = lookback[i]; sp; sp = next)
555 {
556 next = sp->next;
557 FREE(sp);
558 }
559
560 FREE(lookback);
561 FREE(F);
562 }
563
564 static void
digraph(Value_t ** relation)565 digraph(Value_t **relation)
566 {
567 int i;
568
569 infinity = (Value_t)(ngotos + 2);
570 INDEX = NEW2(ngotos + 1, Value_t);
571 VERTICES = NEW2(ngotos + 1, Value_t);
572 top = 0;
573
574 R = relation;
575
576 for (i = 0; i < ngotos; i++)
577 INDEX[i] = 0;
578
579 for (i = 0; i < ngotos; i++)
580 {
581 if (INDEX[i] == 0 && R[i])
582 traverse(i);
583 }
584
585 FREE(INDEX);
586 FREE(VERTICES);
587 }
588
589 static void
traverse(int i)590 traverse(int i)
591 {
592 unsigned *fp1;
593 unsigned *fp2;
594 unsigned *fp3;
595 int j;
596 Value_t *rp;
597
598 Value_t height;
599 unsigned *base;
600
601 VERTICES[++top] = (Value_t)i;
602 INDEX[i] = height = top;
603
604 base = F + i * tokensetsize;
605 fp3 = base + tokensetsize;
606
607 rp = R[i];
608 if (rp)
609 {
610 while ((j = *rp++) >= 0)
611 {
612 if (INDEX[j] == 0)
613 traverse(j);
614
615 if (INDEX[i] > INDEX[j])
616 INDEX[i] = INDEX[j];
617
618 fp1 = base;
619 fp2 = F + j * tokensetsize;
620
621 while (fp1 < fp3)
622 *fp1++ |= *fp2++;
623 }
624 }
625
626 if (INDEX[i] == height)
627 {
628 for (;;)
629 {
630 j = VERTICES[top--];
631 INDEX[j] = infinity;
632
633 if (i == j)
634 break;
635
636 fp1 = base;
637 fp2 = F + j * tokensetsize;
638
639 while (fp1 < fp3)
640 *fp2++ = *fp1++;
641 }
642 }
643 }
644
645 #ifdef NO_LEAKS
646 void
lalr_leaks(void)647 lalr_leaks(void)
648 {
649 int i;
650
651 if (includes != 0)
652 {
653 for (i = 0; i < ngotos; i++)
654 {
655 free(includes[i]);
656 }
657 DO_FREE(includes);
658 }
659 }
660 #endif
661