[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: GLR Default reductions
|
From: |
Akim Demaille |
|
Subject: |
Re: GLR Default reductions |
|
Date: |
13 Oct 2002 16:17:39 +0200 |
|
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Honest Recruiter) |
>>>>> "Akim" == Akim Demaille <address@hidden> writes:
Akim> Hi Paul,
Akim> I'm afraid we _have_ to return to this debate about default
Akim> reduction. A student of mine reported the following problem:
Akim> the simple calculator example exhibits a problem in the GLR
Akim> parsers.
OK, I have it. It turns out to be merely an YYPACT_NINF were
YYTABLE_NINF was expected. But actually, a mere replacement was wrong
too: the code was matching a value from yypact against YYTABLE_NINF,
which is wrong. I finally decided for the following patch, and back
ported it to yacc.c.
Index: ChangeLog
from Akim Demaille <address@hidden>
GLR parsers sometimes raise parse errors instead of performing the
default reduction.
Reported by Charles-Henry de Boysson.
* tests/calc.at (_AT_CHECK_CALC, _AT_CHECK_CALC_ERROR): Don't
check the length of the traces when %glr.
(_AT_CHECK_CALC_ERROR): Also skip `^Stack' lines, coming from
GLR's traces.
(AT_CHECK_CALC_LALR, AT_CHECK_CALC_GLR): New.
Test GLR parsers.
* data/glr.c (YYLEFTMOST_STATE): Fix its value.
(yyltype): Remove the yy prefix from the member names.
(yytable): Complete its comment.
(yygetLRActions): Map error action number from YYTABLE from
YYTABLE_NINF to 0.
(yyisErrorAction): No longer compare YYACTION to YYPACT_NINF
(which was a bug: it should have been YYTABEL_NINF, and yet it was
not satisfying as we could compare an YYACTION computed from
YYDEFACT to YYTABLE_NINF although they are unrelated): 0 is the
only value for error actions.
(yyreportParseError): In verbose parse error messages, don't issue
`error' in the list of expected tokens.
* data/yacc.c (yyparse) <yybackup>: Rewrite the decoding of the
next action to perform to match glr.c's decoding.
(yytable): Complete its comment.
Index: NEWS
--- NEWS Sun, 13 Oct 2002 10:01:29 +0200 akim
+++ NEWS Sun, 13 Oct 2002 16:00:14 +0200 akim
@@ -7,6 +7,13 @@
* Indonesian translation thanks to Tedi Heriyanto.
+* GLR parsers
+ Fix spurious parse errors.
+
+* Pure parsers
+ Some people redefine yyerror to steal yyparse' private variables.
+ Reenable this trick until an official feature replaces it.
+
Changes in version 1.50, 2002-10-04:
* GLR parsing
Index: THANKS
--- THANKS Sun, 13 Oct 2002 10:01:29 +0200 akim
+++ THANKS Sun, 13 Oct 2002 15:56:43 +0200 akim
@@ -1,62 +1,63 @@
Bison was originally written by Robert Corbett. It would not be what
it is today without the invaluable help of these people:
-Airy Andre address@hidden
-Akim Demaille address@hidden
-Albert Chin-A-Young address@hidden
-Alexander Belopolsky address@hidden
-Andreas Schwab address@hidden
-Arnold Robbins address@hidden
-Art Haas address@hidden
-Benoit Perrot address@hidden
-Bruce Lilly address@hidden
-Cris Bailiff address@hidden
-Cris van Pelt address@hidden
-Daniel Hagerty address@hidden
-David J. MacKenzie address@hidden
-Dick Streefland address@hidden
-Enrico Scholz address@hidden
-Evgeny Stambulchik address@hidden
-Fabrice Bauzac address@hidden
-Florian Krohm address@hidden
-H. Merijn Brand address@hidden
-Hans Aberg address@hidden
-Jan Nieuwenhuizen address@hidden
-Jesse Thilo address@hidden
-Jim Meyering address@hidden
-Juan Manuel Guerrero address@hidden
-Kees Zeelenberg address@hidden
-Keith Browne address@hidden
-Laurent Mascherpa address@hidden
-Magnus Fromreide address@hidden
-Marc Autret address@hidden
-Martin Mokrejs address@hidden
-Matt Kraai address@hidden
-Michael Hayes address@hidden
-Mike Castle address@hidden
-Neil Booth address@hidden
-Nelson H. F. Beebe address@hidden
-Nicolas Burrus address@hidden
-Nicolas Tisserand address@hidden
-Noah Friedman address@hidden
-Pascal Bart address@hidden
-Paul Eggert address@hidden
-Paul Hilfinger address@hidden
-Per Allansson address@hidden
-Peter Hámorský address@hidden
-Piotr Gackiewicz address@hidden
-R Blake address@hidden
-Raja R Harinath address@hidden
-Richard Stallman address@hidden
-Robert Anisko address@hidden
-Shura address@hidden
-Tim Josling address@hidden
-Tom Lane address@hidden
-Tom Tromey address@hidden
-Wayne Green address@hidden
-Wolfram Wagner address@hidden
-Wwp address@hidden
-Zack Weinberg address@hidden
+Airy Andre address@hidden
+Akim Demaille address@hidden
+Albert Chin-A-Young address@hidden
+Alexander Belopolsky address@hidden
+Andreas Schwab address@hidden
+Arnold Robbins address@hidden
+Art Haas address@hidden
+Benoit Perrot address@hidden
+Bruce Lilly address@hidden
+Charles-Henri de Boysson address@hidden
+Cris Bailiff address@hidden
+Cris van Pelt address@hidden
+Daniel Hagerty address@hidden
+David J. MacKenzie address@hidden
+Dick Streefland address@hidden
+Enrico Scholz address@hidden
+Evgeny Stambulchik address@hidden
+Fabrice Bauzac address@hidden
+Florian Krohm address@hidden
+H. Merijn Brand address@hidden
+Hans Aberg address@hidden
+Jan Nieuwenhuizen address@hidden
+Jesse Thilo address@hidden
+Jim Meyering address@hidden
+Juan Manuel Guerrero address@hidden
+Kees Zeelenberg address@hidden
+Keith Browne address@hidden
+Laurent Mascherpa address@hidden
+Magnus Fromreide address@hidden
+Marc Autret address@hidden
+Martin Mokrejs address@hidden
+Matt Kraai address@hidden
+Michael Hayes address@hidden
+Mike Castle address@hidden
+Neil Booth address@hidden
+Nelson H. F. Beebe address@hidden
+Nicolas Burrus address@hidden
+Nicolas Tisserand address@hidden
+Noah Friedman address@hidden
+Pascal Bart address@hidden
+Paul Eggert address@hidden
+Paul Hilfinger address@hidden
+Per Allansson address@hidden
+Peter Hámorský address@hidden
+Piotr Gackiewicz address@hidden
+R Blake address@hidden
+Raja R Harinath address@hidden
+Richard Stallman address@hidden
+Robert Anisko address@hidden
+Shura address@hidden
+Tim Josling address@hidden
+Tom Lane address@hidden
+Tom Tromey address@hidden
+Wayne Green address@hidden
+Wolfram Wagner address@hidden
+Wwp address@hidden
+Zack Weinberg address@hidden
Many people are not named here because we lost track of them. We
thank them! Please, help us keeping this list up to date.
Index: data/yacc.c
--- data/yacc.c Sun, 13 Oct 2002 10:01:29 +0200 akim
+++ data/yacc.c Sun, 13 Oct 2002 15:56:43 +0200 akim
@@ -414,7 +414,8 @@ m4_define([b4_symbol_actions],
/* YYTABLE[[YYPACT[STATE-NUM]]]. What to do in state STATE-NUM. If
positive, shift that token. If negative, reduce the rule which
- number is the opposite. If zero, do what YYDEFACT says. */
+ number is the opposite. If zero, do what YYDEFACT says.
+ If YYTABLE_NINF, parse error. */
#define YYTABLE_NINF b4_table_ninf
static const b4_int_type_for([b4_table]) yytable[[]] =
{
@@ -917,23 +918,22 @@ yybackup:
YYDPRINTF ((stderr, "\n"));
}
+ /* Set YYN to the action to take in STATE on seeing token YYCHAR1.
+ Result YYN means
+ - YYN < 0: Reduce on rule -YYN.
+ - YYN = 0: Error.
+ - YYN > 0: Shift to state YYN. */
yyn += yychar1;
if (yyn < 0 || YYLAST < yyn || yycheck[yyn] != yychar1)
- goto yydefault;
-
- yyn = yytable[yyn];
-
- /* yyn is what to do for this token type in this state.
- Negative => reduce, -yyn is rule number.
- Positive => shift, yyn is new state.
- New state is final state => don't bother to shift,
- just return success.
- 0, or most negative number => error. */
+ /* Defaulted action (reduction). */
+ yyn = -yydefact[yystate];
+ else if (yytable[yyn] != YYTABLE_NINF)
+ yyn = yytable[yyn];
+ else
+ yyn = 0;
if (yyn < 0)
{
- if (yyn == YYTABLE_NINF)
- goto yyerrlab;
yyn = -yyn;
goto yyreduce;
}
Index: data/glr.c
--- data/glr.c Sun, 13 Oct 2002 10:01:29 +0200 akim
+++ data/glr.c Sun, 13 Oct 2002 16:01:41 +0200 akim
@@ -169,10 +169,10 @@ m4_define_default([b4_header_guard],
typedef struct yyltype
{
]b4_location_if([
- int yyfirst_line;
- int yyfirst_column;
- int yylast_line;
- int yylast_column;])[
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;])[
} yyltype;
# define YYLTYPE ]b4_ltype[
# define YYLTYPE_IS_TRIVIAL 1
@@ -333,7 +333,8 @@ m4_define_default([b4_header_guard],
/* YYTABLE[YYPACT[STATE-NUM]]. What to do in state STATE-NUM. If
positive, shift that token. If negative, reduce the rule which
- number is the opposite. If zero, do what YYDEFACT says. */
+ number is the opposite. If zero, do what YYDEFACT says.
+ If YYTABLE_NINF, parse error. */
#define YYTABLE_NINF ]b4_table_ninf[
static const ]b4_int_type_for([b4_table])[ yytable[] =
{
@@ -396,10 +397,10 @@ m4_define_default([b4_header_guard],
#ifndef YYLLOC_DEFAULT
# define YYLLOC_DEFAULT(yyCurrent, yyRhs, YYN) \
- yyCurrent.yyfirst_line = YYRHSLOC(yyRhs,1).yyfirst_line; \
- yyCurrent.yyfirst_column = YYRHSLOC(yyRhs,1).yyfirst_column; \
- yyCurrent.yylast_line = YYRHSLOC(yyRhs,YYN).yylast_line; \
- yyCurrent.yylast_column = YYRHSLOC(yyRhs,YYN).yylast_column;
+ yyCurrent.first_line = YYRHSLOC(yyRhs,1).first_line; \
+ yyCurrent.first_column = YYRHSLOC(yyRhs,1).first_column; \
+ yyCurrent.last_line = YYRHSLOC(yyRhs,YYN).last_line; \
+ yyCurrent.last_column = YYRHSLOC(yyRhs,YYN).last_column;
#endif
/* YYLEX -- calling `yylex' with the right arguments. */
@@ -705,16 +706,21 @@ m4_define_default([b4_header_guard],
int* yyaction, const short** yyconflicts)
{
int yyindex = yypact[yystate] + yytoken;
- if (yyindex < 0 || yyindex > YYLAST || yycheck[yyindex] != yytoken)
+ if (yyindex < 0 || YYLAST < yyindex || yycheck[yyindex] != yytoken)
{
*yyaction = -yydefact[yystate];
*yyconflicts = yyconfl;
}
- else
+ else if (yytable[yyindex] != YYTABLE_NINF)
{
*yyaction = yytable[yyindex];
*yyconflicts = yyconfl + yyconflp[yyindex];
}
+ else
+ {
+ *yyaction = 0;
+ *yyconflicts = yyconfl + yyconflp[yyindex];
+ }
}
static inline yyStateNum
@@ -722,7 +728,7 @@ m4_define_default([b4_header_guard],
{
int yyr;
yyr = yypgoto[yylhs - YYNTOKENS] + yystate;
- if (yyr >= 0 && yyr <= YYLAST && yycheck[yyr] == yystate)
+ if (0 <= yyr && yyr <= YYLAST && yycheck[yyr] == yystate)
return yytable[yyr];
else
return yydefgoto[yylhs - YYNTOKENS];
@@ -737,7 +743,7 @@ m4_define_default([b4_header_guard],
static inline bool
yyisErrorAction (int yyaction)
{
- return yyaction == 0 || yyaction == YYPACT_NINF;
+ return yyaction == 0;
}
/* GLRStates */
@@ -1256,7 +1262,7 @@ m4_define_default([b4_header_guard],
}
#if YYDEBUG
-static yyGLRState YYLEFTMOST_STATE = { 0, NULL, -1, 0, { NULL } };
+static yyGLRState YYLEFTMOST_STATE = { 0, 0, -1, NULL, 0, { NULL } };
static void yyreportTree (yySemanticOption* yyx, int yyindent)
{
@@ -1524,7 +1530,7 @@ m4_define_default([b4_header_guard],
{
yyprefix = ", expecting ";
for (yyx = yyn < 0 ? -yyn : 0; yyx < yytname_size; yyx += 1)
- if (yycheck[yyx + yyn] == yyx)
+ if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR)
{
yyp += sprintf (yyp, "%s%s", yyprefix, yytokenName (yyx));
yyprefix = " or ";
@@ -1540,13 +1546,9 @@ m4_define_default([b4_header_guard],
}
}
-/* Recover from a syntax error on STACK, assuming that TOKENP,
+/* Recover from a syntax error on YYSTACK, assuming that YYTOKENP,
YYLVALP, and YYLLOCP point to the syntactic category, semantic
- value, and location of the lookahead.
- NOTE: This uses the panic-mode recovery algorithm described in the
- Bison documentation, which differs from what is in bison.simple.
- Specifically, this routine performs no reductions before shifting
- the error token. */
+ value, and location of the lookahead. */
static void
yyrecoverParseError (yyGLRStack* yystack, YYSTYPE* yylvalp, YYLTYPE* yyllocp)
{
@@ -1855,10 +1857,10 @@ m4_define_default([b4_header_guard],
[#ifndef YYLTYPE
typedef struct yyltype
{
- int yyfirst_line;
- int yyfirst_column;
- int yylast_line;
- int yylast_column;
+ int first_line;
+ int first_column;
+ int last_line;
+ int last_column;
} yyltype;
# define YYLTYPE yyltype
#endif
Index: tests/calc.at
--- tests/calc.at Tue, 30 Jul 2002 13:27:31 +0200 akim
+++ tests/calc.at Sun, 13 Oct 2002 16:11:12 +0200 akim
@@ -16,8 +16,6 @@
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
# 02111-1307, USA.
-AT_BANNER([[Simple Calculator.]])
-
## ---------------------------------------------------- ##
## Compile the grammar described in the documentation. ##
## ---------------------------------------------------- ##
@@ -275,8 +273,8 @@ exp:
# Produce `calc.y'.
m4_define([AT_DATA_CALC_Y],
[_AT_DATA_CALC_Y($[1], $[2], $[3],
- [m4_bmatch([$1], [--yyerror-verbose],
- [[%error-verbose]])])])
+ [m4_bpatsubst([$1], [--[^ ]*])])
+])
@@ -284,17 +282,22 @@ m4_define([AT_DATA_CALC_Y],
# ------------------------------------------------------------
# Run `calc' on INPUT and expect no STDOUT nor STDERR.
#
-# If BISON-OPTIONS contains `--debug', then NUM-STDERR-LINES is the number
-# of expected lines on stderr.
+# If BISON-OPTIONS contains `%debug' but not `%glr-parser', then
+# NUM-STDERR-LINES is the number of expected lines on stderr.
+#
+# We don't count GLR's traces yet, since its traces are somewhat
+# different from LALR's.
m4_define([_AT_CHECK_CALC],
[AT_DATA([[input]],
[[$2
]])
-AT_PARSER_CHECK([./calc input], 0, [], [stderr])dnl
-AT_CHECK([wc -l <stderr | sed 's/[[^0-9]]//g'], 0,
- [m4_bmatch([$1], [--debug],
- [$3], [0])
-])
+AT_PARSER_CHECK([./calc input], 0, [], [stderr])
+m4_bmatch([$1],
+ [%debug.*%glr\|%glr.*%debug],
+ [],
+ [%debug],
+ [AT_CHECK([wc -l <stderr | sed 's/[[^0-9]]//g'], 0, [$3
+])])
])
@@ -309,12 +312,12 @@ m4_define([_AT_CHECK_CALC],
# If BISON-OPTIONS contains `--location', then make sure the ERROR-LOCATION
# is correctly output on stderr.
#
-# If BISON-OPTIONS contains `--yyerror-verbose', then make sure the
+# If BISON-OPTIONS contains `%error-verbose', then make sure the
# IF-YYERROR-VERBOSE message is properly output after `parse error, '
# on STDERR.
#
-# If BISON-OPTIONS contains `--debug', then NUM-STDERR-LINES is the number
-# of expected lines on stderr.
+# If BISON-OPTIONS contains `%debug' but not `%glr', then NUM-STDERR-LINES
+# is the number of expected lines on stderr.
m4_define([_AT_CHECK_CALC_ERROR],
[m4_bmatch([$2], [^/],
[AT_PARSER_CHECK([./calc $2], 0, [], [stderr])],
@@ -322,9 +325,11 @@ m4_define([_AT_CHECK_CALC_ERROR],
[[$2
]])
AT_PARSER_CHECK([./calc input], 0, [], [stderr])])
-
-m4_bmatch([$1], [--debug],
-[AT_CHECK([wc -l <stderr | sed 's/[[^0-9]]//g'], 0, [$3
+m4_bmatch([$1],
+ [%debug.*%glr\|%glr.*%debug],
+ [],
+ [%debug],
+ [AT_CHECK([wc -l <stderr | sed 's/[[^0-9]]//g'], 0, [$3
])])
# Normalize the observed and expected error messages, depending upon the
@@ -332,6 +337,7 @@ m4_define([_AT_CHECK_CALC_ERROR],
# 1. Remove the traces from observed.
sed '/^Starting/d
/^Entering/d
+/^Stack/d
/^Reading/d
/^Reducing/d
/^Shifting/d
@@ -350,7 +356,7 @@ m4_define([_AT_CHECK_CALC_ERROR],
[[sed 's/^[-0-9.]*: //' expout >at-expout
mv at-expout expout]])
# 4. If error-verbose is not used, strip the`, unexpected....' part.
-m4_bmatch([$1], [--yyerror-verbose], [],
+m4_bmatch([$1], [%error-verbose], [],
[[sed 's/parse error, .*$/parse error/' expout >at-expout
mv at-expout expout]])
# 5. Check
@@ -358,8 +364,8 @@ m4_define([_AT_CHECK_CALC_ERROR],
])
-# AT_CHECK_CALC([BISON-OPTIONS], [PARSER-EXPECTED-STDERR])
-# --------------------------------------------------------
+# AT_CHECK_CALC([BISON-OPTIONS])
+# ------------------------------
# Start a testing chunk which compiles `calc' grammar with
# BISON-OPTIONS, and performs several tests over the parser.
m4_define([AT_CHECK_CALC],
@@ -369,7 +375,7 @@ m4_define([AT_CHECK_CALC],
AT_DATA_CALC_Y([$1])
# Specify the output files to avoid problems on different file systems.
-AT_CHECK([bison calc.y -o calc.c m4_bpatsubst([$1], [--yyerror-verbose])],
+AT_CHECK([bison calc.y -o calc.c m4_bpatsubst([$1], [%[^ ]*])],
[0], [], [])
AT_COMPILE([calc])
@@ -427,22 +433,62 @@ calc: error: 0 != 1])
-# ------------------ #
-# Test the parsers. #
-# ------------------ #
+# ------------------------ #
+# Simple LALR Calculator. #
+# ------------------------ #
+
+AT_BANNER([[Simple LALR Calculator.]])
+
+# AT_CHECK_CALC_LALR([BISON-OPTIONS])
+# -----------------------------------
+# Start a testing chunk which compiles `calc' grammar with
+# BISON-OPTIONS, and performs several tests over the parser.
+m4_define([AT_CHECK_CALC_LALR],
+[AT_CHECK_CALC($@)])
+
+AT_CHECK_CALC_LALR()
+
+AT_CHECK_CALC_LALR([--defines])
+AT_CHECK_CALC_LALR([--locations])
+AT_CHECK_CALC_LALR([--name-prefix=calc])
+AT_CHECK_CALC_LALR([--verbose])
+AT_CHECK_CALC_LALR([--yacc])
+AT_CHECK_CALC_LALR([%error-verbose])
+
+AT_CHECK_CALC_LALR([%error-verbose --locations])
+
+AT_CHECK_CALC_LALR([%error-verbose --defines --locations --name-prefix=calc
--verbose --yacc])
+
+AT_CHECK_CALC_LALR([%debug])
+AT_CHECK_CALC_LALR([%error-verbose %debug --defines --locations
--name-prefix=calc --verbose --yacc])
+
+
+# ----------------------- #
+# Simple GLR Calculator. #
+# ----------------------- #
+
+AT_BANNER([[Simple GLR Calculator.]])
+
+# AT_CHECK_CALC_GLR([BISON-OPTIONS])
+# ----------------------------------
+# Start a testing chunk which compiles `calc' grammar with
+# BISON-OPTIONS and %glr-parser, and performs several tests over the parser.
+m4_define([AT_CHECK_CALC_GLR],
+[AT_CHECK_CALC([%glr_parser] $@)])
+
-AT_CHECK_CALC()
+AT_CHECK_CALC_GLR()
-AT_CHECK_CALC([--defines])
-AT_CHECK_CALC([--locations])
-AT_CHECK_CALC([--name-prefix=calc])
-AT_CHECK_CALC([--verbose])
-AT_CHECK_CALC([--yacc])
-AT_CHECK_CALC([--yyerror-verbose])
+AT_CHECK_CALC_GLR([--defines])
+AT_CHECK_CALC_GLR([--locations])
+AT_CHECK_CALC_GLR([--name-prefix=calc])
+AT_CHECK_CALC_GLR([--verbose])
+AT_CHECK_CALC_GLR([--yacc])
+AT_CHECK_CALC_GLR([%error-verbose])
-AT_CHECK_CALC([--locations --yyerror-verbose])
+AT_CHECK_CALC_GLR([%error-verbose --locations])
-AT_CHECK_CALC([--defines --locations --name-prefix=calc --verbose --yacc
--yyerror-verbose])
+AT_CHECK_CALC_GLR([%error-verbose --defines --locations --name-prefix=calc
--verbose --yacc])
-AT_CHECK_CALC([--debug])
-AT_CHECK_CALC([--debug --defines --locations --name-prefix=calc --verbose
--yacc --yyerror-verbose])
+AT_CHECK_CALC_GLR([%debug])
+AT_CHECK_CALC_GLR([%error-verbose %debug --defines --locations
--name-prefix=calc --verbose --yacc])