X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/c3b407f430a6c4bab6f0ef5160bb0c34290f3abb..abd189e8dc6ca848f038da12e4110d6192374b82:/tests/reduce.at?ds=sidebyside diff --git a/tests/reduce.at b/tests/reduce.at index b3a79ba2..e7220cba 100644 --- a/tests/reduce.at +++ b/tests/reduce.at @@ -1,20 +1,19 @@ # Exercising Bison Grammar Reduction. -*- Autotest -*- -# Copyright 2001 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 -# the Free Software Foundation; either version 2, or (at your option) -# any later version. +# Copyright (C) 2001-2002, 2007-2011 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 +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. - +# # You should have received a copy of the GNU General Public License -# along with this program; if not, write to the Free Software -# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA -# 02111-1307, USA. +# along with this program. If not, see . AT_BANNER([[Grammar Reduction.]]) @@ -27,7 +26,7 @@ AT_SETUP([Useless Terminals]) AT_DATA([[input.y]], [[%verbose -%output="input.c" +%output "input.c" %token useless1 %token useless2 @@ -44,10 +43,10 @@ AT_DATA([[input.y]], exp: useful; ]]) -AT_CHECK([[bison input.y]]) +AT_BISON_CHECK([[input.y]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Terminals which are not used: +[[Terminals unused in grammar useless1 useless2 useless3 @@ -71,7 +70,7 @@ AT_SETUP([Useless Nonterminals]) AT_DATA([[input.y]], [[%verbose -%output="input.c" +%output "input.c" %nterm useless1 %nterm useless2 @@ -88,12 +87,21 @@ AT_DATA([[input.y]], exp: useful; ]]) -AT_CHECK([[bison input.y]], 0, [], -[[input.y contains 9 useless nonterminals +AT_BISON_CHECK([[input.y]], 0, [], +[[input.y: warning: 9 nonterminals useless in grammar +input.y:4.8-15: warning: nonterminal useless in grammar: useless1 +input.y:5.8-15: warning: nonterminal useless in grammar: useless2 +input.y:6.8-15: warning: nonterminal useless in grammar: useless3 +input.y:7.8-15: warning: nonterminal useless in grammar: useless4 +input.y:8.8-15: warning: nonterminal useless in grammar: useless5 +input.y:9.8-15: warning: nonterminal useless in grammar: useless6 +input.y:10.8-15: warning: nonterminal useless in grammar: useless7 +input.y:11.8-15: warning: nonterminal useless in grammar: useless8 +input.y:12.8-15: warning: nonterminal useless in grammar: useless9 ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Useless nonterminals: +[[Nonterminals useless in grammar useless1 useless2 useless3 @@ -115,9 +123,11 @@ AT_CLEANUP AT_SETUP([Useless Rules]) +AT_KEYWORDS([report]) + AT_DATA([[input.y]], [[%verbose -%output="input.c" +%output "input.c" %token useful %% exp: useful; @@ -132,12 +142,31 @@ useless8: '8'; useless9: '9'; ]]) -AT_CHECK([[bison input.y]], 0, [], -[[input.y contains 9 useless nonterminals and 9 useless rules +AT_BISON_CHECK([[input.y]], 0, [], +[[input.y: warning: 9 nonterminals useless in grammar +input.y: warning: 9 rules useless in grammar +input.y:6.1-8: warning: nonterminal useless in grammar: useless1 +input.y:7.1-8: warning: nonterminal useless in grammar: useless2 +input.y:8.1-8: warning: nonterminal useless in grammar: useless3 +input.y:9.1-8: warning: nonterminal useless in grammar: useless4 +input.y:10.1-8: warning: nonterminal useless in grammar: useless5 +input.y:11.1-8: warning: nonterminal useless in grammar: useless6 +input.y:12.1-8: warning: nonterminal useless in grammar: useless7 +input.y:13.1-8: warning: nonterminal useless in grammar: useless8 +input.y:14.1-8: warning: nonterminal useless in grammar: useless9 +input.y:6.11-13: warning: rule useless in grammar: useless1: '1' +input.y:7.11-13: warning: rule useless in grammar: useless2: '2' +input.y:8.11-13: warning: rule useless in grammar: useless3: '3' +input.y:9.11-13: warning: rule useless in grammar: useless4: '4' +input.y:10.11-13: warning: rule useless in grammar: useless5: '5' +input.y:11.11-13: warning: rule useless in grammar: useless6: '6' +input.y:12.11-13: warning: rule useless in grammar: useless7: '7' +input.y:13.11-13: warning: rule useless in grammar: useless8: '8' +input.y:14.11-13: warning: rule useless in grammar: useless9: '9' ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Useless nonterminals: +[[Nonterminals useless in grammar useless1 useless2 useless3 @@ -147,7 +176,7 @@ AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, useless7 useless8 useless9 -Terminals which are not used: +Terminals unused in grammar '1' '2' '3' @@ -157,16 +186,16 @@ Terminals which are not used: '7' '8' '9' -Useless rules: -#2 useless1: '1'; -#3 useless2: '2'; -#4 useless3: '3'; -#5 useless4: '4'; -#6 useless5: '5'; -#7 useless6: '6'; -#8 useless7: '7'; -#9 useless8: '8'; -#10 useless9: '9'; +Rules useless in grammar + 2 useless1: '1' + 3 useless2: '2' + 4 useless3: '3' + 5 useless4: '4' + 6 useless5: '5' + 7 useless6: '6' + 8 useless7: '7' + 9 useless8: '8' + 10 useless9: '9' ]]) AT_CLEANUP @@ -182,6 +211,8 @@ AT_CLEANUP AT_SETUP([Reduced Automaton]) +AT_KEYWORDS([report]) + # The non reduced grammar. # ------------------------ AT_DATA([[not-reduced.y]], @@ -190,7 +221,7 @@ AT_DATA([[not-reduced.y]], /* A useful one. */ %token useful %verbose -%output="not-reduced.c" +%output "not-reduced.c" %% @@ -204,22 +235,29 @@ not_reachable: useful { /* A not reachable action. */ } non_productive: non_productive useless_token { /* Another non productive action. */ } ; +%% ]]) -AT_CHECK([[bison not-reduced.y]], 0, [], -[[not-reduced.y contains 2 useless nonterminals and 3 useless rules +AT_BISON_CHECK([[not-reduced.y]], 0, [], +[[not-reduced.y: warning: 2 nonterminals useless in grammar +not-reduced.y: warning: 3 rules useless in grammar +not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable +not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive +not-reduced.y:11.6-57: warning: rule useless in grammar: exp: non_productive +not-reduced.y:14.16-56: warning: rule useless in grammar: not_reachable: useful +not-reduced.y:17.17-18.63: warning: rule useless in grammar: non_productive: non_productive useless_token ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0, -[[Useless nonterminals: +[[Nonterminals useless in grammar not_reachable non_productive -Terminals which are not used: +Terminals unused in grammar useless_token -Useless rules: -#2 exp: non_productive; -#3 not_reachable: useful; -#4 non_productive: non_productive useless_token; +Rules useless in grammar + 2 exp: non_productive + 3 not_reachable: useful + 4 non_productive: non_productive useless_token ]]) # The reduced grammar. @@ -230,7 +268,7 @@ AT_DATA([[reduced.y]], /* A useful one. */ %token useful %verbose -%output="reduced.c" +%output "reduced.c" %% @@ -244,9 +282,10 @@ exp: useful { /* A useful action. */ } //non_productive: non_productive useless_token // { /* Another non productive action. */ } // ; +%% ]]) -AT_CHECK([[bison reduced.y]]) +AT_BISON_CHECK([[reduced.y]]) # Comparing the parsers. cp reduced.c expout @@ -262,9 +301,11 @@ AT_CLEANUP AT_SETUP([Underivable Rules]) +AT_KEYWORDS([report]) + AT_DATA([[input.y]], [[%verbose -%output="input.c" +%output "input.c" %token useful %% exp: useful | underivable; @@ -272,18 +313,1274 @@ underivable: indirection; indirection: underivable; ]]) -AT_CHECK([[bison input.y]], 0, [], -[[input.y contains 2 useless nonterminals and 3 useless rules +AT_BISON_CHECK([[input.y]], 0, [], +[[input.y: warning: 2 nonterminals useless in grammar +input.y: warning: 3 rules useless in grammar +input.y:5.15-25: warning: nonterminal useless in grammar: underivable +input.y:6.14-24: warning: nonterminal useless in grammar: indirection +input.y:5.15-25: warning: rule useless in grammar: exp: underivable +input.y:6.14-24: warning: rule useless in grammar: underivable: indirection +input.y:7.14-24: warning: rule useless in grammar: indirection: underivable ]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, -[[Useless nonterminals: +[[Nonterminals useless in grammar underivable indirection -Useless rules: -#2 exp: underivable; -#3 underivable: indirection; -#4 indirection: underivable; +Rules useless in grammar + 2 exp: underivable + 3 underivable: indirection + 4 indirection: underivable ]]) AT_CLEANUP + + + +## ---------------- ## +## Empty Language. ## +## ---------------- ## + +AT_SETUP([Empty Language]) + +AT_DATA([[input.y]], +[[%output "input.c" +%% +exp: exp; +]]) + +AT_BISON_CHECK([[input.y]], 1, [], +[[input.y: warning: 2 nonterminals useless in grammar +input.y: warning: 2 rules useless in grammar +input.y:3.1-3: fatal error: start symbol exp does not derive any sentence +]]) + +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-reductions. ## +## ------------------------------- ## + +# AT_TEST_LR_DEFAULT_REDUCTIONS(GRAMMAR, INPUT, TABLES) +# ----------------------------------------------------- +m4_define([AT_TEST_LR_DEFAULT_REDUCTIONS], +[ +AT_TEST_TABLES_AND_PARSE([[no %define lr.default-reductions]], + [[most]], [[]], + [[]], + [$1], [$2], [[]], [$3]) +AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions most]], + [[most]], [[]], + [[%define lr.default-reductions most]], + [$1], [$2], [[]], [$3]) +AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions consistent]], + [[consistent]], [[]], + [[%define lr.default-reductions consistent]], + [$1], [$2], [[]], [$3]) +AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions accepting]], + [[accepting]], [[]], + [[%define lr.default-reductions accepting]], + [$1], [$2], [[]], [$3]) +]) + +AT_TEST_LR_DEFAULT_REDUCTIONS([[ +/* The start state is consistent and has a shift on 'a' and no reductions. + After pushing the b below, enter an inconsistent state that has a shift and + one reduction with one lookahead. */ +start: + a b + | a b 'a' + | a c 'b' + ; + +/* After shifting this 'a', enter a consistent state that has no shift and 1 + reduction with multiple lookaheads. */ +a: 'a' ; + +/* After the previous reduction, enter an inconsistent state that has no shift + and multiple reductions. The first reduction has more lookaheads than the + second, so the first should always be preferred as the default reduction if + enabled. The second reduction has one lookahead. */ +b: ; +c: ; +]], +dnl Visit each state mentioned above. +[['a', 'a']], +[[state 0 + + 0 $accept: . start $end + 1 start: . a b + 2 | . a b 'a' + 3 | . a c 'b' + 4 a: . 'a' + + 'a' shift, and go to state 1 + + start go to state 2 + a go to state 3 + + +state 1 + + 4 a: 'a' .]AT_COND_CASE([[accepting]], [[ [$end, 'a', 'b'] + + $end reduce using rule 4 (a) + 'a' reduce using rule 4 (a) + 'b' reduce using rule 4 (a)]], [[ + + $default reduce using rule 4 (a)]])[ + + +state 2 + + 0 $accept: start . $end + + $end shift, and go to state 4 + + +state 3 + + 1 start: a . b + 2 | a . b 'a' + 3 | a . c 'b' + 5 b: . [$end, 'a'] + 6 c: . ['b']]AT_COND_CASE([[most]], [[ + + 'b' reduce using rule 6 (c) + $default reduce using rule 5 (b)]], [[ + + $end reduce using rule 5 (b) + 'a' reduce using rule 5 (b) + 'b' reduce using rule 6 (c)]])[ + + b go to state 5 + c go to state 6 + + +state 4 + + 0 $accept: start $end . + + $default accept + + +state 5 + + 1 start: a b . [$end] + 2 | a b . 'a' + + 'a' shift, and go to state 7 + + ]AT_COND_CASE([[most]], [[$default]], + [[$end]])[ reduce using rule 1 (start) + + +state 6 + + 3 start: a c . 'b' + + 'b' shift, and go to state 8 + + +state 7 + + 2 start: a b 'a' .]AT_COND_CASE([[accepting]], [[ [$end] + + $end reduce using rule 2 (start)]], [[ + + $default reduce using rule 2 (start)]])[ + + +state 8 + + 3 start: a c 'b' .]AT_COND_CASE([[accepting]], [[ [$end] + + $end reduce using rule 3 (start)]], [[ + + $default reduce using rule 3 (start)]])[ +]])