# Exercising Bison Grammar Reduction. -*- Autotest -*- # Copyright (C) 2001, 2002, 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 # 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, see . AT_BANNER([[Grammar Reduction.]]) ## ------------------- ## ## Useless Terminals. ## ## ------------------- ## AT_SETUP([Useless Terminals]) AT_DATA([[input.y]], [[%verbose %output "input.c" %token useless1 %token useless2 %token useless3 %token useless4 %token useless5 %token useless6 %token useless7 %token useless8 %token useless9 %token useful %% exp: useful; ]]) AT_BISON_CHECK([[input.y]]) AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, [[Terminals unused in grammar useless1 useless2 useless3 useless4 useless5 useless6 useless7 useless8 useless9 ]]) AT_CLEANUP ## ---------------------- ## ## Useless Nonterminals. ## ## ---------------------- ## AT_SETUP([Useless Nonterminals]) AT_DATA([[input.y]], [[%verbose %output "input.c" %nterm useless1 %nterm useless2 %nterm useless3 %nterm useless4 %nterm useless5 %nterm useless6 %nterm useless7 %nterm useless8 %nterm useless9 %token useful %% exp: useful; ]]) 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, [[Nonterminals useless in grammar useless1 useless2 useless3 useless4 useless5 useless6 useless7 useless8 useless9 ]]) AT_CLEANUP ## --------------- ## ## Useless Rules. ## ## --------------- ## AT_SETUP([Useless Rules]) AT_KEYWORDS([report]) AT_DATA([[input.y]], [[%verbose %output "input.c" %token useful %% exp: useful; useless1: '1'; useless2: '2'; useless3: '3'; useless4: '4'; useless5: '5'; useless6: '6'; useless7: '7'; useless8: '8'; useless9: '9'; ]]) 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, [[Nonterminals useless in grammar useless1 useless2 useless3 useless4 useless5 useless6 useless7 useless8 useless9 Terminals unused in grammar '1' '2' '3' '4' '5' '6' '7' '8' '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 ## ------------------- ## ## Reduced Automaton. ## ## ------------------- ## # Check that the automaton is that as the for the grammar reduced by # hand. AT_SETUP([Reduced Automaton]) AT_KEYWORDS([report]) # The non reduced grammar. # ------------------------ AT_DATA([[not-reduced.y]], [[/* A useless token. */ %token useless_token /* A useful one. */ %token useful %verbose %output "not-reduced.c" %% exp: useful { /* A useful action. */ } | non_productive { /* A non productive action. */ } ; not_reachable: useful { /* A not reachable action. */ } ; non_productive: non_productive useless_token { /* Another non productive action. */ } ; %% ]]) 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, [[Nonterminals useless in grammar not_reachable non_productive Terminals unused in grammar useless_token Rules useless in grammar 2 exp: non_productive 3 not_reachable: useful 4 non_productive: non_productive useless_token ]]) # The reduced grammar. # -------------------- AT_DATA([[reduced.y]], [[/* A useless token. */ %token useless_token /* A useful one. */ %token useful %verbose %output "reduced.c" %% exp: useful { /* A useful action. */ } // | non_productive { /* A non productive action. */ } */ ; //not_reachable: useful { /* A not reachable action. */ } // ; //non_productive: non_productive useless_token // { /* Another non productive action. */ } // ; %% ]]) AT_BISON_CHECK([[reduced.y]]) # Comparing the parsers. cp reduced.c expout AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout]) AT_CLEANUP ## ------------------- ## ## Underivable Rules. ## ## ------------------- ## AT_SETUP([Underivable Rules]) AT_KEYWORDS([report]) AT_DATA([[input.y]], [[%verbose %output "input.c" %token useful %% exp: useful | underivable; underivable: indirection; indirection: underivable; ]]) 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, [[Nonterminals useless in grammar underivable indirection 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.default_rules. ## ## -------------------------- ## # AT_TEST_LR_DEFAULT_RULES(GRAMMAR, INPUT, TABLES) # ------------------------------------------------ m4_define([AT_TEST_LR_DEFAULT_RULES], [ AT_TEST_TABLES_AND_PARSE([[no %define lr.default_rules]], [[all]], [[]], [[]], [$1], [$2], [[]], [$3]) AT_TEST_TABLES_AND_PARSE([[%define lr.default_rules "all"]], [[all]], [[]], [[%define lr.default_rules "all"]], [$1], [$2], [[]], [$3]) AT_TEST_TABLES_AND_PARSE([[%define lr.default_rules "consistent"]], [[consistent]], [[]], [[%define lr.default_rules "consistent"]], [$1], [$2], [[]], [$3]) AT_TEST_TABLES_AND_PARSE([[%define lr.default_rules "accepting"]], [[accepting]], [[]], [[%define lr.default_rules "accepting"]], [$1], [$2], [[]], [$3]) ]) AT_TEST_LR_DEFAULT_RULES([[ /* 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 rule 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([[all]], [[ '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([[all]], [[$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)]])[ ]])