From f50adbbdb02d476286814f538c2f0e20caa15199 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 13 Oct 2002 14:25:14 +0000 Subject: [PATCH] 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) : Rewrite the decoding of the next action to perform to match glr.c's decoding. (yytable): Complete its comment. --- ChangeLog | 28 ++++++++++++ NEWS | 7 +++ THANKS | 113 ++++++++++++++++++++++++------------------------ data/glr.c | 52 +++++++++++----------- data/yacc.c | 26 +++++------ tests/calc.at | 116 +++++++++++++++++++++++++++++++++++--------------- 6 files changed, 213 insertions(+), 129 deletions(-) diff --git a/ChangeLog b/ChangeLog index cf9d75a3..aadd0970 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,31 @@ +2002-10-13 Akim Demaille + + 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) : Rewrite the decoding of the + next action to perform to match glr.c's decoding. + (yytable): Complete its comment. + 2002-10-13 Paul Eggert Fix problem reported by Henrik Grubbstroem in diff --git a/NEWS b/NEWS index 699fe44c..183b129f 100644 --- a/NEWS +++ b/NEWS @@ -7,6 +7,13 @@ Changes in version 1.50a: * 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 diff --git a/THANKS b/THANKS index 38e7e222..85c6a7d8 100644 --- a/THANKS +++ b/THANKS @@ -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 Airy.Andre@edf.fr -Akim Demaille akim@freefriends.org -Albert Chin-A-Young china@thewrittenword.com -Alexander Belopolsky alexb@rentec.com -Andreas Schwab schwab@suse.de -Arnold Robbins arnold@skeeve.com -Art Haas ahaas@neosoft.com -Benoit Perrot benoit.perrot@epita.fr -Bruce Lilly blilly@erols.com -Cris Bailiff c.bailiff+bison@awayweb.com -Cris van Pelt cris@amf03054.office.wxs.nl -Daniel Hagerty hag@gnu.org -David J. MacKenzie djm@gnu.org -Dick Streefland dick.streefland@altium.nl -Enrico Scholz enrico.scholz@informatik.tu-chemnitz.de -Evgeny Stambulchik fnevgeny@plasma-gate.weizmann.ac.il -Fabrice Bauzac noon@cote-dazur.com -Florian Krohm florian@edamail.fishkill.ibm.com -H. Merijn Brand h.m.brand@hccnet.nl -Hans Aberg haberg@matematik.su.se -Jan Nieuwenhuizen janneke@gnu.org -Jesse Thilo jthilo@gnu.org -Jim Meyering jim@meyering.net -Juan Manuel Guerrero ST001906@HRZ1.HRZ.TU-Darmstadt.De -Kees Zeelenberg kzlg@users.sourceforge.net -Keith Browne kbrowne@legato.com -Laurent Mascherpa laurent.mascherpa@epita.fr -Magnus Fromreide magfr@lysator.liu.se -Marc Autret autret_m@epita.fr -Martin Mokrejs mmokrejs@natur.cuni.cz -Matt Kraai kraai@alumni.cmu.edu -Michael Hayes m.hayes@elec.canterbury.ac.nz -Mike Castle dalgoda@ix.netcom.com -Neil Booth NeilB@earthling.net -Nelson H. F. Beebe beebe@math.utah.edu -Nicolas Burrus nicolas.burrus@epita.fr -Nicolas Tisserand nicolas.tisserand@epita.fr -Noah Friedman friedman@gnu.org -Pascal Bart pascal.bart@epita.fr -Paul Eggert eggert@twinsun.com -Paul Hilfinger Hilfinger@CS.Berkeley.EDU -Per Allansson per@appgate.com -Peter Hámorský hamo@upjs.sk -Piotr Gackiewicz gacek@intertel.com.pl -R Blake blakers@mac.com -Raja R Harinath harinath@cs.umn.edu -Richard Stallman rms@gnu.org -Robert Anisko anisko_r@epita.fr -Shura debil_urod@ngs.ru -Tim Josling tej@melbpc.org.au -Tom Lane tgl@sss.pgh.pa.us -Tom Tromey tromey@cygnus.com -Wayne Green wayne@infosavvy.com -Wolfram Wagner ww@mpi-sb.mpg.de -Wwp subscript@free.fr -Zack Weinberg zack@codesourcery.com +Airy Andre Airy.Andre@edf.fr +Akim Demaille akim@freefriends.org +Albert Chin-A-Young china@thewrittenword.com +Alexander Belopolsky alexb@rentec.com +Andreas Schwab schwab@suse.de +Arnold Robbins arnold@skeeve.com +Art Haas ahaas@neosoft.com +Benoit Perrot benoit.perrot@epita.fr +Bruce Lilly blilly@erols.com +Charles-Henri de Boysson deboys_c@epita.fr +Cris Bailiff c.bailiff+bison@awayweb.com +Cris van Pelt cris@amf03054.office.wxs.nl +Daniel Hagerty hag@gnu.org +David J. MacKenzie djm@gnu.org +Dick Streefland dick.streefland@altium.nl +Enrico Scholz enrico.scholz@informatik.tu-chemnitz.de +Evgeny Stambulchik fnevgeny@plasma-gate.weizmann.ac.il +Fabrice Bauzac noon@cote-dazur.com +Florian Krohm florian@edamail.fishkill.ibm.com +H. Merijn Brand h.m.brand@hccnet.nl +Hans Aberg haberg@matematik.su.se +Jan Nieuwenhuizen janneke@gnu.org +Jesse Thilo jthilo@gnu.org +Jim Meyering jim@meyering.net +Juan Manuel Guerrero ST001906@HRZ1.HRZ.TU-Darmstadt.De +Kees Zeelenberg kzlg@users.sourceforge.net +Keith Browne kbrowne@legato.com +Laurent Mascherpa laurent.mascherpa@epita.fr +Magnus Fromreide magfr@lysator.liu.se +Marc Autret autret_m@epita.fr +Martin Mokrejs mmokrejs@natur.cuni.cz +Matt Kraai kraai@alumni.cmu.edu +Michael Hayes m.hayes@elec.canterbury.ac.nz +Mike Castle dalgoda@ix.netcom.com +Neil Booth NeilB@earthling.net +Nelson H. F. Beebe beebe@math.utah.edu +Nicolas Burrus nicolas.burrus@epita.fr +Nicolas Tisserand nicolas.tisserand@epita.fr +Noah Friedman friedman@gnu.org +Pascal Bart pascal.bart@epita.fr +Paul Eggert eggert@twinsun.com +Paul Hilfinger Hilfinger@CS.Berkeley.EDU +Per Allansson per@appgate.com +Peter Hámorský hamo@upjs.sk +Piotr Gackiewicz gacek@intertel.com.pl +R Blake blakers@mac.com +Raja R Harinath harinath@cs.umn.edu +Richard Stallman rms@gnu.org +Robert Anisko anisko_r@epita.fr +Shura debil_urod@ngs.ru +Tim Josling tej@melbpc.org.au +Tom Lane tgl@sss.pgh.pa.us +Tom Tromey tromey@cygnus.com +Wayne Green wayne@infosavvy.com +Wolfram Wagner ww@mpi-sb.mpg.de +Wwp subscript@free.fr +Zack Weinberg zack@codesourcery.com Many people are not named here because we lost track of them. We thank them! Please, help us keeping this list up to date. diff --git a/data/glr.c b/data/glr.c index 0868f025..a9573ed7 100644 --- a/data/glr.c +++ b/data/glr.c @@ -169,10 +169,10 @@ typedef union b4_stype yystype; 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 @@ static const ]b4_int_type_for([b4_pgoto])[ yypgoto[] = /* 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 @@ int yyparse (void); #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 @@ yygetLRActions (yyStateNum yystate, int yytoken, 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 @@ yyLRgotoState (yyStateNum yystate, yySymbol yylhs) { 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 @@ yyisShiftAction (int yyaction) static inline bool yyisErrorAction (int yyaction) { - return yyaction == 0 || yyaction == YYPACT_NINF; + return yyaction == 0; } /* GLRStates */ @@ -1256,7 +1262,7 @@ yyresolveAction (yySemanticOption* yyopt, yyGLRStack* yystack, } #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 @@ yyreportParseError (yyGLRStack* yystack, YYSTYPE* yylvalp, YYLTYPE* yyllocp) { 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 @@ yyreportParseError (yyGLRStack* yystack, YYSTYPE* yylvalp, YYLTYPE* yyllocp) } } -/* 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 @@ b4_location_if( [#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 diff --git a/data/yacc.c b/data/yacc.c index 31ee8436..f3dcfab4 100644 --- a/data/yacc.c +++ b/data/yacc.c @@ -414,7 +414,8 @@ static const b4_int_type_for([b4_pgoto]) yypgoto[[]] = /* 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; } diff --git a/tests/calc.at b/tests/calc.at index 8875f9cd..63c8604b 100644 --- a/tests/calc.at +++ b/tests/calc.at @@ -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 @@ main (int argc, const char **argv) # 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 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 @@ AT_CHECK([cat stderr], 0, [expout]) ]) -# 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 @@ AT_SETUP([Calculator $1]) 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 @@ AT_CLEANUP -# ------------------ # -# 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]) -- 2.45.2