1/* $Id: lalr.c,v 1.14 2021/05/20 23:57:23 tom Exp $ */
2
3#include "defs.h"
4
5typedef struct shorts
6{
7    struct shorts *next;
8    Value_t value;
9}
10shorts;
11
12static Value_t map_goto(int state, int symbol);
13static Value_t **transpose(Value_t **R, int n);
14static void add_lookback_edge(int stateno, int ruleno, int gotono);
15static void build_relations(void);
16static void compute_FOLLOWS(void);
17static void compute_lookaheads(void);
18static void digraph(Value_t **relation);
19static void initialize_F(void);
20static void initialize_LA(void);
21static void set_accessing_symbol(void);
22static void set_goto_map(void);
23static void set_maxrhs(void);
24static void set_reduction_table(void);
25static void set_shift_table(void);
26static void set_state_table(void);
27static void traverse(int i);
28
29static int tokensetsize;
30Value_t *lookaheads;
31Value_t *LAruleno;
32unsigned *LA;
33Value_t *accessing_symbol;
34core **state_table;
35shifts **shift_table;
36reductions **reduction_table;
37Value_t *goto_base;
38Value_t *goto_map;
39Value_t *from_state;
40Value_t *to_state;
41
42static Value_t infinity;
43static int maxrhs;
44static Value_t ngotos;
45static unsigned *F;
46static Value_t **includes;
47static shorts **lookback;
48static Value_t **R;
49static Value_t *INDEX;
50static Value_t *VERTICES;
51static Value_t top;
52
53void
54lalr(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
71static void
72set_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
81static void
82set_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
91static void
92set_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
101static void
102set_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
111static void
112set_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
139static void
140initialize_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
176static void
177set_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
250static Value_t
251map_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
273static void
274initialize_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
349static void
350build_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
440static void
441add_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
465static Value_t **
466transpose(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
519static void
520compute_FOLLOWS(void)
521{
522    digraph(includes);
523}
524
525static void
526compute_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
559static void
560digraph(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
584static void
585traverse(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
641void
642lalr_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