1 /* $Id: lalr.c,v 1.9 2009/10/27 09:49:27 tom Exp $ */
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);
29 static int tokensetsize;
33 Value_t *accessing_symbol;
36 reductions **reduction_table;
41 static Value_t infinity;
45 static Value_t **includes;
46 static shorts **lookback;
48 static Value_t *INDEX;
49 static Value_t *VERTICES;
55 tokensetsize = WORDSIZE(ntokens);
58 set_accessing_symbol();
60 set_reduction_table();
75 state_table = NEW2(nstates, core *);
76 for (sp = first_state; sp; sp = sp->next)
77 state_table[sp->number] = sp;
81 set_accessing_symbol(void)
85 accessing_symbol = NEW2(nstates, Value_t);
86 for (sp = first_state; sp; sp = sp->next)
87 accessing_symbol[sp->number] = sp->accessing_symbol;
95 shift_table = NEW2(nstates, shifts *);
96 for (sp = first_shift; sp; sp = sp->next)
97 shift_table[sp->number] = sp;
101 set_reduction_table(void)
105 reduction_table = NEW2(nstates, reductions *);
106 for (rp = first_reduction; rp; rp = rp->next)
107 reduction_table[rp->number] = rp;
120 item_end = ritem + nitems;
121 for (itemp = ritem; itemp < item_end; itemp++)
144 lookaheads = NEW2(nstates + 1, Value_t);
147 for (i = 0; i < nstates; i++)
149 lookaheads[i] = (Value_t) k;
150 rp = reduction_table[i];
154 lookaheads[nstates] = (Value_t) k;
156 LA = NEW2(k * tokensetsize, unsigned);
157 LAruleno = NEW2(k, Value_t);
158 lookback = NEW2(k, shorts *);
161 for (i = 0; i < nstates; i++)
163 rp = reduction_table[i];
166 for (j = 0; j < rp->nreds; j++)
168 LAruleno[k] = rp->rules[j];
186 goto_map = NEW2(nvars + 1, Value_t) - ntokens;
187 temp_map = NEW2(nvars + 1, Value_t) - ntokens;
190 for (sp = first_shift; sp; sp = sp->next)
192 for (i = sp->nshifts - 1; i >= 0; i--)
194 symbol = accessing_symbol[sp->shift[i]];
199 if (ngotos == MAXSHORT)
200 fatal("too many gotos");
208 for (i = ntokens; i < nsyms; i++)
210 temp_map[i] = (Value_t) k;
214 for (i = ntokens; i < nsyms; i++)
215 goto_map[i] = temp_map[i];
217 goto_map[nsyms] = (Value_t) ngotos;
218 temp_map[nsyms] = (Value_t) ngotos;
220 from_state = NEW2(ngotos, Value_t);
221 to_state = NEW2(ngotos, Value_t);
223 for (sp = first_shift; sp; sp = sp->next)
226 for (i = sp->nshifts - 1; i >= 0; i--)
228 state2 = sp->shift[i];
229 symbol = accessing_symbol[state2];
234 k = temp_map[symbol]++;
235 from_state[k] = state1;
236 to_state[k] = state2;
240 FREE(temp_map + ntokens);
243 /* Map_goto maps a state/symbol pair into its numeric representation. */
246 map_goto(int state, int symbol)
253 low = goto_map[symbol];
254 high = goto_map[symbol + 1];
259 middle = (low + high) >> 1;
260 s = from_state[middle];
262 return (Value_t) (middle);
286 nwords = ngotos * tokensetsize;
287 F = NEW2(nwords, unsigned);
289 reads = NEW2(ngotos, Value_t *);
290 edge = NEW2(ngotos + 1, Value_t);
294 for (i = 0; i < ngotos; i++)
296 stateno = to_state[i];
297 sp = shift_table[stateno];
303 for (j = 0; j < k; j++)
305 symbol = accessing_symbol[sp->shift[j]];
308 SETBIT(rowp, symbol);
313 symbol = accessing_symbol[sp->shift[j]];
314 if (nullable[symbol])
315 edge[nedges++] = map_goto(stateno, symbol);
320 reads[i] = rp = NEW2(nedges + 1, Value_t);
322 for (j = 0; j < nedges; j++)
330 rowp += tokensetsize;
336 for (i = 0; i < ngotos; i++)
347 build_relations(void)
365 Value_t **new_includes;
367 includes = NEW2(ngotos, Value_t *);
368 edge = NEW2(ngotos + 1, Value_t);
369 states = NEW2(maxrhs + 1, Value_t);
371 for (i = 0; i < ngotos; i++)
374 state1 = from_state[i];
375 symbol1 = accessing_symbol[to_state[i]];
377 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
383 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
386 sp = shift_table[stateno];
389 for (j = 0; j < k; j++)
391 stateno = sp->shift[j];
392 if (accessing_symbol[stateno] == symbol2)
396 states[length++] = stateno;
399 add_lookback_edge(stateno, *rulep, i);
409 stateno = states[--length];
410 edge[nedges++] = map_goto(stateno, *rp);
411 if (nullable[*rp] && length > 0)
419 includes[i] = shortp = NEW2(nedges + 1, Value_t);
420 for (j = 0; j < nedges; j++)
426 new_includes = transpose(includes, ngotos);
428 for (i = 0; i < ngotos; i++)
434 includes = new_includes;
441 add_lookback_edge(int stateno, int ruleno, int gotono)
447 i = lookaheads[stateno];
448 k = lookaheads[stateno + 1];
450 while (!found && i < k)
452 if (LAruleno[i] == ruleno)
460 sp->next = lookback[i];
461 sp->value = (Value_t) gotono;
466 transpose(Value_t ** R2, int n)
475 nedges = NEW2(n, Value_t);
477 for (i = 0; i < n; i++)
487 new_R = NEW2(n, Value_t *);
488 temp_R = NEW2(n, Value_t *);
490 for (i = 0; i < n; i++)
495 sp = NEW2(k + 1, Value_t);
504 for (i = 0; i < n; i++)
510 *temp_R[*sp++]++ = (Value_t) i;
520 compute_FOLLOWS(void)
526 compute_lookaheads(void)
529 unsigned *fp1, *fp2, *fp3;
534 n = lookaheads[nstates];
535 for (i = 0; i < n; i++)
537 fp3 = rowp + tokensetsize;
538 for (sp = lookback[i]; sp; sp = sp->next)
541 fp2 = F + tokensetsize * sp->value;
548 for (i = 0; i < n; i++)
549 for (sp = lookback[i]; sp; sp = next)
560 digraph(Value_t ** relation)
564 infinity = (Value_t) (ngotos + 2);
565 INDEX = NEW2(ngotos + 1, Value_t);
566 VERTICES = NEW2(ngotos + 1, Value_t);
571 for (i = 0; i < ngotos; i++)
574 for (i = 0; i < ngotos; i++)
576 if (INDEX[i] == 0 && R[i])
596 VERTICES[++top] = (Value_t) i;
597 INDEX[i] = height = top;
599 base = F + i * tokensetsize;
600 fp3 = base + tokensetsize;
605 while ((j = *rp++) >= 0)
610 if (INDEX[i] > INDEX[j])
614 fp2 = F + j * tokensetsize;
621 if (INDEX[i] == height)
632 fp2 = F + j * tokensetsize;
648 for (i = 0; i < ngotos; i++)