1 /* $Id: lalr.c,v 1.11 2014/09/18 00:26:39 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;
42 static Value_t infinity;
46 static Value_t **includes;
47 static shorts **lookback;
49 static Value_t *INDEX;
50 static Value_t *VERTICES;
56 tokensetsize = WORDSIZE(ntokens);
59 set_accessing_symbol();
61 set_reduction_table();
76 state_table = NEW2(nstates, core *);
77 for (sp = first_state; sp; sp = sp->next)
78 state_table[sp->number] = sp;
82 set_accessing_symbol(void)
86 accessing_symbol = NEW2(nstates, Value_t);
87 for (sp = first_state; sp; sp = sp->next)
88 accessing_symbol[sp->number] = sp->accessing_symbol;
96 shift_table = NEW2(nstates, shifts *);
97 for (sp = first_shift; sp; sp = sp->next)
98 shift_table[sp->number] = sp;
102 set_reduction_table(void)
106 reduction_table = NEW2(nstates, reductions *);
107 for (rp = first_reduction; rp; rp = rp->next)
108 reduction_table[rp->number] = rp;
121 item_end = ritem + nitems;
122 for (itemp = ritem; itemp < item_end; itemp++)
145 lookaheads = NEW2(nstates + 1, Value_t);
148 for (i = 0; i < nstates; i++)
150 lookaheads[i] = (Value_t) k;
151 rp = reduction_table[i];
155 lookaheads[nstates] = (Value_t) k;
157 LA = NEW2(k * tokensetsize, unsigned);
158 LAruleno = NEW2(k, Value_t);
159 lookback = NEW2(k, shorts *);
162 for (i = 0; i < nstates; i++)
164 rp = reduction_table[i];
167 for (j = 0; j < rp->nreds; j++)
169 LAruleno[k] = rp->rules[j];
188 goto_base = NEW2(nvars + 1, Value_t);
189 temp_base = NEW2(nvars + 1, Value_t);
191 goto_map = goto_base - ntokens;
192 temp_map = temp_base - ntokens;
195 for (sp = first_shift; sp; sp = sp->next)
197 for (i = sp->nshifts - 1; i >= 0; i--)
199 symbol = accessing_symbol[sp->shift[i]];
204 if (ngotos == MAXYYINT)
205 fatal("too many gotos");
213 for (i = ntokens; i < nsyms; i++)
215 temp_map[i] = (Value_t) k;
219 for (i = ntokens; i < nsyms; i++)
220 goto_map[i] = temp_map[i];
222 goto_map[nsyms] = (Value_t) ngotos;
223 temp_map[nsyms] = (Value_t) ngotos;
225 from_state = NEW2(ngotos, Value_t);
226 to_state = NEW2(ngotos, Value_t);
228 for (sp = first_shift; sp; sp = sp->next)
231 for (i = sp->nshifts - 1; i >= 0; i--)
233 state2 = sp->shift[i];
234 symbol = accessing_symbol[state2];
239 k = temp_map[symbol]++;
240 from_state[k] = state1;
241 to_state[k] = state2;
248 /* Map_goto maps a state/symbol pair into its numeric representation. */
251 map_goto(int state, int symbol)
258 low = goto_map[symbol];
259 high = goto_map[symbol + 1];
264 middle = (low + high) >> 1;
265 s = from_state[middle];
267 return (Value_t) (middle);
291 nwords = ngotos * tokensetsize;
292 F = NEW2(nwords, unsigned);
294 reads = NEW2(ngotos, Value_t *);
295 edge = NEW2(ngotos + 1, Value_t);
299 for (i = 0; i < ngotos; i++)
301 stateno = to_state[i];
302 sp = shift_table[stateno];
308 for (j = 0; j < k; j++)
310 symbol = accessing_symbol[sp->shift[j]];
313 SETBIT(rowp, symbol);
318 symbol = accessing_symbol[sp->shift[j]];
319 if (nullable[symbol])
320 edge[nedges++] = map_goto(stateno, symbol);
325 reads[i] = rp = NEW2(nedges + 1, Value_t);
327 for (j = 0; j < nedges; j++)
335 rowp += tokensetsize;
341 for (i = 0; i < ngotos; i++)
352 build_relations(void)
370 Value_t **new_includes;
372 includes = NEW2(ngotos, Value_t *);
373 edge = NEW2(ngotos + 1, Value_t);
374 states = NEW2(maxrhs + 1, Value_t);
376 for (i = 0; i < ngotos; i++)
379 state1 = from_state[i];
380 symbol1 = accessing_symbol[to_state[i]];
382 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
388 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
391 sp = shift_table[stateno];
394 for (j = 0; j < k; j++)
396 stateno = sp->shift[j];
397 if (accessing_symbol[stateno] == symbol2)
401 states[length++] = stateno;
404 add_lookback_edge(stateno, *rulep, i);
414 stateno = states[--length];
415 edge[nedges++] = map_goto(stateno, *rp);
416 if (nullable[*rp] && length > 0)
424 includes[i] = shortp = NEW2(nedges + 1, Value_t);
425 for (j = 0; j < nedges; j++)
431 new_includes = transpose(includes, ngotos);
433 for (i = 0; i < ngotos; i++)
439 includes = new_includes;
446 add_lookback_edge(int stateno, int ruleno, int gotono)
452 i = lookaheads[stateno];
453 k = lookaheads[stateno + 1];
455 while (!found && i < k)
457 if (LAruleno[i] == ruleno)
465 sp->next = lookback[i];
466 sp->value = (Value_t) gotono;
471 transpose(Value_t ** R2, int n)
480 nedges = NEW2(n, Value_t);
482 for (i = 0; i < n; i++)
492 new_R = NEW2(n, Value_t *);
493 temp_R = NEW2(n, Value_t *);
495 for (i = 0; i < n; i++)
500 sp = NEW2(k + 1, Value_t);
509 for (i = 0; i < n; i++)
515 *temp_R[*sp++]++ = (Value_t) i;
525 compute_FOLLOWS(void)
531 compute_lookaheads(void)
534 unsigned *fp1, *fp2, *fp3;
539 n = lookaheads[nstates];
540 for (i = 0; i < n; i++)
542 fp3 = rowp + tokensetsize;
543 for (sp = lookback[i]; sp; sp = sp->next)
546 fp2 = F + tokensetsize * sp->value;
553 for (i = 0; i < n; i++)
554 for (sp = lookback[i]; sp; sp = next)
565 digraph(Value_t ** relation)
569 infinity = (Value_t) (ngotos + 2);
570 INDEX = NEW2(ngotos + 1, Value_t);
571 VERTICES = NEW2(ngotos + 1, Value_t);
576 for (i = 0; i < ngotos; i++)
579 for (i = 0; i < ngotos; i++)
581 if (INDEX[i] == 0 && R[i])
601 VERTICES[++top] = (Value_t) i;
602 INDEX[i] = height = top;
604 base = F + i * tokensetsize;
605 fp3 = base + tokensetsize;
610 while ((j = *rp++) >= 0)
615 if (INDEX[i] > INDEX[j])
619 fp2 = F + j * tokensetsize;
626 if (INDEX[i] == height)
637 fp2 = F + j * tokensetsize;
653 for (i = 0; i < ngotos; i++)