X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/dac3c910059dc8a137355d5c58dfd3a9ad6fbbe1..616429b50868bf9225d55143526442a024e32969:/src/lalr.c diff --git a/src/lalr.c b/src/lalr.c index be178b8d..c16c6f52 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -24,8 +24,10 @@ tokens they accept. */ #include "system.h" +#include "reader.h" #include "types.h" #include "LR0.h" +#include "symtab.h" #include "gram.h" #include "complain.h" #include "lalr.h" @@ -34,7 +36,7 @@ #include "getargs.h" /* All the decorated states, indexed by the state number. */ -state_t **state_table = NULL; +state_t **states = NULL; int tokensetsize; short *LAruleno; @@ -137,7 +139,6 @@ initialize_LA (void) int i; int j; short *np; - reductions *rp; /* Avoid having to special case 0. */ if (!nLA) @@ -149,10 +150,9 @@ initialize_LA (void) np = LAruleno; for (i = 0; i < nstates; i++) - if (!state_table[i]->consistent) - if ((rp = state_table[i]->reductions)) - for (j = 0; j < rp->nreds; j++) - *np++ = rp->rules[j]; + if (!states[i]->consistent) + for (j = 0; j < states[i]->reductions->nreds; j++) + *np++ = states[i]->reductions->rules[j]; } @@ -168,16 +168,14 @@ set_goto_map (void) ngotos = 0; for (state = 0; state < nstates; ++state) { - shifts *sp = state_table[state]->shifts; + shifts *sp = states[state]->shifts; for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) { - int symbol = state_table[sp->shifts[i]]->accessing_symbol; - if (ngotos == MAXSHORT) fatal (_("too many gotos (max %d)"), MAXSHORT); ngotos++; - goto_map[symbol]++; + goto_map[SHIFT_SYMBOL (sp, i)]++; } } @@ -201,15 +199,12 @@ set_goto_map (void) for (state = 0; state < nstates; ++state) { - shifts *sp = state_table[state]->shifts; + shifts *sp = states[state]->shifts; for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) { - int state2 = sp->shifts[i]; - int symbol = state_table[state2]->accessing_symbol; - - int k = temp_map[symbol]++; + int k = temp_map[SHIFT_SYMBOL (sp, i)]++; from_state[k] = state; - to_state[k] = state2; + to_state[k] = sp->shifts[i]; } } @@ -265,18 +260,15 @@ initialize_F (void) for (i = 0; i < ngotos; i++) { int stateno = to_state[i]; - shifts *sp = state_table[stateno]->shifts; + shifts *sp = states[stateno]->shifts; int j; for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++) - { - int symbol = state_table[sp->shifts[j]]->accessing_symbol; - SETBIT (F (i), symbol); - } + SETBIT (F (i), SHIFT_SYMBOL (sp, j)); for (; j < sp->nshifts; j++) { - int symbol = state_table[sp->shifts[j]]->accessing_symbol; + int symbol = SHIFT_SYMBOL (sp, j); if (nullable[symbol]) edge[nedges++] = map_goto (stateno, symbol); } @@ -409,7 +401,7 @@ static void build_relations (void) { short *edge = XCALLOC (short, ngotos + 1); - short *states = XCALLOC (short, ritem_longest_rhs () + 1); + short *states1 = XCALLOC (short, ritem_longest_rhs () + 1); int i; includes = XCALLOC (short *, ngotos); @@ -417,7 +409,7 @@ build_relations (void) for (i = 0; i < ngotos; i++) { int nedges = 0; - int symbol1 = state_table[to_state[i]]->accessing_symbol; + int symbol1 = states[to_state[i]]->accessing_symbol; short *rulep; for (rulep = derives[symbol1]; *rulep > 0; rulep++) @@ -425,21 +417,21 @@ build_relations (void) int done; int length = 1; short *rp; - state_t *state = state_table[from_state[i]]; - states[0] = state->number; + state_t *state = states[from_state[i]]; + states1[0] = state->number; - for (rp = ritem + rule_table[*rulep].rhs; *rp > 0; rp++) + for (rp = &ritem[rules[*rulep].rhs]; *rp >= 0; rp++) { shifts *sp = state->shifts; int j; for (j = 0; j < sp->nshifts; j++) { - state = state_table[sp->shifts[j]]; + state = states[sp->shifts[j]]; if (state->accessing_symbol == *rp) break; } - states[length++] = state->number; + states1[length++] = state->number; } if (!state->consistent) @@ -454,7 +446,7 @@ build_relations (void) /* JF added rp>=ritem && I hope to god its right! */ if (rp >= ritem && ISVAR (*rp)) { - edge[nedges++] = map_goto (states[--length], *rp); + edge[nedges++] = map_goto (states1[--length], *rp); if (nullable[*rp]) done = 0; } @@ -472,7 +464,7 @@ build_relations (void) } XFREE (edge); - XFREE (states); + XFREE (states1); includes = transpose (includes, ngotos); } @@ -530,28 +522,57 @@ initialize_lookaheads (void) { int k; int nlookaheads = 0; - reductions *rp = state_table[i]->reductions; - shifts *sp = state_table[i]->shifts; - - if (rp - && (rp->nreds > 1 || (sp->nshifts && SHIFT_IS_SHIFT (sp, 0)))) + reductions *rp = states[i]->reductions; + shifts *sp = states[i]->shifts; + + /* We need a lookahead either to distinguish different + reductions (i.e., there are two or more), or to distinguish a + reduction from a shift. Otherwise, it is straightforward, + and the state is `consistent'. */ + if (rp->nreds > 1 + || (rp->nreds == 1 && sp->nshifts && SHIFT_IS_SHIFT (sp, 0))) nlookaheads += rp->nreds; else - state_table[i]->consistent = 1; + states[i]->consistent = 1; for (k = 0; k < sp->nshifts; k++) if (SHIFT_IS_ERROR (sp, k)) { - state_table[i]->consistent = 0; + states[i]->consistent = 0; break; } - state_table[i]->nlookaheads = nlookaheads; - state_table[i]->lookaheadsp = nLA; + states[i]->nlookaheads = nlookaheads; + states[i]->lookaheadsp = nLA; nLA += nlookaheads; } } + +/*---------------------------------------. +| Output the lookaheads for each state. | +`---------------------------------------*/ + +static void +lookaheads_print (FILE *out) +{ + int i, j, k; + fprintf (out, "Lookaheads: BEGIN\n"); + for (i = 0; i < nstates; ++i) + { + fprintf (out, "State %d: %d lookaheads\n", + i, states[i]->nlookaheads); + + for (j = 0; j < states[i]->nlookaheads; ++j) + for (k = 0; k < ntokens; ++k) + if (BITISSET (LA (states[i]->lookaheadsp + j), j)) + fprintf (out, " on %d (%s) -> rule %d\n", + k, symbols[k]->tag, + -LAruleno[states[i]->lookaheadsp + j] - 1); + } + fprintf (out, "Lookaheads: END\n"); +} + void lalr (void) { @@ -564,4 +585,7 @@ lalr (void) build_relations (); compute_FOLLOWS (); compute_lookaheads (); + + if (trace_flag) + lookaheads_print (stderr); }