]> git.saurik.com Git - bison.git/blob - tests/reduce.at
Update from GFDL GFDL 1.2 to 1.3.
[bison.git] / tests / reduce.at
1 # Exercising Bison Grammar Reduction. -*- Autotest -*-
2 # Copyright (C) 2001-2002, 2007-2010 Free Software Foundation, Inc.
3
4 # This program is free software: you can redistribute it and/or modify
5 # it under the terms of the GNU General Public License as published by
6 # the Free Software Foundation, either version 3 of the License, or
7 # (at your option) any later version.
8 #
9 # This program is distributed in the hope that it will be useful,
10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 # GNU General Public License for more details.
13 #
14 # You should have received a copy of the GNU General Public License
15 # along with this program. If not, see <http://www.gnu.org/licenses/>.
16
17 AT_BANNER([[Grammar Reduction.]])
18
19
20 ## ------------------- ##
21 ## Useless Terminals. ##
22 ## ------------------- ##
23
24 AT_SETUP([Useless Terminals])
25
26 AT_DATA([[input.y]],
27 [[%verbose
28 %output "input.c"
29
30 %token useless1
31 %token useless2
32 %token useless3
33 %token useless4
34 %token useless5
35 %token useless6
36 %token useless7
37 %token useless8
38 %token useless9
39
40 %token useful
41 %%
42 exp: useful;
43 ]])
44
45 AT_BISON_CHECK([[input.y]])
46
47 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
48 [[Terminals unused in grammar
49 useless1
50 useless2
51 useless3
52 useless4
53 useless5
54 useless6
55 useless7
56 useless8
57 useless9
58 ]])
59
60 AT_CLEANUP
61
62
63
64 ## ---------------------- ##
65 ## Useless Nonterminals. ##
66 ## ---------------------- ##
67
68 AT_SETUP([Useless Nonterminals])
69
70 AT_DATA([[input.y]],
71 [[%verbose
72 %output "input.c"
73
74 %nterm useless1
75 %nterm useless2
76 %nterm useless3
77 %nterm useless4
78 %nterm useless5
79 %nterm useless6
80 %nterm useless7
81 %nterm useless8
82 %nterm useless9
83
84 %token useful
85 %%
86 exp: useful;
87 ]])
88
89 AT_BISON_CHECK([[input.y]], 0, [],
90 [[input.y: warning: 9 nonterminals useless in grammar
91 input.y:4.8-15: warning: nonterminal useless in grammar: useless1
92 input.y:5.8-15: warning: nonterminal useless in grammar: useless2
93 input.y:6.8-15: warning: nonterminal useless in grammar: useless3
94 input.y:7.8-15: warning: nonterminal useless in grammar: useless4
95 input.y:8.8-15: warning: nonterminal useless in grammar: useless5
96 input.y:9.8-15: warning: nonterminal useless in grammar: useless6
97 input.y:10.8-15: warning: nonterminal useless in grammar: useless7
98 input.y:11.8-15: warning: nonterminal useless in grammar: useless8
99 input.y:12.8-15: warning: nonterminal useless in grammar: useless9
100 ]])
101
102 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
103 [[Nonterminals useless in grammar
104 useless1
105 useless2
106 useless3
107 useless4
108 useless5
109 useless6
110 useless7
111 useless8
112 useless9
113 ]])
114
115 AT_CLEANUP
116
117
118
119 ## --------------- ##
120 ## Useless Rules. ##
121 ## --------------- ##
122
123 AT_SETUP([Useless Rules])
124
125 AT_KEYWORDS([report])
126
127 AT_DATA([[input.y]],
128 [[%verbose
129 %output "input.c"
130 %token useful
131 %%
132 exp: useful;
133 useless1: '1';
134 useless2: '2';
135 useless3: '3';
136 useless4: '4';
137 useless5: '5';
138 useless6: '6';
139 useless7: '7';
140 useless8: '8';
141 useless9: '9';
142 ]])
143
144 AT_BISON_CHECK([[input.y]], 0, [],
145 [[input.y: warning: 9 nonterminals useless in grammar
146 input.y: warning: 9 rules useless in grammar
147 input.y:6.1-8: warning: nonterminal useless in grammar: useless1
148 input.y:7.1-8: warning: nonterminal useless in grammar: useless2
149 input.y:8.1-8: warning: nonterminal useless in grammar: useless3
150 input.y:9.1-8: warning: nonterminal useless in grammar: useless4
151 input.y:10.1-8: warning: nonterminal useless in grammar: useless5
152 input.y:11.1-8: warning: nonterminal useless in grammar: useless6
153 input.y:12.1-8: warning: nonterminal useless in grammar: useless7
154 input.y:13.1-8: warning: nonterminal useless in grammar: useless8
155 input.y:14.1-8: warning: nonterminal useless in grammar: useless9
156 input.y:6.11-13: warning: rule useless in grammar: useless1: '1'
157 input.y:7.11-13: warning: rule useless in grammar: useless2: '2'
158 input.y:8.11-13: warning: rule useless in grammar: useless3: '3'
159 input.y:9.11-13: warning: rule useless in grammar: useless4: '4'
160 input.y:10.11-13: warning: rule useless in grammar: useless5: '5'
161 input.y:11.11-13: warning: rule useless in grammar: useless6: '6'
162 input.y:12.11-13: warning: rule useless in grammar: useless7: '7'
163 input.y:13.11-13: warning: rule useless in grammar: useless8: '8'
164 input.y:14.11-13: warning: rule useless in grammar: useless9: '9'
165 ]])
166
167 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
168 [[Nonterminals useless in grammar
169 useless1
170 useless2
171 useless3
172 useless4
173 useless5
174 useless6
175 useless7
176 useless8
177 useless9
178 Terminals unused in grammar
179 '1'
180 '2'
181 '3'
182 '4'
183 '5'
184 '6'
185 '7'
186 '8'
187 '9'
188 Rules useless in grammar
189 2 useless1: '1'
190 3 useless2: '2'
191 4 useless3: '3'
192 5 useless4: '4'
193 6 useless5: '5'
194 7 useless6: '6'
195 8 useless7: '7'
196 9 useless8: '8'
197 10 useless9: '9'
198 ]])
199
200 AT_CLEANUP
201
202
203
204 ## ------------------- ##
205 ## Reduced Automaton. ##
206 ## ------------------- ##
207
208 # Check that the automaton is that as the for the grammar reduced by
209 # hand.
210
211 AT_SETUP([Reduced Automaton])
212
213 AT_KEYWORDS([report])
214
215 # The non reduced grammar.
216 # ------------------------
217 AT_DATA([[not-reduced.y]],
218 [[/* A useless token. */
219 %token useless_token
220 /* A useful one. */
221 %token useful
222 %verbose
223 %output "not-reduced.c"
224
225 %%
226
227 exp: useful { /* A useful action. */ }
228 | non_productive { /* A non productive action. */ }
229 ;
230
231 not_reachable: useful { /* A not reachable action. */ }
232 ;
233
234 non_productive: non_productive useless_token
235 { /* Another non productive action. */ }
236 ;
237 %%
238 ]])
239
240 AT_BISON_CHECK([[not-reduced.y]], 0, [],
241 [[not-reduced.y: warning: 2 nonterminals useless in grammar
242 not-reduced.y: warning: 3 rules useless in grammar
243 not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable
244 not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive
245 not-reduced.y:11.6-57: warning: rule useless in grammar: exp: non_productive
246 not-reduced.y:14.16-56: warning: rule useless in grammar: not_reachable: useful
247 not-reduced.y:17.17-18.63: warning: rule useless in grammar: non_productive: non_productive useless_token
248 ]])
249
250 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0,
251 [[Nonterminals useless in grammar
252 not_reachable
253 non_productive
254 Terminals unused in grammar
255 useless_token
256 Rules useless in grammar
257 2 exp: non_productive
258 3 not_reachable: useful
259 4 non_productive: non_productive useless_token
260 ]])
261
262 # The reduced grammar.
263 # --------------------
264 AT_DATA([[reduced.y]],
265 [[/* A useless token. */
266 %token useless_token
267 /* A useful one. */
268 %token useful
269 %verbose
270 %output "reduced.c"
271
272 %%
273
274 exp: useful { /* A useful action. */ }
275 // | non_productive { /* A non productive action. */ } */
276 ;
277
278 //not_reachable: useful { /* A not reachable action. */ }
279 // ;
280
281 //non_productive: non_productive useless_token
282 // { /* Another non productive action. */ }
283 // ;
284 %%
285 ]])
286
287 AT_BISON_CHECK([[reduced.y]])
288
289 # Comparing the parsers.
290 cp reduced.c expout
291 AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout])
292
293 AT_CLEANUP
294
295
296
297 ## ------------------- ##
298 ## Underivable Rules. ##
299 ## ------------------- ##
300
301 AT_SETUP([Underivable Rules])
302
303 AT_KEYWORDS([report])
304
305 AT_DATA([[input.y]],
306 [[%verbose
307 %output "input.c"
308 %token useful
309 %%
310 exp: useful | underivable;
311 underivable: indirection;
312 indirection: underivable;
313 ]])
314
315 AT_BISON_CHECK([[input.y]], 0, [],
316 [[input.y: warning: 2 nonterminals useless in grammar
317 input.y: warning: 3 rules useless in grammar
318 input.y:5.15-25: warning: nonterminal useless in grammar: underivable
319 input.y:6.14-24: warning: nonterminal useless in grammar: indirection
320 input.y:5.15-25: warning: rule useless in grammar: exp: underivable
321 input.y:6.14-24: warning: rule useless in grammar: underivable: indirection
322 input.y:7.14-24: warning: rule useless in grammar: indirection: underivable
323 ]])
324
325 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
326 [[Nonterminals useless in grammar
327 underivable
328 indirection
329 Rules useless in grammar
330 2 exp: underivable
331 3 underivable: indirection
332 4 indirection: underivable
333 ]])
334
335 AT_CLEANUP
336
337
338
339 ## ---------------- ##
340 ## Empty Language. ##
341 ## ---------------- ##
342
343 AT_SETUP([Empty Language])
344
345 AT_DATA([[input.y]],
346 [[%output "input.c"
347 %%
348 exp: exp;
349 ]])
350
351 AT_BISON_CHECK([[input.y]], 1, [],
352 [[input.y: warning: 2 nonterminals useless in grammar
353 input.y: warning: 2 rules useless in grammar
354 input.y:3.1-3: fatal error: start symbol exp does not derive any sentence
355 ]])
356
357 AT_CLEANUP
358
359
360
361 ## ----------------- ##
362 ## %define lr.type. ##
363 ## ----------------- ##
364
365 # AT_TEST_LR_TYPE(DESCRIPTION,
366 # DECLS, GRAMMAR, INPUT,
367 # BISON-STDERR, TABLES,
368 # [OTHER-CHECKS],
369 # [PARSER-EXIT-VALUE],
370 # [PARSER-STDOUT], [PARSER-STDERR])
371 # -------------------------------------------------
372 m4_define([AT_TEST_LR_TYPE],
373 [
374 AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1],
375 [[LALR]], [[]],
376 [$2], m4_shiftn(2, $@))
377 AT_TEST_TABLES_AND_PARSE([[%define lr.type lalr: ]$1],
378 [[LALR]], [[]],
379 [[%define lr.type lalr
380 ]$2],
381 m4_shiftn(2, $@))
382 AT_TEST_TABLES_AND_PARSE([[%define lr.type ielr: ]$1],
383 [[IELR]], [[]],
384 [[%define lr.type ielr
385 ]$2],
386 m4_shiftn(2, $@))
387 AT_TEST_TABLES_AND_PARSE([[%define lr.type canonical-lr: ]$1],
388 [[canonical LR]], [[]],
389 [[%define lr.type canonical-lr
390 ]$2],
391 m4_shiftn(2, $@))
392 ])
393
394 AT_TEST_LR_TYPE([[Single State Split]],
395 [[%left 'a'
396 // Conflict resolution renders state 12 unreachable for canonical LR(1). We
397 // keep it so that the paser table diff is easier to code.
398 %define lr.keep-unreachable-states]],
399 [[
400 S: 'a' A 'a' /* rule 1 */
401 | 'b' A 'b' /* rule 2 */
402 | 'c' c /* rule 3 */
403 ;
404
405 /* A conflict should appear after the first 'a' in rules 4 and 5 but only after
406 having shifted the first 'a' in rule 1. However, when LALR(1) merging is
407 chosen, the state containing that conflict is reused after having seen the
408 first 'b' in rule 2 and then the first 'a' in rules 4 and 5. In both cases,
409 because of the merged state, if the next token is an 'a', the %left forces a
410 reduction action with rule 5. In the latter case, only a shift is actually
411 grammatically correct. Thus, the parser would report a syntax error for the
412 grammatically correct sentence "baab" because it would encounter a syntax
413 error after that incorrect reduction.
414
415 Despite not being LALR(1), Menhir version 20070322 suffers from this problem
416 as well. It uses David Pager's weak compatibility test for merging states.
417 Bison and Menhir accept non-LR(1) grammars with conflict resolution. Pager
418 designed his algorithm only for LR(1) grammars. */
419 A: 'a' 'a' /* rule 4 */
420 | 'a' /* rule 5 */
421 ;
422
423 /* Rule 3, rule 6, and rule 7 ensure that Bison does not report rule 4 as
424 useless after conflict resolution. This proves that, even though LALR(1)
425 generates incorrect parser tables sometimes, Bison will not necessarily
426 produce any warning to help the user realize it. */
427 c: 'a' 'b' /* rule 6 */
428 | A /* rule 7 */
429 ;
430 ]],
431
432 dnl INPUT
433 [['b', 'a', 'a', 'b']],
434
435 dnl BISON-STDERR
436 [],
437
438 dnl TABLES
439 [[state 0
440
441 0 $accept: . S $end
442 1 S: . 'a' A 'a'
443 2 | . 'b' A 'b'
444 3 | . 'c' c
445
446 'a' shift, and go to state 1
447 'b' shift, and go to state 2
448 'c' shift, and go to state 3
449
450 S go to state 4
451
452
453 state 1
454
455 1 S: 'a' . A 'a'
456 4 A: . 'a' 'a'
457 5 | . 'a'
458
459 'a' shift, and go to state 5
460
461 A go to state 6
462
463
464 state 2
465
466 2 S: 'b' . A 'b'
467 4 A: . 'a' 'a'
468 5 | . 'a'
469
470 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[16]])[
471
472 A go to state 7
473
474
475 state 3
476
477 3 S: 'c' . c
478 4 A: . 'a' 'a'
479 5 | . 'a'
480 6 c: . 'a' 'b'
481 7 | . A
482
483 'a' shift, and go to state 8
484
485 A go to state 9
486 c go to state 10
487
488
489 state 4
490
491 0 $accept: S . $end
492
493 $end shift, and go to state 11
494
495
496 state 5
497
498 4 A: 'a' . 'a'
499 5 | 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
500
501 ]AT_COND_CASE([[canonical LR]], [['a']],
502 [[$default]])[ reduce using rule 5 (A)
503
504 Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
505
506
507 state 6
508
509 1 S: 'a' A . 'a'
510
511 'a' shift, and go to state 13
512
513
514 state 7
515
516 2 S: 'b' A . 'b'
517
518 'b' shift, and go to state 14
519
520
521 state 8
522
523 4 A: 'a' . 'a'
524 5 | 'a' . [$end]
525 6 c: 'a' . 'b'
526
527 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[17]],
528 [[12]])[
529 'b' shift, and go to state 15
530
531 ]AT_COND_CASE([[canonical LR]], [[$end]],
532 [[$default]])[ reduce using rule 5 (A)
533
534
535 state 9
536
537 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
538
539 ]AT_COND_CASE([[canonical LR]], [[$end]],
540 [[$default]])[ reduce using rule 7 (c)
541
542
543 state 10
544
545 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
546
547 ]AT_COND_CASE([[canonical LR]], [[$end]],
548 [[$default]])[ reduce using rule 3 (S)
549
550
551 state 11
552
553 0 $accept: S $end .
554
555 $default accept
556
557
558 state 12
559
560 4 A: 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
561
562 ]AT_COND_CASE([[canonical LR]], [['a']],
563 [[$default]])[ reduce using rule 4 (A)
564
565
566 state 13
567
568 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
569
570 ]AT_COND_CASE([[canonical LR]], [[$end]],
571 [[$default]])[ reduce using rule 1 (S)
572
573
574 state 14
575
576 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
577
578 ]AT_COND_CASE([[canonical LR]], [[$end]],
579 [[$default]])[ reduce using rule 2 (S)
580
581
582 state 15
583
584 6 c: 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
585
586 ]AT_COND_CASE([[canonical LR]], [[$end]],
587 [[$default]])[ reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
588 [[]], [[
589
590
591 state 16
592
593 4 A: 'a' . 'a'
594 5 | 'a' . ['b']
595
596 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[18]],
597 [[12]])[
598
599 ]AT_COND_CASE([[canonical LR]], [['b']],
600 [[$default]])[ reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
601
602
603 state 17
604
605 4 A: 'a' 'a' . [$end]
606
607 $end reduce using rule 4 (A)
608
609
610 state 18
611
612 4 A: 'a' 'a' . ['b']
613
614 'b' reduce using rule 4 (A)]])])[
615 ]],
616
617 dnl OTHER-CHECKS
618 [],
619
620 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
621 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
622 [],
623 [AT_COND_CASE([[LALR]],
624 [[syntax error
625 ]])])
626
627 AT_TEST_LR_TYPE([[Lane Split]],
628 [[%left 'a'
629 // Conflict resolution renders state 16 unreachable for canonical LR(1). We
630 // keep it so that the paser table diff is easier to code.
631 %define lr.keep-unreachable-states]],
632 [[
633 /* Similar to the last test case set but two states must be split. */
634 S: 'a' A 'a' /* rule 1 */
635 | 'b' A 'b' /* rule 2 */
636 | 'c' c /* rule 3 */
637 ;
638
639 A: 'a' 'a' 'a' /* rule 4 */
640 | 'a' 'a' /* rule 5 */
641 ;
642
643 c: 'a' 'a' 'b' /* rule 6 */
644 | A /* rule 7 */
645 ;
646 ]],
647
648 dnl INPUT
649 [['b', 'a', 'a', 'a', 'b']],
650
651 dnl BISON-STDERR
652 [],
653
654 dnl TABLES
655 [[state 0
656
657 0 $accept: . S $end
658 1 S: . 'a' A 'a'
659 2 | . 'b' A 'b'
660 3 | . 'c' c
661
662 'a' shift, and go to state 1
663 'b' shift, and go to state 2
664 'c' shift, and go to state 3
665
666 S go to state 4
667
668
669 state 1
670
671 1 S: 'a' . A 'a'
672 4 A: . 'a' 'a' 'a'
673 5 | . 'a' 'a'
674
675 'a' shift, and go to state 5
676
677 A go to state 6
678
679
680 state 2
681
682 2 S: 'b' . A 'b'
683 4 A: . 'a' 'a' 'a'
684 5 | . 'a' 'a'
685
686 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[18]])[
687
688 A go to state 7
689
690
691 state 3
692
693 3 S: 'c' . c
694 4 A: . 'a' 'a' 'a'
695 5 | . 'a' 'a'
696 6 c: . 'a' 'a' 'b'
697 7 | . A
698
699 'a' shift, and go to state 8
700
701 A go to state 9
702 c go to state 10
703
704
705 state 4
706
707 0 $accept: S . $end
708
709 $end shift, and go to state 11
710
711
712 state 5
713
714 4 A: 'a' . 'a' 'a'
715 5 | 'a' . 'a'
716
717 'a' shift, and go to state 12
718
719
720 state 6
721
722 1 S: 'a' A . 'a'
723
724 'a' shift, and go to state 13
725
726
727 state 7
728
729 2 S: 'b' A . 'b'
730
731 'b' shift, and go to state 14
732
733
734 state 8
735
736 4 A: 'a' . 'a' 'a'
737 5 | 'a' . 'a'
738 6 c: 'a' . 'a' 'b'
739
740 'a' shift, and go to state 15
741
742
743 state 9
744
745 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
746
747 ]AT_COND_CASE([[canonical LR]], [[$end]],
748 [[$default]])[ reduce using rule 7 (c)
749
750
751 state 10
752
753 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
754
755 ]AT_COND_CASE([[canonical LR]], [[$end]],
756 [[$default]])[ reduce using rule 3 (S)
757
758
759 state 11
760
761 0 $accept: S $end .
762
763 $default accept
764
765
766 state 12
767
768 4 A: 'a' 'a' . 'a'
769 5 | 'a' 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
770
771 ]AT_COND_CASE([[canonical LR]], [['a']],
772 [[$default]])[ reduce using rule 5 (A)
773
774 Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
775
776
777 state 13
778
779 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
780
781 ]AT_COND_CASE([[canonical LR]], [[$end]],
782 [[$default]])[ reduce using rule 1 (S)
783
784
785 state 14
786
787 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
788
789 ]AT_COND_CASE([[canonical LR]], [[$end]],
790 [[$default]])[ reduce using rule 2 (S)
791
792
793 state 15
794
795 4 A: 'a' 'a' . 'a'
796 5 | 'a' 'a' . [$end]
797 6 c: 'a' 'a' . 'b'
798
799 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[19]],
800 [[16]])[
801 'b' shift, and go to state 17
802
803 ]AT_COND_CASE([[canonical LR]], [[$end]],
804 [[$default]])[ reduce using rule 5 (A)
805
806
807 state 16
808
809 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
810
811 ]AT_COND_CASE([[canonical LR]], [['a']],
812 [[$default]])[ reduce using rule 4 (A)
813
814
815 state 17
816
817 6 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
818
819 ]AT_COND_CASE([[canonical LR]], [[$end]],
820 [[$default]])[ reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
821 [[]], [[
822
823
824 state 18
825
826 4 A: 'a' . 'a' 'a'
827 5 | 'a' . 'a'
828
829 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
830 [[19]])[
831
832
833 state 19]AT_COND_CASE([[canonical LR]], [[
834
835 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
836
837 ]AT_COND_CASE([[canonical LR]], [[$end]],
838 [[$default]])[ reduce using rule 4 (A)
839
840
841 state 20]])[
842
843 4 A: 'a' 'a' . 'a'
844 5 | 'a' 'a' . ['b']
845
846 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
847 [[16]])[
848
849 ]AT_COND_CASE([[canonical LR]], [['b']],
850 [[$default]])[ reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
851
852
853 state 21
854
855 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['b']]])[
856
857 ]AT_COND_CASE([[canonical LR]], [['b']],
858 [[$default]])[ reduce using rule 4 (A)]])])[
859 ]],
860
861 dnl OTHER-CHECKS
862 [],
863
864 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
865 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
866 [],
867 [AT_COND_CASE([[LALR]],
868 [[syntax error
869 ]])])
870
871 AT_TEST_LR_TYPE([[Complex Lane Split]],
872 [[%left 'a'
873 // Conflict resolution renders state 16 unreachable for canonical LR(1). We
874 // keep it so that the paser table diff is easier to code.
875 %define lr.keep-unreachable-states]],
876 [[
877 /* Similar to the last test case set but forseeing the S/R conflict from the
878 first state that must be split is becoming difficult. Imagine if B were
879 even more complex. Imagine if A had other RHS's ending in other
880 nonterminals. */
881 S: 'a' A 'a'
882 | 'b' A 'b'
883 | 'c' c
884 ;
885 A: 'a' 'a' B
886 ;
887 B: 'a'
888 | %prec 'a'
889 ;
890 c: 'a' 'a' 'b'
891 | A
892 ;
893 ]],
894
895 dnl INPUT
896 [['b', 'a', 'a', 'a', 'b']],
897
898 dnl BISON-STDERR
899 [],
900
901 dnl TABLES
902 [[state 0
903
904 0 $accept: . S $end
905 1 S: . 'a' A 'a'
906 2 | . 'b' A 'b'
907 3 | . 'c' c
908
909 'a' shift, and go to state 1
910 'b' shift, and go to state 2
911 'c' shift, and go to state 3
912
913 S go to state 4
914
915
916 state 1
917
918 1 S: 'a' . A 'a'
919 4 A: . 'a' 'a' B
920
921 'a' shift, and go to state 5
922
923 A go to state 6
924
925
926 state 2
927
928 2 S: 'b' . A 'b'
929 4 A: . 'a' 'a' B
930
931 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[19]])[
932
933 A go to state 7
934
935
936 state 3
937
938 3 S: 'c' . c
939 4 A: . 'a' 'a' B
940 7 c: . 'a' 'a' 'b'
941 8 | . A
942
943 'a' shift, and go to state 8
944
945 A go to state 9
946 c go to state 10
947
948
949 state 4
950
951 0 $accept: S . $end
952
953 $end shift, and go to state 11
954
955
956 state 5
957
958 4 A: 'a' . 'a' B
959
960 'a' shift, and go to state 12
961
962
963 state 6
964
965 1 S: 'a' A . 'a'
966
967 'a' shift, and go to state 13
968
969
970 state 7
971
972 2 S: 'b' A . 'b'
973
974 'b' shift, and go to state 14
975
976
977 state 8
978
979 4 A: 'a' . 'a' B
980 7 c: 'a' . 'a' 'b'
981
982 'a' shift, and go to state 15
983
984
985 state 9
986
987 8 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
988
989 ]AT_COND_CASE([[canonical LR]], [[$end]],
990 [[$default]])[ reduce using rule 8 (c)
991
992
993 state 10
994
995 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
996
997 ]AT_COND_CASE([[canonical LR]], [[$end]],
998 [[$default]])[ reduce using rule 3 (S)
999
1000
1001 state 11
1002
1003 0 $accept: S $end .
1004
1005 $default accept
1006
1007
1008 state 12
1009
1010 4 A: 'a' 'a' . B
1011 5 B: . 'a'
1012 6 | . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
1013
1014 ]AT_COND_CASE([[canonical LR]], [['a']],
1015 [[$default]])[ reduce using rule 6 (B)
1016
1017 B go to state 17
1018
1019 Conflict between rule 6 and token 'a' resolved as reduce (%left 'a').
1020
1021
1022 state 13
1023
1024 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1025
1026 ]AT_COND_CASE([[canonical LR]], [[$end]],
1027 [[$default]])[ reduce using rule 1 (S)
1028
1029
1030 state 14
1031
1032 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1033
1034 ]AT_COND_CASE([[canonical LR]], [[$end]],
1035 [[$default]])[ reduce using rule 2 (S)
1036
1037
1038 state 15
1039
1040 4 A: 'a' 'a' . B
1041 5 B: . 'a'
1042 6 | . [$end]
1043 7 c: 'a' 'a' . 'b'
1044
1045 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1046 [[16]])[
1047 'b' shift, and go to state 18
1048
1049 ]AT_COND_CASE([[canonical LR]], [[$end]],
1050 [[$default]])[ reduce using rule 6 (B)
1051
1052 B go to state ]AT_COND_CASE([[canonical LR]], [[21]], [[17]])[
1053
1054
1055 state 16
1056
1057 5 B: 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
1058
1059 ]AT_COND_CASE([[canonical LR]], [['a']],
1060 [[$default]])[ reduce using rule 5 (B)
1061
1062
1063 state 17
1064
1065 4 A: 'a' 'a' B .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
1066
1067 ]AT_COND_CASE([[canonical LR]], [['a']],
1068 [[$default]])[ reduce using rule 4 (A)
1069
1070
1071 state 18
1072
1073 7 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1074
1075 ]AT_COND_CASE([[canonical LR]], [[$end]],
1076 [[$default]])[ reduce using rule 7 (c)]AT_COND_CASE([[LALR]], [], [[
1077
1078
1079 state 19
1080
1081 4 A: 'a' . 'a' B
1082
1083 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[22]],
1084 [[20]])[
1085
1086
1087 state 20]AT_COND_CASE([[canonical LR]], [[
1088
1089 5 B: 'a' . [$end]
1090
1091 $end reduce using rule 5 (B)
1092
1093
1094 state 21
1095
1096 4 A: 'a' 'a' B . [$end]
1097
1098 $end reduce using rule 4 (A)
1099
1100
1101 state 22]])[
1102
1103 4 A: 'a' 'a' . B
1104 5 B: . 'a'
1105 6 | . ['b']
1106
1107 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[23]],
1108 [[16]])[
1109
1110 ]AT_COND_CASE([[canonical LR]], [['b']],
1111 [[$default]])[ reduce using rule 6 (B)
1112
1113 B go to state ]AT_COND_CASE([[canonical LR]], [[24
1114
1115
1116 state 23
1117
1118 5 B: 'a' . ['b']
1119
1120 'b' reduce using rule 5 (B)
1121
1122
1123 state 24
1124
1125 4 A: 'a' 'a' B . ['b']
1126
1127 'b' reduce using rule 4 (A)]], [[17]])])[
1128 ]],
1129
1130 dnl OTHER-CHECKS
1131 [],
1132
1133 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1134 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1135 [],
1136 [AT_COND_CASE([[LALR]],
1137 [[syntax error
1138 ]])])
1139
1140 AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]],
1141 [[%define lr.keep-unreachable-states]],
1142 [[
1143 /* The partial state chart diagram below is for LALR(1). State 0 is the start
1144 state. States are iterated for successor construction in numerical order.
1145 Transitions are downwards.
1146
1147 State 13 has a R/R conflict that cannot be predicted by Bison's LR(1)
1148 algorithm using annotations alone. That is, when state 11's successor on
1149 'd' is merged with state 5 (which is originally just state 1's successor on
1150 'd'), state 5's successor on 'e' must then be changed because the resulting
1151 lookaheads that propagate to it now make it incompatible with state 8's
1152 successor on 'e'. In other words, state 13 must be split to avoid the
1153 conflict.
1154
1155 0
1156 / | \
1157 a / c| \ b
1158 1 3 2
1159 | | |
1160 d| |c | d
1161 | 11 |
1162 | | |
1163 \ /d |
1164 5 8
1165 \ |
1166 e \ / e
1167 13
1168 R/R
1169
1170 This grammar is designed carefully to make sure that, despite Bison's LR(1)
1171 algorithm's bread-first iteration of transitions to reconstruct states,
1172 state 11's successors are constructed after state 5's and state 8's.
1173 Otherwise (for example, if you remove the first 'c' in each of rules 6 and
1174 7), state 5's successor on 'e' would never be merged with state 8's, so the
1175 split of the resulting state 13 would never need to be performed. */
1176 S: 'a' A 'f'
1177 | 'a' B
1178 | 'b' A 'f'
1179 | 'b' B 'g'
1180 | 'b' 'd'
1181 | 'c' 'c' A 'g'
1182 | 'c' 'c' B
1183 ;
1184 A: 'd' 'e' ;
1185 B: 'd' 'e' ;
1186 ]],
1187
1188 dnl INPUT
1189 [['b', 'd', 'e', 'g']],
1190
1191 dnl BISON-STDERR
1192 [AT_COND_CASE([[LALR]],
1193 [[input.y: conflicts: 1 reduce/reduce
1194 ]], [])],
1195
1196 dnl TABLES
1197 [[state 0
1198
1199 0 $accept: . S $end
1200 1 S: . 'a' A 'f'
1201 2 | . 'a' B
1202 3 | . 'b' A 'f'
1203 4 | . 'b' B 'g'
1204 5 | . 'b' 'd'
1205 6 | . 'c' 'c' A 'g'
1206 7 | . 'c' 'c' B
1207
1208 'a' shift, and go to state 1
1209 'b' shift, and go to state 2
1210 'c' shift, and go to state 3
1211
1212 S go to state 4
1213
1214
1215 state 1
1216
1217 1 S: 'a' . A 'f'
1218 2 | 'a' . B
1219 8 A: . 'd' 'e'
1220 9 B: . 'd' 'e'
1221
1222 'd' shift, and go to state 5
1223
1224 A go to state 6
1225 B go to state 7
1226
1227
1228 state 2
1229
1230 3 S: 'b' . A 'f'
1231 4 | 'b' . B 'g'
1232 5 | 'b' . 'd'
1233 8 A: . 'd' 'e'
1234 9 B: . 'd' 'e'
1235
1236 'd' shift, and go to state 8
1237
1238 A go to state 9
1239 B go to state 10
1240
1241
1242 state 3
1243
1244 6 S: 'c' . 'c' A 'g'
1245 7 | 'c' . 'c' B
1246
1247 'c' shift, and go to state 11
1248
1249
1250 state 4
1251
1252 0 $accept: S . $end
1253
1254 $end shift, and go to state 12
1255
1256
1257 state 5
1258
1259 8 A: 'd' . 'e'
1260 9 B: 'd' . 'e'
1261
1262 'e' shift, and go to state ]AT_COND_CASE([[LALR]], [[13]],
1263 [[canonical LR]], [[13]],
1264 [[20]])[
1265
1266
1267 state 6
1268
1269 1 S: 'a' A . 'f'
1270
1271 'f' shift, and go to state 14
1272
1273
1274 state 7
1275
1276 2 S: 'a' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1277
1278 ]AT_COND_CASE([[canonical LR]], [[$end]],
1279 [[$default]])[ reduce using rule 2 (S)
1280
1281
1282 state 8
1283
1284 5 S: 'b' 'd' . [$end]
1285 8 A: 'd' . 'e'
1286 9 B: 'd' . 'e'
1287
1288 'e' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1289 [[13]])[
1290
1291 ]AT_COND_CASE([[canonical LR]], [[$end]],
1292 [[$default]])[ reduce using rule 5 (S)
1293
1294
1295 state 9
1296
1297 3 S: 'b' A . 'f'
1298
1299 'f' shift, and go to state 15
1300
1301
1302 state 10
1303
1304 4 S: 'b' B . 'g'
1305
1306 'g' shift, and go to state 16
1307
1308
1309 state 11
1310
1311 6 S: 'c' 'c' . A 'g'
1312 7 | 'c' 'c' . B
1313 8 A: . 'd' 'e'
1314 9 B: . 'd' 'e'
1315
1316 'd' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
1317 [[5]])[
1318
1319 A go to state 17
1320 B go to state 18
1321
1322
1323 state 12
1324
1325 0 $accept: S $end .
1326
1327 $default accept]AT_COND_CASE([[LALR]], [[
1328
1329
1330 state 13
1331
1332 8 A: 'd' 'e' . ['f', 'g']
1333 9 B: 'd' 'e' . [$end, 'g']
1334
1335 $end reduce using rule 9 (B)
1336 'g' reduce using rule 8 (A)
1337 'g' [reduce using rule 9 (B)]
1338 $default reduce using rule 8 (A)]], [[
1339
1340
1341 state 13
1342
1343 8 A: 'd' 'e' . ['f']
1344 9 B: 'd' 'e' . ]AT_COND_CASE([[canonical LR]], [[[$end]]], [[['g']]])[
1345
1346 ]AT_COND_CASE([[canonical LR]], [[$end]],
1347 [['g' ]])[ reduce using rule 9 (B)
1348 ]AT_COND_CASE([[canonical LR]], [['f' ]],
1349 [[$default]])[ reduce using rule 8 (A)]])[
1350
1351
1352 state 14
1353
1354 1 S: 'a' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1355
1356 ]AT_COND_CASE([[canonical LR]], [[$end]],
1357 [[$default]])[ reduce using rule 1 (S)
1358
1359
1360 state 15
1361
1362 3 S: 'b' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1363
1364 ]AT_COND_CASE([[canonical LR]], [[$end]],
1365 [[$default]])[ reduce using rule 3 (S)
1366
1367
1368 state 16
1369
1370 4 S: 'b' B 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1371
1372 ]AT_COND_CASE([[canonical LR]], [[$end]],
1373 [[$default]])[ reduce using rule 4 (S)
1374
1375
1376 state 17
1377
1378 6 S: 'c' 'c' A . 'g'
1379
1380 'g' shift, and go to state 19
1381
1382
1383 state 18
1384
1385 7 S: 'c' 'c' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1386
1387 ]AT_COND_CASE([[canonical LR]], [[$end]],
1388 [[$default]])[ reduce using rule 7 (S)
1389
1390
1391 state 19
1392
1393 6 S: 'c' 'c' A 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1394
1395 ]AT_COND_CASE([[canonical LR]], [[$end]],
1396 [[$default]])[ reduce using rule 6 (S)]AT_COND_CASE([[LALR]],
1397 [[]], [[
1398
1399
1400 state 20]AT_COND_CASE([[canonical LR]], [[
1401
1402 8 A: 'd' 'e' . ['f']
1403 9 B: 'd' 'e' . ['g']
1404
1405 'f' reduce using rule 8 (A)
1406 'g' reduce using rule 9 (B)
1407
1408
1409 state 21
1410
1411 8 A: 'd' . 'e'
1412 9 B: 'd' . 'e'
1413
1414 'e' shift, and go to state 22
1415
1416
1417 state 22
1418
1419 8 A: 'd' 'e' . ['g']
1420 9 B: 'd' 'e' . [$end]
1421
1422 $end reduce using rule 9 (B)
1423 'g' reduce using rule 8 (A)]], [[
1424
1425 8 A: 'd' 'e' . ['f', 'g']
1426 9 B: 'd' 'e' . [$end]
1427
1428 $end reduce using rule 9 (B)
1429 $default reduce using rule 8 (A)]])])[
1430 ]],
1431
1432 dnl OTHER-CHECKS
1433 [],
1434
1435 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1436 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1437 [],
1438 [AT_COND_CASE([[LALR]],
1439 [[syntax error
1440 ]])])
1441
1442
1443
1444 ## ------------------------------- ##
1445 ## %define lr.default-reductions. ##
1446 ## ------------------------------- ##
1447
1448 # AT_TEST_LR_DEFAULT_REDUCTIONS(GRAMMAR, INPUT, TABLES)
1449 # -----------------------------------------------------
1450 m4_define([AT_TEST_LR_DEFAULT_REDUCTIONS],
1451 [
1452 AT_TEST_TABLES_AND_PARSE([[no %define lr.default-reductions]],
1453 [[all]], [[]],
1454 [[]],
1455 [$1], [$2], [[]], [$3])
1456 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions all]],
1457 [[all]], [[]],
1458 [[%define lr.default-reductions all]],
1459 [$1], [$2], [[]], [$3])
1460 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions consistent]],
1461 [[consistent]], [[]],
1462 [[%define lr.default-reductions consistent]],
1463 [$1], [$2], [[]], [$3])
1464 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions accepting]],
1465 [[accepting]], [[]],
1466 [[%define lr.default-reductions accepting]],
1467 [$1], [$2], [[]], [$3])
1468 ])
1469
1470 AT_TEST_LR_DEFAULT_REDUCTIONS([[
1471 /* The start state is consistent and has a shift on 'a' and no reductions.
1472 After pushing the b below, enter an inconsistent state that has a shift and
1473 one reduction with one lookahead. */
1474 start:
1475 a b
1476 | a b 'a'
1477 | a c 'b'
1478 ;
1479
1480 /* After shifting this 'a', enter a consistent state that has no shift and 1
1481 reduction with multiple lookaheads. */
1482 a: 'a' ;
1483
1484 /* After the previous reduction, enter an inconsistent state that has no shift
1485 and multiple reductions. The first reduction has more lookaheads than the
1486 second, so the first should always be preferred as the default reduction if
1487 enabled. The second reduction has one lookahead. */
1488 b: ;
1489 c: ;
1490 ]],
1491 dnl Visit each state mentioned above.
1492 [['a', 'a']],
1493 [[state 0
1494
1495 0 $accept: . start $end
1496 1 start: . a b
1497 2 | . a b 'a'
1498 3 | . a c 'b'
1499 4 a: . 'a'
1500
1501 'a' shift, and go to state 1
1502
1503 start go to state 2
1504 a go to state 3
1505
1506
1507 state 1
1508
1509 4 a: 'a' .]AT_COND_CASE([[accepting]], [[ [$end, 'a', 'b']
1510
1511 $end reduce using rule 4 (a)
1512 'a' reduce using rule 4 (a)
1513 'b' reduce using rule 4 (a)]], [[
1514
1515 $default reduce using rule 4 (a)]])[
1516
1517
1518 state 2
1519
1520 0 $accept: start . $end
1521
1522 $end shift, and go to state 4
1523
1524
1525 state 3
1526
1527 1 start: a . b
1528 2 | a . b 'a'
1529 3 | a . c 'b'
1530 5 b: . [$end, 'a']
1531 6 c: . ['b']]AT_COND_CASE([[all]], [[
1532
1533 'b' reduce using rule 6 (c)
1534 $default reduce using rule 5 (b)]], [[
1535
1536 $end reduce using rule 5 (b)
1537 'a' reduce using rule 5 (b)
1538 'b' reduce using rule 6 (c)]])[
1539
1540 b go to state 5
1541 c go to state 6
1542
1543
1544 state 4
1545
1546 0 $accept: start $end .
1547
1548 $default accept
1549
1550
1551 state 5
1552
1553 1 start: a b . [$end]
1554 2 | a b . 'a'
1555
1556 'a' shift, and go to state 7
1557
1558 ]AT_COND_CASE([[all]], [[$default]], [[$end]])[ reduce using rule 1 (start)
1559
1560
1561 state 6
1562
1563 3 start: a c . 'b'
1564
1565 'b' shift, and go to state 8
1566
1567
1568 state 7
1569
1570 2 start: a b 'a' .]AT_COND_CASE([[accepting]], [[ [$end]
1571
1572 $end reduce using rule 2 (start)]], [[
1573
1574 $default reduce using rule 2 (start)]])[
1575
1576
1577 state 8
1578
1579 3 start: a c 'b' .]AT_COND_CASE([[accepting]], [[ [$end]
1580
1581 $end reduce using rule 3 (start)]], [[
1582
1583 $default reduce using rule 3 (start)]])[
1584 ]])