diff options
author | Joel E. Denny <jdenny@ces.clemson.edu> | 2009-04-21 03:40:16 -0400 |
---|---|---|
committer | Joel E. Denny <jdenny@ces.clemson.edu> | 2009-04-21 06:00:09 -0400 |
commit | db34f7988941444bdc5f2b6adcf7fb83648f9a18 (patch) | |
tree | a6cc5ed3c438885d831a47caa00a3e8160ed7e20 /src | |
parent | 7fe11bb55c1ca7e08f392b8bf413d18062019dd3 (diff) | |
download | bison-db34f7988941444bdc5f2b6adcf7fb83648f9a18.tar.gz |
Finish implementing %define lr.type.
Its value can be "LALR", "IELR", or "canonical LR".
* lib/timevar.def (TV_IELR_PHASE1): New var.
(TV_IELR_PHASE2): New var.
(TV_IELR_PHASE3): New var.
(TV_IELR_PHASE4): New var.
* src/local.mk (src_bison_SOURCES): Add AnnotationList.c,
AnnotationList.h, InadequacyList.c, InadequacyList.h, Sbitset.c,
Sbitset.h, ielr.c, and ielr.h.
* src/getargs.h, src/getargs.c (enum trace, trace_args,
trace_types): Add trace_ielr.
* src/lalr.h, src/lalr.c (ngotos): Export it.
(F): Rename to...
(goto_follows): ... this, update all uses, and export it.
(set_goto_map): Export it.
(map_goto): Export it.
(compute_lookahead_tokens): Don't free goto_follows yet. Now
handled in ielr.
(initialize_LA): Export it. Move lookback allocation to...
(lalr): ... here because, for canonical LR, initialize_LA must
be invoked but lookback and much of the rest of LALR isn't
needed.
* main.c (main): Instead of lalr, invoke ielr, which invokes
lalr.
* src/reader.c (reader): Default lr.type to "LALR".
Default lr.default_rules to "accepting" if lr.type is "canonical
LR". Leave the default as "all" otherwise.
Check for a valid lr.type value.
* src/state.h, src/state.c (struct state_list): Add state_list
member.
(state_new): Initialize state_list member to NULL.
(state_new_isocore): New function, exported.
* tests/existing.at (AT_TEST_EXISTING_GRAMMAR): New macro that
exercises all values of lr.type.
(GNU AWK Grammar): Rename test group to...
(GNU AWK 3.1.0 Grammar): ... this, and extend to use
AT_TEST_EXISTING_GRAMMAR.
(GNU Cim Grammar): Extend to use AT_TEST_EXISTING_GRAMMAR.
(GNU pic Grammar): Rename test group to...
(GNU pic (Groff 1.18.1) Grammar): ... this, and extend to use
AT_TEST_EXISTING_GRAMMAR.
* tests/reduce.at (AT_TEST_LR_TYPE): New macro that exercises
all values of lr.type.
(Single State Split): New test groups using AT_TEST_LR_TYPE.
(Lane Split): Likewise.
(Complex Lane Split): Likewise.
(Split During Added Lookahead Propagation): Likewise.
Diffstat (limited to 'src')
-rw-r--r-- | src/getargs.c | 2 | ||||
-rw-r--r-- | src/getargs.h | 1 | ||||
-rw-r--r-- | src/lalr.c | 33 | ||||
-rw-r--r-- | src/lalr.h | 40 | ||||
-rw-r--r-- | src/local.mk | 8 | ||||
-rw-r--r-- | src/main.c | 9 | ||||
-rw-r--r-- | src/reader.c | 13 | ||||
-rw-r--r-- | src/state.c | 31 | ||||
-rw-r--r-- | src/state.h | 12 |
9 files changed, 111 insertions, 38 deletions
diff --git a/src/getargs.c b/src/getargs.c index 368470fb..fdf9dd0b 100644 --- a/src/getargs.c +++ b/src/getargs.c @@ -186,6 +186,7 @@ static const char * const trace_args[] = "m4 - m4 traces", "skeleton - skeleton postprocessing", "time - time consumption", + "ielr - IELR conversion", "all - all of the above", 0 }; @@ -205,6 +206,7 @@ static const int trace_types[] = trace_m4, trace_skeleton, trace_time, + trace_ielr, trace_all }; diff --git a/src/getargs.h b/src/getargs.h index 13efae2c..32135b5e 100644 --- a/src/getargs.h +++ b/src/getargs.h @@ -103,6 +103,7 @@ enum trace trace_skeleton = 1 << 9, /**< Skeleton postprocessing. */ trace_m4 = 1 << 10, /**< M4 traces. */ trace_muscles = 1 << 11, /**< M4 definitions of the muscles. */ + trace_ielr = 1 << 12, /**< IELR conversion. */ trace_all = ~0 /**< All of the above. */ }; /** What debug items bison displays during its run. */ @@ -43,9 +43,10 @@ #include "symtab.h" goto_number *goto_map; -static goto_number ngotos; +goto_number ngotos; state_number *from_state; state_number *to_state; +bitsetv goto_follows = NULL; /* Linked list of goto numbers. */ typedef struct goto_list @@ -64,17 +65,13 @@ static bitsetv LA = NULL; size_t nLA; -/* And for the famous F variable, which name is so descriptive that a - comment is hardly needed. <grin>. */ -static bitsetv F = NULL; - static goto_number **includes; static goto_list **lookback; -static void +void set_goto_map (void) { state_number s; @@ -134,12 +131,7 @@ set_goto_map (void) } - -/*----------------------------------------------------------. -| Map a state/symbol pair into its numeric representation. | -`----------------------------------------------------------*/ - -static goto_number +goto_number map_goto (state_number s0, symbol_number sym) { goto_number high; @@ -174,7 +166,7 @@ initialize_F (void) goto_number i; - F = bitsetv_create (ngotos, ntokens, BITSET_FIXED); + goto_follows = bitsetv_create (ngotos, ntokens, BITSET_FIXED); for (i = 0; i < ngotos; i++) { @@ -183,7 +175,7 @@ initialize_F (void) int j; FOR_EACH_SHIFT (sp, j) - bitset_set (F[i], TRANSITION_SYMBOL (sp, j)); + bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j)); for (; j < sp->num; j++) { @@ -203,7 +195,7 @@ initialize_F (void) } } - relation_digraph (reads, ngotos, &F); + relation_digraph (reads, ngotos, &goto_follows); for (i = 0; i < ngotos; i++) free (reads[i]); @@ -264,7 +256,7 @@ build_relations (void) { done = true; /* Each rhs ends in a rule number, and there is a - sentinel before the first rhs, so it is safe to + sentinel (ritem[-1]=0) before the first rhs, so it is safe to decrement RP here. */ rp--; if (ISVAR (*rp)) @@ -303,7 +295,7 @@ compute_FOLLOWS (void) { goto_number i; - relation_digraph (includes, ngotos, &F); + relation_digraph (includes, ngotos, &goto_follows); for (i = 0; i < ngotos; i++) free (includes[i]); @@ -320,14 +312,13 @@ compute_lookahead_tokens (void) for (i = 0; i < nLA; i++) for (sp = lookback[i]; sp; sp = sp->next) - bitset_or (LA[i], LA[i], F[sp->value]); + bitset_or (LA[i], LA[i], goto_follows[sp->value]); /* Free LOOKBACK. */ for (i = 0; i < nLA; i++) LIST_FREE (goto_list, lookback[i]); free (lookback); - bitsetv_free (F); } @@ -373,7 +364,7 @@ state_lookahead_tokens_count (state *s, bool default_rule_only_for_accept) | Compute LA, NLA, and the lookahead_tokens members. | `----------------------------------------------------*/ -static void +void initialize_LA (void) { state_number i; @@ -395,7 +386,6 @@ initialize_LA (void) nLA = 1; pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED); - lookback = xcalloc (nLA, sizeof *lookback); /* Initialize the members LOOKAHEAD_TOKENS for each state whose reductions require lookahead tokens. */ @@ -454,6 +444,7 @@ lalr (void) initialize_LA (); set_goto_map (); initialize_F (); + lookback = xcalloc (nLA, sizeof *lookback); build_relations (); compute_FOLLOWS (); compute_lookahead_tokens (); @@ -1,7 +1,7 @@ /* Compute lookahead criteria for bison, - Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006, 2007 Free Software - Foundation, Inc. + Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006, 2007, 2009 + Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -37,14 +37,30 @@ which rules need lookahead in each state, and which lookahead tokens they accept. - Builds: - - #goto_map - - #from_state - - #to_state + Also builds: + - #goto_map + - #from_state + - #to_state + - #goto_follows */ void lalr (void); /** + * Set #nLA and allocate all reduction lookahead sets. Normally invoked by + * #lalr. + */ +void initialize_LA (void); + +/** + * Build only: + * - #goto_map + * - #from_state + * - #to_state + * Normally invoked by #lalr. + */ +void set_goto_map (void); + +/** * Update state numbers recorded in #goto_map, #from_state, and #to_state such * that: * - \c nstates_old is the old number of states. @@ -62,7 +78,6 @@ void lalr_update_state_numbers (state_number old_to_new[], Can be performed once the action tables are computed. */ void lalr_free (void); - typedef size_t goto_number; # define GOTO_NUMBER_MAXIMUM ((goto_number) -1) @@ -73,11 +88,20 @@ typedef size_t goto_number; TO_STATE of the first of them. */ extern goto_number *goto_map; -/** State number which a transition leads from. */ +/** The size of #from_state and #to_state. */ +extern goto_number ngotos; + +/** State number which a transition leads from. */ extern state_number *from_state; /** State number it leads to. */ extern state_number *to_state; +/** Map a state/symbol pair into its numeric representation. */ +goto_number map_goto (state_number s0, symbol_number sym); + +/* goto_follows[i] is the set of tokens following goto i. */ +extern bitsetv goto_follows; + #endif /* !LALR_H_ */ diff --git a/src/local.mk b/src/local.mk index ffcf4b01..bdf9d2e3 100644 --- a/src/local.mk +++ b/src/local.mk @@ -34,8 +34,14 @@ EXTRA_SCRIPTS = src/yacc src_bison_CFLAGS = $(AM_CFLAGS) $(WERROR_CFLAGS) src_bison_SOURCES = \ + src/AnnotationList.c \ + src/AnnotationList.h \ + src/InadequacyList.c \ + src/InadequacyList.h \ src/LR0.c \ src/LR0.h \ + src/Sbitset.c \ + src/Sbitset.h \ src/assoc.c \ src/assoc.h \ src/closure.c \ @@ -57,6 +63,8 @@ src_bison_SOURCES = \ src/graphviz.h \ src/lalr.c \ src/lalr.h \ + src/ielr.c \ + src/ielr.h \ src/location.c \ src/location.h \ src/main.c \ @@ -35,6 +35,7 @@ #include "getargs.h" #include "gram.h" #include "lalr.h" +#include "ielr.h" #include "muscle-tab.h" #include "nullable.h" #include "output.h" @@ -102,10 +103,10 @@ main (int argc, char *argv[]) generate_states (); timevar_pop (TV_LR0); - /* make it deterministic. In file lalr. */ - timevar_push (TV_LALR); - lalr (); - timevar_pop (TV_LALR); + /* Make it deterministic by computing lookahead sets. Except when LALR(1) is + requested, split states to eliminate LR(1)-relative inadequacies. In file + lalr and ielr. */ + ielr (); /* Find and record any conflicts: places where one token of lookahead is not enough to disambiguate the parsing. In file diff --git a/src/reader.c b/src/reader.c index 8c88dc04..f607f9ee 100644 --- a/src/reader.c +++ b/src/reader.c @@ -555,11 +555,22 @@ reader (void) gram_scanner_initialize (); gram_parse (); - muscle_percent_define_default ("lr.default_rules", "all"); + /* IELR would be a better default, but LALR is historically the default. */ + { + char *lr_type; + muscle_percent_define_default ("lr.type", "LALR"); + lr_type = muscle_percent_define_get ("lr.type"); + if (0 != strcmp (lr_type, "canonical LR")) + muscle_percent_define_default ("lr.default_rules", "all"); + else + muscle_percent_define_default ("lr.default_rules", "accepting"); + free (lr_type); + } /* Check front-end %define variable values. */ { static char const * const values[] = { + "lr.type", "LALR", "IELR", "canonical LR", NULL, "lr.default_rules", "all", "consistent", "accepting", NULL, NULL }; diff --git a/src/state.c b/src/state.c index d3460c15..a0f5cdb8 100644 --- a/src/state.c +++ b/src/state.c @@ -1,7 +1,7 @@ /* Type definitions for nondeterministic finite state machine for Bison. - Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software - Foundation, Inc. + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free + Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -142,6 +142,7 @@ state_new (symbol_number accessing_symbol, res->transitions = NULL; res->reductions = NULL; res->errs = NULL; + res->state_list = NULL; res->consistent = 0; res->solved_conflicts = NULL; res->solved_conflicts_xml = NULL; @@ -154,6 +155,32 @@ state_new (symbol_number accessing_symbol, return res; } +state * +state_new_isocore (state const *s) +{ + state *res; + size_t items_size = s->nitems * sizeof *s->items; + + aver (nstates < STATE_NUMBER_MAXIMUM); + + res = xmalloc (offsetof (state, items) + items_size); + res->number = nstates++; + res->accessing_symbol = s->accessing_symbol; + res->transitions = + transitions_new (s->transitions->num, s->transitions->states); + res->reductions = reductions_new (s->reductions->num, s->reductions->rules); + res->errs = NULL; + res->state_list = NULL; + res->consistent = s->consistent; + res->solved_conflicts = NULL; + res->solved_conflicts_xml = NULL; + + res->nitems = s->nitems; + memcpy (res->items, s->items, items_size); + + return res; +} + /*---------. | Free S. | diff --git a/src/state.h b/src/state.h index 4afc1f00..931b48f1 100644 --- a/src/state.h +++ b/src/state.h @@ -1,7 +1,7 @@ /* Type definitions for nondeterministic finite state machine for Bison. - Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007 Free - Software Foundation, Inc. + Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007, 2009 + Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -193,6 +193,8 @@ typedef struct | states. | `---------*/ +struct state_list; + struct state { state_number number; @@ -201,6 +203,11 @@ struct state reductions *reductions; errs *errs; + /* When an includer (such as ielr.c) needs to store states in a list, the + includer can define struct state_list as the list node structure and can + store in this member a reference to the node containing each state. */ + struct state_list *state_list; + /* If non-zero, then no lookahead sets on reduce actions are needed to decide what to do in state S. */ char consistent; @@ -222,6 +229,7 @@ extern state *final_state; /* Create a new state with ACCESSING_SYMBOL for those items. */ state *state_new (symbol_number accessing_symbol, size_t core_size, item_number *core); +state *state_new_isocore (state const *s); /* Set the transitions of STATE. */ void state_transitions_set (state *s, int num, state **trans); |