From f805dfcb3fc6517dd0a49939fd6610999afcca00 Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" Date: Tue, 21 Apr 2009 03:40:16 -0400 Subject: [PATCH 1/1] 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/Makefile.am (bison_SOURCES): Add AnnotationList.c, AnnotationList.h, InadequacyList.c, InadequacyList.h, Sbitset.c, Sbitset.h, ielr.h, and ielr.c. * 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. --- ChangeLog | 50 ++ lib/timevar.def | 6 +- src/Makefile.am | 8 +- src/getargs.c | 4 +- src/getargs.h | 3 +- src/lalr.c | 33 +- src/lalr.h | 40 +- src/main.c | 11 +- src/reader.c | 13 +- src/state.c | 31 +- src/state.h | 12 +- tests/existing.at | 1719 +++++++++++++++++++++++++++++++++++++++++++-- tests/reduce.at | 1083 ++++++++++++++++++++++++++++ 13 files changed, 2909 insertions(+), 104 deletions(-) diff --git a/ChangeLog b/ChangeLog index 962f5342..d7e97f34 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,53 @@ +2009-04-21 Joel E. Denny + + 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/Makefile.am (bison_SOURCES): Add AnnotationList.c, + AnnotationList.h, InadequacyList.c, InadequacyList.h, Sbitset.c, + Sbitset.h, ielr.h, and ielr.c. + * 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. + 2009-04-21 Joel E. Denny Add new files for IELR and canonical LR implementation. diff --git a/lib/timevar.def b/lib/timevar.def index 3a4128f2..5caf7c3d 100644 --- a/lib/timevar.def +++ b/lib/timevar.def @@ -1,6 +1,6 @@ /* This file contains the definitions for timing variables used to -*- C -*- measure run-time performance of the compiler. - Copyright (C) 2002, 2007 Free Software Foundation, Inc. + Copyright (C) 2002, 2007, 2009 Free Software Foundation, Inc. Contributed by Akim Demaille . This file is part of Bison, the GNU Compiler Compiler. @@ -41,6 +41,10 @@ DEFTIMEVAR (TV_REDUCE , "reducing the grammar") DEFTIMEVAR (TV_SETS , "computing the sets") DEFTIMEVAR (TV_LR0 , "LR(0)") DEFTIMEVAR (TV_LALR , "LALR(1)") +DEFTIMEVAR (TV_IELR_PHASE1 , "IELR(1) Phase 1") +DEFTIMEVAR (TV_IELR_PHASE2 , "IELR(1) Phase 2") +DEFTIMEVAR (TV_IELR_PHASE3 , "IELR(1) Phase 3") +DEFTIMEVAR (TV_IELR_PHASE4 , "IELR(1) Phase 4") DEFTIMEVAR (TV_CONFLICTS , "conflicts") /* Time spent outputing results. */ diff --git a/src/Makefile.am b/src/Makefile.am index a5cf94ee..825266a8 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,7 +1,7 @@ # Make bison/src. -# Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software -# Foundation, Inc. +# Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 +# Free Software Foundation, Inc. # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by @@ -31,7 +31,10 @@ bin_SCRIPTS = $(YACC_SCRIPT) EXTRA_SCRIPTS = yacc bison_SOURCES = \ + AnnotationList.c AnnotationList.h \ + InadequacyList.c InadequacyList.h \ LR0.c LR0.h \ + Sbitset.c Sbitset.h \ assoc.c assoc.h \ closure.c closure.h \ complain.c complain.h \ @@ -42,6 +45,7 @@ bison_SOURCES = \ getargs.c getargs.h \ gram.c gram.h \ lalr.h lalr.c \ + ielr.h ielr.c \ location.c location.h \ main.c \ muscle_tab.c muscle_tab.h \ diff --git a/src/getargs.c b/src/getargs.c index bb060c55..4b35171e 100644 --- a/src/getargs.c +++ b/src/getargs.c @@ -1,7 +1,7 @@ /* Parse command line arguments for Bison. Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004, - 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -181,6 +181,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 }; @@ -200,6 +201,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 11390674..d9d95202 100644 --- a/src/getargs.h +++ b/src/getargs.h @@ -1,7 +1,7 @@ /* Parse command line arguments for bison. Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004, - 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -107,6 +107,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. */ diff --git a/src/lalr.c b/src/lalr.c index 9f5d43f3..01011498 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -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. . */ -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 (); diff --git a/src/lalr.h b/src/lalr.h index c65c9b48..103a4c86 100644 --- a/src/lalr.h +++ b/src/lalr.h @@ -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,13 +37,29 @@ 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: @@ -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/main.c b/src/main.c index b3ef70ac..6c93a4ef 100644 --- a/src/main.c +++ b/src/main.c @@ -1,7 +1,7 @@ /* Top level entry point of Bison. Copyright (C) 1984, 1986, 1989, 1992, 1995, 2000, 2001, 2002, 2004, - 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -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 68e8b44e..b2fdc3b6 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); diff --git a/tests/existing.at b/tests/existing.at index ba2c40cb..b754f3c6 100644 --- a/tests/existing.at +++ b/tests/existing.at @@ -1,7 +1,7 @@ # Exercising Bison on actual grammars. -*- Autotest -*- -# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004, 2005, -# 2007 Free Software Foundation, Inc. +# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004, +# 2005, 2007, 2009 Free Software Foundation, Inc. # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by @@ -17,21 +17,70 @@ # along with this program. If not, see . AT_BANNER([[Existing Grammars.]]) -## ----------------- ## -## GNU AWK Grammar. ## -## ----------------- ## -AT_SETUP([GNU AWK Grammar]) +# AT_TEST_EXISTING_GRAMMAR(DESCRIPTION, +# DECLS, GRAMMAR, INPUT, +# BISON-STDERR, LAST-STATE, LALR1-DIFF, +# [OTHER-CHECKS], +# [PARSER-EXIT-VALUE], +# [PARSER-STDOUT], [PARSER-STDERR]) +# -------------------------------------------------------------- +m4_define([AT_TEST_EXISTING_GRAMMAR], [_AT_TEST_EXISTING_GRAMMAR([$][1], $@)]) + +m4_define([_AT_TEST_EXISTING_GRAMMAR], +[ +dnl See how the parser tables have changed. As the .output format evolves, the +dnl diff comments with line numbers might be a pain to maintain. When that +dnl time comes, just use sed to drop the line numbers. For now, as LR(1) +dnl support is rapidly evolving, let's keep that information to be careful. +dnl However, we don't do diffs for canonical LR(1) because the diff is huge. +m4_pushdef([AT_LALR1_DIFF_CHECK], +[AT_CHECK([[sed 's/^%define lr.type .*$//' input.y > input-lalr.y]]) +AT_BISON_CHECK([[--report=all input-lalr.y]], [[0]], [ignore], [ignore]) +AT_CHECK([[diff -u input-lalr.output input.output \ + | sed -n '/^@@/,$p' | sed 's/^ $//']], + [[0]], [$1])]) + +AT_TEST_TABLES_AND_PARSE([$2[: LALR(1)]], [[LALR]], [[last-state]], + [[%define lr.type "LALR" +]$3], + [$4], [$5], [$6], [$7], + [AT_LALR1_DIFF_CHECK([$8])$9]m4_if($#, 8, [], + $#, 9, [], + [, m4_shiftn(9, + $@)])) +AT_TEST_TABLES_AND_PARSE([$2[: IELR(1)]], [[IELR]], [[last-state]], + [[%define lr.type "IELR" +]$3], + [$4], [$5], [$6], [$7], + [AT_LALR1_DIFF_CHECK([$8])$9]m4_if($#, 8, [], + $#, 9, [], + [, m4_shiftn(9, + $@)])) +AT_TEST_TABLES_AND_PARSE([$2[: Canonical LR(1)]], [[canonical LR]], + [[last-state,no-xml]], + [[%define lr.type "canonical LR" +]$3], + [$4], [$5], [$6], [$7], + [$9]m4_if($#, 8, [], $#, 9, [], [, m4_shiftn(9, $@)])) + +m4_popdef([AT_LALR1_DIFF_CHECK]) +]) + + + +## ----------------------- ## +## GNU AWK 3.1.0 Grammar. ## +## ----------------------- ## # We have been careful to strip all the actions excepts the -# mid-rule actions. We rely on %expect to check that there are -# indeed 65 SR conflicts. +# mid-rule actions. # -# Bison was once wrong, due to an incorrect computation of nullable. -# It reported 485 SR conflicts! +# There are 65 SR conflicts. Bison was once wrong, due to an incorrect +# computation of nullable. It reported 485 SR conflicts! -AT_DATA([[input.y]], -[[%expect 65 +AT_TEST_EXISTING_GRAMMAR([[GNU AWK 3.1.0 Grammar]], +[[%error-verbose %token FUNC_CALL NAME REGEXP %token ERROR @@ -66,8 +115,8 @@ AT_DATA([[input.y]], %left INCREMENT DECREMENT %left '$' %left '(' ')' -%% - +]], +[[ start : opt_nls program opt_nls ; @@ -344,29 +393,397 @@ semi comma : ',' opt_nls ; - -%% -]]) - -# Pass plenty of options, to exercise plenty of code, even if we -# don't actually check the output. But SEGV is watching us, and -# so might do dmalloc. -AT_BISON_CHECK([[--verbose --defines input.y]]) - -AT_CLEANUP +]], + +dnl INPUT +dnl +dnl For example, in AWK: +dnl +dnl getline $!4*0; +dnl +dnl The grammar below (from GNU AWK 3.1.0) using canonical LR(1) or IELR(1) +dnl parses it as: +dnl +dnl getline $!(4*0); +dnl +dnl That is, they shift `*' immediately and make it part of the getline +dnl argument. +dnl +dnl The grammar below using LALR(1) parses it as a syntax error. So does +dnl GNU AWK 3.0.6, 3.1.0, and 3.1.1. They reduce the full getline expression +dnl before shifting `*' even though `*' is not a valid lookahead. +dnl +dnl GNU AWK 3.1.2, 3.1.3, 3.1.4, and 3.1.5 parse it as: +dnl +dnl (getline $!4)*0; +dnl +dnl That is, like the other versions of GNU AWK, they reduce the full getline +dnl expression before shifting `*'. However, because of a different LHS on the +dnl getline rule, `*' actually is a valid lookahead. Solaris /usr/xpg4/bin/awk +dnl and the Open Group awk specification seem to agree: +dnl +dnl http://www.opengroup.org/pubs/online/7908799/xcu/awk.html +dnl +dnl /bin/nawk and /bin/awk on Solaris 10 report it as a syntax error, but they +dnl don't like even `print $!4;'. +[[LEX_GETLINE, '$', '!', YNUMBER, '*', YNUMBER, ';']], + +dnl BISON-STDERR +[AT_COND_CASE([[canonical LR]], +[[input.y: conflicts: 265 shift/reduce]], +[[input.y: conflicts: 65 shift/reduce]])[ +]], + +dnl LAST-STATE +[AT_COND_CASE([[LALR]], [[319]], [[canonical LR]], [[2358]], [[328]])], + +dnl LALR1-DIFF not used for canonical LR(1) because the diff is huge. +dnl Isocore map from LALR(1) state number to new state number plus descriptions +dnl of any change in the actions resulting in a change in accepted language: +dnl - 24 -> 320 +dnl - 16 -> 321 +dnl - 17 -> 322 +dnl - 20 -> 323 +dnl - 21 -> 324 +dnl - 54 -> 325 +dnl - 56 -> 326: reduce -> shift on '*', '/', and '%' +dnl - 58 -> 327: reduce -> shift on '*', '/', and '%' +dnl - 61 -> 328: reduce -> shift on '*', '/', and '%' +[AT_COND_CASE([[LALR]], [], +[[@@ -712,7 +712,7 @@ + 156 | . '$' non_post_simp_exp + + NAME shift, and go to state 9 +- '$' shift, and go to state 24 ++ '$' shift, and go to state 320 + + NAME [reduce using rule 152 (opt_variable)] + '$' [reduce using rule 152 (opt_variable)] +@@ -5379,7 +5379,7 @@ + 156 | . '$' non_post_simp_exp + + NAME shift, and go to state 9 +- '$' shift, and go to state 24 ++ '$' shift, and go to state 320 + + NAME [reduce using rule 152 (opt_variable)] + '$' [reduce using rule 152 (opt_variable)] +@@ -5399,7 +5399,7 @@ + 156 | . '$' non_post_simp_exp + + NAME shift, and go to state 9 +- '$' shift, and go to state 24 ++ '$' shift, and go to state 320 + + NAME [reduce using rule 152 (opt_variable)] + '$' [reduce using rule 152 (opt_variable)] +@@ -6214,7 +6214,7 @@ + 156 | . '$' non_post_simp_exp + + NAME shift, and go to state 9 +- '$' shift, and go to state 24 ++ '$' shift, and go to state 320 + + NAME [reduce using rule 152 (opt_variable)] + '$' [reduce using rule 152 (opt_variable)] +@@ -11099,3 +11099,274 @@ + 45 statement: LEX_FOR '(' opt_exp semi opt_nls exp semi opt_nls opt_exp r_paren opt_nls statement . + + $default reduce using rule 45 (statement) ++ ++ ++state 320 ++ ++ 139 non_post_simp_exp: . '!' simp_exp ++ 140 | . '(' exp r_paren ++ 141 | . LEX_BUILTIN '(' opt_expression_list r_paren ++ 142 | . LEX_LENGTH '(' opt_expression_list r_paren ++ 143 | . LEX_LENGTH ++ 144 | . FUNC_CALL '(' opt_expression_list r_paren ++ 145 | . variable ++ 146 | . INCREMENT variable ++ 147 | . DECREMENT variable ++ 148 | . YNUMBER ++ 149 | . YSTRING ++ 150 | . '-' simp_exp ++ 151 | . '+' simp_exp ++ 154 variable: . NAME ++ 155 | . NAME '[' expression_list ']' ++ 156 | . '$' non_post_simp_exp ++ 156 | '$' . non_post_simp_exp ++ ++ FUNC_CALL shift, and go to state 8 ++ NAME shift, and go to state 9 ++ YNUMBER shift, and go to state 10 ++ YSTRING shift, and go to state 11 ++ INCREMENT shift, and go to state 321 ++ DECREMENT shift, and go to state 322 ++ LEX_BUILTIN shift, and go to state 18 ++ LEX_LENGTH shift, and go to state 19 ++ '+' shift, and go to state 323 ++ '-' shift, and go to state 324 ++ '!' shift, and go to state 325 ++ '$' shift, and go to state 320 ++ '(' shift, and go to state 55 ++ ++ non_post_simp_exp go to state 62 ++ variable go to state 63 ++ ++ ++state 321 ++ ++ 146 non_post_simp_exp: INCREMENT . variable ++ 154 variable: . NAME ++ 155 | . NAME '[' expression_list ']' ++ 156 | . '$' non_post_simp_exp ++ ++ NAME shift, and go to state 9 ++ '$' shift, and go to state 320 ++ ++ variable go to state 50 ++ ++ ++state 322 ++ ++ 147 non_post_simp_exp: DECREMENT . variable ++ 154 variable: . NAME ++ 155 | . NAME '[' expression_list ']' ++ 156 | . '$' non_post_simp_exp ++ ++ NAME shift, and go to state 9 ++ '$' shift, and go to state 320 ++ ++ variable go to state 51 ++ ++ ++state 323 ++ ++ 130 simp_exp: . non_post_simp_exp ++ 131 | . simp_exp '^' simp_exp ++ 132 | . simp_exp '*' simp_exp ++ 133 | . simp_exp '/' simp_exp ++ 134 | . simp_exp '%' simp_exp ++ 135 | . simp_exp '+' simp_exp ++ 136 | . simp_exp '-' simp_exp ++ 137 | . variable INCREMENT ++ 138 | . variable DECREMENT ++ 139 non_post_simp_exp: . '!' simp_exp ++ 140 | . '(' exp r_paren ++ 141 | . LEX_BUILTIN '(' opt_expression_list r_paren ++ 142 | . LEX_LENGTH '(' opt_expression_list r_paren ++ 143 | . LEX_LENGTH ++ 144 | . FUNC_CALL '(' opt_expression_list r_paren ++ 145 | . variable ++ 146 | . INCREMENT variable ++ 147 | . DECREMENT variable ++ 148 | . YNUMBER ++ 149 | . YSTRING ++ 150 | . '-' simp_exp ++ 151 | . '+' simp_exp ++ 151 | '+' . simp_exp ++ 154 variable: . NAME ++ 155 | . NAME '[' expression_list ']' ++ 156 | . '$' non_post_simp_exp ++ ++ FUNC_CALL shift, and go to state 8 ++ NAME shift, and go to state 9 ++ YNUMBER shift, and go to state 10 ++ YSTRING shift, and go to state 11 ++ INCREMENT shift, and go to state 16 ++ DECREMENT shift, and go to state 17 ++ LEX_BUILTIN shift, and go to state 18 ++ LEX_LENGTH shift, and go to state 19 ++ '+' shift, and go to state 20 ++ '-' shift, and go to state 21 ++ '!' shift, and go to state 54 ++ '$' shift, and go to state 24 ++ '(' shift, and go to state 55 ++ ++ simp_exp go to state 326 ++ non_post_simp_exp go to state 35 ++ variable go to state 57 ++ ++ ++state 324 ++ ++ 130 simp_exp: . non_post_simp_exp ++ 131 | . simp_exp '^' simp_exp ++ 132 | . simp_exp '*' simp_exp ++ 133 | . simp_exp '/' simp_exp ++ 134 | . simp_exp '%' simp_exp ++ 135 | . simp_exp '+' simp_exp ++ 136 | . simp_exp '-' simp_exp ++ 137 | . variable INCREMENT ++ 138 | . variable DECREMENT ++ 139 non_post_simp_exp: . '!' simp_exp ++ 140 | . '(' exp r_paren ++ 141 | . LEX_BUILTIN '(' opt_expression_list r_paren ++ 142 | . LEX_LENGTH '(' opt_expression_list r_paren ++ 143 | . LEX_LENGTH ++ 144 | . FUNC_CALL '(' opt_expression_list r_paren ++ 145 | . variable ++ 146 | . INCREMENT variable ++ 147 | . DECREMENT variable ++ 148 | . YNUMBER ++ 149 | . YSTRING ++ 150 | . '-' simp_exp ++ 150 | '-' . simp_exp ++ 151 | . '+' simp_exp ++ 154 variable: . NAME ++ 155 | . NAME '[' expression_list ']' ++ 156 | . '$' non_post_simp_exp ++ ++ FUNC_CALL shift, and go to state 8 ++ NAME shift, and go to state 9 ++ YNUMBER shift, and go to state 10 ++ YSTRING shift, and go to state 11 ++ INCREMENT shift, and go to state 16 ++ DECREMENT shift, and go to state 17 ++ LEX_BUILTIN shift, and go to state 18 ++ LEX_LENGTH shift, and go to state 19 ++ '+' shift, and go to state 20 ++ '-' shift, and go to state 21 ++ '!' shift, and go to state 54 ++ '$' shift, and go to state 24 ++ '(' shift, and go to state 55 ++ ++ simp_exp go to state 327 ++ non_post_simp_exp go to state 35 ++ variable go to state 57 ++ ++ ++state 325 ++ ++ 130 simp_exp: . non_post_simp_exp ++ 131 | . simp_exp '^' simp_exp ++ 132 | . simp_exp '*' simp_exp ++ 133 | . simp_exp '/' simp_exp ++ 134 | . simp_exp '%' simp_exp ++ 135 | . simp_exp '+' simp_exp ++ 136 | . simp_exp '-' simp_exp ++ 137 | . variable INCREMENT ++ 138 | . variable DECREMENT ++ 139 non_post_simp_exp: . '!' simp_exp ++ 139 | '!' . simp_exp ++ 140 | . '(' exp r_paren ++ 141 | . LEX_BUILTIN '(' opt_expression_list r_paren ++ 142 | . LEX_LENGTH '(' opt_expression_list r_paren ++ 143 | . LEX_LENGTH ++ 144 | . FUNC_CALL '(' opt_expression_list r_paren ++ 145 | . variable ++ 146 | . INCREMENT variable ++ 147 | . DECREMENT variable ++ 148 | . YNUMBER ++ 149 | . YSTRING ++ 150 | . '-' simp_exp ++ 151 | . '+' simp_exp ++ 154 variable: . NAME ++ 155 | . NAME '[' expression_list ']' ++ 156 | . '$' non_post_simp_exp ++ ++ FUNC_CALL shift, and go to state 8 ++ NAME shift, and go to state 9 ++ YNUMBER shift, and go to state 10 ++ YSTRING shift, and go to state 11 ++ INCREMENT shift, and go to state 16 ++ DECREMENT shift, and go to state 17 ++ LEX_BUILTIN shift, and go to state 18 ++ LEX_LENGTH shift, and go to state 19 ++ '+' shift, and go to state 20 ++ '-' shift, and go to state 21 ++ '!' shift, and go to state 54 ++ '$' shift, and go to state 24 ++ '(' shift, and go to state 55 ++ ++ simp_exp go to state 328 ++ non_post_simp_exp go to state 35 ++ variable go to state 57 ++ ++ ++state 326 ++ ++ 131 simp_exp: simp_exp . '^' simp_exp ++ 132 | simp_exp . '*' simp_exp ++ 133 | simp_exp . '/' simp_exp ++ 134 | simp_exp . '%' simp_exp ++ 135 | simp_exp . '+' simp_exp ++ 136 | simp_exp . '-' simp_exp ++ 151 non_post_simp_exp: '+' simp_exp . [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, APPEND_OP, MATCHOP, NEWLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, '?', ':', ',', '<', '>', '|', TWOWAYIO, '+', '-', '!', '$', '(', ')', '@:>@', '{', ';'] ++ ++ '*' shift, and go to state 89 ++ '/' shift, and go to state 90 ++ '%' shift, and go to state 91 ++ '^' shift, and go to state 92 ++ ++ $default reduce using rule 151 (non_post_simp_exp) ++ ++ Conflict between rule 151 and token '+' resolved as reduce ('+' < UNARY). ++ Conflict between rule 151 and token '-' resolved as reduce ('-' < UNARY). ++ ++ ++state 327 ++ ++ 131 simp_exp: simp_exp . '^' simp_exp ++ 132 | simp_exp . '*' simp_exp ++ 133 | simp_exp . '/' simp_exp ++ 134 | simp_exp . '%' simp_exp ++ 135 | simp_exp . '+' simp_exp ++ 136 | simp_exp . '-' simp_exp ++ 150 non_post_simp_exp: '-' simp_exp . [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, APPEND_OP, MATCHOP, NEWLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, '?', ':', ',', '<', '>', '|', TWOWAYIO, '+', '-', '!', '$', '(', ')', '@:>@', '{', ';'] ++ ++ '*' shift, and go to state 89 ++ '/' shift, and go to state 90 ++ '%' shift, and go to state 91 ++ '^' shift, and go to state 92 ++ ++ $default reduce using rule 150 (non_post_simp_exp) ++ ++ Conflict between rule 150 and token '+' resolved as reduce ('+' < UNARY). ++ Conflict between rule 150 and token '-' resolved as reduce ('-' < UNARY). ++ ++ ++state 328 ++ ++ 131 simp_exp: simp_exp . '^' simp_exp ++ 132 | simp_exp . '*' simp_exp ++ 133 | simp_exp . '/' simp_exp ++ 134 | simp_exp . '%' simp_exp ++ 135 | simp_exp . '+' simp_exp ++ 136 | simp_exp . '-' simp_exp ++ 139 non_post_simp_exp: '!' simp_exp . [error, FUNC_CALL, NAME, YNUMBER, YSTRING, RELOP, APPEND_OP, MATCHOP, NEWLINE, LEX_IN, LEX_AND, LEX_OR, INCREMENT, DECREMENT, LEX_BUILTIN, LEX_LENGTH, '?', ':', ',', '<', '>', '|', TWOWAYIO, '+', '-', '!', '$', '(', ')', '@:>@', '{', ';'] ++ ++ '*' shift, and go to state 89 ++ '/' shift, and go to state 90 ++ '%' shift, and go to state 91 ++ '^' shift, and go to state 92 ++ ++ $default reduce using rule 139 (non_post_simp_exp) ++ ++ Conflict between rule 139 and token '+' resolved as reduce ('+' < UNARY). ++ Conflict between rule 139 and token '-' resolved as reduce ('-' < UNARY). +]])], + +dnl OTHER-CHECKS +[], + +dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR +dnl In the case of the syntax error, the parser recovers, so it returns 0. +[[0]], +[], +[AT_COND_CASE([[LALR]], +[[syntax error, unexpected '*', expecting NEWLINE or '{' or ';' +]])]) ## ----------------- ## ## GNU Cim Grammar. ## ## ----------------- ## -AT_SETUP([GNU Cim Grammar]) - # GNU Cim, the GNU Simula 87 Compiler. # Bison was once wrong, due to an incorrect computation of the RR conflicts. # It reported 80 SR && 99 RR conflicts instead of 78/10!!! -AT_DATA([[input.y]], +AT_TEST_EXISTING_GRAMMAR([[GNU Cim Grammar]], [[%union {} %token @@ -428,7 +845,8 @@ AT_DATA([[input.y]], %left HDOT %start MAIN_MODULE -%% +]], +[[ /* GRAMATIKK FOR PROGRAM MODULES */ MAIN_MODULE : {} MODULS @@ -947,17 +1365,26 @@ ARGUMENT_LIST : EXPRESSION HPAREXPSEPARATOR ARGUMENT_LIST ; -%% -]]) +]], + +dnl INPUT +[[]], + +dnl BISON-STDERR +[AT_COND_CASE([[canonical LR]], +[[input.y: conflicts: 1876 shift/reduce, 144 reduce/reduce]], +[[input.y: conflicts: 78 shift/reduce, 10 reduce/reduce]])[ +]], + +dnl LAST-STATE +[AT_COND_CASE([[canonical LR]], [[10425]], [[442]])], -# Pass plenty of options, to exercise plenty of code, even if we -# don't actually check the output. But SEGV is watching us, and -# so might do dmalloc. -AT_BISON_CHECK([[--verbose --defines input.y]], 0, [], -[[input.y: conflicts: 78 shift/reduce, 10 reduce/reduce -]]) +dnl LALR1-DIFF not used for canonical LR(1) because the diff is huge. +[], -AT_CHECK([[grep '^State.*conflicts:' input.output]], 0, +dnl OTHER-CHECKS +[AT_COND_CASE([[canonical LR]], [[]], +[AT_CHECK([[grep '^State.*conflicts:' input.output]], [[0]], [[State 64 conflicts: 14 shift/reduce State 164 conflicts: 1 shift/reduce State 201 conflicts: 33 shift/reduce, 4 reduce/reduce @@ -967,22 +1394,19 @@ State 335 conflicts: 9 shift/reduce, 2 reduce/reduce State 356 conflicts: 1 shift/reduce State 360 conflicts: 9 shift/reduce, 2 reduce/reduce State 427 conflicts: 9 shift/reduce, 2 reduce/reduce -]]) +]])])]) -AT_CLEANUP - -## ----------------- ## -## GNU pic Grammar. ## -## ----------------- ## - -AT_SETUP([GNU pic Grammar]) +## -------------------------------- ## +## GNU pic (Groff 1.18.1) Grammar. ## +## -------------------------------- ## # GNU pic, part of groff. # Bison once reported shift/reduce conflicts that it shouldn't have. -AT_DATA([[input.y]], -[[%union {} +AT_TEST_EXISTING_GRAMMAR([[GNU pic (Groff 1.18.1) Grammar]], +[[%error-verbose +%union {} %token LABEL %token VARIABLE @@ -1148,9 +1572,8 @@ works */ %left '*' '/' '%' %right '!' %right '^' - -%% - +]], +[[ top: optional_separator | element_list @@ -1513,13 +1936,1189 @@ expr: | expr OROR expr | '!' expr ; -]]) - -# Pass plenty of options, to exercise plenty of code, even if we -# don't actually check the output. But SEGV is watching us, and -# so might do dmalloc. -AT_BISON_CHECK([[--verbose --defines input.y]], 0, [], -[[input.y:453.11-48: warning: rule useless in parser due to conflicts: path: ORDINAL LAST object_type relative_path -]]) - -AT_CLEANUP +]], + +dnl INPUT +dnl +dnl For example, in pic: +dnl +dnl .PS +dnl A: circle "A" +dnl B: A left +dnl circle "B" at B +dnl .PE +dnl +dnl Even using groff 1.19.2, the 3rd line above is a syntax error. Change +dnl "left" to "right", and it still is. However, add "upper" or "lower" before +dnl "left or "right" and it's accepted to mean ".nw", ".ne", ".sw", or ".se". +dnl (There seem to be no aliases for "north" and "south" that can stand alone +dnl without being followed by "of".) +[[VARIABLE, '=', LABEL, LEFT, DOT_X]], + +dnl BISON-STDERR +[[input.y:471.11-48: warning: rule useless in parser due to conflicts: path: ORDINAL LAST object_type relative_path +]], + +dnl LAST-STATE +[AT_COND_CASE([[LALR]], [[422]], [[canonical LR]], [[4833]], [[427]])], + +dnl LALR1-DIFF not used for canonical LR(1) because the diff is huge. +dnl Isocore map from LALR(1) state number to new state number plus descriptions +dnl of any change in the actions resulting in a change in accepted language: +dnl - 102 -> 423: reduce -> shift on LEFT and RIGHT +dnl - 237 -> 425 +dnl - 266 -> 424 +dnl - 339 -> 426 +dnl - 383 -> 427 +[AT_COND_CASE([[LALR]], [], +[[@@ -1223,7 +1223,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -1377,7 +1377,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -1854,7 +1854,7 @@ + + text go to state 162 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -2047,7 +2047,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -2571,7 +2571,7 @@ + position_not_place go to state 99 + expr_pair go to state 191 + place go to state 101 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -2732,7 +2732,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -2875,7 +2875,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -3018,7 +3018,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -3256,7 +3256,7 @@ + + state 102 + +- 146 place: label . [$end, LABEL, VARIABLE, NUMBER, TEXT, ORDINAL, LEFT_ARROW_HEAD, RIGHT_ARROW_HEAD, DOUBLE_ARROW_HEAD, LAST, UP, DOWN, LEFT, RIGHT, HEIGHT, RADIUS, WIDTH, DIAMETER, FROM, TO, AT, WITH, BY, THEN, SOLID, DOTTED, DASHED, CHOP, SAME, INVISIBLE, LJUST, RJUST, ABOVE, BELOW, AND, HERE, DOT_X, DOT_Y, DOT_HT, DOT_WID, DOT_RAD, SIN, COS, ATAN2, LOG, EXP, SQRT, K_MAX, K_MIN, INT, RAND, SRAND, CW, CCW, THICKNESS, FILL, COLORED, OUTLINED, SHADED, ALIGNED, SPRINTF, '(', '`', ',', '>', '+', '-', '!', ';', '}', '@:>@', ')'] ++ 146 place: label . [$end, LABEL, VARIABLE, NUMBER, TEXT, ORDINAL, LEFT_ARROW_HEAD, RIGHT_ARROW_HEAD, DOUBLE_ARROW_HEAD, LAST, UP, DOWN, LEFT, RIGHT, HEIGHT, RADIUS, WIDTH, DIAMETER, FROM, TO, AT, WITH, BY, THEN, SOLID, DOTTED, DASHED, CHOP, SAME, INVISIBLE, LJUST, RJUST, ABOVE, BELOW, HERE, DOT_X, DOT_Y, DOT_HT, DOT_WID, DOT_RAD, SIN, COS, ATAN2, LOG, EXP, SQRT, K_MAX, K_MIN, INT, RAND, SRAND, CW, CCW, THICKNESS, FILL, COLORED, OUTLINED, SHADED, ALIGNED, SPRINTF, '(', '`', '+', '-', '!', ';', '}', '@:>@'] + 147 | label . corner + 153 label: label . '.' LABEL + 180 corner: . DOT_N +@@ -3645,7 +3645,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -3804,7 +3804,7 @@ + text_expr go to state 239 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -4481,7 +4481,7 @@ + $default reduce using rule 89 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -4673,7 +4673,7 @@ + $default reduce using rule 91 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -4867,7 +4867,7 @@ + $default reduce using rule 95 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -5065,7 +5065,7 @@ + $default reduce using rule 93 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -5260,7 +5260,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -5403,7 +5403,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -5546,7 +5546,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -5689,7 +5689,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -6475,7 +6475,7 @@ + + expr_pair go to state 280 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -6633,7 +6633,7 @@ + $default reduce using rule 105 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -6825,7 +6825,7 @@ + $default reduce using rule 107 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -7017,7 +7017,7 @@ + $default reduce using rule 114 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -7264,7 +7264,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -7408,7 +7408,7 @@ + $default reduce using rule 109 (object_spec) + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -7819,12 +7819,12 @@ + position_not_place go to state 296 + expr_pair go to state 100 + place go to state 297 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 + corner go to state 106 +- expr go to state 266 ++ expr go to state 424 + + + state 165 +@@ -7987,7 +7987,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -8172,7 +8172,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -8333,7 +8333,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -8494,7 +8494,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -8655,7 +8655,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -8816,7 +8816,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -8977,7 +8977,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -9138,7 +9138,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -9299,7 +9299,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -9460,7 +9460,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -9623,7 +9623,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -9784,7 +9784,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -9921,7 +9921,7 @@ + + $default reduce using rule 47 (any_expr) + +- between go to state 237 ++ between go to state 425 + + + state 193 +@@ -10152,7 +10152,7 @@ + + expr_pair go to state 317 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -10298,7 +10298,7 @@ + + expr_pair go to state 318 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -10622,7 +10622,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -10765,7 +10765,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -10908,7 +10908,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11051,7 +11051,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11194,7 +11194,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11337,7 +11337,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11480,7 +11480,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11637,7 +11637,7 @@ + position_not_place go to state 99 + expr_pair go to state 100 + place go to state 101 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11780,7 +11780,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -11923,7 +11923,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -12066,7 +12066,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -12209,7 +12209,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -12352,7 +12352,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -12495,7 +12495,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -12638,7 +12638,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -12794,12 +12794,12 @@ + position_not_place go to state 99 + expr_pair go to state 100 + place go to state 101 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 + corner go to state 106 +- expr go to state 266 ++ expr go to state 424 + + + state 238 +@@ -12937,7 +12937,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -13160,7 +13160,7 @@ + text_expr go to state 342 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -13319,7 +13319,7 @@ + text_expr go to state 344 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -13502,7 +13502,7 @@ + text_expr go to state 348 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -13661,7 +13661,7 @@ + text_expr go to state 350 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -13804,7 +13804,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -14747,7 +14747,7 @@ + position_not_place go to state 99 + expr_pair go to state 191 + place go to state 101 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -15074,7 +15074,7 @@ + text go to state 113 + expr_pair go to state 365 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -15693,12 +15693,12 @@ + position_not_place go to state 99 + expr_pair go to state 100 + place go to state 101 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 + corner go to state 106 +- expr go to state 266 ++ expr go to state 424 + + + state 315 +@@ -16124,7 +16124,7 @@ + + $default reduce using rule 239 (expr) + +- between go to state 237 ++ between go to state 425 + + Conflict between rule 239 and token OF resolved as shift ('<' < OF). + Conflict between rule 239 and token BETWEEN resolved as shift ('<' < BETWEEN). +@@ -17234,7 +17234,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -17416,7 +17416,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -17577,7 +17577,7 @@ + text_expr go to state 112 + text go to state 113 + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -17772,12 +17772,12 @@ + position_not_place go to state 99 + expr_pair go to state 100 + place go to state 101 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 + corner go to state 106 +- expr go to state 266 ++ expr go to state 424 + + + state 383 +@@ -18071,7 +18071,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -18221,7 +18221,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -18830,7 +18830,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -18987,7 +18987,7 @@ + '!' shift, and go to state 94 + + place go to state 114 +- label go to state 102 ++ label go to state 423 + ordinal go to state 103 + optional_ordinal_last go to state 104 + nth_primitive go to state 105 +@@ -19089,3 +19089,440 @@ + 29 placeless_element: FOR VARIABLE '=' expr TO expr optional_by DO $@6 DELIMITED . + + $default reduce using rule 29 (placeless_element) ++ ++ ++state 423 ++ ++ 146 place: label . [$end, AND, DOT_X, DOT_Y, DOT_HT, DOT_WID, DOT_RAD, ',', '>', '+', '-', ';', '}', '@:>@', ')'] ++ 147 | label . corner ++ 153 label: label . '.' LABEL ++ 180 corner: . DOT_N ++ 181 | . DOT_E ++ 182 | . DOT_W ++ 183 | . DOT_S ++ 184 | . DOT_NE ++ 185 | . DOT_SE ++ 186 | . DOT_NW ++ 187 | . DOT_SW ++ 188 | . DOT_C ++ 189 | . DOT_START ++ 190 | . DOT_END ++ 191 | . TOP ++ 192 | . BOTTOM ++ 193 | . LEFT ++ 194 | . RIGHT ++ 195 | . UPPER LEFT ++ 196 | . LOWER LEFT ++ 197 | . UPPER RIGHT ++ 198 | . LOWER RIGHT ++ 199 | . LEFT_CORNER ++ 200 | . RIGHT_CORNER ++ 201 | . UPPER LEFT_CORNER ++ 202 | . LOWER LEFT_CORNER ++ 203 | . UPPER RIGHT_CORNER ++ 204 | . LOWER RIGHT_CORNER ++ 205 | . NORTH ++ 206 | . SOUTH ++ 207 | . EAST ++ 208 | . WEST ++ 209 | . CENTER ++ 210 | . START ++ 211 | . END ++ ++ LEFT shift, and go to state 53 ++ RIGHT shift, and go to state 54 ++ DOT_N shift, and go to state 56 ++ DOT_E shift, and go to state 57 ++ DOT_W shift, and go to state 58 ++ DOT_S shift, and go to state 59 ++ DOT_NE shift, and go to state 60 ++ DOT_SE shift, and go to state 61 ++ DOT_NW shift, and go to state 62 ++ DOT_SW shift, and go to state 63 ++ DOT_C shift, and go to state 64 ++ DOT_START shift, and go to state 65 ++ DOT_END shift, and go to state 66 ++ TOP shift, and go to state 78 ++ BOTTOM shift, and go to state 79 ++ UPPER shift, and go to state 80 ++ LOWER shift, and go to state 81 ++ LEFT_CORNER shift, and go to state 82 ++ RIGHT_CORNER shift, and go to state 83 ++ NORTH shift, and go to state 84 ++ SOUTH shift, and go to state 85 ++ EAST shift, and go to state 86 ++ WEST shift, and go to state 87 ++ CENTER shift, and go to state 88 ++ END shift, and go to state 89 ++ START shift, and go to state 90 ++ '.' shift, and go to state 204 ++ ++ $default reduce using rule 146 (place) ++ ++ corner go to state 205 ++ ++ ++state 424 ++ ++ 140 position_not_place: expr . between position AND position ++ 141 | expr . '<' position ',' position '>' ++ 142 between: . BETWEEN ++ 143 | . OF THE WAY BETWEEN ++ 144 expr_pair: expr . ',' expr ++ 219 expr: expr . '+' expr ++ 220 | expr . '-' expr ++ 221 | expr . '*' expr ++ 222 | expr . '/' expr ++ 223 | expr . '%' expr ++ 224 | expr . '^' expr ++ 239 | expr . '<' expr ++ 240 | expr . LESSEQUAL expr ++ 241 | expr . '>' expr ++ 242 | expr . GREATEREQUAL expr ++ 243 | expr . EQUALEQUAL expr ++ 244 | expr . NOTEQUAL expr ++ 245 | expr . ANDAND expr ++ 246 | expr . OROR expr ++ ++ OF shift, and go to state 220 ++ BETWEEN shift, and go to state 221 ++ ANDAND shift, and go to state 222 ++ OROR shift, and go to state 223 ++ NOTEQUAL shift, and go to state 224 ++ EQUALEQUAL shift, and go to state 225 ++ LESSEQUAL shift, and go to state 226 ++ GREATEREQUAL shift, and go to state 227 ++ ',' shift, and go to state 228 ++ '<' shift, and go to state 229 ++ '>' shift, and go to state 230 ++ '+' shift, and go to state 231 ++ '-' shift, and go to state 232 ++ '*' shift, and go to state 233 ++ '/' shift, and go to state 234 ++ '%' shift, and go to state 235 ++ '^' shift, and go to state 236 ++ ++ between go to state 425 ++ ++ ++state 425 ++ ++ 134 position: . position_not_place ++ 135 | . place ++ 136 position_not_place: . expr_pair ++ 137 | . position '+' expr_pair ++ 138 | . position '-' expr_pair ++ 139 | . '(' position ',' position ')' ++ 140 | . expr between position AND position ++ 140 | expr between . position AND position ++ 141 | . expr '<' position ',' position '>' ++ 144 expr_pair: . expr ',' expr ++ 145 | . '(' expr_pair ')' ++ 146 place: . label ++ 147 | . label corner ++ 148 | . corner label ++ 149 | . corner OF label ++ 150 | . HERE ++ 151 label: . LABEL ++ 152 | . nth_primitive ++ 153 | . label '.' LABEL ++ 154 ordinal: . ORDINAL ++ 155 | . '`' any_expr TH ++ 156 optional_ordinal_last: . LAST ++ 157 | . ordinal LAST ++ 158 nth_primitive: . ordinal object_type ++ 159 | . optional_ordinal_last object_type ++ 180 corner: . DOT_N ++ 181 | . DOT_E ++ 182 | . DOT_W ++ 183 | . DOT_S ++ 184 | . DOT_NE ++ 185 | . DOT_SE ++ 186 | . DOT_NW ++ 187 | . DOT_SW ++ 188 | . DOT_C ++ 189 | . DOT_START ++ 190 | . DOT_END ++ 191 | . TOP ++ 192 | . BOTTOM ++ 193 | . LEFT ++ 194 | . RIGHT ++ 195 | . UPPER LEFT ++ 196 | . LOWER LEFT ++ 197 | . UPPER RIGHT ++ 198 | . LOWER RIGHT ++ 199 | . LEFT_CORNER ++ 200 | . RIGHT_CORNER ++ 201 | . UPPER LEFT_CORNER ++ 202 | . LOWER LEFT_CORNER ++ 203 | . UPPER RIGHT_CORNER ++ 204 | . LOWER RIGHT_CORNER ++ 205 | . NORTH ++ 206 | . SOUTH ++ 207 | . EAST ++ 208 | . WEST ++ 209 | . CENTER ++ 210 | . START ++ 211 | . END ++ 212 expr: . VARIABLE ++ 213 | . NUMBER ++ 214 | . place DOT_X ++ 215 | . place DOT_Y ++ 216 | . place DOT_HT ++ 217 | . place DOT_WID ++ 218 | . place DOT_RAD ++ 219 | . expr '+' expr ++ 220 | . expr '-' expr ++ 221 | . expr '*' expr ++ 222 | . expr '/' expr ++ 223 | . expr '%' expr ++ 224 | . expr '^' expr ++ 225 | . '-' expr ++ 226 | . '(' any_expr ')' ++ 227 | . SIN '(' any_expr ')' ++ 228 | . COS '(' any_expr ')' ++ 229 | . ATAN2 '(' any_expr ',' any_expr ')' ++ 230 | . LOG '(' any_expr ')' ++ 231 | . EXP '(' any_expr ')' ++ 232 | . SQRT '(' any_expr ')' ++ 233 | . K_MAX '(' any_expr ',' any_expr ')' ++ 234 | . K_MIN '(' any_expr ',' any_expr ')' ++ 235 | . INT '(' any_expr ')' ++ 236 | . RAND '(' any_expr ')' ++ 237 | . RAND '(' ')' ++ 238 | . SRAND '(' any_expr ')' ++ 239 | . expr '<' expr ++ 240 | . expr LESSEQUAL expr ++ 241 | . expr '>' expr ++ 242 | . expr GREATEREQUAL expr ++ 243 | . expr EQUALEQUAL expr ++ 244 | . expr NOTEQUAL expr ++ 245 | . expr ANDAND expr ++ 246 | . expr OROR expr ++ 247 | . '!' expr ++ ++ LABEL shift, and go to state 48 ++ VARIABLE shift, and go to state 49 ++ NUMBER shift, and go to state 50 ++ ORDINAL shift, and go to state 51 ++ LAST shift, and go to state 52 ++ LEFT shift, and go to state 53 ++ RIGHT shift, and go to state 54 ++ HERE shift, and go to state 55 ++ DOT_N shift, and go to state 56 ++ DOT_E shift, and go to state 57 ++ DOT_W shift, and go to state 58 ++ DOT_S shift, and go to state 59 ++ DOT_NE shift, and go to state 60 ++ DOT_SE shift, and go to state 61 ++ DOT_NW shift, and go to state 62 ++ DOT_SW shift, and go to state 63 ++ DOT_C shift, and go to state 64 ++ DOT_START shift, and go to state 65 ++ DOT_END shift, and go to state 66 ++ SIN shift, and go to state 67 ++ COS shift, and go to state 68 ++ ATAN2 shift, and go to state 69 ++ LOG shift, and go to state 70 ++ EXP shift, and go to state 71 ++ SQRT shift, and go to state 72 ++ K_MAX shift, and go to state 73 ++ K_MIN shift, and go to state 74 ++ INT shift, and go to state 75 ++ RAND shift, and go to state 76 ++ SRAND shift, and go to state 77 ++ TOP shift, and go to state 78 ++ BOTTOM shift, and go to state 79 ++ UPPER shift, and go to state 80 ++ LOWER shift, and go to state 81 ++ LEFT_CORNER shift, and go to state 82 ++ RIGHT_CORNER shift, and go to state 83 ++ NORTH shift, and go to state 84 ++ SOUTH shift, and go to state 85 ++ EAST shift, and go to state 86 ++ WEST shift, and go to state 87 ++ CENTER shift, and go to state 88 ++ END shift, and go to state 89 ++ START shift, and go to state 90 ++ '(' shift, and go to state 91 ++ '`' shift, and go to state 92 ++ '-' shift, and go to state 93 ++ '!' shift, and go to state 94 ++ ++ position go to state 426 ++ position_not_place go to state 99 ++ expr_pair go to state 100 ++ place go to state 101 ++ label go to state 423 ++ ordinal go to state 103 ++ optional_ordinal_last go to state 104 ++ nth_primitive go to state 105 ++ corner go to state 106 ++ expr go to state 424 ++ ++ ++state 426 ++ ++ 137 position_not_place: position . '+' expr_pair ++ 138 | position . '-' expr_pair ++ 140 | expr between position . AND position ++ ++ AND shift, and go to state 427 ++ '+' shift, and go to state 197 ++ '-' shift, and go to state 198 ++ ++ ++state 427 ++ ++ 134 position: . position_not_place ++ 135 | . place ++ 136 position_not_place: . expr_pair ++ 137 | . position '+' expr_pair ++ 138 | . position '-' expr_pair ++ 139 | . '(' position ',' position ')' ++ 140 | . expr between position AND position ++ 140 | expr between position AND . position ++ 141 | . expr '<' position ',' position '>' ++ 144 expr_pair: . expr ',' expr ++ 145 | . '(' expr_pair ')' ++ 146 place: . label ++ 147 | . label corner ++ 148 | . corner label ++ 149 | . corner OF label ++ 150 | . HERE ++ 151 label: . LABEL ++ 152 | . nth_primitive ++ 153 | . label '.' LABEL ++ 154 ordinal: . ORDINAL ++ 155 | . '`' any_expr TH ++ 156 optional_ordinal_last: . LAST ++ 157 | . ordinal LAST ++ 158 nth_primitive: . ordinal object_type ++ 159 | . optional_ordinal_last object_type ++ 180 corner: . DOT_N ++ 181 | . DOT_E ++ 182 | . DOT_W ++ 183 | . DOT_S ++ 184 | . DOT_NE ++ 185 | . DOT_SE ++ 186 | . DOT_NW ++ 187 | . DOT_SW ++ 188 | . DOT_C ++ 189 | . DOT_START ++ 190 | . DOT_END ++ 191 | . TOP ++ 192 | . BOTTOM ++ 193 | . LEFT ++ 194 | . RIGHT ++ 195 | . UPPER LEFT ++ 196 | . LOWER LEFT ++ 197 | . UPPER RIGHT ++ 198 | . LOWER RIGHT ++ 199 | . LEFT_CORNER ++ 200 | . RIGHT_CORNER ++ 201 | . UPPER LEFT_CORNER ++ 202 | . LOWER LEFT_CORNER ++ 203 | . UPPER RIGHT_CORNER ++ 204 | . LOWER RIGHT_CORNER ++ 205 | . NORTH ++ 206 | . SOUTH ++ 207 | . EAST ++ 208 | . WEST ++ 209 | . CENTER ++ 210 | . START ++ 211 | . END ++ 212 expr: . VARIABLE ++ 213 | . NUMBER ++ 214 | . place DOT_X ++ 215 | . place DOT_Y ++ 216 | . place DOT_HT ++ 217 | . place DOT_WID ++ 218 | . place DOT_RAD ++ 219 | . expr '+' expr ++ 220 | . expr '-' expr ++ 221 | . expr '*' expr ++ 222 | . expr '/' expr ++ 223 | . expr '%' expr ++ 224 | . expr '^' expr ++ 225 | . '-' expr ++ 226 | . '(' any_expr ')' ++ 227 | . SIN '(' any_expr ')' ++ 228 | . COS '(' any_expr ')' ++ 229 | . ATAN2 '(' any_expr ',' any_expr ')' ++ 230 | . LOG '(' any_expr ')' ++ 231 | . EXP '(' any_expr ')' ++ 232 | . SQRT '(' any_expr ')' ++ 233 | . K_MAX '(' any_expr ',' any_expr ')' ++ 234 | . K_MIN '(' any_expr ',' any_expr ')' ++ 235 | . INT '(' any_expr ')' ++ 236 | . RAND '(' any_expr ')' ++ 237 | . RAND '(' ')' ++ 238 | . SRAND '(' any_expr ')' ++ 239 | . expr '<' expr ++ 240 | . expr LESSEQUAL expr ++ 241 | . expr '>' expr ++ 242 | . expr GREATEREQUAL expr ++ 243 | . expr EQUALEQUAL expr ++ 244 | . expr NOTEQUAL expr ++ 245 | . expr ANDAND expr ++ 246 | . expr OROR expr ++ 247 | . '!' expr ++ ++ LABEL shift, and go to state 48 ++ VARIABLE shift, and go to state 49 ++ NUMBER shift, and go to state 50 ++ ORDINAL shift, and go to state 51 ++ LAST shift, and go to state 52 ++ LEFT shift, and go to state 53 ++ RIGHT shift, and go to state 54 ++ HERE shift, and go to state 55 ++ DOT_N shift, and go to state 56 ++ DOT_E shift, and go to state 57 ++ DOT_W shift, and go to state 58 ++ DOT_S shift, and go to state 59 ++ DOT_NE shift, and go to state 60 ++ DOT_SE shift, and go to state 61 ++ DOT_NW shift, and go to state 62 ++ DOT_SW shift, and go to state 63 ++ DOT_C shift, and go to state 64 ++ DOT_START shift, and go to state 65 ++ DOT_END shift, and go to state 66 ++ SIN shift, and go to state 67 ++ COS shift, and go to state 68 ++ ATAN2 shift, and go to state 69 ++ LOG shift, and go to state 70 ++ EXP shift, and go to state 71 ++ SQRT shift, and go to state 72 ++ K_MAX shift, and go to state 73 ++ K_MIN shift, and go to state 74 ++ INT shift, and go to state 75 ++ RAND shift, and go to state 76 ++ SRAND shift, and go to state 77 ++ TOP shift, and go to state 78 ++ BOTTOM shift, and go to state 79 ++ UPPER shift, and go to state 80 ++ LOWER shift, and go to state 81 ++ LEFT_CORNER shift, and go to state 82 ++ RIGHT_CORNER shift, and go to state 83 ++ NORTH shift, and go to state 84 ++ SOUTH shift, and go to state 85 ++ EAST shift, and go to state 86 ++ WEST shift, and go to state 87 ++ CENTER shift, and go to state 88 ++ END shift, and go to state 89 ++ START shift, and go to state 90 ++ '(' shift, and go to state 91 ++ '`' shift, and go to state 92 ++ '-' shift, and go to state 93 ++ '!' shift, and go to state 94 ++ ++ position go to state 402 ++ position_not_place go to state 99 ++ expr_pair go to state 100 ++ place go to state 101 ++ label go to state 423 ++ ordinal go to state 103 ++ optional_ordinal_last go to state 104 ++ nth_primitive go to state 105 ++ corner go to state 106 ++ expr go to state 424 +]])], + +dnl OTHER-CHECKS +[], + +dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR +[AT_COND_CASE([[LALR]], [[1]], [[0]])], +[], +[AT_COND_CASE([[LALR]], +[[syntax error, unexpected LEFT +]])]) diff --git a/tests/reduce.at b/tests/reduce.at index 058d7c0d..6642f654 100644 --- a/tests/reduce.at +++ b/tests/reduce.at @@ -359,6 +359,1089 @@ AT_CLEANUP +## ----------------- ## +## %define lr.type. ## +## ----------------- ## + +# AT_TEST_LR_TYPE(DESCRIPTION, +# DECLS, GRAMMAR, INPUT, +# BISON-STDERR, TABLES, +# [OTHER-CHECKS], +# [PARSER-EXIT-VALUE], +# [PARSER-STDOUT], [PARSER-STDERR]) +# ------------------------------------------------- +m4_define([AT_TEST_LR_TYPE], +[ +AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1], + [[LALR]], [[]], + [$2], m4_shiftn(2, $@)) +AT_TEST_TABLES_AND_PARSE([[%define lr.type "LALR": ]$1], + [[LALR]], [[]], + [[%define lr.type "LALR" +]$2], + m4_shiftn(2, $@)) +AT_TEST_TABLES_AND_PARSE([[%define lr.type "IELR": ]$1], + [[IELR]], [[]], + [[%define lr.type "IELR" +]$2], + m4_shiftn(2, $@)) +AT_TEST_TABLES_AND_PARSE([[%define lr.type "canonical LR": ]$1], + [[canonical LR]], [[]], + [[%define lr.type "canonical LR" +]$2], + m4_shiftn(2, $@)) +]) + +AT_TEST_LR_TYPE([[Single State Split]], +[[%left 'a' +// Conflict resolution renders state 12 unreachable for canonical LR(1). We +// keep it so that the paser table diff is easier to code. +%define lr.keep_unreachable_states]], +[[ +S: 'a' A 'a' /* rule 1 */ + | 'b' A 'b' /* rule 2 */ + | 'c' c /* rule 3 */ + ; + +/* A conflict should appear after the first 'a' in rules 4 and 5 but only after + having shifted the first 'a' in rule 1. However, when LALR(1) merging is + chosen, the state containing that conflict is reused after having seen the + first 'b' in rule 2 and then the first 'a' in rules 4 and 5. In both cases, + because of the merged state, if the next token is an 'a', the %left forces a + reduction action with rule 5. In the latter case, only a shift is actually + grammatically correct. Thus, the parser would report a syntax error for the + grammatically correct sentence "baab" because it would encounter a syntax + error after that incorrect reduction. + + Despite not being LALR(1), Menhir version 20070322 suffers from this problem + as well. It uses David Pager's weak compatibility test for merging states. + Bison and Menhir accept non-LR(1) grammars with conflict resolution. Pager + designed his algorithm only for LR(1) grammars. */ +A: 'a' 'a' /* rule 4 */ + | 'a' /* rule 5 */ + ; + +/* Rule 3, rule 6, and rule 7 ensure that Bison does not report rule 4 as + useless after conflict resolution. This proves that, even though LALR(1) + generates incorrect parser tables sometimes, Bison will not necessarily + produce any warning to help the user realize it. */ +c: 'a' 'b' /* rule 6 */ + | A /* rule 7 */ + ; +]], + +dnl INPUT +[['b', 'a', 'a', 'b']], + +dnl BISON-STDERR +[], + +dnl TABLES +[[state 0 + + 0 $accept: . S $end + 1 S: . 'a' A 'a' + 2 | . 'b' A 'b' + 3 | . 'c' c + + 'a' shift, and go to state 1 + 'b' shift, and go to state 2 + 'c' shift, and go to state 3 + + S go to state 4 + + +state 1 + + 1 S: 'a' . A 'a' + 4 A: . 'a' 'a' + 5 | . 'a' + + 'a' shift, and go to state 5 + + A go to state 6 + + +state 2 + + 2 S: 'b' . A 'b' + 4 A: . 'a' 'a' + 5 | . 'a' + + 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[16]])[ + + A go to state 7 + + +state 3 + + 3 S: 'c' . c + 4 A: . 'a' 'a' + 5 | . 'a' + 6 c: . 'a' 'b' + 7 | . A + + 'a' shift, and go to state 8 + + A go to state 9 + c go to state 10 + + +state 4 + + 0 $accept: S . $end + + $end shift, and go to state 11 + + +state 5 + + 4 A: 'a' . 'a' + 5 | 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 5 (A) + + Conflict between rule 5 and token 'a' resolved as reduce (%left 'a'). + + +state 6 + + 1 S: 'a' A . 'a' + + 'a' shift, and go to state 13 + + +state 7 + + 2 S: 'b' A . 'b' + + 'b' shift, and go to state 14 + + +state 8 + + 4 A: 'a' . 'a' + 5 | 'a' . [$end] + 6 c: 'a' . 'b' + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[17]], + [[12]])[ + 'b' shift, and go to state 15 + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 5 (A) + + +state 9 + + 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 7 (c) + + +state 10 + + 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 3 (S) + + +state 11 + + 0 $accept: S $end . + + $default accept + + +state 12 + + 4 A: 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 4 (A) + + +state 13 + + 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 1 (S) + + +state 14 + + 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 2 (S) + + +state 15 + + 6 c: 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 6 (c)]AT_COND_CASE([[LALR]], + [[]], [[ + + +state 16 + + 4 A: 'a' . 'a' + 5 | 'a' . ['b'] + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[18]], + [[12]])[ + + ]AT_COND_CASE([[canonical LR]], [['b']], + [[$default]])[ reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[ + + +state 17 + + 4 A: 'a' 'a' . [$end] + + $end reduce using rule 4 (A) + + +state 18 + + 4 A: 'a' 'a' . ['b'] + + 'b' reduce using rule 4 (A)]])])[ +]], + +dnl OTHER-CHECKS +[], + +dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR +[AT_COND_CASE([[LALR]], [[1]], [[0]])], +[], +[AT_COND_CASE([[LALR]], +[[syntax error +]])]) + +AT_TEST_LR_TYPE([[Lane Split]], +[[%left 'a' +// Conflict resolution renders state 16 unreachable for canonical LR(1). We +// keep it so that the paser table diff is easier to code. +%define lr.keep_unreachable_states]], +[[ +/* Similar to the last test case set but two states must be split. */ +S: 'a' A 'a' /* rule 1 */ + | 'b' A 'b' /* rule 2 */ + | 'c' c /* rule 3 */ + ; + +A: 'a' 'a' 'a' /* rule 4 */ + | 'a' 'a' /* rule 5 */ + ; + +c: 'a' 'a' 'b' /* rule 6 */ + | A /* rule 7 */ + ; +]], + +dnl INPUT +[['b', 'a', 'a', 'a', 'b']], + +dnl BISON-STDERR +[], + +dnl TABLES +[[state 0 + + 0 $accept: . S $end + 1 S: . 'a' A 'a' + 2 | . 'b' A 'b' + 3 | . 'c' c + + 'a' shift, and go to state 1 + 'b' shift, and go to state 2 + 'c' shift, and go to state 3 + + S go to state 4 + + +state 1 + + 1 S: 'a' . A 'a' + 4 A: . 'a' 'a' 'a' + 5 | . 'a' 'a' + + 'a' shift, and go to state 5 + + A go to state 6 + + +state 2 + + 2 S: 'b' . A 'b' + 4 A: . 'a' 'a' 'a' + 5 | . 'a' 'a' + + 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[18]])[ + + A go to state 7 + + +state 3 + + 3 S: 'c' . c + 4 A: . 'a' 'a' 'a' + 5 | . 'a' 'a' + 6 c: . 'a' 'a' 'b' + 7 | . A + + 'a' shift, and go to state 8 + + A go to state 9 + c go to state 10 + + +state 4 + + 0 $accept: S . $end + + $end shift, and go to state 11 + + +state 5 + + 4 A: 'a' . 'a' 'a' + 5 | 'a' . 'a' + + 'a' shift, and go to state 12 + + +state 6 + + 1 S: 'a' A . 'a' + + 'a' shift, and go to state 13 + + +state 7 + + 2 S: 'b' A . 'b' + + 'b' shift, and go to state 14 + + +state 8 + + 4 A: 'a' . 'a' 'a' + 5 | 'a' . 'a' + 6 c: 'a' . 'a' 'b' + + 'a' shift, and go to state 15 + + +state 9 + + 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 7 (c) + + +state 10 + + 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 3 (S) + + +state 11 + + 0 $accept: S $end . + + $default accept + + +state 12 + + 4 A: 'a' 'a' . 'a' + 5 | 'a' 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 5 (A) + + Conflict between rule 5 and token 'a' resolved as reduce (%left 'a'). + + +state 13 + + 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 1 (S) + + +state 14 + + 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 2 (S) + + +state 15 + + 4 A: 'a' 'a' . 'a' + 5 | 'a' 'a' . [$end] + 6 c: 'a' 'a' . 'b' + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[19]], + [[16]])[ + 'b' shift, and go to state 17 + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 5 (A) + + +state 16 + + 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 4 (A) + + +state 17 + + 6 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 6 (c)]AT_COND_CASE([[LALR]], + [[]], [[ + + +state 18 + + 4 A: 'a' . 'a' 'a' + 5 | 'a' . 'a' + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]], + [[19]])[ + + +state 19]AT_COND_CASE([[canonical LR]], [[ + + 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 4 (A) + + +state 20]])[ + + 4 A: 'a' 'a' . 'a' + 5 | 'a' 'a' . ['b'] + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]], + [[16]])[ + + ]AT_COND_CASE([[canonical LR]], [['b']], + [[$default]])[ reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[ + + +state 21 + + 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['b']]])[ + + ]AT_COND_CASE([[canonical LR]], [['b']], + [[$default]])[ reduce using rule 4 (A)]])])[ +]], + +dnl OTHER-CHECKS +[], + +dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR +[AT_COND_CASE([[LALR]], [[1]], [[0]])], +[], +[AT_COND_CASE([[LALR]], +[[syntax error +]])]) + +AT_TEST_LR_TYPE([[Complex Lane Split]], +[[%left 'a' +// Conflict resolution renders state 16 unreachable for canonical LR(1). We +// keep it so that the paser table diff is easier to code. +%define lr.keep_unreachable_states]], +[[ +/* Similar to the last test case set but forseeing the S/R conflict from the + first state that must be split is becoming difficult. Imagine if B were + even more complex. Imagine if A had other RHS's ending in other + nonterminals. */ +S: 'a' A 'a' + | 'b' A 'b' + | 'c' c + ; +A: 'a' 'a' B + ; +B: 'a' + | %prec 'a' + ; +c: 'a' 'a' 'b' + | A + ; +]], + +dnl INPUT +[['b', 'a', 'a', 'a', 'b']], + +dnl BISON-STDERR +[], + +dnl TABLES +[[state 0 + + 0 $accept: . S $end + 1 S: . 'a' A 'a' + 2 | . 'b' A 'b' + 3 | . 'c' c + + 'a' shift, and go to state 1 + 'b' shift, and go to state 2 + 'c' shift, and go to state 3 + + S go to state 4 + + +state 1 + + 1 S: 'a' . A 'a' + 4 A: . 'a' 'a' B + + 'a' shift, and go to state 5 + + A go to state 6 + + +state 2 + + 2 S: 'b' . A 'b' + 4 A: . 'a' 'a' B + + 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[19]])[ + + A go to state 7 + + +state 3 + + 3 S: 'c' . c + 4 A: . 'a' 'a' B + 7 c: . 'a' 'a' 'b' + 8 | . A + + 'a' shift, and go to state 8 + + A go to state 9 + c go to state 10 + + +state 4 + + 0 $accept: S . $end + + $end shift, and go to state 11 + + +state 5 + + 4 A: 'a' . 'a' B + + 'a' shift, and go to state 12 + + +state 6 + + 1 S: 'a' A . 'a' + + 'a' shift, and go to state 13 + + +state 7 + + 2 S: 'b' A . 'b' + + 'b' shift, and go to state 14 + + +state 8 + + 4 A: 'a' . 'a' B + 7 c: 'a' . 'a' 'b' + + 'a' shift, and go to state 15 + + +state 9 + + 8 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 8 (c) + + +state 10 + + 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 3 (S) + + +state 11 + + 0 $accept: S $end . + + $default accept + + +state 12 + + 4 A: 'a' 'a' . B + 5 B: . 'a' + 6 | . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 6 (B) + + B go to state 17 + + Conflict between rule 6 and token 'a' resolved as reduce (%left 'a'). + + +state 13 + + 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 1 (S) + + +state 14 + + 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 2 (S) + + +state 15 + + 4 A: 'a' 'a' . B + 5 B: . 'a' + 6 | . [$end] + 7 c: 'a' 'a' . 'b' + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]], + [[16]])[ + 'b' shift, and go to state 18 + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 6 (B) + + B go to state ]AT_COND_CASE([[canonical LR]], [[21]], [[17]])[ + + +state 16 + + 5 B: 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 5 (B) + + +state 17 + + 4 A: 'a' 'a' B .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[ + + ]AT_COND_CASE([[canonical LR]], [['a']], + [[$default]])[ reduce using rule 4 (A) + + +state 18 + + 7 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 7 (c)]AT_COND_CASE([[LALR]], [], [[ + + +state 19 + + 4 A: 'a' . 'a' B + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[22]], + [[20]])[ + + +state 20]AT_COND_CASE([[canonical LR]], [[ + + 5 B: 'a' . [$end] + + $end reduce using rule 5 (B) + + +state 21 + + 4 A: 'a' 'a' B . [$end] + + $end reduce using rule 4 (A) + + +state 22]])[ + + 4 A: 'a' 'a' . B + 5 B: . 'a' + 6 | . ['b'] + + 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[23]], + [[16]])[ + + ]AT_COND_CASE([[canonical LR]], [['b']], + [[$default]])[ reduce using rule 6 (B) + + B go to state ]AT_COND_CASE([[canonical LR]], [[24 + + +state 23 + + 5 B: 'a' . ['b'] + + 'b' reduce using rule 5 (B) + + +state 24 + + 4 A: 'a' 'a' B . ['b'] + + 'b' reduce using rule 4 (A)]], [[17]])])[ +]], + +dnl OTHER-CHECKS +[], + +dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR +[AT_COND_CASE([[LALR]], [[1]], [[0]])], +[], +[AT_COND_CASE([[LALR]], +[[syntax error +]])]) + +AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]], +[[%define lr.keep_unreachable_states]], +[[ +/* The partial state chart diagram below is for LALR(1). State 0 is the start + state. States are iterated for successor construction in numerical order. + Transitions are downwards. + + State 13 has a R/R conflict that cannot be predicted by Bison's LR(1) + algorithm using annotations alone. That is, when state 11's successor on + 'd' is merged with state 5 (which is originally just state 1's successor on + 'd'), state 5's successor on 'e' must then be changed because the resulting + lookaheads that propagate to it now make it incompatible with state 8's + successor on 'e'. In other words, state 13 must be split to avoid the + conflict. + + 0 + / | \ + a / c| \ b + 1 3 2 + | | | + d| |c | d + | 11 | + | | | + \ /d | + 5 8 + \ | + e \ / e + 13 + R/R + + This grammar is designed carefully to make sure that, despite Bison's LR(1) + algorithm's bread-first iteration of transitions to reconstruct states, + state 11's successors are constructed after state 5's and state 8's. + Otherwise (for example, if you remove the first 'c' in each of rules 6 and + 7), state 5's successor on 'e' would never be merged with state 8's, so the + split of the resulting state 13 would never need to be performed. */ +S: 'a' A 'f' + | 'a' B + | 'b' A 'f' + | 'b' B 'g' + | 'b' 'd' + | 'c' 'c' A 'g' + | 'c' 'c' B + ; +A: 'd' 'e' ; +B: 'd' 'e' ; +]], + +dnl INPUT +[['b', 'd', 'e', 'g']], + +dnl BISON-STDERR +[AT_COND_CASE([[LALR]], +[[input.y: conflicts: 1 reduce/reduce +]], [])], + +dnl TABLES +[[state 0 + + 0 $accept: . S $end + 1 S: . 'a' A 'f' + 2 | . 'a' B + 3 | . 'b' A 'f' + 4 | . 'b' B 'g' + 5 | . 'b' 'd' + 6 | . 'c' 'c' A 'g' + 7 | . 'c' 'c' B + + 'a' shift, and go to state 1 + 'b' shift, and go to state 2 + 'c' shift, and go to state 3 + + S go to state 4 + + +state 1 + + 1 S: 'a' . A 'f' + 2 | 'a' . B + 8 A: . 'd' 'e' + 9 B: . 'd' 'e' + + 'd' shift, and go to state 5 + + A go to state 6 + B go to state 7 + + +state 2 + + 3 S: 'b' . A 'f' + 4 | 'b' . B 'g' + 5 | 'b' . 'd' + 8 A: . 'd' 'e' + 9 B: . 'd' 'e' + + 'd' shift, and go to state 8 + + A go to state 9 + B go to state 10 + + +state 3 + + 6 S: 'c' . 'c' A 'g' + 7 | 'c' . 'c' B + + 'c' shift, and go to state 11 + + +state 4 + + 0 $accept: S . $end + + $end shift, and go to state 12 + + +state 5 + + 8 A: 'd' . 'e' + 9 B: 'd' . 'e' + + 'e' shift, and go to state ]AT_COND_CASE([[LALR]], [[13]], + [[canonical LR]], [[13]], + [[20]])[ + + +state 6 + + 1 S: 'a' A . 'f' + + 'f' shift, and go to state 14 + + +state 7 + + 2 S: 'a' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 2 (S) + + +state 8 + + 5 S: 'b' 'd' . [$end] + 8 A: 'd' . 'e' + 9 B: 'd' . 'e' + + 'e' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]], + [[13]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 5 (S) + + +state 9 + + 3 S: 'b' A . 'f' + + 'f' shift, and go to state 15 + + +state 10 + + 4 S: 'b' B . 'g' + + 'g' shift, and go to state 16 + + +state 11 + + 6 S: 'c' 'c' . A 'g' + 7 | 'c' 'c' . B + 8 A: . 'd' 'e' + 9 B: . 'd' 'e' + + 'd' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]], + [[5]])[ + + A go to state 17 + B go to state 18 + + +state 12 + + 0 $accept: S $end . + + $default accept]AT_COND_CASE([[LALR]], [[ + + +state 13 + + 8 A: 'd' 'e' . ['f', 'g'] + 9 B: 'd' 'e' . [$end, 'g'] + + $end reduce using rule 9 (B) + 'g' reduce using rule 8 (A) + 'g' [reduce using rule 9 (B)] + $default reduce using rule 8 (A)]], [[ + + +state 13 + + 8 A: 'd' 'e' . ['f'] + 9 B: 'd' 'e' . ]AT_COND_CASE([[canonical LR]], [[[$end]]], [[['g']]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [['g' ]])[ reduce using rule 9 (B) + ]AT_COND_CASE([[canonical LR]], [['f' ]], + [[$default]])[ reduce using rule 8 (A)]])[ + + +state 14 + + 1 S: 'a' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 1 (S) + + +state 15 + + 3 S: 'b' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 3 (S) + + +state 16 + + 4 S: 'b' B 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 4 (S) + + +state 17 + + 6 S: 'c' 'c' A . 'g' + + 'g' shift, and go to state 19 + + +state 18 + + 7 S: 'c' 'c' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 7 (S) + + +state 19 + + 6 S: 'c' 'c' A 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[ + + ]AT_COND_CASE([[canonical LR]], [[$end]], + [[$default]])[ reduce using rule 6 (S)]AT_COND_CASE([[LALR]], + [[]], [[ + + +state 20]AT_COND_CASE([[canonical LR]], [[ + + 8 A: 'd' 'e' . ['f'] + 9 B: 'd' 'e' . ['g'] + + 'f' reduce using rule 8 (A) + 'g' reduce using rule 9 (B) + + +state 21 + + 8 A: 'd' . 'e' + 9 B: 'd' . 'e' + + 'e' shift, and go to state 22 + + +state 22 + + 8 A: 'd' 'e' . ['g'] + 9 B: 'd' 'e' . [$end] + + $end reduce using rule 9 (B) + 'g' reduce using rule 8 (A)]], [[ + + 8 A: 'd' 'e' . ['f', 'g'] + 9 B: 'd' 'e' . [$end] + + $end reduce using rule 9 (B) + $default reduce using rule 8 (A)]])])[ +]], + +dnl OTHER-CHECKS +[], + +dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR +[AT_COND_CASE([[LALR]], [[1]], [[0]])], +[], +[AT_COND_CASE([[LALR]], +[[syntax error +]])]) + + + ## -------------------------- ## ## %define lr.default_rules. ## ## -------------------------- ## -- 2.45.2