lalr.c revision 264803 
1/* $Id: lalr.c,v 1.10 2014/02/19 00:35:17 Tom.Shields 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_map;
38Value_t *from_state;
39Value_t *to_state;
40
41static Value_t infinity;
42static int maxrhs;
43static int ngotos;
44static unsigned *F;
45static Value_t **includes;
46static shorts **lookback;
47static Value_t **R;
48static Value_t *INDEX;
49static Value_t *VERTICES;
50static Value_t top;
51
52void
53lalr(void)
54{
55    tokensetsize = WORDSIZE(ntokens);
56
57    set_state_table();
58    set_accessing_symbol();
59    set_shift_table();
60    set_reduction_table();
61    set_maxrhs();
62    initialize_LA();
63    set_goto_map();
64    initialize_F();
65    build_relations();
66    compute_FOLLOWS();
67    compute_lookaheads();
68}
69
70static void
71set_state_table(void)
72{
73    core *sp;
74
75    state_table = NEW2(nstates, core *);
76    for (sp = first_state; sp; sp = sp->next)
77	state_table[sp->number] = sp;
78}
79
80static void
81set_accessing_symbol(void)
82{
83    core *sp;
84
85    accessing_symbol = NEW2(nstates, Value_t);
86    for (sp = first_state; sp; sp = sp->next)
87	accessing_symbol[sp->number] = sp->accessing_symbol;
88}
89
90static void
91set_shift_table(void)
92{
93    shifts *sp;
94
95    shift_table = NEW2(nstates, shifts *);
96    for (sp = first_shift; sp; sp = sp->next)
97	shift_table[sp->number] = sp;
98}
99
100static void
101set_reduction_table(void)
102{
103    reductions *rp;
104
105    reduction_table = NEW2(nstates, reductions *);
106    for (rp = first_reduction; rp; rp = rp->next)
107	reduction_table[rp->number] = rp;
108}
109
110static void
111set_maxrhs(void)
112{
113    Value_t *itemp;
114    Value_t *item_end;
115    int length;
116    int max;
117
118    length = 0;
119    max = 0;
120    item_end = ritem + nitems;
121    for (itemp = ritem; itemp < item_end; itemp++)
122    {
123	if (*itemp >= 0)
124	{
125	    length++;
126	}
127	else
128	{
129	    if (length > max)
130		max = length;
131	    length = 0;
132	}
133    }
134
135    maxrhs = max;
136}
137
138static void
139initialize_LA(void)
140{
141    int i, j, k;
142    reductions *rp;
143
144    lookaheads = NEW2(nstates + 1, Value_t);
145
146    k = 0;
147    for (i = 0; i < nstates; i++)
148    {
149	lookaheads[i] = (Value_t) k;
150	rp = reduction_table[i];
151	if (rp)
152	    k += rp->nreds;
153    }
154    lookaheads[nstates] = (Value_t) k;
155
156    LA = NEW2(k * tokensetsize, unsigned);
157    LAruleno = NEW2(k, Value_t);
158    lookback = NEW2(k, shorts *);
159
160    k = 0;
161    for (i = 0; i < nstates; i++)
162    {
163	rp = reduction_table[i];
164	if (rp)
165	{
166	    for (j = 0; j < rp->nreds; j++)
167	    {
168		LAruleno[k] = rp->rules[j];
169		k++;
170	    }
171	}
172    }
173}
174
175static void
176set_goto_map(void)
177{
178    shifts *sp;
179    int i;
180    int symbol;
181    int k;
182    Value_t *temp_map;
183    Value_t state2;
184    Value_t state1;
185
186    goto_map = NEW2(nvars + 1, Value_t) - ntokens;
187    temp_map = NEW2(nvars + 1, Value_t) - ntokens;
188
189    ngotos = 0;
190    for (sp = first_shift; sp; sp = sp->next)
191    {
192	for (i = sp->nshifts - 1; i >= 0; i--)
193	{
194	    symbol = accessing_symbol[sp->shift[i]];
195
196	    if (ISTOKEN(symbol))
197		break;
198
199	    if (ngotos == MAXYYINT)
200		fatal("too many gotos");
201
202	    ngotos++;
203	    goto_map[symbol]++;
204	}
205    }
206
207    k = 0;
208    for (i = ntokens; i < nsyms; i++)
209    {
210	temp_map[i] = (Value_t) k;
211	k += goto_map[i];
212    }
213
214    for (i = ntokens; i < nsyms; i++)
215	goto_map[i] = temp_map[i];
216
217    goto_map[nsyms] = (Value_t) ngotos;
218    temp_map[nsyms] = (Value_t) ngotos;
219
220    from_state = NEW2(ngotos, Value_t);
221    to_state = NEW2(ngotos, Value_t);
222
223    for (sp = first_shift; sp; sp = sp->next)
224    {
225	state1 = sp->number;
226	for (i = sp->nshifts - 1; i >= 0; i--)
227	{
228	    state2 = sp->shift[i];
229	    symbol = accessing_symbol[state2];
230
231	    if (ISTOKEN(symbol))
232		break;
233
234	    k = temp_map[symbol]++;
235	    from_state[k] = state1;
236	    to_state[k] = state2;
237	}
238    }
239
240    FREE(temp_map + ntokens);
241}
242
243/*  Map_goto maps a state/symbol pair into its numeric representation.	*/
244
245static Value_t
246map_goto(int state, int symbol)
247{
248    int high;
249    int low;
250    int middle;
251    int s;
252
253    low = goto_map[symbol];
254    high = goto_map[symbol + 1];
255
256    for (;;)
257    {
258	assert(low <= high);
259	middle = (low + high) >> 1;
260	s = from_state[middle];
261	if (s == state)
262	    return (Value_t) (middle);
263	else if (s < state)
264	    low = middle + 1;
265	else
266	    high = middle - 1;
267    }
268}
269
270static void
271initialize_F(void)
272{
273    int i;
274    int j;
275    int k;
276    shifts *sp;
277    Value_t *edge;
278    unsigned *rowp;
279    Value_t *rp;
280    Value_t **reads;
281    int nedges;
282    int stateno;
283    int symbol;
284    int nwords;
285
286    nwords = ngotos * tokensetsize;
287    F = NEW2(nwords, unsigned);
288
289    reads = NEW2(ngotos, Value_t *);
290    edge = NEW2(ngotos + 1, Value_t);
291    nedges = 0;
292
293    rowp = F;
294    for (i = 0; i < ngotos; i++)
295    {
296	stateno = to_state[i];
297	sp = shift_table[stateno];
298
299	if (sp)
300	{
301	    k = sp->nshifts;
302
303	    for (j = 0; j < k; j++)
304	    {
305		symbol = accessing_symbol[sp->shift[j]];
306		if (ISVAR(symbol))
307		    break;
308		SETBIT(rowp, symbol);
309	    }
310
311	    for (; j < k; j++)
312	    {
313		symbol = accessing_symbol[sp->shift[j]];
314		if (nullable[symbol])
315		    edge[nedges++] = map_goto(stateno, symbol);
316	    }
317
318	    if (nedges)
319	    {
320		reads[i] = rp = NEW2(nedges + 1, Value_t);
321
322		for (j = 0; j < nedges; j++)
323		    rp[j] = edge[j];
324
325		rp[nedges] = -1;
326		nedges = 0;
327	    }
328	}
329
330	rowp += tokensetsize;
331    }
332
333    SETBIT(F, 0);
334    digraph(reads);
335
336    for (i = 0; i < ngotos; i++)
337    {
338	if (reads[i])
339	    FREE(reads[i]);
340    }
341
342    FREE(reads);
343    FREE(edge);
344}
345
346static void
347build_relations(void)
348{
349    int i;
350    int j;
351    int k;
352    Value_t *rulep;
353    Value_t *rp;
354    shifts *sp;
355    int length;
356    int nedges;
357    int done_flag;
358    Value_t state1;
359    Value_t stateno;
360    int symbol1;
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	nedges = 0;
374	state1 = from_state[i];
375	symbol1 = accessing_symbol[to_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    int k;
474
475    nedges = NEW2(n, Value_t);
476
477    for (i = 0; i < n; i++)
478    {
479	sp = R2[i];
480	if (sp)
481	{
482	    while (*sp >= 0)
483		nedges[*sp++]++;
484	}
485    }
486
487    new_R = NEW2(n, Value_t *);
488    temp_R = NEW2(n, Value_t *);
489
490    for (i = 0; i < n; i++)
491    {
492	k = nedges[i];
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    int i;
645
646    if (includes != 0)
647    {
648	for (i = 0; i < ngotos; i++)
649	{
650	    free(includes[i]);
651	}
652	DO_FREE(includes);
653    }
654}
655#endif
656