| # Exercising Bison on counterexamples. -*- Autotest -*- |
| |
| # Copyright (C) 2020-2021 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 <https://www.gnu.org/licenses/>. |
| |
| AT_BANNER([[Counterexamples.]]) |
| |
| # AT_BISON_CHECK_CEX(TREE, FLAT) |
| # ------------------------------ |
| m4_define([AT_BISON_CHECK_CEX], |
| [AT_KEYWORDS([cex]) |
| |
| AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr]) |
| # FIXME: Avoid trailing white spaces. |
| AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g;s/ *$//;' stderr]], |
| [], [$1]) |
| |
| m4_pushdef([AT_SET_ENV_IF], |
| [[YYFLAT=1; export YYFLAT;]]m4_defn([AT_SET_ENV_IF])) |
| AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr]) |
| AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g' stderr]], |
| [], [$2]) |
| m4_popdef([AT_SET_ENV_IF]) |
| |
| ]) |
| |
| ## --------------------- ## |
| ## Simple Unifying S/R. ## |
| ## --------------------- ## |
| |
| AT_SETUP([Unifying S/R]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B C |
| %% |
| s: a x | y c; |
| a: A; |
| c: C; |
| x: B | B C; |
| y: A | A B; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example: A . B C |
| Shift derivation |
| s |
| `-> 2: y c |
| `-> 8: A . B `-> 4: C |
| Reduce derivation |
| s |
| `-> 1: a x |
| `-> 3: A . `-> 6: B C |
| input.y:4.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example A . B C |
| Shift derivation s -> [ y -> [ A . B ] c -> [ C ] ] |
| Reduce derivation s -> [ a -> [ A . ] x -> [ B C ] ] |
| input.y:4.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ------------------- ## |
| ## Deep Unifying S/R. ## |
| ## ------------------- ## |
| |
| AT_SETUP([Deep Unifying S/R]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B C |
| %% |
| s: ac | a bc; |
| ac: A ac C | b; |
| b: B | B b; |
| a: A | A a; |
| bc: B bc C | B C; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example: A . B C |
| Shift derivation |
| s |
| `-> 1: ac |
| `-> 3: A ac C |
| `-> 4: b |
| `-> 5: . B |
| Reduce derivation |
| s |
| `-> 2: a bc |
| `-> 7: A . `-> 10: B C |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example: A A . B B C C |
| Shift derivation |
| s |
| `-> 1: ac |
| `-> 3: A ac C |
| `-> 3: A ac C |
| `-> 4: b |
| `-> 6: . b |
| `-> 5: B B |
| Reduce derivation |
| s |
| `-> 2: a bc |
| `-> 8: A a `-> 9: B bc C |
| `-> 7: A . `-> 10: B C |
| input.y:6.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example A . B C |
| Shift derivation s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ] |
| Reduce derivation s -> [ a -> [ A . ] bc -> [ B C ] ] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example A A . B B C C |
| Shift derivation s -> [ ac -> [ A ac -> [ A ac -> [ b -> [ . b -> [ B B ] ] ] C ] C ] ] |
| Reduce derivation s -> [ a -> [ A a -> [ A . ] ] bc -> [ B bc -> [ B C ] C ] ] |
| input.y:6.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ------------------------------------ ## |
| ## S/R Conflict with Nullable Symbols. ## |
| ## ------------------------------------ ## |
| |
| AT_SETUP([S/R Conflict with Nullable Symbols]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B X Y |
| %% |
| s: ax by | A xby; |
| ax: A x; |
| x: %empty | X x; |
| by: B y; |
| y: %empty | Y y; |
| xby: B | X xby Y; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example: A . B |
| Shift derivation |
| s |
| `-> 2: A xby |
| `-> 9: . B |
| Reduce derivation |
| s |
| `-> 1: ax by |
| `-> 3: A x `-> 6: B y |
| `-> 4: %empty . `-> 6: %empty |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| First example: A X . B Y $end |
| Shift derivation |
| $accept |
| `-> 0: s $end |
| `-> 2: A xby |
| `-> 10: X xby Y |
| `-> 9: . B |
| Second example: A X . B y $end |
| Reduce derivation |
| $accept |
| `-> 0: s $end |
| `-> 1: ax by |
| `-> 3: A x `-> 6: B y |
| `-> 5: X x |
| `-> 4: %empty . |
| input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example A . B |
| Shift derivation s -> [ A xby -> [ . B ] ] |
| Reduce derivation s -> [ ax -> [ A x -> [ . ] ] by -> [ B y -> [ ] ] ] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| First example A X . B Y $end |
| Shift derivation $accept -> [ s -> [ A xby -> [ X xby -> [ . B ] Y ] ] $end ] |
| Second example A X . B y $end |
| Reduce derivation $accept -> [ s -> [ ax -> [ A x -> [ X x -> [ . ] ] ] by -> [ B y ] ] $end ] |
| input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ---------------------------- ## |
| ## Non-unifying Ambiguous S/R. ## |
| ## ---------------------------- ## |
| |
| AT_SETUP([Non-unifying Ambiguous S/R]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B C D E |
| %% |
| g: s | x; |
| s: A x E | A x D E; |
| x: b cd | bc; |
| b: B; |
| cd: C D; |
| bc: B C; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token C [-Wcounterexamples] |
| First example: B . C $end |
| Shift derivation |
| $accept |
| `-> 0: g $end |
| `-> 2: x |
| `-> 6: bc |
| `-> 9: B . C |
| Second example: B . C D $end |
| Reduce derivation |
| $accept |
| `-> 0: g $end |
| `-> 2: x |
| `-> 5: b cd |
| `-> 7: B . `-> 8: C D |
| input.y:6.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token C [-Wcounterexamples] |
| First example B . C $end |
| Shift derivation $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ] |
| Second example B . C D $end |
| Reduce derivation $accept -> [ g -> [ x -> [ b -> [ B . ] cd -> [ C D ] ] ] $end ] |
| input.y:6.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ------------------------------ ## |
| ## Non-unifying Unambiguous S/R. ## |
| ## ------------------------------ ## |
| |
| AT_SETUP([Non-unifying Unambiguous S/R]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B |
| %% |
| s: t | s t; |
| t: x | y; |
| x: A; |
| y: A A B; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| First example: A . A B $end |
| Shift derivation |
| $accept |
| `-> 0: s $end |
| `-> 1: t |
| `-> 4: y |
| `-> 6: A . A B |
| Second example: A . A $end |
| Reduce derivation |
| $accept |
| `-> 0: s $end |
| `-> 2: s t |
| `-> 1: t `-> 3: x |
| `-> 3: x `-> 5: A |
| `-> 5: A . |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| First example A . A B $end |
| Shift derivation $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ] |
| Second example A . A $end |
| Reduce derivation $accept -> [ s -> [ s -> [ t -> [ x -> [ A . ] ] ] t -> [ x -> [ A ] ] ] $end ] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ----------------------- ## |
| ## S/R after first token. ## |
| ## ----------------------- ## |
| |
| AT_SETUP([S/R after first token]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B X Y |
| %% |
| a: r t | s; |
| r: b; |
| b: B; |
| t: A xx | A x xy; |
| s: b A xx y; |
| x: X; |
| xx: X X; |
| xy: X Y; |
| y: Y; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| Example: b . A X X Y |
| Shift derivation |
| a |
| `-> 2: s |
| `-> 7: b . xx y |
| `-> 9: A X X `-> 11: Y |
| Reduce derivation |
| a |
| `-> 1: r t |
| `-> 3: b . `-> 6: A x xy |
| `-> 8: X `-> 10: X Y |
| input.y: warning: shift/reduce conflict on token X [-Wcounterexamples] |
| First example: A X . X |
| Shift derivation |
| a |
| `-> 1: t |
| `-> 5: A xx |
| `-> 9: X . X |
| Second example: X . X xy |
| Reduce derivation |
| a |
| `-> 1: x t |
| `-> 8: X . `-> 6: X xy |
| input.y:4.4: warning: rule useless in parser due to conflicts [-Wother] |
| input.y:8.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| Example b . A X X Y |
| Shift derivation a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ] |
| Reduce derivation a -> [ r -> [ b . ] t -> [ A x -> [ X ] xy -> [ X Y ] ] ] |
| input.y: warning: shift/reduce conflict on token X [-Wcounterexamples] |
| First example A X . X |
| Shift derivation a -> [ t -> [ A xx -> [ X . X ] ] ] |
| Second example X . X xy |
| Reduce derivation a -> [ x -> [ X . ] t -> [ X xy ] ] |
| input.y:4.4: warning: rule useless in parser due to conflicts [-Wother] |
| input.y:8.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ----------------------------- ## |
| ## Unifying R/R counterexample. ## |
| ## ----------------------------- ## |
| |
| AT_SETUP([Unifying R/R counterexample]) |
| |
| AT_DATA([[input.y]], |
| [[%token A |
| %% |
| a : A b ; |
| b : A | b; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples] |
| Example: A b . |
| First reduce derivation |
| a |
| `-> 1: A b . |
| Second reduce derivation |
| a |
| `-> 1: A b |
| `-> 3: b . |
| input.y:4.9: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples] |
| Example A b . |
| First reduce derivation a -> [ A b . ] |
| Second reduce derivation a -> [ A b -> [ b . ] ] |
| input.y:4.9: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## --------------------------------- ## |
| ## Non-unifying R/R LR(1) conflict. ## |
| ## --------------------------------- ## |
| |
| AT_SETUP([Non-unifying R/R LR(1) conflict]) |
| |
| AT_DATA([[input.y]], |
| [[%token A B C D |
| %% |
| s: a A | B a C | b C | B b A; |
| a: D; |
| b: D; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on tokens A, C [-Wcounterexamples] |
| First example: D . A $end |
| First reduce derivation |
| $accept |
| `-> 0: s $end |
| `-> 1: a A |
| `-> 5: D . |
| Second example: B D . A $end |
| Second reduce derivation |
| $accept |
| `-> 0: s $end |
| `-> 4: B b A |
| `-> 6: D . |
| input.y:5.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on tokens A, C [-Wcounterexamples] |
| First example D . A $end |
| First reduce derivation $accept -> [ s -> [ a -> [ D . ] A ] $end ] |
| Second example B D . A $end |
| Second reduce derivation $accept -> [ s -> [ B b -> [ D . ] A ] $end ] |
| input.y:5.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## --------------------------------- ## |
| ## Non-unifying R/R LR(2) conflict. ## |
| ## --------------------------------- ## |
| |
| AT_SETUP([Non-unifying R/R LR(2) conflict]) |
| |
| AT_DATA([[input.y]], |
| [[%token H J K X |
| %% |
| s: a J; |
| a: H i; |
| i: X | i J K; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token J [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example: H i . J K $end |
| Shift derivation |
| $accept |
| `-> 0: a $end |
| `-> 2: H i |
| `-> 4: i . J K |
| Second example: H i . J $end |
| Reduce derivation |
| $accept |
| `-> 0: s $end |
| `-> 1: a J |
| `-> 2: H i . |
| input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token J [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example H i . J K $end |
| Shift derivation $accept -> [ a -> [ H i -> [ i . J K ] ] $end ] |
| Second example H i . J $end |
| Reduce derivation $accept -> [ s -> [ a -> [ H i . ] J ] $end ] |
| input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## -------------------- ## |
| ## Cex Search Prepend. ## |
| ## -------------------- ## |
| |
| # Tests prepend steps in uniying counterexample |
| # graph search |
| |
| AT_SETUP([Cex Search Prepend]) |
| |
| AT_DATA([[input.y]], |
| [[%token N A B C D |
| %% |
| s: n | n C; |
| n: N n D | N n C | N a B | N b; |
| a: A; |
| b: A B C | A B D; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example: N A . B C |
| Shift derivation |
| s |
| `-> 1: n |
| `-> 6: N b |
| `-> 8: A . B C |
| Reduce derivation |
| s |
| `-> 2: n C |
| `-> 5: N a B |
| `-> 7: A . |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example: N N A . B D C |
| Shift derivation |
| s |
| `-> 1: n |
| `-> 4: N n C |
| `-> 6: N b |
| `-> 9: A . B D |
| Reduce derivation |
| s |
| `-> 2: n C |
| `-> 3: N n D |
| `-> 5: N a B |
| `-> 7: A . |
| input.y:5.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example N A . B C |
| Shift derivation s -> [ n -> [ N b -> [ A . B C ] ] ] |
| Reduce derivation s -> [ n -> [ N a -> [ A . ] B ] C ] |
| input.y: warning: shift/reduce conflict on token B [-Wcounterexamples] |
| Example N N A . B D C |
| Shift derivation s -> [ n -> [ N n -> [ N b -> [ A . B D ] ] C ] ] |
| Reduce derivation s -> [ n -> [ N n -> [ N a -> [ A . ] B ] D ] C ] |
| input.y:5.4: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ------------------- ## |
| ## R/R cex with prec. ## |
| ## ------------------- ## |
| |
| # Tests that counterexamples containing rules using |
| # precedence/associativity directives work. |
| |
| AT_SETUP([R/R cex with prec]) |
| |
| AT_DATA([[input.y]], |
| [[%left b |
| %right c |
| %% |
| S: B C | C B; |
| A : B | C | %empty; |
| B : A b A; |
| C : A c A; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples] |
| Example: B . b c |
| First reduce derivation |
| S |
| `-> 1: B C |
| `-> 6: A b A `-> 7: A c A |
| `-> 3: B . `-> 6: %empty `-> 7: %empty `-> 7: %empty |
| Second reduce derivation |
| S |
| `-> 1: B C |
| `-> 7: A c A |
| `-> 3: B `-> 7: %empty |
| `-> 6: A b A |
| `-> 5: %empty . `-> 6: %empty |
| input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples] |
| Example: C . c b |
| First reduce derivation |
| S |
| `-> 2: C B |
| `-> 7: A c A `-> 6: A b A |
| `-> 4: C . `-> 7: %empty `-> 6: %empty `-> 6: %empty |
| Second reduce derivation |
| S |
| `-> 2: C B |
| `-> 6: A b A |
| `-> 4: C `-> 6: %empty |
| `-> 7: A c A |
| `-> 5: %empty . `-> 7: %empty |
| ]], |
| [[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples] |
| Example B . b c |
| First reduce derivation S -> [ B -> [ A -> [ B . ] b A -> [ ] ] C -> [ A -> [ ] c A -> [ ] ] ] |
| Second reduce derivation S -> [ B C -> [ A -> [ B -> [ A -> [ . ] b A -> [ ] ] ] c A -> [ ] ] ] |
| input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples] |
| Example C . c b |
| First reduce derivation S -> [ C -> [ A -> [ C . ] c A -> [ ] ] B -> [ A -> [ ] b A -> [ ] ] ] |
| Second reduce derivation S -> [ C B -> [ A -> [ C -> [ A -> [ . ] c A -> [ ] ] ] b A -> [ ] ] ] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ------------------- ## |
| ## Null nonterminals. ## |
| ## ------------------- ## |
| |
| AT_SETUP([Null nonterminals]) |
| |
| AT_DATA([[input.y]], |
| [[%token A |
| %% |
| a : b d | c d ; |
| b : ; |
| c : ; |
| d : a | c A | d; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| First example: . c A A $end |
| First reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 3: %empty . `-> 6: c A A |
| Second example: . c A A $end |
| Second reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 2: c d |
| `-> 4: %empty . `-> 6: c A A |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example: b . c A A $end |
| First reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 5: a |
| `-> 1: b d |
| `-> 3: %empty . `-> 6: c A A |
| Second example: b . A $end |
| Second reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 6: c A |
| `-> 4: %empty . |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example: c . c A A $end |
| First reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 2: c d |
| `-> 5: a |
| `-> 1: b d |
| `-> 3: %empty . `-> 6: c A A |
| Second example: c . A $end |
| Second reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 2: c d |
| `-> 6: c A |
| `-> 4: %empty . |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example: b c . A |
| Shift derivation |
| a |
| `-> 1: b d |
| `-> 6: c . A |
| Second example: b c . c A A $end |
| Reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 5: a |
| `-> 2: c d |
| `-> 5: a |
| `-> 1: b d |
| `-> 3: %empty . `-> 6: c A A |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| First example: b c . c A A $end |
| First reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 5: a |
| `-> 2: c d |
| `-> 5: a |
| `-> 1: b d |
| `-> 3: %empty . `-> 6: c A A |
| Second example: b c . A $end |
| Second reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 5: a |
| `-> 2: c d |
| `-> 6: c A |
| `-> 4: %empty . |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| First example: b c . A |
| Shift derivation |
| a |
| `-> 1: b d |
| `-> 6: c . A |
| Second example: b c . A $end |
| Reduce derivation |
| $accept |
| `-> 0: a $end |
| `-> 1: b d |
| `-> 5: a |
| `-> 2: c d |
| `-> 6: c A |
| `-> 4: %empty . |
| input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples] |
| Example: b d . |
| First reduce derivation |
| a |
| `-> 1: b d . |
| Second reduce derivation |
| a |
| `-> 1: b d |
| `-> 7: d . |
| input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples] |
| Example: c d . |
| First reduce derivation |
| a |
| `-> 2: c d . |
| Second reduce derivation |
| a |
| `-> 2: c d |
| `-> 7: d . |
| input.y:5.4: warning: rule useless in parser due to conflicts [-Wother] |
| input.y:6.15: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr] |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| First example . c A A $end |
| First reduce derivation $accept -> [ a -> [ b -> [ . ] d -> [ c A A ] ] $end ] |
| Second example . c A A $end |
| Second reduce derivation $accept -> [ a -> [ c -> [ . ] d -> [ c A A ] ] $end ] |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example b . c A A $end |
| First reduce derivation $accept -> [ a -> [ b d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] $end ] |
| Second example b . A $end |
| Second reduce derivation $accept -> [ a -> [ b d -> [ c -> [ . ] A ] ] $end ] |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example c . c A A $end |
| First reduce derivation $accept -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] $end ] |
| Second example c . A $end |
| Second reduce derivation $accept -> [ a -> [ c d -> [ c -> [ . ] A ] ] $end ] |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| time limit exceeded: XXX |
| First example b c . A |
| Shift derivation a -> [ b d -> [ c . A ] ] |
| Second example b c . c A A $end |
| Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] ] ] $end ] |
| input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples] |
| First example b c . c A A $end |
| First reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] ] ] $end ] |
| Second example b c . A $end |
| Second reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ] A ] ] ] ] $end ] |
| input.y: warning: shift/reduce conflict on token A [-Wcounterexamples] |
| First example b c . A |
| Shift derivation a -> [ b d -> [ c . A ] ] |
| Second example b c . A $end |
| Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ] A ] ] ] ] $end ] |
| input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples] |
| Example b d . |
| First reduce derivation a -> [ b d . ] |
| Second reduce derivation a -> [ b d -> [ d . ] ] |
| input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples] |
| Example c d . |
| First reduce derivation a -> [ c d . ] |
| Second reduce derivation a -> [ c d -> [ d . ] ] |
| input.y:5.4: warning: rule useless in parser due to conflicts [-Wother] |
| input.y:6.15: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## --------------------------- ## |
| ## Non-unifying Prefix Share. ## |
| ## --------------------------- ## |
| |
| AT_SETUP([Non-unifying Prefix Share]) |
| |
| # Tests for a counterexample which should start its derivation |
| # at a shared symbol rather than the start symbol. |
| |
| AT_DATA([[input.y]], |
| [[%token H J |
| %% |
| s: a | a J; |
| a: H i J J |
| i: %empty | i J; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token J [-Wcounterexamples] |
| Example: H i J . J J |
| Shift derivation |
| s |
| `-> 2: a J |
| `-> 3: H i J . J |
| Reduce derivation |
| s |
| `-> 1: a |
| `-> 3: H i J J |
| `-> 5: i J . |
| input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother] |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token J [-Wcounterexamples] |
| Example H i J . J J |
| Shift derivation s -> [ a -> [ H i J . J ] J ] |
| Reduce derivation s -> [ a -> [ H i -> [ i J . ] J J ] ] |
| input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## -------------------- ## |
| ## Deep Null Unifying. ## |
| ## ---------------------## |
| |
| # Tests that nested nullable nonterminals |
| # are derived correctly. |
| |
| AT_SETUP([Deep Null Unifying]) |
| |
| AT_DATA([[input.y]], |
| [[%token A D |
| %% |
| s: A a d | A a a d; |
| a: b; |
| b: c |
| c: %empty |
| d: D; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token D [-Wcounterexamples] |
| Example: A a . D |
| Shift derivation |
| s |
| `-> 1: A a d |
| `-> 6: . D |
| Reduce derivation |
| s |
| `-> 2: A a a d |
| `-> 3: b `-> 6: D |
| `-> 4: c |
| `-> 5: %empty . |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token D [-Wcounterexamples] |
| Example A a . D |
| Shift derivation s -> [ A a d -> [ . D ] ] |
| Reduce derivation s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] ] |
| ]]) |
| |
| AT_CLEANUP |
| |
| ## ------------------------ ## |
| ## Deep Null Non-unifying. ## |
| ## -------------------------## |
| |
| # Tests that expand_to_conflict works with nullable sybols |
| |
| AT_SETUP([Deep Null Non-unifying]) |
| |
| AT_DATA([[input.y]], |
| [[%token A D E |
| %% |
| s: A a d | A a a d E; |
| a: b; |
| b: c |
| c: %empty |
| d: D; |
| ]]) |
| |
| AT_BISON_CHECK_CEX( |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token D [-Wcounterexamples] |
| First example: A a . D $end |
| Shift derivation |
| $accept |
| `-> 0: s $end |
| `-> 1: A a d |
| `-> 6: . D |
| Second example: A a . D E $end |
| Reduce derivation |
| $accept |
| `-> 0: s $end |
| `-> 2: A a a d E |
| `-> 3: b `-> 6: D |
| `-> 4: c |
| `-> 5: %empty . |
| ]], |
| [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr] |
| input.y: warning: shift/reduce conflict on token D [-Wcounterexamples] |
| First example A a . D $end |
| Shift derivation $accept -> [ s -> [ A a d -> [ . D ] ] $end ] |
| Second example A a . D E $end |
| Reduce derivation $accept -> [ s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] E ] $end ] |
| ]]) |
| |
| AT_CLEANUP |
