1# Exercising Bison on counterexamples.                         -*- Autotest -*-
2
3# Copyright (C) 2020-2021 Free Software Foundation, Inc.
4
5# This program is free software: you can redistribute it and/or modify
6# it under the terms of the GNU General Public License as published by
7# the Free Software Foundation, either version 3 of the License, or
8# (at your option) any later version.
9#
10# This program is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13# GNU General Public License for more details.
14#
15# You should have received a copy of the GNU General Public License
16# along with this program.  If not, see <https://www.gnu.org/licenses/>.
17
18AT_BANNER([[Counterexamples.]])
19
20# AT_BISON_CHECK_CEX(TREE, FLAT)
21# ------------------------------
22m4_define([AT_BISON_CHECK_CEX],
23[AT_KEYWORDS([cex])
24
25AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
26# FIXME: Avoid trailing white spaces.
27AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g;s/ *$//;' stderr]],
28         [], [$1])
29
30m4_pushdef([AT_SET_ENV_IF],
31           [[YYFLAT=1; export YYFLAT;]]m4_defn([AT_SET_ENV_IF]))
32AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
33AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g' stderr]],
34         [], [$2])
35m4_popdef([AT_SET_ENV_IF])
36
37])
38
39## --------------------- ##
40## Simple Unifying S/R.  ##
41## --------------------- ##
42
43AT_SETUP([Unifying S/R])
44
45AT_DATA([[input.y]],
46[[%token A B C
47%%
48s: a x | y c;
49a: A;
50c: C;
51x: B | B C;
52y: A | A B;
53]])
54
55AT_BISON_CHECK_CEX(
56[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
57input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
58  Example: A . B C
59  Shift derivation
60    s
61    `-> y         c
62        `-> A . B `-> C
63  Reduce derivation
64    s
65    `-> a       x
66        `-> A . `-> B C
67input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
68]],
69[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
70input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
71  Example           A . B C
72  Shift derivation  s -> [ y -> [ A . B ] c -> [ C ] ]
73  Reduce derivation s -> [ a -> [ A . ] x -> [ B C ] ]
74input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
75]])
76
77AT_CLEANUP
78
79## ------------------- ##
80## Deep Unifying S/R.  ##
81## ------------------- ##
82
83AT_SETUP([Deep Unifying S/R])
84
85AT_DATA([[input.y]],
86[[%token A B C
87%%
88s: ac | a bc;
89ac: A ac C | b;
90b: B | B b;
91a: A | A a;
92bc: B bc C | B C;
93]])
94
95AT_BISON_CHECK_CEX(
96[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
97input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
98  Example: A . B C
99  Shift derivation
100    s
101    `-> ac
102        `-> A ac          C
103              `-> b
104                  `-> . B
105  Reduce derivation
106    s
107    `-> a       bc
108        `-> A . `-> B C
109input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
110  Example: A A . B B C C
111  Shift derivation
112    s
113    `-> ac
114        `-> A ac                        C
115              `-> A ac                C
116                    `-> b
117                        `-> . b
118                              `-> B B
119  Reduce derivation
120    s
121    `-> a             bc
122        `-> A a       `-> B bc      C
123              `-> A .       `-> B C
124input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
125]],
126[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
127input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
128  Example           A . B C
129  Shift derivation  s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ]
130  Reduce derivation s -> [ a -> [ A . ] bc -> [ B C ] ]
131input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
132  Example           A A . B B C C
133  Shift derivation  s -> [ ac -> [ A ac -> [ A ac -> [ b -> [ . b -> [ B B ] ] ] C ] C ] ]
134  Reduce derivation s -> [ a -> [ A a -> [ A . ] ] bc -> [ B bc -> [ B C ] C ] ]
135input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
136]])
137
138AT_CLEANUP
139
140## ------------------------------------ ##
141## S/R Conflict with Nullable Symbols.  ##
142## ------------------------------------ ##
143
144AT_SETUP([S/R Conflict with Nullable Symbols])
145
146AT_DATA([[input.y]],
147[[%token A B X Y
148%%
149s: ax by | A xby;
150ax: A x;
151x: %empty | X x;
152by: B y;
153y: %empty | Y y;
154xby: B | X xby Y;
155]])
156
157AT_BISON_CHECK_CEX(
158[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
159input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
160  Example: A . B
161  Shift derivation
162    s
163    `-> A xby
164          `-> . B
165  Reduce derivation
166    s
167    `-> ax          by
168        `-> A x     `-> B y
169              `-> .       `-> %empty
170input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
171  First example: A X . B Y $end
172  Shift derivation
173    $accept
174    `-> s                     $end
175        `-> A xby
176              `-> X xby     Y
177                    `-> . B
178  Second example: A X . B y $end
179  Reduce derivation
180    $accept
181    `-> s                             $end
182        `-> ax                by
183            `-> A x           `-> B y
184                  `-> X x
185                        `-> .
186input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
187]],
188[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
189input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
190  Example           A . B
191  Shift derivation  s -> [ A xby -> [ . B ] ]
192  Reduce derivation s -> [ ax -> [ A x -> [ . ] ] by -> [ B y -> [ ] ] ]
193input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
194  First example     A X . B Y $end
195  Shift derivation  $accept -> [ s -> [ A xby -> [ X xby -> [ . B ] Y ] ] $end ]
196  Second example    A X . B y $end
197  Reduce derivation $accept -> [ s -> [ ax -> [ A x -> [ X x -> [ . ] ] ] by -> [ B y ] ] $end ]
198input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
199]])
200
201AT_CLEANUP
202
203## ---------------------------- ##
204## Non-unifying Ambiguous S/R.  ##
205## ---------------------------- ##
206
207AT_SETUP([Non-unifying Ambiguous S/R])
208
209AT_DATA([[input.y]],
210[[%token A B C D E
211%%
212g: s | x;
213s: A x E | A x D E;
214x: b cd | bc;
215b: B;
216cd: C D;
217bc: B C;
218]])
219
220AT_BISON_CHECK_CEX(
221[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
222input.y: warning: shift/reduce conflict on token C [-Wcounterexamples]
223  First example: B . C $end
224  Shift derivation
225    $accept
226    `-> g                 $end
227        `-> x
228            `-> bc
229                `-> B . C
230  Second example: B . C D $end
231  Reduce derivation
232    $accept
233    `-> g                       $end
234        `-> x
235            `-> b       cd
236                `-> B . `-> C D
237input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
238]],
239[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
240input.y: warning: shift/reduce conflict on token C [-Wcounterexamples]
241  First example     B . C $end
242  Shift derivation  $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ]
243  Second example    B . C D $end
244  Reduce derivation $accept -> [ g -> [ x -> [ b -> [ B . ] cd -> [ C D ] ] ] $end ]
245input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
246]])
247
248AT_CLEANUP
249
250## ------------------------------ ##
251## Non-unifying Unambiguous S/R.  ##
252## ------------------------------ ##
253
254AT_SETUP([Non-unifying Unambiguous S/R])
255
256AT_DATA([[input.y]],
257[[%token A B
258%%
259s: t | s t;
260t: x | y;
261x: A;
262y: A A B;
263]])
264
265AT_BISON_CHECK_CEX(
266[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
267input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
268  First example: A . A B $end
269  Shift derivation
270    $accept
271    `-> s                   $end
272        `-> t
273            `-> y
274                `-> A . A B
275  Second example: A . A $end
276  Reduce derivation
277    $accept
278    `-> s                             $end
279        `-> s               t
280            `-> t           `-> x
281                `-> x           `-> A
282                    `-> A .
283]],
284[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
285input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
286  First example     A . A B $end
287  Shift derivation  $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ]
288  Second example    A . A $end
289  Reduce derivation $accept -> [ s -> [ s -> [ t -> [ x -> [ A . ] ] ] t -> [ x -> [ A ] ] ] $end ]
290]])
291
292AT_CLEANUP
293
294## ----------------------- ##
295## S/R after first token.  ##
296## ----------------------- ##
297
298AT_SETUP([S/R after first token])
299
300AT_DATA([[input.y]],
301[[%token A B X Y
302%%
303a: r t | s;
304r: b;
305b: B;
306t: A xx | A x xy;
307s: b A xx y;
308x: X;
309xx: X X;
310xy: X Y;
311y: Y;
312]])
313
314AT_BISON_CHECK_CEX(
315[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
316input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
317  Example: b . A X X Y
318  Shift derivation
319    a
320    `-> s
321        `-> b . xx        y
322                `-> A X X `-> Y
323  Reduce derivation
324    a
325    `-> r       t
326        `-> b . `-> A x     xy
327                      `-> X `-> X Y
328input.y: warning: shift/reduce conflict on token X [-Wcounterexamples]
329  First example: A X . X
330  Shift derivation
331    a
332    `-> t
333        `-> A xx
334              `-> X . X
335  Second example: X . X xy
336  Reduce derivation
337    a
338    `-> x       t
339        `-> X . `-> X xy
340input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
341input.y:8.4: warning: rule useless in parser due to conflicts [-Wother]
342]],
343[[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
344input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
345  Example           b . A X X Y
346  Shift derivation  a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ]
347  Reduce derivation a -> [ r -> [ b . ] t -> [ A x -> [ X ] xy -> [ X Y ] ] ]
348input.y: warning: shift/reduce conflict on token X [-Wcounterexamples]
349  First example     A X . X
350  Shift derivation  a -> [ t -> [ A xx -> [ X . X ] ] ]
351  Second example    X . X xy
352  Reduce derivation a -> [ x -> [ X . ] t -> [ X xy ] ]
353input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
354input.y:8.4: warning: rule useless in parser due to conflicts [-Wother]
355]])
356
357AT_CLEANUP
358
359## ----------------------------- ##
360## Unifying R/R counterexample.  ##
361## ----------------------------- ##
362
363AT_SETUP([Unifying R/R counterexample])
364
365AT_DATA([[input.y]],
366[[%token A
367%%
368a : A b ;
369b : A | b;
370]])
371
372AT_BISON_CHECK_CEX(
373[[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
374input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
375  Example: A b .
376  First reduce derivation
377    a
378    `-> A b .
379  Second reduce derivation
380    a
381    `-> A b
382          `-> b .
383input.y:4.9: warning: rule useless in parser due to conflicts [-Wother]
384]],
385[[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
386input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
387  Example                  A b .
388  First reduce derivation  a -> [ A b . ]
389  Second reduce derivation a -> [ A b -> [ b . ] ]
390input.y:4.9: warning: rule useless in parser due to conflicts [-Wother]
391]])
392
393AT_CLEANUP
394
395## --------------------------------- ##
396## Non-unifying R/R LR(1) conflict.  ##
397## --------------------------------- ##
398
399AT_SETUP([Non-unifying R/R LR(1) conflict])
400
401AT_DATA([[input.y]],
402[[%token A B C D
403%%
404s: a A | B a C | b C | B b A;
405a: D;
406b: D;
407]])
408
409AT_BISON_CHECK_CEX(
410[[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
411input.y: warning: reduce/reduce conflict on tokens A, C [-Wcounterexamples]
412  First example: D . A $end
413  First reduce derivation
414    $accept
415    `-> s             $end
416        `-> a       A
417            `-> D .
418  Second example: B D . A $end
419  Second reduce derivation
420    $accept
421    `-> s               $end
422        `-> B b       A
423              `-> D .
424input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
425]],
426[[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
427input.y: warning: reduce/reduce conflict on tokens A, C [-Wcounterexamples]
428  First example            D . A $end
429  First reduce derivation  $accept -> [ s -> [ a -> [ D . ] A ] $end ]
430  Second example           B D . A $end
431  Second reduce derivation $accept -> [ s -> [ B b -> [ D . ] A ] $end ]
432input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
433]])
434
435AT_CLEANUP
436
437## --------------------------------- ##
438## Non-unifying R/R LR(2) conflict.  ##
439## --------------------------------- ##
440
441AT_SETUP([Non-unifying R/R LR(2) conflict])
442
443AT_DATA([[input.y]],
444[[%token H J K X
445%%
446s: a J;
447a: H i;
448i: X | i J K;
449]])
450
451AT_BISON_CHECK_CEX(
452[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
453input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
454time limit exceeded: XXX
455  First example: H i . J K $end
456  Shift derivation
457    $accept
458    `-> a                 $end
459        `-> H i
460              `-> i . J K
461  Second example: H i . J $end
462  Reduce derivation
463    $accept
464    `-> s               $end
465        `-> a         J
466            `-> H i .
467input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
468]],
469[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
470input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
471time limit exceeded: XXX
472  First example     H i . J K $end
473  Shift derivation  $accept -> [ a -> [ H i -> [ i . J K ] ] $end ]
474  Second example    H i . J $end
475  Reduce derivation $accept -> [ s -> [ a -> [ H i . ] J ] $end ]
476input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
477]])
478
479AT_CLEANUP
480
481## -------------------- ##
482## Cex Search Prepend.  ##
483## -------------------- ##
484
485# Tests prepend steps in uniying counterexample
486# graph search
487
488AT_SETUP([Cex Search Prepend])
489
490AT_DATA([[input.y]],
491[[%token N A B C D
492%%
493s: n | n C;
494n: N n D | N n C | N a B | N b;
495a: A;
496b: A B C | A B D;
497]])
498
499AT_BISON_CHECK_CEX(
500[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
501input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
502  Example: N A . B C
503  Shift derivation
504    s
505    `-> n
506        `-> N b
507              `-> A . B C
508  Reduce derivation
509    s
510    `-> n               C
511        `-> N a       B
512              `-> A .
513input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
514  Example: N N A . B D C
515  Shift derivation
516    s
517    `-> n
518        `-> N n                 C
519              `-> N b
520                    `-> A . B D
521  Reduce derivation
522    s
523    `-> n                       C
524        `-> N n               D
525              `-> N a       B
526                    `-> A .
527input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
528]],
529[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
530input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
531  Example           N A . B C
532  Shift derivation  s -> [ n -> [ N b -> [ A . B C ] ] ]
533  Reduce derivation s -> [ n -> [ N a -> [ A . ] B ] C ]
534input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
535  Example           N N A . B D C
536  Shift derivation  s -> [ n -> [ N n -> [ N b -> [ A . B D ] ] C ] ]
537  Reduce derivation s -> [ n -> [ N n -> [ N a -> [ A . ] B ] D ] C ]
538input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
539]])
540
541AT_CLEANUP
542
543## ------------------- ##
544## R/R cex with prec.  ##
545## ------------------- ##
546
547# Tests that counterexamples containing rules using
548# precedence/associativity directives work.
549
550AT_SETUP([R/R cex with prec])
551
552AT_DATA([[input.y]],
553[[%left b
554%right c
555%%
556S: B C | C B;
557A : B  | C  | %empty;
558B : A b A;
559C : A c A;
560]])
561
562AT_BISON_CHECK_CEX(
563[[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
564input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
565  Example: B . b c
566  First reduce derivation
567    S
568    `-> B                        C
569        `-> A       b A          `-> A          c A
570            `-> B .   `-> %empty     `-> %empty   `-> %empty
571  Second reduce derivation
572    S
573    `-> B C
574          `-> A                          c A
575              `-> B                        `-> %empty
576                  `-> A     b A
577                      `-> .   `-> %empty
578input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
579  Example: C . c b
580  First reduce derivation
581    S
582    `-> C                        B
583        `-> A       c A          `-> A          b A
584            `-> C .   `-> %empty     `-> %empty   `-> %empty
585  Second reduce derivation
586    S
587    `-> C B
588          `-> A                          b A
589              `-> C                        `-> %empty
590                  `-> A     c A
591                      `-> .   `-> %empty
592]],
593[[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
594input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
595  Example                  B . b c
596  First reduce derivation  S -> [ B -> [ A -> [ B . ] b A -> [ ] ] C -> [ A -> [ ] c A -> [ ] ] ]
597  Second reduce derivation S -> [ B C -> [ A -> [ B -> [ A -> [ . ] b A -> [ ] ] ] c A -> [ ] ] ]
598input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
599  Example                  C . c b
600  First reduce derivation  S -> [ C -> [ A -> [ C . ] c A -> [ ] ] B -> [ A -> [ ] b A -> [ ] ] ]
601  Second reduce derivation S -> [ C B -> [ A -> [ C -> [ A -> [ . ] c A -> [ ] ] ] b A -> [ ] ] ]
602]])
603
604AT_CLEANUP
605
606## ------------------- ##
607## Null nonterminals.  ##
608## ------------------- ##
609
610AT_SETUP([Null nonterminals])
611
612AT_DATA([[input.y]],
613[[%token A
614%%
615a : b d | c d ;
616b : ;
617c : ;
618d : a | c A | d;
619]])
620
621AT_BISON_CHECK_CEX(
622[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
623input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
624input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
625  First example: . c A A $end
626  First reduce derivation
627    $accept
628    `-> a                   $end
629        `-> b     d
630            `-> . `-> c A A
631  Second example: . c A A $end
632  Second reduce derivation
633    $accept
634    `-> a                   $end
635        `-> c     d
636            `-> . `-> c A A
637input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
638time limit exceeded: XXX
639  First example: b . c A A $end
640  First reduce derivation
641    $accept
642    `-> a                             $end
643        `-> b d
644              `-> a
645                  `-> b     d
646                      `-> . `-> c A A
647  Second example: b . A $end
648  Second reduce derivation
649    $accept
650    `-> a                 $end
651        `-> b d
652              `-> c     A
653                  `-> .
654input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
655time limit exceeded: XXX
656  First example: c . c A A $end
657  First reduce derivation
658    $accept
659    `-> a                             $end
660        `-> c d
661              `-> a
662                  `-> b     d
663                      `-> . `-> c A A
664  Second example: c . A $end
665  Second reduce derivation
666    $accept
667    `-> a                 $end
668        `-> c d
669              `-> c     A
670                  `-> .
671input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
672time limit exceeded: XXX
673  First example: b c . A
674  Shift derivation
675    a
676    `-> b d
677          `-> c . A
678  Second example: b c . c A A $end
679  Reduce derivation
680    $accept
681    `-> a                                       $end
682        `-> b d
683              `-> a
684                  `-> c d
685                        `-> a
686                            `-> b     d
687                                `-> . `-> c A A
688input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
689  First example: b c . c A A $end
690  First reduce derivation
691    $accept
692    `-> a                                       $end
693        `-> b d
694              `-> a
695                  `-> c d
696                        `-> a
697                            `-> b     d
698                                `-> . `-> c A A
699  Second example: b c . A $end
700  Second reduce derivation
701    $accept
702    `-> a                           $end
703        `-> b d
704              `-> a
705                  `-> c d
706                        `-> c     A
707                            `-> .
708input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
709  First example: b c . A
710  Shift derivation
711    a
712    `-> b d
713          `-> c . A
714  Second example: b c . A $end
715  Reduce derivation
716    $accept
717    `-> a                           $end
718        `-> b d
719              `-> a
720                  `-> c d
721                        `-> c     A
722                            `-> .
723input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
724  Example: b d .
725  First reduce derivation
726    a
727    `-> b d .
728  Second reduce derivation
729    a
730    `-> b d
731          `-> d .
732input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
733  Example: c d .
734  First reduce derivation
735    a
736    `-> c d .
737  Second reduce derivation
738    a
739    `-> c d
740          `-> d .
741input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
742input.y:6.15: warning: rule useless in parser due to conflicts [-Wother]
743]],
744[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
745input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
746input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
747  First example            . c A A $end
748  First reduce derivation  $accept -> [ a -> [ b -> [ . ] d -> [ c A A ] ] $end ]
749  Second example           . c A A $end
750  Second reduce derivation $accept -> [ a -> [ c -> [ . ] d -> [ c A A ] ] $end ]
751input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
752time limit exceeded: XXX
753  First example            b . c A A $end
754  First reduce derivation  $accept -> [ a -> [ b d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] $end ]
755  Second example           b . A $end
756  Second reduce derivation $accept -> [ a -> [ b d -> [ c -> [ . ] A ] ] $end ]
757input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
758time limit exceeded: XXX
759  First example            c . c A A $end
760  First reduce derivation  $accept -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] $end ]
761  Second example           c . A $end
762  Second reduce derivation $accept -> [ a -> [ c d -> [ c -> [ . ] A ] ] $end ]
763input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
764time limit exceeded: XXX
765  First example     b c . A
766  Shift derivation  a -> [ b d -> [ c . A ] ]
767  Second example    b c . c A A $end
768  Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] ] ] $end ]
769input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
770  First example            b c . c A A $end
771  First reduce derivation  $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] ] ] $end ]
772  Second example           b c . A $end
773  Second reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ] A ] ] ] ] $end ]
774input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
775  First example     b c . A
776  Shift derivation  a -> [ b d -> [ c . A ] ]
777  Second example    b c . A $end
778  Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ] A ] ] ] ] $end ]
779input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
780  Example                  b d .
781  First reduce derivation  a -> [ b d . ]
782  Second reduce derivation a -> [ b d -> [ d . ] ]
783input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
784  Example                  c d .
785  First reduce derivation  a -> [ c d . ]
786  Second reduce derivation a -> [ c d -> [ d . ] ]
787input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
788input.y:6.15: warning: rule useless in parser due to conflicts [-Wother]
789]])
790
791AT_CLEANUP
792
793## --------------------------- ##
794## Non-unifying Prefix Share.  ##
795## --------------------------- ##
796
797AT_SETUP([Non-unifying Prefix Share])
798
799# Tests for a counterexample which should start its derivation
800# at a shared symbol rather than the start symbol.
801
802AT_DATA([[input.y]],
803[[%token H J
804%%
805s: a | a J;
806a: H i J J
807i: %empty | i J;
808]])
809
810AT_BISON_CHECK_CEX(
811[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
812input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
813  Example: H i J . J J
814  Shift derivation
815    s
816    `-> a             J
817        `-> H i J . J
818  Reduce derivation
819    s
820    `-> a
821        `-> H i         J J
822              `-> i J .
823input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
824]],
825[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
826input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
827  Example           H i J . J J
828  Shift derivation  s -> [ a -> [ H i J . J ] J ]
829  Reduce derivation s -> [ a -> [ H i -> [ i J . ] J J ] ]
830input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
831]])
832
833AT_CLEANUP
834
835## -------------------- ##
836## Deep Null Unifying.  ##
837## ---------------------##
838
839# Tests that nested nullable nonterminals
840# are derived correctly.
841
842AT_SETUP([Deep Null Unifying])
843
844AT_DATA([[input.y]],
845[[%token A D
846%%
847s: A a d | A a a d;
848a: b;
849b: c
850c: %empty
851d: D;
852]])
853
854AT_BISON_CHECK_CEX(
855[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
856input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
857  Example: A a . D
858  Shift derivation
859    s
860    `-> A a d
861            `-> . D
862  Reduce derivation
863    s
864    `-> A a a             d
865            `-> b         `-> D
866                `-> c
867                    `-> .
868]],
869[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
870input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
871  Example           A a . D
872  Shift derivation  s -> [ A a d -> [ . D ] ]
873  Reduce derivation s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] ]
874]])
875
876AT_CLEANUP
877
878## ------------------------ ##
879## Deep Null Non-unifying.  ##
880## -------------------------##
881
882# Tests that expand_to_conflict works with nullable sybols
883
884AT_SETUP([Deep Null Non-unifying])
885
886AT_DATA([[input.y]],
887[[%token A D E
888%%
889s: A a d | A a a d E;
890a: b;
891b: c
892c: %empty
893d: D;
894]])
895
896AT_BISON_CHECK_CEX(
897[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
898input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
899  First example: A a . D $end
900  Shift derivation
901    $accept
902    `-> s               $end
903        `-> A a d
904                `-> . D
905  Second example: A a . D E $end
906  Reduce derivation
907    $accept
908    `-> s                             $end
909        `-> A a a             d     E
910                `-> b         `-> D
911                    `-> c
912                        `-> .
913]],
914[[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
915input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
916  First example     A a . D $end
917  Shift derivation  $accept -> [ s -> [ A a d -> [ . D ] ] $end ]
918  Second example    A a . D E $end
919  Reduce derivation $accept -> [ s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] E ] $end ]
920]])
921
922AT_CLEANUP
923