X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/342b8b6e2156e923797745af2da2596e3086ccd5..3feec03433c1d0b0aed2a17dd6ffde6a37667647:/src/lalr.c diff --git a/src/lalr.c b/src/lalr.c index 48635ef3..c6d3f5c3 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -1,5 +1,5 @@ /* Compute look-ahead criteria for bison, - Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc. + Copyright 1984, 1986, 1989, 2000, 2001 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -32,15 +32,15 @@ #include "nullable.h" #include "derives.h" +/* All the decorated states, indexed by the state number. Warning: + there is a state_TABLE in LR0.c, but it is different and static. + */ +state_t *state_table = NULL; + int tokensetsize; -short *lookaheads; short *LAruleno; unsigned *LA; -short *accessing_symbol; -char *consistent; -core **state_table; -shifts **shift_table; -reductions **reduction_table; + short *goto_map; short *from_state; short *to_state; @@ -48,9 +48,13 @@ short *to_state; extern void berror PARAMS ((const char *)); static int infinity; -static int maxrhs; static int ngotos; -static unsigned *F; + +/* And for the famous F variable, which named is so descriptive that a + comment is hardly needed. . */ +static unsigned *F = NULL; +#define F(Rule) (F + (Rule) * tokensetsize) + static short **includes; static shorts **lookback; static short **R; @@ -74,8 +78,8 @@ traverse (int i) VERTICES[++top] = i; INDEX[i] = height = top; - base = F + i * tokensetsize; - fp3 = base + tokensetsize; + base = F (i); + fp3 = F (i + 1); rp = R[i]; if (rp) @@ -89,7 +93,7 @@ traverse (int i) INDEX[i] = INDEX[j]; fp1 = base; - fp2 = F + j * tokensetsize; + fp2 = F (j); while (fp1 < fp3) *fp1++ |= *fp2++; @@ -107,7 +111,7 @@ traverse (int i) break; fp1 = base; - fp2 = F + j * tokensetsize; + fp2 = F (j); while (fp1 < fp3) *fp2++ = *fp1++; @@ -132,65 +136,85 @@ digraph (short **relation) INDEX[i] = 0; for (i = 0; i < ngotos; i++) - { - if (INDEX[i] == 0 && R[i]) - traverse (i); - } + if (INDEX[i] == 0 && R[i]) + traverse (i); XFREE (INDEX); XFREE (VERTICES); } -static void -set_state_table (void) -{ - core *sp; - - state_table = XCALLOC (core *, nstates); - - for (sp = first_state; sp; sp = sp->next) - state_table[sp->number] = sp; -} - - -static void -set_accessing_symbol (void) -{ - core *sp; - - accessing_symbol = XCALLOC (short, nstates); - - for (sp = first_state; sp; sp = sp->next) - accessing_symbol[sp->number] = sp->accessing_symbol; -} +/*--------------------. +| Build STATE_TABLE. | +`--------------------*/ static void -set_shift_table (void) -{ - shifts *sp; - - shift_table = XCALLOC (shifts *, nstates); - - for (sp = first_shift; sp; sp = sp->next) - shift_table[sp->number] = sp; -} - - -static void -set_reduction_table (void) +set_state_table (void) { - reductions *rp; - - reduction_table = XCALLOC (reductions *, nstates); - - for (rp = first_reduction; rp; rp = rp->next) - reduction_table[rp->number] = rp; + /* NSTATES + 1 because lookahead for the pseudo state number NSTATES + might be used (see conflicts.c). It is too opaque for me to + provide a probably less hacky implementation. --akim */ + state_table = XCALLOC (state_t, nstates + 1); + + { + core *sp; + for (sp = first_state; sp; sp = sp->next) + { + state_table[sp->number].state = sp; + state_table[sp->number].accessing_symbol = sp->accessing_symbol; + } + } + + { + shifts *sp; + for (sp = first_shift; sp; sp = sp->next) + state_table[sp->number].shift_table = sp; + } + + { + reductions *rp; + for (rp = first_reduction; rp; rp = rp->next) + state_table[rp->number].reduction_table = rp; + } + + /* Initializing the lookaheads members. Please note that it must be + performed after having set some of the other members which are + used below. Change with extreme caution. */ + { + int i; + int count = 0; + for (i = 0; i < nstates; i++) + { + int k; + reductions *rp = state_table[i].reduction_table; + shifts *sp = state_table[i].shift_table; + + state_table[i].lookaheads = count; + + if (rp + && (rp->nreds > 1 + || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol)))) + count += rp->nreds; + else + state_table[i].consistent = 1; + + if (sp) + for (k = 0; k < sp->nshifts; k++) + if (state_table[sp->shifts[k]].accessing_symbol + == error_token_number) + { + state_table[i].consistent = 0; + break; + } + } + state_table[nstates].lookaheads = count; + } } -static void -set_maxrhs (void) +/* Return the size of the longest ride hand side of the rules. */ +static size_t +maxrhs (void) { short *itemp; int length; @@ -212,7 +236,7 @@ set_maxrhs (void) } } - maxrhs = max; + return max; } @@ -221,65 +245,23 @@ initialize_LA (void) { int i; int j; - int count; - reductions *rp; - shifts *sp; short *np; + reductions *rp; - consistent = XCALLOC (char, nstates); - lookaheads = XCALLOC (short, nstates + 1); - - count = 0; - for (i = 0; i < nstates; i++) - { - int k; - - lookaheads[i] = count; - - rp = reduction_table[i]; - sp = shift_table[i]; - if (rp && (rp->nreds > 1 - || (sp && !ISVAR (accessing_symbol[sp->shifts[0]])))) - count += rp->nreds; - else - consistent[i] = 1; - - if (sp) - for (k = 0; k < sp->nshifts; k++) - { - if (accessing_symbol[sp->shifts[k]] == error_token_number) - { - consistent[i] = 0; - break; - } - } - } - - lookaheads[nstates] = count; + size_t nLA = state_table[nstates].lookaheads; + if (!nLA) + nLA = 1; - if (count == 0) - { - LA = XCALLOC (unsigned, 1 * tokensetsize); - LAruleno = XCALLOC (short, 1); - lookback = XCALLOC (shorts *, 1); - } - else - { - LA = XCALLOC (unsigned, count * tokensetsize); - LAruleno = XCALLOC (short, count); - lookback = XCALLOC (shorts *, count); - } + LA = XCALLOC (unsigned, nLA * tokensetsize); + LAruleno = XCALLOC (short, nLA); + lookback = XCALLOC (shorts *, nLA); np = LAruleno; for (i = 0; i < nstates; i++) - { - if (!consistent[i]) - { - if ((rp = reduction_table[i])) - for (j = 0; j < rp->nreds; j++) - *np++ = rp->rules[j]; - } - } + if (!state_table[i].consistent) + if ((rp = state_table[i].reduction_table)) + for (j = 0; j < rp->nreds; j++) + *np++ = rp->rules[j]; } @@ -302,7 +284,7 @@ set_goto_map (void) { for (i = sp->nshifts - 1; i >= 0; i--) { - symbol = accessing_symbol[sp->shifts[i]]; + symbol = state_table[sp->shifts[i]].accessing_symbol; if (ISTOKEN (symbol)) break; @@ -337,7 +319,7 @@ set_goto_map (void) for (i = sp->nshifts - 1; i >= 0; i--) { state2 = sp->shifts[i]; - symbol = accessing_symbol[state2]; + symbol = state_table[state2].accessing_symbol; if (ISTOKEN (symbol)) break; @@ -413,7 +395,7 @@ initialize_F (void) for (i = 0; i < ngotos; i++) { stateno = to_state[i]; - sp = shift_table[stateno]; + sp = state_table[stateno].shift_table; if (sp) { @@ -421,7 +403,7 @@ initialize_F (void) for (j = 0; j < k; j++) { - symbol = accessing_symbol[sp->shifts[j]]; + symbol = state_table[sp->shifts[j]].accessing_symbol; if (ISVAR (symbol)) break; SETBIT (rowp, symbol); @@ -429,7 +411,7 @@ initialize_F (void) for (; j < k; j++) { - symbol = accessing_symbol[sp->shifts[j]]; + symbol = state_table[sp->shifts[j]].accessing_symbol; if (nullable[symbol]) edge[nedges++] = map_goto (stateno, symbol); } @@ -452,10 +434,7 @@ initialize_F (void) digraph (reads); for (i = 0; i < ngotos; i++) - { - if (reads[i]) - XFREE (reads[i]); - } + XFREE (reads[i]); XFREE (reads); XFREE (edge); @@ -470,8 +449,8 @@ add_lookback_edge (int stateno, int ruleno, int gotono) int found; shorts *sp; - i = lookaheads[stateno]; - k = lookaheads[stateno + 1]; + i = state_table[stateno].lookaheads; + k = state_table[stateno + 1].lookaheads; found = 0; while (!found && i < k) { @@ -568,13 +547,13 @@ build_relations (void) includes = XCALLOC (short *, ngotos); edge = XCALLOC (short, ngotos + 1); - states = XCALLOC (short, maxrhs + 1); + states = XCALLOC (short, maxrhs () + 1); for (i = 0; i < ngotos; i++) { nedges = 0; state1 = from_state[i]; - symbol1 = accessing_symbol[to_state[i]]; + symbol1 = state_table[to_state[i]].accessing_symbol; for (rulep = derives[symbol1]; *rulep > 0; rulep++) { @@ -585,20 +564,20 @@ build_relations (void) for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++) { symbol2 = *rp; - sp = shift_table[stateno]; + sp = state_table[stateno].shift_table; k = sp->nshifts; for (j = 0; j < k; j++) { stateno = sp->shifts[j]; - if (accessing_symbol[stateno] == symbol2) + if (state_table[stateno].accessing_symbol == symbol2) break; } states[length++] = stateno; } - if (!consistent[stateno]) + if (!state_table[stateno].consistent) add_lookback_edge (stateno, *rulep, i); length--; @@ -651,10 +630,7 @@ compute_FOLLOWS (void) digraph (includes); for (i = 0; i < ngotos; i++) - { - if (includes[i]) - XFREE (includes[i]); - } + XFREE (includes[i]); XFREE (includes); } @@ -664,33 +640,21 @@ static void compute_lookaheads (void) { int i; - int n; - unsigned *fp1; - unsigned *fp2; - unsigned *fp3; shorts *sp; - unsigned *rowp; - shorts *sptmp; /* JF */ - rowp = LA; - n = lookaheads[nstates]; - for (i = 0; i < n; i++) - { - fp3 = rowp + tokensetsize; - for (sp = lookback[i]; sp; sp = sp->next) - { - fp1 = rowp; - fp2 = F + tokensetsize * sp->value; - while (fp1 < fp3) - *fp1++ |= *fp2++; - } - - rowp = fp3; - } - - for (i = 0; i < n; i++) + for (i = 0; i < state_table[nstates].lookaheads; i++) + for (sp = lookback[i]; sp; sp = sp->next) + { + unsigned *fp1 = LA (i); + unsigned *fp2 = F (sp->value); + while (fp1 < LA (i + 1)) + *fp1++ |= *fp2++; + } + + /* Free LOOKBACK. */ + for (i = 0; i < state_table[nstates].lookaheads; i++) { - /* JF removed ref to freed storage */ + shorts *sptmp; for (sp = lookback[i]; sp; sp = sptmp) { sptmp = sp->next; @@ -709,10 +673,6 @@ lalr (void) tokensetsize = WORDSIZE (ntokens); set_state_table (); - set_accessing_symbol (); - set_shift_table (); - set_reduction_table (); - set_maxrhs (); initialize_LA (); set_goto_map (); initialize_F ();