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.

diff --git a/ChangeLog b/ChangeLog
index 962f53427c416091f2b53afd76b026792b23d0ad..d7e97f347ef908ada16943cfcd9af9095a2e6c32 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,53 @@
+2009-04-21  Joel E. Denny  <jdenny@ces.clemson.edu>
+
+       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  <jdenny@ces.clemson.edu>
 
        Add new files for IELR and canonical LR implementation.

diff --git a/lib/timevar.def b/lib/timevar.def
index 3a4128f28b804d1bbe220bf624e4777585ccd72e..5caf7c3d2932c75736b994bb03a6ea94672f87dd 100644 (file)
--- 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 <akim@freefriends.org>.
 
    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 a5cf94ee6f3646c06427f5e884b23b3bd7767dab..825266a8413cc38fe8740642d33145b763ee4044 100644 (file)
--- 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 bb060c55a28f9d9ec3e935a97090efa82cdb7a51..4b35171e70c290412ab02c145d33ed5864eefc9d 100644 (file)
--- 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 1139067452f7bcdf208997e011266eed151a7ea8..d9d952022d29cb5217ed2dfda1b944ee795d43e4 100644 (file)
--- 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 9f5d43f3d0fbf640bb25be30e2ce2a88b296523b..0101149833cad5f3380bd3044f24a609a6c52115 100644 (file)
--- 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.  <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 ();

diff --git a/src/lalr.h b/src/lalr.h
index c65c9b48803ad79d079d2c0cb8f11ffaabf0e8af..103a4c865f42ba2f7269774b10a653ee47aa0825 100644 (file)
--- 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 b3ef70ac733846afe4661409ea17ac5db48a89cb..6c93a4ef9d5ce0707096f7fc65964f939df3a9b6 100644 (file)
--- 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 68e8b44e9b4edda3e224f17ffeb39aa953bee543..b2fdc3b6105c4a3f8caa8e24d01ff572f87be73c 100644 (file)
--- 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 d3460c1575366c846c803f63c2d2e01c66a85aa9..a0f5cdb84371f20c7be2cbf5793a96dbfcff75e8 100644 (file)
--- 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 4afc1f00a11d47d998203f8d925b0e489dfbc5b1..931b48f1bf0aab6356b3889f001854230911e7b2 100644 (file)
--- 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 ba2c40cba58256e0afa4a35cbd6d35c83a5c17f0..b754f3c69fe914a913cad926f461576227978575 100644 (file)
--- 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 <http://www.gnu.org/licenses/>.
 
 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 058d7c0d3210f0b2ebd31e46d1b933be0b2fc452..6642f6540751e87c0e8e5cfd74752f9317267c93 100644 (file)
--- 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.  ##
 ## -------------------------- ##