| blob | db8ec071b0dd1d9e1e9c136c71a356845e1f2be0 |
1 # Exercising Bison Grammar Reduction. -*- Autotest -*-
3 # Copyright (C) 2001-2002, 2007-2015, 2018-2021 Free Software
4 # Foundation, Inc.
6 # This program is free software: you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation, either version 3 of the License, or
9 # (at your option) any later version.
10 #
11 # This program is distributed in the hope that it will be useful,
12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 # GNU General Public License for more details.
15 #
16 # You should have received a copy of the GNU General Public License
17 # along with this program. If not, see <https://www.gnu.org/licenses/>.
19 AT_BANNER([[Grammar Reduction.]])
22 ## ------------------- ##
23 ## Useless Terminals. ##
24 ## ------------------- ##
26 AT_SETUP([Useless Terminals])
28 AT_DATA([[input.y]],
29 [[%verbose
30 %output "input.c"
32 %token useless1
33 %token useless2
34 %token useless3
35 %token useless4
36 %token useless5
37 %token useless6
38 %token useless7
39 %token useless8
40 %token useless9
42 %token useful
43 %%
44 exp: useful;
45 ]])
47 AT_BISON_CHECK([[input.y]])
49 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
50 [[Terminals unused in grammar
51 useless1
52 useless2
53 useless3
54 useless4
55 useless5
56 useless6
57 useless7
58 useless8
59 useless9
60 ]])
62 AT_CLEANUP
66 ## ---------------------- ##
67 ## Useless Nonterminals. ##
68 ## ---------------------- ##
70 AT_SETUP([Useless Nonterminals])
71 AT_BISON_OPTION_PUSHDEFS
73 AT_DATA([[input.y]],
74 [[%code {
75 ]AT_YYERROR_DECLARE_EXTERN[
76 ]AT_YYLEX_DECLARE_EXTERN[
77 }
78 %verbose
79 %output "input.c"
81 %token useful
82 %%
83 exp: useful;
84 useless1:
85 useless2:
86 useless3:
87 ]])
89 AT_BISON_CHECK([[input.y]], 0, [],
90 [[input.y: warning: 3 nonterminals useless in grammar [-Wother]
91 input.y: warning: 3 rules useless in grammar [-Wother]
92 input.y:11.1-8: warning: nonterminal useless in grammar: useless1 [-Wother]
93 input.y:12.1-8: warning: nonterminal useless in grammar: useless2 [-Wother]
94 input.y:13.1-8: warning: nonterminal useless in grammar: useless3 [-Wother]
95 ]])
97 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
98 [[Nonterminals useless in grammar
99 useless1
100 useless2
101 useless3
102 Rules useless in grammar
103 2 useless1: %empty
104 3 useless2: %empty
105 4 useless3: %empty
106 ]])
108 # Make sure the generated parser is correct.
109 AT_COMPILE([input.o])
111 AT_BISON_OPTION_POPDEFS
112 AT_CLEANUP
116 ## --------------- ##
117 ## Useless Rules. ##
118 ## --------------- ##
120 AT_SETUP([Useless Rules])
122 AT_BISON_OPTION_PUSHDEFS
123 AT_KEYWORDS([report])
125 AT_DATA([[input.y]],
126 [[%code {
127 ]AT_YYERROR_DECLARE_EXTERN[
128 ]AT_YYLEX_DECLARE_EXTERN[
129 }
130 %verbose
131 %output "input.c"
132 %token useful
133 %%
134 exp: useful;
135 useless1: '1';
136 useless2: '2';
137 useless3: '3';
138 useless4: '4';
139 useless5: '5';
140 useless6: '6';
141 useless7: '7';
142 useless8: '8';
143 useless9: '9';
144 ]])
146 AT_BISON_CHECK([[-fcaret input.y]], 0, [],
147 [[input.y: warning: 9 nonterminals useless in grammar [-Wother]
148 input.y: warning: 9 rules useless in grammar [-Wother]
149 input.y:10.1-8: warning: nonterminal useless in grammar: useless1 [-Wother]
150 10 | useless1: '1';
151 | ^~~~~~~~
152 input.y:11.1-8: warning: nonterminal useless in grammar: useless2 [-Wother]
153 11 | useless2: '2';
154 | ^~~~~~~~
155 input.y:12.1-8: warning: nonterminal useless in grammar: useless3 [-Wother]
156 12 | useless3: '3';
157 | ^~~~~~~~
158 input.y:13.1-8: warning: nonterminal useless in grammar: useless4 [-Wother]
159 13 | useless4: '4';
160 | ^~~~~~~~
161 input.y:14.1-8: warning: nonterminal useless in grammar: useless5 [-Wother]
162 14 | useless5: '5';
163 | ^~~~~~~~
164 input.y:15.1-8: warning: nonterminal useless in grammar: useless6 [-Wother]
165 15 | useless6: '6';
166 | ^~~~~~~~
167 input.y:16.1-8: warning: nonterminal useless in grammar: useless7 [-Wother]
168 16 | useless7: '7';
169 | ^~~~~~~~
170 input.y:17.1-8: warning: nonterminal useless in grammar: useless8 [-Wother]
171 17 | useless8: '8';
172 | ^~~~~~~~
173 input.y:18.1-8: warning: nonterminal useless in grammar: useless9 [-Wother]
174 18 | useless9: '9';
175 | ^~~~~~~~
176 ]])
179 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
180 [[Nonterminals useless in grammar
181 useless1
182 useless2
183 useless3
184 useless4
185 useless5
186 useless6
187 useless7
188 useless8
189 useless9
190 Terminals unused in grammar
191 '1'
192 '2'
193 '3'
194 '4'
195 '5'
196 '6'
197 '7'
198 '8'
199 '9'
200 Rules useless in grammar
201 2 useless1: '1'
202 3 useless2: '2'
203 4 useless3: '3'
204 5 useless4: '4'
205 6 useless5: '5'
206 7 useless6: '6'
207 8 useless7: '7'
208 9 useless8: '8'
209 10 useless9: '9'
210 ]])
212 # Make sure the generated parser is correct.
213 AT_COMPILE([input.o])
215 AT_BISON_OPTION_POPDEFS
216 AT_CLEANUP
220 ## --------------- ##
221 ## Useless Parts. ##
222 ## --------------- ##
224 AT_SETUP([Useless Parts])
226 # We used to emit code that used symbol numbers before the useless
227 # symbol elimination, hence before the renumbering of the useful
228 # symbols. As a result, the evaluation of the skeleton failed because
229 # it used non existing symbol numbers. Which is the happy scenario:
230 # we could use numbers of other existing symbols...
231 # https://lists.gnu.org/r/bug-bison/2019-01/msg00044.html
233 AT_BISON_OPTION_PUSHDEFS
234 AT_DATA([[input.y]],
235 [[%code {
236 ]AT_YYERROR_DECLARE_EXTERN[
237 ]AT_YYLEX_DECLARE_EXTERN[
238 }
239 %union { void* ptr; }
240 %type <ptr> used1
241 %type <ptr> used2
243 %%
244 start
245 : used1
246 ;
248 used1
249 : used2 { $$ = $1; }
250 ;
252 unused
253 : used2
254 ;
256 used2
257 : { $$ = YY_NULLPTR; }
258 ;
259 ]])
261 AT_BISON_CHECK([[-fcaret -rall -o input.c input.y]], 0, [],
262 [[input.y: warning: 1 nonterminal useless in grammar [-Wother]
263 input.y: warning: 1 rule useless in grammar [-Wother]
264 input.y:18.1-6: warning: nonterminal useless in grammar: unused [-Wother]
265 18 | unused
266 | ^~~~~~
267 ]])
270 AT_CHECK([[sed -n '/^State 0/q;/^$/!p' input.output]], 0,
271 [[Nonterminals useless in grammar
272 unused
273 Rules useless in grammar
274 4 unused: used2
275 Grammar
276 0 $accept: start $end
277 1 start: used1
278 2 used1: used2
279 3 used2: %empty
280 Terminals, with rules where they appear
281 $end (0) 0
282 error (256)
283 Nonterminals, with rules where they appear
284 $accept (3)
285 on left: 0
286 start (4)
287 on left: 1
288 on right: 0
289 used1 <ptr> (5)
290 on left: 2
291 on right: 1
292 used2 <ptr> (6)
293 on left: 3
294 on right: 2
295 ]])
297 # Make sure the generated parser is correct.
298 AT_COMPILE([input.o])
300 AT_BISON_OPTION_POPDEFS
301 AT_CLEANUP
305 ## ------------------- ##
306 ## Reduced Automaton. ##
307 ## ------------------- ##
309 # Check that the automaton is that as the for the grammar reduced by
310 # hand.
312 AT_SETUP([Reduced Automaton])
314 AT_KEYWORDS([report])
316 # The non reduced grammar.
317 # ------------------------
318 AT_DATA([[not-reduced.y]],
319 [[/* A useless token. */
320 %token useless_token
321 /* A useful one. */
322 %token useful
323 %verbose
324 %output "not-reduced.c"
326 %%
328 exp: useful { /* A useful action. */ }
329 | non_productive { /* A non productive action. */ }
330 ;
332 not_reachable: useful { /* A not reachable action. */ }
333 ;
335 non_productive: non_productive useless_token
336 { /* Another non productive action. */ }
337 ;
338 %%
339 ]])
341 AT_BISON_CHECK([[-fcaret not-reduced.y]], 0, [],
342 [[not-reduced.y: warning: 2 nonterminals useless in grammar [-Wother]
343 not-reduced.y: warning: 3 rules useless in grammar [-Wother]
344 not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable [-Wother]
345 14 | not_reachable: useful { /* A not reachable action. */ }
346 | ^~~~~~~~~~~~~
347 not-reduced.y:17.1-14: warning: nonterminal useless in grammar: non_productive [-Wother]
348 17 | non_productive: non_productive useless_token
349 | ^~~~~~~~~~~~~~
350 not-reduced.y:11.6-57: warning: rule useless in grammar [-Wother]
351 11 | | non_productive { /* A non productive action. */ }
352 | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
353 ]])
355 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0,
356 [[Nonterminals useless in grammar
357 not_reachable
358 non_productive
359 Terminals unused in grammar
360 useless_token
361 Rules useless in grammar
362 2 exp: non_productive
363 3 not_reachable: useful
364 4 non_productive: non_productive useless_token
365 ]])
367 # The reduced grammar.
368 # --------------------
369 AT_DATA([[reduced.y]],
370 [[/* A useless token. */
371 %token useless_token
372 /* A useful one. */
373 %token useful
374 %verbose
375 %output "reduced.c"
377 %%
379 exp: useful { /* A useful action. */ }
380 // | non_productive { /* A non productive action. */ } */
381 ;
383 //not_reachable: useful { /* A not reachable action. */ }
384 // ;
386 //non_productive: non_productive useless_token
387 // { /* Another non productive action. */ }
388 // ;
389 %%
390 ]])
392 AT_BISON_CHECK([[reduced.y]])
394 # Comparing the parsers.
395 cp reduced.c expout
396 AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout])
398 AT_CLEANUP
402 ## ------------------- ##
403 ## Underivable Rules. ##
404 ## ------------------- ##
406 AT_SETUP([Underivable Rules])
408 AT_KEYWORDS([report])
410 AT_DATA([[input.y]],
411 [[%verbose
412 %output "input.c"
413 %token useful
414 %%
415 exp: useful | underivable;
416 underivable: indirection;
417 indirection: underivable;
418 ]])
420 AT_BISON_CHECK([[-fcaret input.y]], 0, [],
421 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
422 input.y: warning: 3 rules useless in grammar [-Wother]
423 input.y:6.1-11: warning: nonterminal useless in grammar: underivable [-Wother]
424 6 | underivable: indirection;
425 | ^~~~~~~~~~~
426 input.y:7.1-11: warning: nonterminal useless in grammar: indirection [-Wother]
427 7 | indirection: underivable;
428 | ^~~~~~~~~~~
429 input.y:5.15-25: warning: rule useless in grammar [-Wother]
430 5 | exp: useful | underivable;
431 | ^~~~~~~~~~~
432 ]])
434 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
435 [[Nonterminals useless in grammar
436 underivable
437 indirection
438 Rules useless in grammar
439 2 exp: underivable
440 3 underivable: indirection
441 4 indirection: underivable
442 ]])
444 AT_CLEANUP
448 ## ------------------- ##
449 ## Bad start symbols. ##
450 ## ------------------- ##
452 AT_SETUP([Bad start symbols])
454 m4_pushdef([AT_TEST],
455 [AT_BISON_OPTION_PUSHDEFS([$1])
456 AT_DATA([[input.y]],
457 [%%
458 $1
459 ])
461 AT_BISON_CHECK([[input.y]], 1, [],
462 [$2
463 ])
464 AT_BISON_OPTION_POPDEFS([$1])
465 ])
467 AT_TEST(
468 [[exp: exp;]],
469 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
470 input.y: warning: 2 rules useless in grammar [-Wother]
471 input.y:2.1-3: error: start symbol exp does not derive any sentence]])
473 AT_TEST(
474 [[%start exp;
475 exp: exp;]],
476 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
477 input.y: warning: 2 rules useless in grammar [-Wother]
478 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
480 AT_TEST(
481 [[%start exp stmt;
482 exp: exp;
483 stmt: "stmt"]],
484 [[input.y: warning: 1 nonterminal useless in grammar [-Wother]
485 input.y: warning: 2 rules useless in grammar [-Wother]
486 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
488 AT_TEST(
489 [[%start exp stmt;
490 exp: exp;
491 stmt: stmt]],
492 [[input.y: warning: 3 nonterminals useless in grammar [-Wother]
493 input.y: warning: 4 rules useless in grammar [-Wother]
494 input.y:2.8-10: error: start symbol exp does not derive any sentence
495 input.y:2.12-15: error: start symbol stmt does not derive any sentence]])
497 AT_TEST(
498 [[%start exp;
499 stmt: stmt]],
500 [[input.y:2.8-10: warning: symbol 'exp' is used, but is not defined as a token and has no rules [-Wother]
501 input.y: warning: 3 nonterminals useless in grammar [-Wother]
502 input.y: warning: 2 rules useless in grammar [-Wother]
503 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
505 AT_TEST(
506 [[%token FOO;
507 %start FOO;
508 stmt: FOO]],
509 [[input.y:2.8-10: error: the start symbol FOO is a token]])
511 m4_popdef([AT_TEST])
513 AT_CLEANUP
517 ## ----------------- ##
518 ## %define lr.type. ##
519 ## ----------------- ##
521 # AT_TEST_LR_TYPE(DESCRIPTION,
522 # DECLS, GRAMMAR, INPUT,
523 # BISON-STDERR, TABLES,
524 # [OTHER-CHECKS],
525 # [PARSER-EXIT-VALUE],
526 # [PARSER-STDOUT], [PARSER-STDERR])
527 # -------------------------------------------------
528 m4_define([AT_TEST_LR_TYPE],
529 [
530 AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1],
531 [[LALR]], [[]],
532 [$2], m4_shiftn(2, $@))
533 AT_TEST_TABLES_AND_PARSE([[%define lr.type lalr: ]$1],
534 [[LALR]], [[]],
535 [[%define lr.type lalr
536 ]$2],
537 m4_shiftn(2, $@))
538 AT_TEST_TABLES_AND_PARSE([[%define lr.type ielr: ]$1],
539 [[IELR]], [[]],
540 [[%define lr.type ielr
541 ]$2],
542 m4_shiftn(2, $@))
543 AT_TEST_TABLES_AND_PARSE([[%define lr.type canonical-lr: ]$1],
544 [[canonical LR]], [[]],
545 [[%define lr.type canonical-lr
546 ]$2],
547 m4_shiftn(2, $@))
548 ])
550 AT_TEST_LR_TYPE([[Single State Split]],
551 [[%left 'a'
552 // Conflict resolution renders state 12 unreachable for canonical LR(1). We
553 // keep it so that the parser table diff is easier to code.
554 %define lr.keep-unreachable-state]],
555 [[
556 S: 'a' A 'a' /* rule 1 */
557 | 'b' A 'b' /* rule 2 */
558 | 'c' c /* rule 3 */
559 ;
561 /* A conflict should appear after the first 'a' in rules 4 and 5 but only after
562 having shifted the first 'a' in rule 1. However, when LALR(1) merging is
563 chosen, the state containing that conflict is reused after having seen the
564 first 'b' in rule 2 and then the first 'a' in rules 4 and 5. In both cases,
565 because of the merged state, if the next token is an 'a', the %left forces a
566 reduction action with rule 5. In the latter case, only a shift is actually
567 grammatically correct. Thus, the parser would report a syntax error for the
568 grammatically correct sentence "baab" because it would encounter a syntax
569 error after that incorrect reduction.
571 Despite not being LALR(1), Menhir version 20070322 suffers from this problem
572 as well. It uses David Pager's weak compatibility test for merging states.
573 Bison and Menhir accept non-LR(1) grammars with conflict resolution. Pager
574 designed his algorithm only for LR(1) grammars. */
575 A: 'a' 'a' /* rule 4 */
576 | 'a' /* rule 5 */
577 ;
579 /* Rule 3, rule 6, and rule 7 ensure that Bison does not report rule 4 as
580 useless after conflict resolution. This proves that, even though LALR(1)
581 generates incorrect parser tables sometimes, Bison will not necessarily
582 produce any warning to help the user realize it. */
583 c: 'a' 'b' /* rule 6 */
584 | A /* rule 7 */
585 ;
586 ]],
588 dnl INPUT
589 [['b', 'a', 'a', 'b']],
591 dnl BISON-STDERR
592 [],
594 dnl TABLES
595 [[State 0
597 0 $accept: . S $end
598 1 S: . 'a' A 'a'
599 2 | . 'b' A 'b'
600 3 | . 'c' c
602 'a' shift, and go to state 1
603 'b' shift, and go to state 2
604 'c' shift, and go to state 3
606 S go to state 4
609 State 1
611 1 S: 'a' . A 'a'
612 4 A: . 'a' 'a'
613 5 | . 'a'
615 'a' shift, and go to state 5
617 A go to state 6
620 State 2
622 2 S: 'b' . A 'b'
623 4 A: . 'a' 'a'
624 5 | . 'a'
626 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[16]])[
628 A go to state 7
631 State 3
633 3 S: 'c' . c
634 4 A: . 'a' 'a'
635 5 | . 'a'
636 6 c: . 'a' 'b'
637 7 | . A
639 'a' shift, and go to state 8
641 A go to state 9
642 c go to state 10
645 State 4
647 0 $accept: S . $end
649 $end shift, and go to state 11
652 State 5
654 4 A: 'a' . 'a'
655 5 | 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
657 ]AT_COND_CASE([[canonical LR]], [['a']],
658 [[$default]])[ reduce using rule 5 (A)
660 Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
663 State 6
665 1 S: 'a' A . 'a'
667 'a' shift, and go to state 13
670 State 7
672 2 S: 'b' A . 'b'
674 'b' shift, and go to state 14
677 State 8
679 4 A: 'a' . 'a'
680 5 | 'a' . [$end]
681 6 c: 'a' . 'b'
683 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[17]],
684 [[12]])[
685 'b' shift, and go to state 15
687 ]AT_COND_CASE([[canonical LR]], [[$end]],
688 [[$default]])[ reduce using rule 5 (A)
691 State 9
693 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
695 ]AT_COND_CASE([[canonical LR]], [[$end]],
696 [[$default]])[ reduce using rule 7 (c)
699 State 10
701 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
703 ]AT_COND_CASE([[canonical LR]], [[$end]],
704 [[$default]])[ reduce using rule 3 (S)
707 State 11
709 0 $accept: S $end .
711 $default accept
714 State 12
716 4 A: 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
718 ]AT_COND_CASE([[canonical LR]], [['a']],
719 [[$default]])[ reduce using rule 4 (A)
722 State 13
724 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
726 ]AT_COND_CASE([[canonical LR]], [[$end]],
727 [[$default]])[ reduce using rule 1 (S)
730 State 14
732 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
734 ]AT_COND_CASE([[canonical LR]], [[$end]],
735 [[$default]])[ reduce using rule 2 (S)
738 State 15
740 6 c: 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
742 ]AT_COND_CASE([[canonical LR]], [[$end]],
743 [[$default]])[ reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
744 [[]], [[
747 State 16
749 4 A: 'a' . 'a'
750 5 | 'a' . ['b']
752 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[18]],
753 [[12]])[
755 ]AT_COND_CASE([[canonical LR]], [['b']],
756 [[$default]])[ reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
759 State 17
761 4 A: 'a' 'a' . [$end]
763 $end reduce using rule 4 (A)
766 State 18
768 4 A: 'a' 'a' . ['b']
770 'b' reduce using rule 4 (A)]])])[
771 ]],
773 dnl OTHER-CHECKS
774 [],
776 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
777 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
778 [],
779 [AT_COND_CASE([[LALR]],
780 [[syntax error
781 ]])])
783 AT_TEST_LR_TYPE([[Lane Split]],
784 [[%left 'a'
785 // Conflict resolution renders state 16 unreachable for canonical LR(1). We
786 // keep it so that the parser table diff is easier to code.
787 %define lr.keep-unreachable-state]],
788 [[
789 /* Similar to the last test case set but two states must be split. */
790 S: 'a' A 'a' /* rule 1 */
791 | 'b' A 'b' /* rule 2 */
792 | 'c' c /* rule 3 */
793 ;
795 A: 'a' 'a' 'a' /* rule 4 */
796 | 'a' 'a' /* rule 5 */
797 ;
799 c: 'a' 'a' 'b' /* rule 6 */
800 | A /* rule 7 */
801 ;
802 ]],
804 dnl INPUT
805 [['b', 'a', 'a', 'a', 'b']],
807 dnl BISON-STDERR
808 [],
810 dnl TABLES
811 [[State 0
813 0 $accept: . S $end
814 1 S: . 'a' A 'a'
815 2 | . 'b' A 'b'
816 3 | . 'c' c
818 'a' shift, and go to state 1
819 'b' shift, and go to state 2
820 'c' shift, and go to state 3
822 S go to state 4
825 State 1
827 1 S: 'a' . A 'a'
828 4 A: . 'a' 'a' 'a'
829 5 | . 'a' 'a'
831 'a' shift, and go to state 5
833 A go to state 6
836 State 2
838 2 S: 'b' . A 'b'
839 4 A: . 'a' 'a' 'a'
840 5 | . 'a' 'a'
842 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[18]])[
844 A go to state 7
847 State 3
849 3 S: 'c' . c
850 4 A: . 'a' 'a' 'a'
851 5 | . 'a' 'a'
852 6 c: . 'a' 'a' 'b'
853 7 | . A
855 'a' shift, and go to state 8
857 A go to state 9
858 c go to state 10
861 State 4
863 0 $accept: S . $end
865 $end shift, and go to state 11
868 State 5
870 4 A: 'a' . 'a' 'a'
871 5 | 'a' . 'a'
873 'a' shift, and go to state 12
876 State 6
878 1 S: 'a' A . 'a'
880 'a' shift, and go to state 13
883 State 7
885 2 S: 'b' A . 'b'
887 'b' shift, and go to state 14
890 State 8
892 4 A: 'a' . 'a' 'a'
893 5 | 'a' . 'a'
894 6 c: 'a' . 'a' 'b'
896 'a' shift, and go to state 15
899 State 9
901 7 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
903 ]AT_COND_CASE([[canonical LR]], [[$end]],
904 [[$default]])[ reduce using rule 7 (c)
907 State 10
909 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
911 ]AT_COND_CASE([[canonical LR]], [[$end]],
912 [[$default]])[ reduce using rule 3 (S)
915 State 11
917 0 $accept: S $end .
919 $default accept
922 State 12
924 4 A: 'a' 'a' . 'a'
925 5 | 'a' 'a' . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
927 ]AT_COND_CASE([[canonical LR]], [['a']],
928 [[$default]])[ reduce using rule 5 (A)
930 Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
933 State 13
935 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
937 ]AT_COND_CASE([[canonical LR]], [[$end]],
938 [[$default]])[ reduce using rule 1 (S)
941 State 14
943 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
945 ]AT_COND_CASE([[canonical LR]], [[$end]],
946 [[$default]])[ reduce using rule 2 (S)
949 State 15
951 4 A: 'a' 'a' . 'a'
952 5 | 'a' 'a' . [$end]
953 6 c: 'a' 'a' . 'b'
955 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[19]],
956 [[16]])[
957 'b' shift, and go to state 17
959 ]AT_COND_CASE([[canonical LR]], [[$end]],
960 [[$default]])[ reduce using rule 5 (A)
963 State 16
965 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
967 ]AT_COND_CASE([[canonical LR]], [['a']],
968 [[$default]])[ reduce using rule 4 (A)
971 State 17
973 6 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
975 ]AT_COND_CASE([[canonical LR]], [[$end]],
976 [[$default]])[ reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
977 [[]], [[
980 State 18
982 4 A: 'a' . 'a' 'a'
983 5 | 'a' . 'a'
985 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
986 [[19]])[
989 State 19]AT_COND_CASE([[canonical LR]], [[
991 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
993 ]AT_COND_CASE([[canonical LR]], [[$end]],
994 [[$default]])[ reduce using rule 4 (A)
997 State 20]])[
999 4 A: 'a' 'a' . 'a'
1000 5 | 'a' 'a' . ['b']
1002 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
1003 [[16]])[
1005 ]AT_COND_CASE([[canonical LR]], [['b']],
1006 [[$default]])[ reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
1009 State 21
1011 4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[ ['b']]])[
1013 ]AT_COND_CASE([[canonical LR]], [['b']],
1014 [[$default]])[ reduce using rule 4 (A)]])])[
1015 ]],
1017 dnl OTHER-CHECKS
1018 [],
1020 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1021 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1022 [],
1023 [AT_COND_CASE([[LALR]],
1024 [[syntax error
1025 ]])])
1027 AT_TEST_LR_TYPE([[Complex Lane Split]],
1028 [[%left 'a'
1029 // Conflict resolution renders state 16 unreachable for canonical LR(1). We
1030 // keep it so that the parser table diff is easier to code.
1031 %define lr.keep-unreachable-state]],
1032 [[
1033 /* Similar to the last test case set but forseeing the S/R conflict from the
1034 first state that must be split is becoming difficult. Imagine if B were
1035 even more complex. Imagine if A had other RHS's ending in other
1036 nonterminals. */
1037 S: 'a' A 'a'
1038 | 'b' A 'b'
1039 | 'c' c
1040 ;
1041 A: 'a' 'a' B
1042 ;
1043 B: 'a'
1044 | %empty %prec 'a'
1045 ;
1046 c: 'a' 'a' 'b'
1047 | A
1048 ;
1049 ]],
1051 dnl INPUT
1052 [['b', 'a', 'a', 'a', 'b']],
1054 dnl BISON-STDERR
1055 [],
1057 dnl TABLES
1058 [[State 0
1060 0 $accept: . S $end
1061 1 S: . 'a' A 'a'
1062 2 | . 'b' A 'b'
1063 3 | . 'c' c
1065 'a' shift, and go to state 1
1066 'b' shift, and go to state 2
1067 'c' shift, and go to state 3
1069 S go to state 4
1072 State 1
1074 1 S: 'a' . A 'a'
1075 4 A: . 'a' 'a' B
1077 'a' shift, and go to state 5
1079 A go to state 6
1082 State 2
1084 2 S: 'b' . A 'b'
1085 4 A: . 'a' 'a' B
1087 'a' shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[19]])[
1089 A go to state 7
1092 State 3
1094 3 S: 'c' . c
1095 4 A: . 'a' 'a' B
1096 7 c: . 'a' 'a' 'b'
1097 8 | . A
1099 'a' shift, and go to state 8
1101 A go to state 9
1102 c go to state 10
1105 State 4
1107 0 $accept: S . $end
1109 $end shift, and go to state 11
1112 State 5
1114 4 A: 'a' . 'a' B
1116 'a' shift, and go to state 12
1119 State 6
1121 1 S: 'a' A . 'a'
1123 'a' shift, and go to state 13
1126 State 7
1128 2 S: 'b' A . 'b'
1130 'b' shift, and go to state 14
1133 State 8
1135 4 A: 'a' . 'a' B
1136 7 c: 'a' . 'a' 'b'
1138 'a' shift, and go to state 15
1141 State 9
1143 8 c: A .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1145 ]AT_COND_CASE([[canonical LR]], [[$end]],
1146 [[$default]])[ reduce using rule 8 (c)
1149 State 10
1151 3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1153 ]AT_COND_CASE([[canonical LR]], [[$end]],
1154 [[$default]])[ reduce using rule 3 (S)
1157 State 11
1159 0 $accept: S $end .
1161 $default accept
1164 State 12
1166 4 A: 'a' 'a' . B
1167 5 B: . 'a'
1168 6 | %empty . ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
1170 ]AT_COND_CASE([[canonical LR]], [['a']],
1171 [[$default]])[ reduce using rule 6 (B)
1173 B go to state 17
1175 Conflict between rule 6 and token 'a' resolved as reduce (%left 'a').
1178 State 13
1180 1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1182 ]AT_COND_CASE([[canonical LR]], [[$end]],
1183 [[$default]])[ reduce using rule 1 (S)
1186 State 14
1188 2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1190 ]AT_COND_CASE([[canonical LR]], [[$end]],
1191 [[$default]])[ reduce using rule 2 (S)
1194 State 15
1196 4 A: 'a' 'a' . B
1197 5 B: . 'a'
1198 6 | %empty . [$end]
1199 7 c: 'a' 'a' . 'b'
1201 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1202 [[16]])[
1203 'b' shift, and go to state 18
1205 ]AT_COND_CASE([[canonical LR]], [[$end]],
1206 [[$default]])[ reduce using rule 6 (B)
1208 B go to state ]AT_COND_CASE([[canonical LR]], [[21]], [[17]])[
1211 State 16
1213 5 B: 'a' .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
1215 ]AT_COND_CASE([[canonical LR]], [['a']],
1216 [[$default]])[ reduce using rule 5 (B)
1219 State 17
1221 4 A: 'a' 'a' B .]AT_COND_CASE([[canonical LR]], [[ ['a']]])[
1223 ]AT_COND_CASE([[canonical LR]], [['a']],
1224 [[$default]])[ reduce using rule 4 (A)
1227 State 18
1229 7 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1231 ]AT_COND_CASE([[canonical LR]], [[$end]],
1232 [[$default]])[ reduce using rule 7 (c)]AT_COND_CASE([[LALR]], [], [[
1235 State 19
1237 4 A: 'a' . 'a' B
1239 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[22]],
1240 [[20]])[
1243 State 20]AT_COND_CASE([[canonical LR]], [[
1245 5 B: 'a' . [$end]
1247 $end reduce using rule 5 (B)
1250 State 21
1252 4 A: 'a' 'a' B . [$end]
1254 $end reduce using rule 4 (A)
1257 State 22]])[
1259 4 A: 'a' 'a' . B
1260 5 B: . 'a'
1261 6 | %empty . ['b']
1263 'a' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[23]],
1264 [[16]])[
1266 ]AT_COND_CASE([[canonical LR]], [['b']],
1267 [[$default]])[ reduce using rule 6 (B)
1269 B go to state ]AT_COND_CASE([[canonical LR]], [[24
1272 State 23
1274 5 B: 'a' . ['b']
1276 'b' reduce using rule 5 (B)
1279 State 24
1281 4 A: 'a' 'a' B . ['b']
1283 'b' reduce using rule 4 (A)]], [[17]])])[
1284 ]],
1286 dnl OTHER-CHECKS
1287 [],
1289 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1290 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1291 [],
1292 [AT_COND_CASE([[LALR]],
1293 [[syntax error
1294 ]])])
1296 AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]],
1297 [[%define lr.keep-unreachable-state]],
1298 [[
1299 /* The partial state chart diagram below is for LALR(1). State 0 is the start
1300 state. States are iterated for successor construction in numerical order.
1301 Transitions are downwards.
1303 State 13 has a R/R conflict that cannot be predicted by Bison's LR(1)
1304 algorithm using annotations alone. That is, when state 11's successor on
1305 'd' is merged with state 5 (which is originally just state 1's successor on
1306 'd'), state 5's successor on 'e' must then be changed because the resulting
1307 lookaheads that propagate to it now make it incompatible with state 8's
1308 successor on 'e'. In other words, state 13 must be split to avoid the
1309 conflict.
1311 0
1312 / | \
1313 a / c| \ b
1314 1 3 2
1315 | | |
1316 d| |c | d
1317 | 11 |
1318 | | |
1319 \ /d |
1320 5 8
1321 \ |
1322 e \ / e
1323 13
1324 R/R
1326 This grammar is designed carefully to make sure that, despite Bison's LR(1)
1327 algorithm's bread-first iteration of transitions to reconstruct states,
1328 state 11's successors are constructed after state 5's and state 8's.
1329 Otherwise (for example, if you remove the first 'c' in each of rules 6 and
1330 7), state 5's successor on 'e' would never be merged with state 8's, so the
1331 split of the resulting state 13 would never need to be performed. */
1332 S: 'a' A 'f'
1333 | 'a' B
1334 | 'b' A 'f'
1335 | 'b' B 'g'
1336 | 'b' 'd'
1337 | 'c' 'c' A 'g'
1338 | 'c' 'c' B
1339 ;
1340 A: 'd' 'e' ;
1341 B: 'd' 'e' ;
1342 ]],
1344 dnl INPUT
1345 [['b', 'd', 'e', 'g']],
1347 dnl BISON-STDERR
1348 [AT_COND_CASE([[LALR]],
1349 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1350 input.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
1351 ]], [])],
1353 dnl TABLES
1354 [[State 0
1356 0 $accept: . S $end
1357 1 S: . 'a' A 'f'
1358 2 | . 'a' B
1359 3 | . 'b' A 'f'
1360 4 | . 'b' B 'g'
1361 5 | . 'b' 'd'
1362 6 | . 'c' 'c' A 'g'
1363 7 | . 'c' 'c' B
1365 'a' shift, and go to state 1
1366 'b' shift, and go to state 2
1367 'c' shift, and go to state 3
1369 S go to state 4
1372 State 1
1374 1 S: 'a' . A 'f'
1375 2 | 'a' . B
1376 8 A: . 'd' 'e'
1377 9 B: . 'd' 'e'
1379 'd' shift, and go to state 5
1381 A go to state 6
1382 B go to state 7
1385 State 2
1387 3 S: 'b' . A 'f'
1388 4 | 'b' . B 'g'
1389 5 | 'b' . 'd'
1390 8 A: . 'd' 'e'
1391 9 B: . 'd' 'e'
1393 'd' shift, and go to state 8
1395 A go to state 9
1396 B go to state 10
1399 State 3
1401 6 S: 'c' . 'c' A 'g'
1402 7 | 'c' . 'c' B
1404 'c' shift, and go to state 11
1407 State 4
1409 0 $accept: S . $end
1411 $end shift, and go to state 12
1414 State 5
1416 8 A: 'd' . 'e'
1417 9 B: 'd' . 'e'
1419 'e' shift, and go to state ]AT_COND_CASE([[LALR]], [[13]],
1420 [[canonical LR]], [[13]],
1421 [[20]])[
1424 State 6
1426 1 S: 'a' A . 'f'
1428 'f' shift, and go to state 14
1431 State 7
1433 2 S: 'a' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1435 ]AT_COND_CASE([[canonical LR]], [[$end]],
1436 [[$default]])[ reduce using rule 2 (S)
1439 State 8
1441 5 S: 'b' 'd' . [$end]
1442 8 A: 'd' . 'e'
1443 9 B: 'd' . 'e'
1445 'e' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1446 [[13]])[
1448 ]AT_COND_CASE([[canonical LR]], [[$end]],
1449 [[$default]])[ reduce using rule 5 (S)
1452 State 9
1454 3 S: 'b' A . 'f'
1456 'f' shift, and go to state 15
1459 State 10
1461 4 S: 'b' B . 'g'
1463 'g' shift, and go to state 16
1466 State 11
1468 6 S: 'c' 'c' . A 'g'
1469 7 | 'c' 'c' . B
1470 8 A: . 'd' 'e'
1471 9 B: . 'd' 'e'
1473 'd' shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
1474 [[5]])[
1476 A go to state 17
1477 B go to state 18
1480 State 12
1482 0 $accept: S $end .
1484 $default accept]AT_COND_CASE([[LALR]], [[
1487 State 13
1489 8 A: 'd' 'e' . ['f', 'g']
1490 9 B: 'd' 'e' . [$end, 'g']
1492 $end reduce using rule 9 (B)
1493 'g' reduce using rule 8 (A)
1494 'g' [reduce using rule 9 (B)]
1495 $default reduce using rule 8 (A)]], [[
1498 State 13
1500 8 A: 'd' 'e' . ['f']
1501 9 B: 'd' 'e' . ]AT_COND_CASE([[canonical LR]], [[[$end]]], [[['g']]])[
1503 ]AT_COND_CASE([[canonical LR]], [[$end]],
1504 [['g' ]])[ reduce using rule 9 (B)
1505 ]AT_COND_CASE([[canonical LR]], [['f' ]],
1506 [[$default]])[ reduce using rule 8 (A)]])[
1509 State 14
1511 1 S: 'a' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1513 ]AT_COND_CASE([[canonical LR]], [[$end]],
1514 [[$default]])[ reduce using rule 1 (S)
1517 State 15
1519 3 S: 'b' A 'f' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1521 ]AT_COND_CASE([[canonical LR]], [[$end]],
1522 [[$default]])[ reduce using rule 3 (S)
1525 State 16
1527 4 S: 'b' B 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1529 ]AT_COND_CASE([[canonical LR]], [[$end]],
1530 [[$default]])[ reduce using rule 4 (S)
1533 State 17
1535 6 S: 'c' 'c' A . 'g'
1537 'g' shift, and go to state 19
1540 State 18
1542 7 S: 'c' 'c' B .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1544 ]AT_COND_CASE([[canonical LR]], [[$end]],
1545 [[$default]])[ reduce using rule 7 (S)
1548 State 19
1550 6 S: 'c' 'c' A 'g' .]AT_COND_CASE([[canonical LR]], [[ [$end]]])[
1552 ]AT_COND_CASE([[canonical LR]], [[$end]],
1553 [[$default]])[ reduce using rule 6 (S)]AT_COND_CASE([[LALR]],
1554 [[]], [[
1557 State 20]AT_COND_CASE([[canonical LR]], [[
1559 8 A: 'd' 'e' . ['f']
1560 9 B: 'd' 'e' . ['g']
1562 'f' reduce using rule 8 (A)
1563 'g' reduce using rule 9 (B)
1566 State 21
1568 8 A: 'd' . 'e'
1569 9 B: 'd' . 'e'
1571 'e' shift, and go to state 22
1574 State 22
1576 8 A: 'd' 'e' . ['g']
1577 9 B: 'd' 'e' . [$end]
1579 $end reduce using rule 9 (B)
1580 'g' reduce using rule 8 (A)]], [[
1582 8 A: 'd' 'e' . ['f', 'g']
1583 9 B: 'd' 'e' . [$end]
1585 $end reduce using rule 9 (B)
1586 $default reduce using rule 8 (A)]])])[
1587 ]],
1589 dnl OTHER-CHECKS
1590 [],
1592 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1593 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1594 [],
1595 [AT_COND_CASE([[LALR]],
1596 [[syntax error
1597 ]])])
1601 ## ------------------------------ ##
1602 ## %define lr.default-reduction. ##
1603 ## ------------------------------ ##
1605 # AT_TEST_LR_DEFAULT_REDUCTIONS(GRAMMAR, INPUT, TABLES)
1606 # -----------------------------------------------------
1607 m4_define([AT_TEST_LR_DEFAULT_REDUCTIONS],
1608 [
1609 AT_TEST_TABLES_AND_PARSE([[no %define lr.default-reduction]],
1610 [[most]], [[]],
1611 [[]],
1612 [$1], [$2], [[]], [$3])
1613 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction most]],
1614 [[most]], [[]],
1615 [[%define lr.default-reduction most]],
1616 [$1], [$2], [[]], [$3])
1617 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction consistent]],
1618 [[consistent]], [[]],
1619 [[%define lr.default-reduction consistent]],
1620 [$1], [$2], [[]], [$3])
1621 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction accepting]],
1622 [[accepting]], [[]],
1623 [[%define lr.default-reduction accepting]],
1624 [$1], [$2], [[]], [$3])
1625 ])
1627 AT_TEST_LR_DEFAULT_REDUCTIONS([[
1628 /* The start state is consistent and has a shift on 'a' and no reductions.
1629 After pushing the b below, enter an inconsistent state that has a shift and
1630 one reduction with one lookahead. */
1631 start:
1632 a b
1633 | a b 'a'
1634 | a c 'b'
1635 ;
1637 /* After shifting this 'a', enter a consistent state that has no shift and 1
1638 reduction with multiple lookaheads. */
1639 a: 'a' ;
1641 /* After the previous reduction, enter an inconsistent state that has no shift
1642 and multiple reductions. The first reduction has more lookaheads than the
1643 second, so the first should always be preferred as the default reduction if
1644 enabled. The second reduction has one lookahead. */
1645 b: %empty;
1646 c: %empty;
1647 ]],
1648 dnl Visit each state mentioned above.
1649 [['a', 'a']],
1650 [[State 0
1652 0 $accept: . start $end
1653 1 start: . a b
1654 2 | . a b 'a'
1655 3 | . a c 'b'
1656 4 a: . 'a'
1658 'a' shift, and go to state 1
1660 start go to state 2
1661 a go to state 3
1664 State 1
1666 4 a: 'a' .]AT_COND_CASE([[accepting]], [[ [$end, 'a', 'b']
1668 $end reduce using rule 4 (a)
1669 'a' reduce using rule 4 (a)
1670 'b' reduce using rule 4 (a)]], [[
1672 $default reduce using rule 4 (a)]])[
1675 State 2
1677 0 $accept: start . $end
1679 $end shift, and go to state 4
1682 State 3
1684 1 start: a . b
1685 2 | a . b 'a'
1686 3 | a . c 'b'
1687 5 b: %empty . [$end, 'a']
1688 6 c: %empty . ['b']]AT_COND_CASE([[most]], [[
1690 'b' reduce using rule 6 (c)
1691 $default reduce using rule 5 (b)]], [[
1693 $end reduce using rule 5 (b)
1694 'a' reduce using rule 5 (b)
1695 'b' reduce using rule 6 (c)]])[
1697 b go to state 5
1698 c go to state 6
1701 State 4
1703 0 $accept: start $end .
1705 $default accept
1708 State 5
1710 1 start: a b . [$end]
1711 2 | a b . 'a'
1713 'a' shift, and go to state 7
1715 ]AT_COND_CASE([[most]], [[$default]],
1716 [[$end]])[ reduce using rule 1 (start)
1719 State 6
1721 3 start: a c . 'b'
1723 'b' shift, and go to state 8
1726 State 7
1728 2 start: a b 'a' .]AT_COND_CASE([[accepting]], [[ [$end]
1730 $end reduce using rule 2 (start)]], [[
1732 $default reduce using rule 2 (start)]])[
1735 State 8
1737 3 start: a c 'b' .]AT_COND_CASE([[accepting]], [[ [$end]
1739 $end reduce using rule 3 (start)]], [[
1741 $default reduce using rule 3 (start)]])[
1742 ]])