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 <akim@epita.fr>
+
+ 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 <akim@epita.fr>
* src/state.h (SHIFT_DISABLE, SHIFT_IS_DISABLED): New.
}
-/*---------------------------------.
-| 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. |
`------------------------------------------------------------*/
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. */
/* 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;
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 \
+ output.h output.c \
+ state.h state.c \
print.c reader.c reduce.c symtab.c warshall.c vcg.c print_graph.c
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 state.h \
print.h reader.h reduce.h symtab.h warshall.h system.h types.h \
vcg.h vcg_defaults.h print_graph.h
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 \
+ output.h output.c \
+ state.h state.c \
print.c reader.c reduce.c symtab.c warshall.c vcg.c print_graph.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 state.h \
print.h reader.h reduce.h symtab.h warshall.h system.h types.h \
vcg.h vcg_defaults.h print_graph.h
complain$U.$(OBJEXT) conflicts$U.$(OBJEXT) derives$U.$(OBJEXT) \
files$U.$(OBJEXT) getargs$U.$(OBJEXT) gram$U.$(OBJEXT) \
lalr$U.$(OBJEXT) lex$U.$(OBJEXT) main$U.$(OBJEXT) \
- nullable$U.$(OBJEXT) output$U.$(OBJEXT) print$U.$(OBJEXT) \
- reader$U.$(OBJEXT) reduce$U.$(OBJEXT) symtab$U.$(OBJEXT) \
- warshall$U.$(OBJEXT) vcg$U.$(OBJEXT) print_graph$U.$(OBJEXT)
+ nullable$U.$(OBJEXT) output$U.$(OBJEXT) state$U.$(OBJEXT) \
+ print$U.$(OBJEXT) reader$U.$(OBJEXT) reduce$U.$(OBJEXT) \
+ symtab$U.$(OBJEXT) warshall$U.$(OBJEXT) vcg$U.$(OBJEXT) \
+ print_graph$U.$(OBJEXT)
bison_OBJECTS = $(am_bison_OBJECTS)
bison_LDADD = $(LDADD)
bison_DEPENDENCIES = ../lib/libbison.a
@AMDEP_TRUE@ $(DEPDIR)/main$U.Po $(DEPDIR)/nullable$U.Po \
@AMDEP_TRUE@ $(DEPDIR)/output$U.Po $(DEPDIR)/print$U.Po \
@AMDEP_TRUE@ $(DEPDIR)/print_graph$U.Po $(DEPDIR)/reader$U.Po \
-@AMDEP_TRUE@ $(DEPDIR)/reduce$U.Po $(DEPDIR)/symtab$U.Po \
-@AMDEP_TRUE@ $(DEPDIR)/vcg$U.Po $(DEPDIR)/vmsgetargs$U.Po \
-@AMDEP_TRUE@ $(DEPDIR)/warshall$U.Po
+@AMDEP_TRUE@ $(DEPDIR)/reduce$U.Po $(DEPDIR)/state$U.Po \
+@AMDEP_TRUE@ $(DEPDIR)/symtab$U.Po $(DEPDIR)/vcg$U.Po \
+@AMDEP_TRUE@ $(DEPDIR)/vmsgetargs$U.Po $(DEPDIR)/warshall$U.Po
COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \
$(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS)
CCLD = $(CC)
@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/print_graph$U.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/reader$U.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/reduce$U.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/state$U.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/symtab$U.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/vcg$U.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@$(DEPDIR)/vmsgetargs$U.Po@am__quote@
$(CPP) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) `if test -f $(srcdir)/reader.c; then echo $(srcdir)/reader.c; else echo reader.c; fi` | sed 's/^# \([0-9]\)/#line \1/' | $(ANSI2KNR) > reader_.c || rm -f reader_.c
reduce_.c: reduce.c $(ANSI2KNR)
$(CPP) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) `if test -f $(srcdir)/reduce.c; then echo $(srcdir)/reduce.c; else echo reduce.c; fi` | sed 's/^# \([0-9]\)/#line \1/' | $(ANSI2KNR) > reduce_.c || rm -f reduce_.c
+state_.c: state.c $(ANSI2KNR)
+ $(CPP) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) `if test -f $(srcdir)/state.c; then echo $(srcdir)/state.c; else echo state.c; fi` | sed 's/^# \([0-9]\)/#line \1/' | $(ANSI2KNR) > state_.c || rm -f state_.c
symtab_.c: symtab.c $(ANSI2KNR)
$(CPP) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) `if test -f $(srcdir)/symtab.c; then echo $(srcdir)/symtab.c; else echo symtab.c; fi` | sed 's/^# \([0-9]\)/#line \1/' | $(ANSI2KNR) > symtab_.c || rm -f symtab_.c
vcg_.c: vcg.c $(ANSI2KNR)
getargs_.$(OBJEXT) gram_.$(OBJEXT) lalr_.$(OBJEXT) lex_.$(OBJEXT) \
main_.$(OBJEXT) nullable_.$(OBJEXT) output_.$(OBJEXT) print_.$(OBJEXT) \
print_graph_.$(OBJEXT) reader_.$(OBJEXT) reduce_.$(OBJEXT) \
-symtab_.$(OBJEXT) vcg_.$(OBJEXT) vmsgetargs_.$(OBJEXT) \
+state_.$(OBJEXT) symtab_.$(OBJEXT) vcg_.$(OBJEXT) vmsgetargs_.$(OBJEXT) \
warshall_.$(OBJEXT) : $(ANSI2KNR)
uninstall-info-am:
install-pkgdataDATA: $(pkgdata_DATA)
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);
}
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
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)
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++)
{
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. */
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;
}
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++)
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;
}
}
}
}
- 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)
{
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"));
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)
{
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);
}
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)
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)
}
#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);
output_edge (&edge, fgraph);
close_edge (fgraph);
}
- }
}
--- /dev/null
+/* Type definitions for nondeterministic finite state machine for bison,
+ Copyright 2001 Free Software Foundation, Inc.
+
+ 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 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. */
+
+
+#include "system.h"
+#include "state.h"
+
+/*---------------------------------.
+| Create a new array of N shitfs. |
+`---------------------------------*/
+
+shifts *
+shifts_new (int n)
+{
+ shifts *res = SHIFTS_ALLOC (n);
+ res->nshifts = n;
+ return res;
+}
/* 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.
(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. */
projects / bison.git / commitdiff
