[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] Finish implementing %define lr.type.
|
From: |
Joel E. Denny |
|
Subject: |
[PATCH] Finish implementing %define lr.type. |
|
Date: |
Tue, 21 Apr 2009 06:30:51 -0400 (EDT) |
Pushed to branch-2.5 and master.
>From f805dfcb3fc6517dd0a49939fd6610999afcca00 Mon Sep 17 00:00:00 2001
From: Joel E. Denny <address@hidden>
Date: Tue, 21 Apr 2009 03:40:16 -0400
Subject: [PATCH] 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/lib/timevar.def b/lib/timevar.def
index 3a4128f..5caf7c3 100644
--- a/lib/timevar.def
+++ b/lib/timevar.def
@@ -1,6 +1,6 @@
/* This file contains the definitions for timing variables used to -*- C -*-
measure run-time performance of the compiler.
- Copyright (C) 2002, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2007, 2009 Free Software Foundation, Inc.
Contributed by Akim Demaille <address@hidden>.
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 a5cf94e..825266a 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1,7 +1,7 @@
# Make bison/src.
-# Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software
-# Foundation, Inc.
+# Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
+# Free Software Foundation, Inc.
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -31,7 +31,10 @@ bin_SCRIPTS = $(YACC_SCRIPT)
EXTRA_SCRIPTS = yacc
bison_SOURCES = \
+ AnnotationList.c AnnotationList.h \
+ InadequacyList.c InadequacyList.h \
LR0.c LR0.h \
+ Sbitset.c Sbitset.h \
assoc.c assoc.h \
closure.c closure.h \
complain.c complain.h \
@@ -42,6 +45,7 @@ bison_SOURCES = \
getargs.c getargs.h \
gram.c gram.h \
lalr.h lalr.c \
+ ielr.h ielr.c \
location.c location.h \
main.c \
muscle_tab.c muscle_tab.h \
diff --git a/src/getargs.c b/src/getargs.c
index bb060c5..4b35171 100644
--- a/src/getargs.c
+++ b/src/getargs.c
@@ -1,7 +1,7 @@
/* Parse command line arguments for Bison.
Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004,
- 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+ 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -181,6 +181,7 @@ static const char * const trace_args[] =
"m4 - m4 traces",
"skeleton - skeleton postprocessing",
"time - time consumption",
+ "ielr - IELR conversion",
"all - all of the above",
0
};
@@ -200,6 +201,7 @@ static const int trace_types[] =
trace_m4,
trace_skeleton,
trace_time,
+ trace_ielr,
trace_all
};
diff --git a/src/getargs.h b/src/getargs.h
index 1139067..d9d9520 100644
--- a/src/getargs.h
+++ b/src/getargs.h
@@ -1,7 +1,7 @@
/* Parse command line arguments for bison.
Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004,
- 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+ 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -107,6 +107,7 @@ enum trace
trace_skeleton = 1 << 9, /**< Skeleton postprocessing. */
trace_m4 = 1 << 10, /**< M4 traces. */
trace_muscles = 1 << 11, /**< M4 definitions of the muscles. */
+ trace_ielr = 1 << 12, /**< IELR conversion. */
trace_all = ~0 /**< All of the above. */
};
/** What debug items bison displays during its run. */
diff --git a/src/lalr.c b/src/lalr.c
index 9f5d43f..0101149 100644
--- a/src/lalr.c
+++ b/src/lalr.c
@@ -43,9 +43,10 @@
#include "symtab.h"
goto_number *goto_map;
-static goto_number ngotos;
+goto_number ngotos;
state_number *from_state;
state_number *to_state;
+bitsetv goto_follows = NULL;
/* Linked list of goto numbers. */
typedef struct goto_list
@@ -64,17 +65,13 @@ static bitsetv LA = NULL;
size_t nLA;
-/* And for the famous F variable, which name is so descriptive that a
- comment is hardly needed. <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 c65c9b4..103a4c8 100644
--- a/src/lalr.h
+++ b/src/lalr.h
@@ -1,7 +1,7 @@
/* Compute lookahead criteria for bison,
- Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006, 2007 Free Software
- Foundation, Inc.
+ Copyright (C) 1984, 1986, 1989, 2000, 2002, 2004, 2006, 2007, 2009
+ Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -37,14 +37,30 @@
which rules need lookahead in each state, and which lookahead
tokens they accept.
- Builds:
- - #goto_map
- - #from_state
- - #to_state
+ Also builds:
+ - #goto_map
+ - #from_state
+ - #to_state
+ - #goto_follows
*/
void lalr (void);
/**
+ * Set #nLA and allocate all reduction lookahead sets. Normally invoked by
+ * #lalr.
+ */
+void initialize_LA (void);
+
+/**
+ * Build only:
+ * - #goto_map
+ * - #from_state
+ * - #to_state
+ * Normally invoked by #lalr.
+ */
+void set_goto_map (void);
+
+/**
* Update state numbers recorded in #goto_map, #from_state, and #to_state such
* that:
* - \c nstates_old is the old number of states.
@@ -62,7 +78,6 @@ void lalr_update_state_numbers (state_number old_to_new[],
Can be performed once the action tables are computed. */
void lalr_free (void);
-
typedef size_t goto_number;
# define GOTO_NUMBER_MAXIMUM ((goto_number) -1)
@@ -73,11 +88,20 @@ typedef size_t goto_number;
TO_STATE of the first of them. */
extern goto_number *goto_map;
-/** State number which a transition leads from. */
+/** The size of #from_state and #to_state. */
+extern goto_number ngotos;
+
+/** State number which a transition leads from. */
extern state_number *from_state;
/** State number it leads to. */
extern state_number *to_state;
+/** Map a state/symbol pair into its numeric representation. */
+goto_number map_goto (state_number s0, symbol_number sym);
+
+/* goto_follows[i] is the set of tokens following goto i. */
+extern bitsetv goto_follows;
+
#endif /* !LALR_H_ */
diff --git a/src/main.c b/src/main.c
index b3ef70a..6c93a4e 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,7 +1,7 @@
/* Top level entry point of Bison.
Copyright (C) 1984, 1986, 1989, 1992, 1995, 2000, 2001, 2002, 2004,
- 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+ 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -35,6 +35,7 @@
#include "getargs.h"
#include "gram.h"
#include "lalr.h"
+#include "ielr.h"
#include "muscle_tab.h"
#include "nullable.h"
#include "output.h"
@@ -102,10 +103,10 @@ main (int argc, char *argv[])
generate_states ();
timevar_pop (TV_LR0);
- /* make it deterministic. In file lalr. */
- timevar_push (TV_LALR);
- lalr ();
- timevar_pop (TV_LALR);
+ /* Make it deterministic by computing lookahead sets. Except when LALR(1) is
+ requested, split states to eliminate LR(1)-relative inadequacies. In file
+ lalr and ielr. */
+ ielr ();
/* Find and record any conflicts: places where one token of
lookahead is not enough to disambiguate the parsing. In file
diff --git a/src/reader.c b/src/reader.c
index 68e8b44..b2fdc3b 100644
--- a/src/reader.c
+++ b/src/reader.c
@@ -555,11 +555,22 @@ reader (void)
gram_scanner_initialize ();
gram_parse ();
- muscle_percent_define_default ("lr.default_rules", "all");
+ /* IELR would be a better default, but LALR is historically the default. */
+ {
+ char *lr_type;
+ muscle_percent_define_default ("lr.type", "LALR");
+ lr_type = muscle_percent_define_get ("lr.type");
+ if (0 != strcmp (lr_type, "canonical LR"))
+ muscle_percent_define_default ("lr.default_rules", "all");
+ else
+ muscle_percent_define_default ("lr.default_rules", "accepting");
+ free (lr_type);
+ }
/* Check front-end %define variable values. */
{
static char const * const values[] = {
+ "lr.type", "LALR", "IELR", "canonical LR", NULL,
"lr.default_rules", "all", "consistent", "accepting", NULL,
NULL
};
diff --git a/src/state.c b/src/state.c
index d3460c1..a0f5cdb 100644
--- a/src/state.c
+++ b/src/state.c
@@ -1,7 +1,7 @@
/* Type definitions for nondeterministic finite state machine for Bison.
- Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software
- Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free
+ Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -142,6 +142,7 @@ state_new (symbol_number accessing_symbol,
res->transitions = NULL;
res->reductions = NULL;
res->errs = NULL;
+ res->state_list = NULL;
res->consistent = 0;
res->solved_conflicts = NULL;
res->solved_conflicts_xml = NULL;
@@ -154,6 +155,32 @@ state_new (symbol_number accessing_symbol,
return res;
}
+state *
+state_new_isocore (state const *s)
+{
+ state *res;
+ size_t items_size = s->nitems * sizeof *s->items;
+
+ aver (nstates < STATE_NUMBER_MAXIMUM);
+
+ res = xmalloc (offsetof (state, items) + items_size);
+ res->number = nstates++;
+ res->accessing_symbol = s->accessing_symbol;
+ res->transitions =
+ transitions_new (s->transitions->num, s->transitions->states);
+ res->reductions = reductions_new (s->reductions->num, s->reductions->rules);
+ res->errs = NULL;
+ res->state_list = NULL;
+ res->consistent = s->consistent;
+ res->solved_conflicts = NULL;
+ res->solved_conflicts_xml = NULL;
+
+ res->nitems = s->nitems;
+ memcpy (res->items, s->items, items_size);
+
+ return res;
+}
+
/*---------.
| Free S. |
diff --git a/src/state.h b/src/state.h
index 4afc1f0..931b48f 100644
--- a/src/state.h
+++ b/src/state.h
@@ -1,7 +1,7 @@
/* Type definitions for nondeterministic finite state machine for Bison.
- Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007 Free
- Software Foundation, Inc.
+ Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2007, 2009
+ Free Software Foundation, Inc.
This file is part of Bison, the GNU Compiler Compiler.
@@ -193,6 +193,8 @@ typedef struct
| states. |
`---------*/
+struct state_list;
+
struct state
{
state_number number;
@@ -201,6 +203,11 @@ struct state
reductions *reductions;
errs *errs;
+ /* When an includer (such as ielr.c) needs to store states in a list, the
+ includer can define struct state_list as the list node structure and can
+ store in this member a reference to the node containing each state. */
+ struct state_list *state_list;
+
/* If non-zero, then no lookahead sets on reduce actions are needed to
decide what to do in state S. */
char consistent;
@@ -222,6 +229,7 @@ extern state *final_state;
/* Create a new state with ACCESSING_SYMBOL for those items. */
state *state_new (symbol_number accessing_symbol,
size_t core_size, item_number *core);
+state *state_new_isocore (state const *s);
/* Set the transitions of STATE. */
void state_transitions_set (state *s, int num, state **trans);
diff --git a/tests/existing.at b/tests/existing.at
index ba2c40c..b754f3c 100644
--- a/tests/existing.at
+++ b/tests/existing.at
@@ -1,7 +1,7 @@
# Exercising Bison on actual grammars. -*- Autotest -*-
-# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004, 2005,
-# 2007 Free Software Foundation, Inc.
+# Copyright (C) 1989, 1990, 1991, 1992, 2000, 2001, 2002, 2003, 2004,
+# 2005, 2007, 2009 Free Software Foundation, Inc.
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
@@ -17,21 +17,70 @@
# along with this program. If not, see <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
address@hidden 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 058d7c0..6642f65 100644
--- a/tests/reduce.at
+++ b/tests/reduce.at
@@ -359,6 +359,1089 @@ AT_CLEANUP
+## ----------------- ##
+## %define lr.type. ##
+## ----------------- ##
+
+# AT_TEST_LR_TYPE(DESCRIPTION,
+# DECLS, GRAMMAR, INPUT,
+# BISON-STDERR, TABLES,
+# [OTHER-CHECKS],
+# [PARSER-EXIT-VALUE],
+# [PARSER-STDOUT], [PARSER-STDERR])
+# -------------------------------------------------
+m4_define([AT_TEST_LR_TYPE],
+[
+AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1],
+ [[LALR]], [[]],
+ [$2], m4_shiftn(2, $@))
+AT_TEST_TABLES_AND_PARSE([[%define lr.type "LALR": ]$1],
+ [[LALR]], [[]],
+ [[%define lr.type "LALR"
+]$2],
+ m4_shiftn(2, $@))
+AT_TEST_TABLES_AND_PARSE([[%define lr.type "IELR": ]$1],
+ [[IELR]], [[]],
+ [[%define lr.type "IELR"
+]$2],
+ m4_shiftn(2, $@))
+AT_TEST_TABLES_AND_PARSE([[%define lr.type "canonical LR": ]$1],
+ [[canonical LR]], [[]],
+ [[%define lr.type "canonical LR"
+]$2],
+ m4_shiftn(2, $@))
+])
+
+AT_TEST_LR_TYPE([[Single State Split]],
+[[%left 'a'
+// Conflict resolution renders state 12 unreachable for canonical LR(1). We
+// keep it so that the paser table diff is easier to code.
+%define lr.keep_unreachable_states]],
+[[
+S: 'a' A 'a' /* rule 1 */
+ | 'b' A 'b' /* rule 2 */
+ | 'c' c /* rule 3 */
+ ;
+
+/* A conflict should appear after the first 'a' in rules 4 and 5 but only after
+ having shifted the first 'a' in rule 1. However, when LALR(1) merging is
+ chosen, the state containing that conflict is reused after having seen the
+ first 'b' in rule 2 and then the first 'a' in rules 4 and 5. In both cases,
+ because of the merged state, if the next token is an 'a', the %left forces a
+ reduction action with rule 5. In the latter case, only a shift is actually
+ grammatically correct. Thus, the parser would report a syntax error for the
+ grammatically correct sentence "baab" because it would encounter a syntax
+ error after that incorrect reduction.
+
+ Despite not being LALR(1), Menhir version 20070322 suffers from this problem
+ as well. It uses David Pager's weak compatibility test for merging states.
+ Bison and Menhir accept non-LR(1) grammars with conflict resolution. Pager
+ designed his algorithm only for LR(1) grammars. */
+A: 'a' 'a' /* rule 4 */
+ | 'a' /* rule 5 */
+ ;
+
+/* Rule 3, rule 6, and rule 7 ensure that Bison does not report rule 4 as
+ useless after conflict resolution. This proves that, even though LALR(1)
+ generates incorrect parser tables sometimes, Bison will not necessarily
+ produce any warning to help the user realize it. */
+c: 'a' 'b' /* rule 6 */
+ | A /* rule 7 */
+ ;
+]],
+
+dnl INPUT
+[['b', 'a', 'a', 'b']],
+
+dnl BISON-STDERR
+[],
+
+dnl TABLES
+[[state 0
+
+ 0 $accept: . S $end
+ 1 S: . 'a' A 'a'
+ 2 | . 'b' A 'b'
+ 3 | . 'c' c
+
+ 'a' shift, and go to state 1
+ 'b' shift, and go to state 2
+ 'c' shift, and go to state 3
+
+ S go to state 4
+
+
+state 1
+
+ 1 S: 'a' . A 'a'
+ 4 A: . 'a' 'a'
+ 5 | . 'a'
+
+ 'a' shift, and go to state 5
+
+ A go to state 6
+
+
+state 2
+
+ 2 S: 'b' . A 'b'
+ 4 A: . 'a' 'a'
+ 5 | . 'a'
+
+ 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[16]])[
+
+ A go to state 7
+
+
+state 3
+
+ 3 S: 'c' . c
+ 4 A: . 'a' 'a'
+ 5 | . 'a'
+ 6 c: . 'a' 'b'
+ 7 | . A
+
+ 'a' shift, and go to state 8
+
+ A go to state 9
+ c go to state 10
+
+
+state 4
+
+ 0 $accept: S . $end
+
+ $end shift, and go to state 11
+
+
+state 5
+
+ 4 A: 'a' . 'a'
+ 5 | 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 5 (A)
+
+ Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
+
+
+state 6
+
+ 1 S: 'a' A . 'a'
+
+ 'a' shift, and go to state 13
+
+
+state 7
+
+ 2 S: 'b' A . 'b'
+
+ 'b' shift, and go to state 14
+
+
+state 8
+
+ 4 A: 'a' . 'a'
+ 5 | 'a' . [$end]
+ 6 c: 'a' . 'b'
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[17]],
+ [[12]])[
+ 'b' shift, and go to state 15
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 5 (A)
+
+
+state 9
+
+ 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 7 (c)
+
+
+state 10
+
+ 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 3 (S)
+
+
+state 11
+
+ 0 $accept: S $end .
+
+ $default accept
+
+
+state 12
+
+ 4 A: 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 4 (A)
+
+
+state 13
+
+ 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 1 (S)
+
+
+state 14
+
+ 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 2 (S)
+
+
+state 15
+
+ 6 c: 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 6
(c)]AT_COND_CASE([[LALR]],
+ [[]], [[
+
+
+state 16
+
+ 4 A: 'a' . 'a'
+ 5 | 'a' . ['b']
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[18]],
+ [[12]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['b']],
+ [[$default]])[ reduce using rule 5
(A)]AT_COND_CASE([[canonical LR]], [[
+
+
+state 17
+
+ 4 A: 'a' 'a' . [$end]
+
+ $end reduce using rule 4 (A)
+
+
+state 18
+
+ 4 A: 'a' 'a' . ['b']
+
+ 'b' reduce using rule 4 (A)]])])[
+]],
+
+dnl OTHER-CHECKS
+[],
+
+dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
+[AT_COND_CASE([[LALR]], [[1]], [[0]])],
+[],
+[AT_COND_CASE([[LALR]],
+[[syntax error
+]])])
+
+AT_TEST_LR_TYPE([[Lane Split]],
+[[%left 'a'
+// Conflict resolution renders state 16 unreachable for canonical LR(1). We
+// keep it so that the paser table diff is easier to code.
+%define lr.keep_unreachable_states]],
+[[
+/* Similar to the last test case set but two states must be split. */
+S: 'a' A 'a' /* rule 1 */
+ | 'b' A 'b' /* rule 2 */
+ | 'c' c /* rule 3 */
+ ;
+
+A: 'a' 'a' 'a' /* rule 4 */
+ | 'a' 'a' /* rule 5 */
+ ;
+
+c: 'a' 'a' 'b' /* rule 6 */
+ | A /* rule 7 */
+ ;
+]],
+
+dnl INPUT
+[['b', 'a', 'a', 'a', 'b']],
+
+dnl BISON-STDERR
+[],
+
+dnl TABLES
+[[state 0
+
+ 0 $accept: . S $end
+ 1 S: . 'a' A 'a'
+ 2 | . 'b' A 'b'
+ 3 | . 'c' c
+
+ 'a' shift, and go to state 1
+ 'b' shift, and go to state 2
+ 'c' shift, and go to state 3
+
+ S go to state 4
+
+
+state 1
+
+ 1 S: 'a' . A 'a'
+ 4 A: . 'a' 'a' 'a'
+ 5 | . 'a' 'a'
+
+ 'a' shift, and go to state 5
+
+ A go to state 6
+
+
+state 2
+
+ 2 S: 'b' . A 'b'
+ 4 A: . 'a' 'a' 'a'
+ 5 | . 'a' 'a'
+
+ 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[18]])[
+
+ A go to state 7
+
+
+state 3
+
+ 3 S: 'c' . c
+ 4 A: . 'a' 'a' 'a'
+ 5 | . 'a' 'a'
+ 6 c: . 'a' 'a' 'b'
+ 7 | . A
+
+ 'a' shift, and go to state 8
+
+ A go to state 9
+ c go to state 10
+
+
+state 4
+
+ 0 $accept: S . $end
+
+ $end shift, and go to state 11
+
+
+state 5
+
+ 4 A: 'a' . 'a' 'a'
+ 5 | 'a' . 'a'
+
+ 'a' shift, and go to state 12
+
+
+state 6
+
+ 1 S: 'a' A . 'a'
+
+ 'a' shift, and go to state 13
+
+
+state 7
+
+ 2 S: 'b' A . 'b'
+
+ 'b' shift, and go to state 14
+
+
+state 8
+
+ 4 A: 'a' . 'a' 'a'
+ 5 | 'a' . 'a'
+ 6 c: 'a' . 'a' 'b'
+
+ 'a' shift, and go to state 15
+
+
+state 9
+
+ 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 7 (c)
+
+
+state 10
+
+ 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 3 (S)
+
+
+state 11
+
+ 0 $accept: S $end .
+
+ $default accept
+
+
+state 12
+
+ 4 A: 'a' 'a' . 'a'
+ 5 | 'a' 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 5 (A)
+
+ Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
+
+
+state 13
+
+ 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 1 (S)
+
+
+state 14
+
+ 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 2 (S)
+
+
+state 15
+
+ 4 A: 'a' 'a' . 'a'
+ 5 | 'a' 'a' . [$end]
+ 6 c: 'a' 'a' . 'b'
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[19]],
+ [[16]])[
+ 'b' shift, and go to state 17
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 5 (A)
+
+
+state 16
+
+ 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 4 (A)
+
+
+state 17
+
+ 6 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 6
(c)]AT_COND_CASE([[LALR]],
+ [[]], [[
+
+
+state 18
+
+ 4 A: 'a' . 'a' 'a'
+ 5 | 'a' . 'a'
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
+ [[19]])[
+
+
+state 19]AT_COND_CASE([[canonical LR]], [[
+
+ 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 4 (A)
+
+
+state 20]])[
+
+ 4 A: 'a' 'a' . 'a'
+ 5 | 'a' 'a' . ['b']
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
+ [[16]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['b']],
+ [[$default]])[ reduce using rule 5
(A)]AT_COND_CASE([[canonical LR]], [[
+
+
+state 21
+
+ 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['b']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['b']],
+ [[$default]])[ reduce using rule 4 (A)]])])[
+]],
+
+dnl OTHER-CHECKS
+[],
+
+dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
+[AT_COND_CASE([[LALR]], [[1]], [[0]])],
+[],
+[AT_COND_CASE([[LALR]],
+[[syntax error
+]])])
+
+AT_TEST_LR_TYPE([[Complex Lane Split]],
+[[%left 'a'
+// Conflict resolution renders state 16 unreachable for canonical LR(1). We
+// keep it so that the paser table diff is easier to code.
+%define lr.keep_unreachable_states]],
+[[
+/* Similar to the last test case set but forseeing the S/R conflict from the
+ first state that must be split is becoming difficult. Imagine if B were
+ even more complex. Imagine if A had other RHS's ending in other
+ nonterminals. */
+S: 'a' A 'a'
+ | 'b' A 'b'
+ | 'c' c
+ ;
+A: 'a' 'a' B
+ ;
+B: 'a'
+ | %prec 'a'
+ ;
+c: 'a' 'a' 'b'
+ | A
+ ;
+]],
+
+dnl INPUT
+[['b', 'a', 'a', 'a', 'b']],
+
+dnl BISON-STDERR
+[],
+
+dnl TABLES
+[[state 0
+
+ 0 $accept: . S $end
+ 1 S: . 'a' A 'a'
+ 2 | . 'b' A 'b'
+ 3 | . 'c' c
+
+ 'a' shift, and go to state 1
+ 'b' shift, and go to state 2
+ 'c' shift, and go to state 3
+
+ S go to state 4
+
+
+state 1
+
+ 1 S: 'a' . A 'a'
+ 4 A: . 'a' 'a' B
+
+ 'a' shift, and go to state 5
+
+ A go to state 6
+
+
+state 2
+
+ 2 S: 'b' . A 'b'
+ 4 A: . 'a' 'a' B
+
+ 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[19]])[
+
+ A go to state 7
+
+
+state 3
+
+ 3 S: 'c' . c
+ 4 A: . 'a' 'a' B
+ 7 c: . 'a' 'a' 'b'
+ 8 | . A
+
+ 'a' shift, and go to state 8
+
+ A go to state 9
+ c go to state 10
+
+
+state 4
+
+ 0 $accept: S . $end
+
+ $end shift, and go to state 11
+
+
+state 5
+
+ 4 A: 'a' . 'a' B
+
+ 'a' shift, and go to state 12
+
+
+state 6
+
+ 1 S: 'a' A . 'a'
+
+ 'a' shift, and go to state 13
+
+
+state 7
+
+ 2 S: 'b' A . 'b'
+
+ 'b' shift, and go to state 14
+
+
+state 8
+
+ 4 A: 'a' . 'a' B
+ 7 c: 'a' . 'a' 'b'
+
+ 'a' shift, and go to state 15
+
+
+state 9
+
+ 8 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 8 (c)
+
+
+state 10
+
+ 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 3 (S)
+
+
+state 11
+
+ 0 $accept: S $end .
+
+ $default accept
+
+
+state 12
+
+ 4 A: 'a' 'a' . B
+ 5 B: . 'a'
+ 6 | . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 6 (B)
+
+ B go to state 17
+
+ Conflict between rule 6 and token 'a' resolved as reduce (%left 'a').
+
+
+state 13
+
+ 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 1 (S)
+
+
+state 14
+
+ 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 2 (S)
+
+
+state 15
+
+ 4 A: 'a' 'a' . B
+ 5 B: . 'a'
+ 6 | . [$end]
+ 7 c: 'a' 'a' . 'b'
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
+ [[16]])[
+ 'b' shift, and go to state 18
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 6 (B)
+
+ B go to state ]AT_COND_CASE([[canonical LR]], [[21]], [[17]])[
+
+
+state 16
+
+ 5 B: 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 5 (B)
+
+
+state 17
+
+ 4 A: 'a' 'a' B .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['a']],
+ [[$default]])[ reduce using rule 4 (A)
+
+
+state 18
+
+ 7 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 7
(c)]AT_COND_CASE([[LALR]], [], [[
+
+
+state 19
+
+ 4 A: 'a' . 'a' B
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[22]],
+ [[20]])[
+
+
+state 20]AT_COND_CASE([[canonical LR]], [[
+
+ 5 B: 'a' . [$end]
+
+ $end reduce using rule 5 (B)
+
+
+state 21
+
+ 4 A: 'a' 'a' B . [$end]
+
+ $end reduce using rule 4 (A)
+
+
+state 22]])[
+
+ 4 A: 'a' 'a' . B
+ 5 B: . 'a'
+ 6 | . ['b']
+
+ 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[23]],
+ [[16]])[
+
+ ]AT_COND_CASE([[canonical LR]], [['b']],
+ [[$default]])[ reduce using rule 6 (B)
+
+ B go to state ]AT_COND_CASE([[canonical LR]], [[24
+
+
+state 23
+
+ 5 B: 'a' . ['b']
+
+ 'b' reduce using rule 5 (B)
+
+
+state 24
+
+ 4 A: 'a' 'a' B . ['b']
+
+ 'b' reduce using rule 4 (A)]], [[17]])])[
+]],
+
+dnl OTHER-CHECKS
+[],
+
+dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
+[AT_COND_CASE([[LALR]], [[1]], [[0]])],
+[],
+[AT_COND_CASE([[LALR]],
+[[syntax error
+]])])
+
+AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]],
+[[%define lr.keep_unreachable_states]],
+[[
+/* The partial state chart diagram below is for LALR(1). State 0 is the start
+ state. States are iterated for successor construction in numerical order.
+ Transitions are downwards.
+
+ State 13 has a R/R conflict that cannot be predicted by Bison's LR(1)
+ algorithm using annotations alone. That is, when state 11's successor on
+ 'd' is merged with state 5 (which is originally just state 1's successor on
+ 'd'), state 5's successor on 'e' must then be changed because the resulting
+ lookaheads that propagate to it now make it incompatible with state 8's
+ successor on 'e'. In other words, state 13 must be split to avoid the
+ conflict.
+
+ 0
+ / | \
+ a / c| \ b
+ 1 3 2
+ | | |
+ d| |c | d
+ | 11 |
+ | | |
+ \ /d |
+ 5 8
+ \ |
+ e \ / e
+ 13
+ R/R
+
+ This grammar is designed carefully to make sure that, despite Bison's LR(1)
+ algorithm's bread-first iteration of transitions to reconstruct states,
+ state 11's successors are constructed after state 5's and state 8's.
+ Otherwise (for example, if you remove the first 'c' in each of rules 6 and
+ 7), state 5's successor on 'e' would never be merged with state 8's, so the
+ split of the resulting state 13 would never need to be performed. */
+S: 'a' A 'f'
+ | 'a' B
+ | 'b' A 'f'
+ | 'b' B 'g'
+ | 'b' 'd'
+ | 'c' 'c' A 'g'
+ | 'c' 'c' B
+ ;
+A: 'd' 'e' ;
+B: 'd' 'e' ;
+]],
+
+dnl INPUT
+[['b', 'd', 'e', 'g']],
+
+dnl BISON-STDERR
+[AT_COND_CASE([[LALR]],
+[[input.y: conflicts: 1 reduce/reduce
+]], [])],
+
+dnl TABLES
+[[state 0
+
+ 0 $accept: . S $end
+ 1 S: . 'a' A 'f'
+ 2 | . 'a' B
+ 3 | . 'b' A 'f'
+ 4 | . 'b' B 'g'
+ 5 | . 'b' 'd'
+ 6 | . 'c' 'c' A 'g'
+ 7 | . 'c' 'c' B
+
+ 'a' shift, and go to state 1
+ 'b' shift, and go to state 2
+ 'c' shift, and go to state 3
+
+ S go to state 4
+
+
+state 1
+
+ 1 S: 'a' . A 'f'
+ 2 | 'a' . B
+ 8 A: . 'd' 'e'
+ 9 B: . 'd' 'e'
+
+ 'd' shift, and go to state 5
+
+ A go to state 6
+ B go to state 7
+
+
+state 2
+
+ 3 S: 'b' . A 'f'
+ 4 | 'b' . B 'g'
+ 5 | 'b' . 'd'
+ 8 A: . 'd' 'e'
+ 9 B: . 'd' 'e'
+
+ 'd' shift, and go to state 8
+
+ A go to state 9
+ B go to state 10
+
+
+state 3
+
+ 6 S: 'c' . 'c' A 'g'
+ 7 | 'c' . 'c' B
+
+ 'c' shift, and go to state 11
+
+
+state 4
+
+ 0 $accept: S . $end
+
+ $end shift, and go to state 12
+
+
+state 5
+
+ 8 A: 'd' . 'e'
+ 9 B: 'd' . 'e'
+
+ 'e' shift, and go to state ]AT_COND_CASE([[LALR]], [[13]],
+ [[canonical LR]], [[13]],
+ [[20]])[
+
+
+state 6
+
+ 1 S: 'a' A . 'f'
+
+ 'f' shift, and go to state 14
+
+
+state 7
+
+ 2 S: 'a' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 2 (S)
+
+
+state 8
+
+ 5 S: 'b' 'd' . [$end]
+ 8 A: 'd' . 'e'
+ 9 B: 'd' . 'e'
+
+ 'e' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
+ [[13]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 5 (S)
+
+
+state 9
+
+ 3 S: 'b' A . 'f'
+
+ 'f' shift, and go to state 15
+
+
+state 10
+
+ 4 S: 'b' B . 'g'
+
+ 'g' shift, and go to state 16
+
+
+state 11
+
+ 6 S: 'c' 'c' . A 'g'
+ 7 | 'c' 'c' . B
+ 8 A: . 'd' 'e'
+ 9 B: . 'd' 'e'
+
+ 'd' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
+ [[5]])[
+
+ A go to state 17
+ B go to state 18
+
+
+state 12
+
+ 0 $accept: S $end .
+
+ $default accept]AT_COND_CASE([[LALR]], [[
+
+
+state 13
+
+ 8 A: 'd' 'e' . ['f', 'g']
+ 9 B: 'd' 'e' . [$end, 'g']
+
+ $end reduce using rule 9 (B)
+ 'g' reduce using rule 8 (A)
+ 'g' [reduce using rule 9 (B)]
+ $default reduce using rule 8 (A)]], [[
+
+
+state 13
+
+ 8 A: 'd' 'e' . ['f']
+ 9 B: 'd' 'e' . ]AT_COND_CASE([[canonical LR]], [[[$end]]], [[['g']]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [['g' ]])[ reduce using rule 9 (B)
+ ]AT_COND_CASE([[canonical LR]], [['f' ]],
+ [[$default]])[ reduce using rule 8 (A)]])[
+
+
+state 14
+
+ 1 S: 'a' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 1 (S)
+
+
+state 15
+
+ 3 S: 'b' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 3 (S)
+
+
+state 16
+
+ 4 S: 'b' B 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 4 (S)
+
+
+state 17
+
+ 6 S: 'c' 'c' A . 'g'
+
+ 'g' shift, and go to state 19
+
+
+state 18
+
+ 7 S: 'c' 'c' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 7 (S)
+
+
+state 19
+
+ 6 S: 'c' 'c' A 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
+
+ ]AT_COND_CASE([[canonical LR]], [[$end]],
+ [[$default]])[ reduce using rule 6
(S)]AT_COND_CASE([[LALR]],
+ [[]], [[
+
+
+state 20]AT_COND_CASE([[canonical LR]], [[
+
+ 8 A: 'd' 'e' . ['f']
+ 9 B: 'd' 'e' . ['g']
+
+ 'f' reduce using rule 8 (A)
+ 'g' reduce using rule 9 (B)
+
+
+state 21
+
+ 8 A: 'd' . 'e'
+ 9 B: 'd' . 'e'
+
+ 'e' shift, and go to state 22
+
+
+state 22
+
+ 8 A: 'd' 'e' . ['g']
+ 9 B: 'd' 'e' . [$end]
+
+ $end reduce using rule 9 (B)
+ 'g' reduce using rule 8 (A)]], [[
+
+ 8 A: 'd' 'e' . ['f', 'g']
+ 9 B: 'd' 'e' . [$end]
+
+ $end reduce using rule 9 (B)
+ $default reduce using rule 8 (A)]])])[
+]],
+
+dnl OTHER-CHECKS
+[],
+
+dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
+[AT_COND_CASE([[LALR]], [[1]], [[0]])],
+[],
+[AT_COND_CASE([[LALR]],
+[[syntax error
+]])])
+
+
+
## -------------------------- ##
## %define lr.default_rules. ##
## -------------------------- ##
--
1.5.4.3
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [PATCH] Finish implementing %define lr.type.,
Joel E. Denny <=