X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/3519ec76a359c6236e4f043982c6a6433b04eac5..9703cc49e0f3518e136b435b6cbcae3263eb7b7a:/src/lalr.c diff --git a/src/lalr.c b/src/lalr.c index 8e83de90..4b11caaa 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -1,46 +1,48 @@ /* Compute look-ahead criteria for bison, - Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc. + Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc. -This file is part of Bison, the GNU Compiler Compiler. + This file is part of Bison, the GNU Compiler Compiler. -Bison is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. + Bison is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. -Bison is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + Bison is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with Bison; see the file COPYING. If not, write to -the Free Software Foundation, Inc., 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ + You should have received a copy of the GNU General Public License + along with Bison; see the file COPYING. If not, write to + the Free Software Foundation, Inc., 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. */ /* Compute how to make the finite state machine deterministic; find which rules need lookahead in each state, and which lookahead - tokens they accept. */ + tokens they accept. */ #include "system.h" #include "types.h" -#include "state.h" -#include "alloc.h" +#include "LR0.h" #include "gram.h" #include "complain.h" #include "lalr.h" #include "nullable.h" +#include "derives.h" -extern short **derives; +/* 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; @@ -124,8 +126,8 @@ digraph (short **relation) int i; infinity = ngotos + 2; - INDEX = NEW2 (ngotos + 1, short); - VERTICES = NEW2 (ngotos + 1, short); + INDEX = XCALLOC (short, ngotos + 1); + VERTICES = XCALLOC (short, ngotos + 1); top = 0; R = relation; @@ -139,8 +141,8 @@ digraph (short **relation) traverse (i); } - FREE (INDEX); - FREE (VERTICES); + XFREE (INDEX); + XFREE (VERTICES); } static void @@ -148,22 +150,13 @@ set_state_table (void) { core *sp; - state_table = NEW2 (nstates, core *); + state_table = XCALLOC (state_t, nstates); for (sp = first_state; sp; sp = sp->next) - state_table[sp->number] = sp; -} - - -static void -set_accessing_symbol (void) -{ - core *sp; - - accessing_symbol = NEW2 (nstates, short); - - for (sp = first_state; sp; sp = sp->next) - accessing_symbol[sp->number] = sp->accessing_symbol; + { + state_table[sp->number].state = sp; + state_table[sp->number].accessing_symbol = sp->accessing_symbol; + } } @@ -172,7 +165,7 @@ set_shift_table (void) { shifts *sp; - shift_table = NEW2 (nstates, shifts *); + shift_table = XCALLOC (shifts *, nstates); for (sp = first_shift; sp; sp = sp->next) shift_table[sp->number] = sp; @@ -184,7 +177,7 @@ set_reduction_table (void) { reductions *rp; - reduction_table = NEW2 (nstates, reductions *); + reduction_table = XCALLOC (reductions *, nstates); for (rp = first_reduction; rp; rp = rp->next) reduction_table[rp->number] = rp; @@ -228,8 +221,8 @@ initialize_LA (void) shifts *sp; short *np; - consistent = NEW2 (nstates, char); - lookaheads = NEW2 (nstates + 1, short); + consistent = XCALLOC (char, nstates); + lookaheads = XCALLOC (short, nstates + 1); count = 0; for (i = 0; i < nstates; i++) @@ -240,36 +233,36 @@ initialize_LA (void) rp = reduction_table[i]; sp = shift_table[i]; - if (rp && (rp->nreds > 1 - || (sp && !ISVAR (accessing_symbol[sp->shifts[0]])))) + if (rp + && (rp->nreds > 1 + || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol)))) 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; - } - } + if (state_table[sp->shifts[k]].accessing_symbol + == error_token_number) + { + consistent[i] = 0; + break; + } } lookaheads[nstates] = count; if (count == 0) { - LA = NEW2 (1 * tokensetsize, unsigned); - LAruleno = NEW2 (1, short); - lookback = NEW2 (1, shorts *); + LA = XCALLOC (unsigned, 1 * tokensetsize); + LAruleno = XCALLOC (short, 1); + lookback = XCALLOC (shorts *, 1); } else { - LA = NEW2 (count * tokensetsize, unsigned); - LAruleno = NEW2 (count, short); - lookback = NEW2 (count, shorts *); + LA = XCALLOC (unsigned, count * tokensetsize); + LAruleno = XCALLOC (short, count); + lookback = XCALLOC (shorts *, count); } np = LAruleno; @@ -296,15 +289,15 @@ set_goto_map (void) int state2; int state1; - goto_map = NEW2 (nvars + 1, short) - ntokens; - temp_map = NEW2 (nvars + 1, short) - ntokens; + goto_map = XCALLOC (short, nvars + 1) - ntokens; + temp_map = XCALLOC (short, nvars + 1) - ntokens; ngotos = 0; for (sp = first_shift; sp; sp = sp->next) { 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; @@ -330,8 +323,8 @@ set_goto_map (void) goto_map[nsyms] = ngotos; temp_map[nsyms] = ngotos; - from_state = NEW2 (ngotos, short); - to_state = NEW2 (ngotos, short); + from_state = XCALLOC (short, ngotos); + to_state = XCALLOC (short, ngotos); for (sp = first_shift; sp; sp = sp->next) { @@ -339,7 +332,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; @@ -350,12 +343,14 @@ set_goto_map (void) } } - FREE (temp_map + ntokens); + XFREE (temp_map + ntokens); } -/* Map_goto maps a state/symbol pair into its numeric representation. */ +/*----------------------------------------------------------. +| Map a state/symbol pair into its numeric representation. | +`----------------------------------------------------------*/ static int map_goto (int state, int symbol) @@ -380,8 +375,8 @@ map_goto (int state, int symbol) high = middle - 1; } - berror ("map_goto"); -/* NOTREACHED */ + assert (0); + /* NOTREACHED */ return 0; } @@ -403,10 +398,10 @@ initialize_F (void) int nwords; nwords = ngotos * tokensetsize; - F = NEW2 (nwords, unsigned); + F = XCALLOC (unsigned, nwords); - reads = NEW2 (ngotos, short *); - edge = NEW2 (ngotos + 1, short); + reads = XCALLOC (short *, ngotos); + edge = XCALLOC (short, ngotos + 1); nedges = 0; rowp = F; @@ -421,7 +416,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,14 +424,14 @@ 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); } if (nedges) { - reads[i] = rp = NEW2 (nedges + 1, short); + reads[i] = rp = XCALLOC (short, nedges + 1); for (j = 0; j < nedges; j++) rp[j] = edge[j]; @@ -454,11 +449,11 @@ initialize_F (void) for (i = 0; i < ngotos; i++) { if (reads[i]) - FREE (reads[i]); + XFREE (reads[i]); } - FREE (reads); - FREE (edge); + XFREE (reads); + XFREE (edge); } @@ -481,10 +476,9 @@ add_lookback_edge (int stateno, int ruleno, int gotono) i++; } - if (found == 0) - berror ("add_lookback_edge"); + assert (found); - sp = NEW (shorts); + sp = XCALLOC (shorts, 1); sp->next = lookback[i]; sp->value = gotono; lookback[i] = sp; @@ -501,7 +495,7 @@ transpose (short **R_arg, int n) int i; int k; - nedges = NEW2 (n, short); + nedges = XCALLOC (short, n); for (i = 0; i < n; i++) { @@ -513,22 +507,22 @@ transpose (short **R_arg, int n) } } - new_R = NEW2 (n, short *); - temp_R = NEW2 (n, short *); + new_R = XCALLOC (short *, n); + temp_R = XCALLOC (short *, n); for (i = 0; i < n; i++) { k = nedges[i]; if (k > 0) { - sp = NEW2 (k + 1, short); + sp = XCALLOC (short, k + 1); new_R[i] = sp; temp_R[i] = sp; sp[k] = -1; } } - FREE (nedges); + XFREE (nedges); for (i = 0; i < n; i++) { @@ -540,7 +534,7 @@ transpose (short **R_arg, int n) } } - FREE (temp_R); + XFREE (temp_R); return new_R; } @@ -567,15 +561,15 @@ build_relations (void) short *states; short **new_includes; - includes = NEW2 (ngotos, short *); - edge = NEW2 (ngotos + 1, short); - states = NEW2 (maxrhs + 1, short); + includes = XCALLOC (short *, ngotos); + edge = XCALLOC (short, ngotos + 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++) { @@ -592,7 +586,7 @@ build_relations (void) for (j = 0; j < k; j++) { stateno = sp->shifts[j]; - if (accessing_symbol[stateno] == symbol2) + if (state_table[stateno].accessing_symbol == symbol2) break; } @@ -621,7 +615,7 @@ build_relations (void) if (nedges) { - includes[i] = shortp = NEW2 (nedges + 1, short); + includes[i] = shortp = XCALLOC (short, nedges + 1); for (j = 0; j < nedges; j++) shortp[j] = edge[j]; shortp[nedges] = -1; @@ -632,14 +626,14 @@ build_relations (void) for (i = 0; i < ngotos; i++) if (includes[i]) - FREE (includes[i]); + XFREE (includes[i]); - FREE (includes); + XFREE (includes); includes = new_includes; - FREE (edge); - FREE (states); + XFREE (edge); + XFREE (states); } @@ -654,10 +648,10 @@ compute_FOLLOWS (void) for (i = 0; i < ngotos; i++) { if (includes[i]) - FREE (includes[i]); + XFREE (includes[i]); } - FREE (includes); + XFREE (includes); } @@ -695,12 +689,12 @@ compute_lookaheads (void) for (sp = lookback[i]; sp; sp = sptmp) { sptmp = sp->next; - FREE (sp); + XFREE (sp); } } - FREE (lookback); - FREE (F); + XFREE (lookback); + XFREE (F); } @@ -710,7 +704,6 @@ lalr (void) tokensetsize = WORDSIZE (ntokens); set_state_table (); - set_accessing_symbol (); set_shift_table (); set_reduction_table (); set_maxrhs ();