From: Akim Demaille Date: Wed, 5 Dec 2001 09:34:55 +0000 (+0000) Subject: Pessimize the code to simplify it: from now on, all the states X-Git-Tag: before-m4-back-end~195 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/d954473deedae21f333fc4a10b3b1649179ff2e0 Pessimize the code to simplify it: from now on, all the states have a valid SHIFTS, which NSHIFTS is possibly 0. * src/LR0.c (shifts_new): Be global and move to.. * src/state.c, src/state.h: here. * src/conflicts, src/lalr.c, src/output.c, src/print.c, * src/print_graph: Adjust. --- diff --git a/ChangeLog b/ChangeLog index eb53eab6..f77d7f24 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,14 @@ +2001-12-05 Akim Demaille + + Pessimize the code to simplify it: from now on, all the states + have a valid SHIFTS, which NSHIFTS is possibly 0. + + * src/LR0.c (shifts_new): Be global and move to.. + * src/state.c, src/state.h: here. + * src/conflicts, src/lalr.c, src/output.c, src/print.c, + * src/print_graph: Adjust. + + 2001-12-05 Akim Demaille * src/state.h (SHIFT_DISABLE, SHIFT_IS_DISABLED): New. diff --git a/src/LR0.c b/src/LR0.c index 94a2ed84..6910f3e0 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -314,19 +314,6 @@ new_states (void) } -/*---------------------------------. -| Create a new array of N shitfs. | -`---------------------------------*/ - -static shifts * -shifts_new (int n) -{ - shifts *res = SHIFTS_ALLOC (n); - res->nshifts = n; - return res; -} - - /*------------------------------------------------------------. | Save the NSHIFTS of SHIFTSET into the current linked list. | `------------------------------------------------------------*/ @@ -393,7 +380,7 @@ augment_automaton (void) sp = first_shift; - if (!sp) + if (!sp->nshifts) { /* There are no shifts for any state. Make one shift, from the initial state to the next-to-final state. */ @@ -610,8 +597,7 @@ generate_states (void) /* create the shifts structures for the shifts to those states, now that the state numbers transitioning to are known */ - if (nshifts > 0) - save_shifts (); + save_shifts (); /* states are queued when they are created; process them all */ this_state = this_state->next; diff --git a/src/Makefile.am b/src/Makefile.am index 922bd9df..067bc110 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -38,8 +38,11 @@ bin_PROGRAMS = bison bison_SOURCES = LR0.c closure.c complain.c conflicts.c \ derives.c \ files.c getargs.c gram.c lalr.c lex.c main.c nullable.c \ - output.c print_graph.c \ - muscle_tab.c options.c \ + output.h output.c \ + state.h state.c \ + print_graph.h print_graph.c \ + muscle_tab.h muscle_tab.c \ + options.h options.c \ print.c reader.c reduce.c symtab.c warshall.c vcg.c EXTRA_bison_SOURCES = vmsgetargs.c @@ -47,9 +50,7 @@ EXTRA_bison_SOURCES = vmsgetargs.c noinst_HEADERS = LR0.h closure.h complain.h conflicts.h \ derives.h \ files.h getargs.h gram.h lalr.h lex.h nullable.h \ - output.h print_graph.h \ - muscle_tab.h options.h \ - print.h reader.h reduce.h state.h symtab.h warshall.h system.h \ + print.h reader.h reduce.h symtab.h warshall.h system.h \ types.h vcg.h vcg_defaults.h pkgdata_DATA = bison.simple bison.hairy diff --git a/src/conflicts.c b/src/conflicts.c index a9bf9519..f4b08ede 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -60,10 +60,9 @@ flush_shift (int state, int token) shifts *shiftp = state_table[state].shift_table; int i; - if (shiftp) - for (i = 0; i < shiftp->nshifts; i++) - if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token) - SHIFT_DISABLE (shiftp, i); + for (i = 0; i < shiftp->nshifts; i++) + if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token) + SHIFT_DISABLE (shiftp, i); } @@ -174,10 +173,9 @@ set_conflicts (int state) lookaheadset[i] = 0; shiftp = state_table[state].shift_table; - if (shiftp) - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i)); + for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) + SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i)); /* Loop over all rules which require lookahead in this state. First check for shift-reduce conflict, and try to resolve using @@ -436,16 +434,15 @@ print_reductions (FILE *out, int state) shiftset[i] = 0; shiftp = state_table[state].shift_table; - if (shiftp) - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - { - /* if this state has a shift for the error token, don't use a - default rule. */ - if (SHIFT_IS_ERROR (shiftp, i)) - nodefault = 1; - SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); - } + for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) + { + /* if this state has a shift for the error token, don't use a + default rule. */ + if (SHIFT_IS_ERROR (shiftp, i)) + nodefault = 1; + SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); + } errp = err_table[state]; if (errp) @@ -507,10 +504,9 @@ print_reductions (FILE *out, int state) for (i = 0; i < tokensetsize; i++) shiftset[i] = 0; - if (shiftp) - for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) - if (!SHIFT_IS_DISABLED (shiftp, i)) - SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); + for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) + SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); for (i = 0; i < ntokens; i++) { diff --git a/src/lalr.c b/src/lalr.c index e6738bda..4b1a4d49 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -165,6 +165,15 @@ set_state_table (void) state_table[rp->number].reduction_table = rp; } + /* Pessimization, but simplification of the code: make sense all the + states have a shift_table, even if reduced to 0 shifts. */ + { + int i; + for (i = 0; i < nstates; i++) + if (!state_table[i].shift_table) + state_table[i].shift_table = shifts_new (0); + } + /* 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. */ @@ -180,18 +189,17 @@ set_state_table (void) state_table[i].lookaheads = count; if (rp - && (rp->nreds > 1 || (sp && SHIFT_IS_SHIFT (sp, 0)))) + && (rp->nreds > 1 || (sp->nshifts && SHIFT_IS_SHIFT (sp, 0)))) count += rp->nreds; else state_table[i].consistent = 1; - if (sp) - for (k = 0; k < sp->nshifts; k++) - if (SHIFT_IS_ERROR (sp, k)) - { - state_table[i].consistent = 0; - break; - } + for (k = 0; k < sp->nshifts; k++) + if (SHIFT_IS_ERROR (sp, k)) + { + state_table[i].consistent = 0; + break; + } } state_table[nstates].lookaheads = count; } @@ -239,18 +247,16 @@ set_goto_map (void) ngotos = 0; for (sp = first_shift; sp; sp = sp->next) - { - for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) - { - symbol = state_table[sp->shifts[i]].accessing_symbol; + for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) + { + symbol = state_table[sp->shifts[i]].accessing_symbol; - if (ngotos == MAXSHORT) - fatal (_("too many gotos (max %d)"), MAXSHORT); + if (ngotos == MAXSHORT) + fatal (_("too many gotos (max %d)"), MAXSHORT); - ngotos++; - goto_map[symbol]++; - } - } + ngotos++; + goto_map[symbol]++; + } k = 0; for (i = ntokens; i < nsyms; i++) @@ -336,29 +342,26 @@ initialize_F (void) int stateno = to_state[i]; shifts *sp = state_table[stateno].shift_table; - if (sp) + int j; + for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++) { - 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 * tokensetsize, symbol); - } + int symbol = state_table[sp->shifts[j]].accessing_symbol; + SETBIT (F + i * tokensetsize, symbol); + } - for (; j < sp->nshifts; j++) - { - int symbol = state_table[sp->shifts[j]].accessing_symbol; - if (nullable[symbol]) - edge[nedges++] = map_goto (stateno, symbol); - } + for (; j < sp->nshifts; j++) + { + int symbol = state_table[sp->shifts[j]].accessing_symbol; + if (nullable[symbol]) + edge[nedges++] = map_goto (stateno, symbol); + } - if (nedges) - { - reads[i] = XCALLOC (short, nedges + 1); - shortcpy (reads[i], edge, nedges); - reads[i][nedges] = -1; - nedges = 0; - } + if (nedges) + { + reads[i] = XCALLOC (short, nedges + 1); + shortcpy (reads[i], edge, nedges); + reads[i][nedges] = -1; + nedges = 0; } } diff --git a/src/output.c b/src/output.c index c78b0f9a..dd64fe7d 100644 --- a/src/output.c +++ b/src/output.c @@ -399,40 +399,33 @@ action_row (int state) } } - shiftp = state_table[state].shift_table; - /* Now see which tokens are allowed for shifts in this state. For them, record the shift as the thing to do. So shift is preferred to reduce. */ + shiftp = state_table[state].shift_table; - if (shiftp) + for (i = 0; i < shiftp->nshifts; i++) { - k = shiftp->nshifts; - - for (i = 0; i < k; i++) - { - shift_state = shiftp->shifts[i]; - if (!shift_state) - continue; + shift_state = shiftp->shifts[i]; + if (!shift_state) + continue; - symbol = state_table[shift_state].accessing_symbol; + symbol = state_table[shift_state].accessing_symbol; - if (ISVAR (symbol)) - break; + if (ISVAR (symbol)) + break; - actrow[symbol] = shift_state; + actrow[symbol] = shift_state; - /* Do not use any default reduction if there is a shift for - error */ - if (symbol == error_token_number) - nodefault = 1; - } + /* Do not use any default reduction if there is a shift for + error */ + if (symbol == error_token_number) + nodefault = 1; } - errp = err_table[state]; - /* See which tokens are an explicit error in this state (due to %nonassoc). For them, record MINSHORT as the action. */ + errp = err_table[state]; if (errp) { diff --git a/src/print.c b/src/print.c index 9ac1feb3..426ca9ae 100644 --- a/src/print.c +++ b/src/print.c @@ -86,13 +86,12 @@ static void print_actions (FILE *out, int state) { int i; - int k; shifts *shiftp = state_table[state].shift_table; reductions *redp = state_table[state].reduction_table; errs *errp = err_table[state]; - if (!shiftp && !redp) + if (!shiftp->nshifts && !redp) { if (final_state == state) fprintf (out, _(" $default\taccept\n")); @@ -101,37 +100,25 @@ print_actions (FILE *out, int state) return; } - if (shiftp) - { - k = shiftp->nshifts; + for (i = 0; i < shiftp->nshifts; i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) + { + int state1 = shiftp->shifts[i]; + int symbol = state_table[state1].accessing_symbol; + /* The following line used to be turned off. */ + if (ISVAR (symbol)) + break; + if (symbol == 0) /* I.e. strcmp(tags[symbol],"$")==0 */ + fprintf (out, + _(" $ \tgo to state %d\n"), state1); + else + fprintf (out, + _(" %-4s\tshift, and go to state %d\n"), + tags[symbol], state1); + } - for (i = 0; i < k; i++) - { - int symbol; - int state1 = shiftp->shifts[i]; - if (!state1) - continue; - symbol = state_table[state1].accessing_symbol; - /* The following line used to be turned off. */ - if (ISVAR (symbol)) - break; - if (symbol == 0) /* I.e. strcmp(tags[symbol],"$")==0 */ - fprintf (out, - _(" $ \tgo to state %d\n"), state1); - else - fprintf (out, - _(" %-4s\tshift, and go to state %d\n"), - tags[symbol], state1); - } - - if (i > 0) - fputc ('\n', out); - } - else - { - i = 0; - k = 0; - } + if (i > 0) + fputc ('\n', out); if (errp) { @@ -161,18 +148,16 @@ print_actions (FILE *out, int state) print_reductions (out, state); } - if (i < k) + if (i < shiftp->nshifts) { - for (; i < k; i++) - { - int symbol; - int state1 = shiftp->shifts[i]; - if (!state1) - continue; - symbol = state_table[state1].accessing_symbol; - fprintf (out, _(" %-4s\tgo to state %d\n"), - tags[symbol], state1); - } + for (; i < shiftp->nshifts; i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) + { + int state1 = shiftp->shifts[i]; + int symbol = state_table[state1].accessing_symbol; + fprintf (out, _(" %-4s\tgo to state %d\n"), + tags[symbol], state1); + } fputc ('\n', out); } diff --git a/src/print_graph.c b/src/print_graph.c index 4d95a587..5a3ba52d 100644 --- a/src/print_graph.c +++ b/src/print_graph.c @@ -84,20 +84,17 @@ static void print_actions (int state, const char *node_name) { int i; - int k; - int state1; - int symbol; - shifts *shiftp; - errs *errp; - reductions *redp; + + shifts *shiftp = state_table[state].shift_table; + reductions *redp = state_table[state].reduction_table; +#if 0 + errs *errp = err_table[state]; +#endif + static char buff[10]; edge_t edge; - shiftp = state_table[state].shift_table; - redp = state_table[state].reduction_table; - errp = err_table[state]; - - if (!shiftp && !redp) + if (!shiftp->nshifts && !redp) { #if 0 if (final_state == state) @@ -108,42 +105,26 @@ print_actions (int state, const char *node_name) return; } - if (shiftp) - { - k = shiftp->nshifts; - - for (i = 0; i < k; i++) - { - if (!shiftp->shifts[i]) - continue; - state1 = shiftp->shifts[i]; - symbol = state_table[state1].accessing_symbol; - - if (ISVAR (symbol)) - break; - - { - new_edge (&edge); - - if (state > state1) - edge.type = back_edge; - open_edge (&edge, fgraph); - /* The edge source is the current node. */ - edge.sourcename = node_name; - sprintf (buff, "%d", state1); - edge.targetname = buff; - edge.color = (symbol == 0) ? red : blue; - edge.label = tags[symbol]; - output_edge (&edge, fgraph); - close_edge (fgraph); - } - } - } - else - { - i = 0; - k = 0; - } + for (i = 0; i < shiftp->nshifts; i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) + { + int state1 = shiftp->shifts[i]; + int symbol = state_table[state1].accessing_symbol; + + new_edge (&edge); + + if (state > state1) + edge.type = back_edge; + open_edge (&edge, fgraph); + /* The edge source is the current node. */ + edge.sourcename = node_name; + sprintf (buff, "%d", state1); + edge.targetname = buff; + edge.color = (symbol == 0) ? red : blue; + edge.label = tags[symbol]; + output_edge (&edge, fgraph); + close_edge (fgraph); + } #if 0 if (errp) @@ -182,14 +163,12 @@ print_actions (int state, const char *node_name) } #endif - if (i < k) - { - for (; i < k; i++) + if (i < shiftp->nshifts) + for (; i < shiftp->nshifts; i++) + if (!SHIFT_IS_DISABLED (shiftp, i)) { - if (!shiftp->shifts[i]) - continue; - state1 = shiftp->shifts[i]; - symbol = state_table[state1].accessing_symbol; + int state1 = shiftp->shifts[i]; + int symbol = state_table[state1].accessing_symbol; new_edge (&edge); open_edge (&edge, fgraph); @@ -201,7 +180,6 @@ print_actions (int state, const char *node_name) output_edge (&edge, fgraph); close_edge (fgraph); } - } } diff --git a/src/state.h b/src/state.h index 3bf9022f..8e60058e 100644 --- a/src/state.h +++ b/src/state.h @@ -1,5 +1,5 @@ /* Type definitions for nondeterministic finite state machine for bison, - Copyright 1984, 1989, 2000 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -124,6 +124,9 @@ typedef struct shifts (shifts *) xcalloc ((unsigned) (sizeof (shifts) \ + (Nshifts - 1) * sizeof (short)), 1) +shifts * shifts_new PARAMS ((int n)); + + /* What is the symbol which is shifted by SHIFTS->shifts[Shift]? Can be a token (amongst which the error token), or non terminals in case of gotos. */