xref: /freebsd/contrib/byacc/lalr.c (revision b2d48be1bc7df45ddd13b143a160d0acb5a383c5) 
1 /* $Id: lalr.c,v 1.11 2014/09/18 00:26:39 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
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
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
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
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
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
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
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
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
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
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
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
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 **
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
525 compute_FOLLOWS(void)
526 {
527     digraph(includes);
528 }
529 
530 static 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
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
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
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