You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
%token END
%%
top
: body ';' END
;
body
: RepeatI
| RepeatI ';' RepeatD
;
RepeatI
: 'I'
| 'I' ';' RepeatI
;
RepeatD
: 'D'
| 'D' ';' RepeatD
;
%%
Failure message:
test-parser.y: warning: 3 shift/reduce conflicts [-Wconflicts-sr]
test-parser.y:10.5-11: warning: rule useless in parser due to conflicts [-Wother]
10 | : RepeatI
| ^~~~~~~
test-parser.y:14.5-7: warning: rule useless in parser due to conflicts [-Wother]
14 | : 'I'
| ^~~
test-parser.y:18.5-7: warning: rule useless in parser due to conflicts [-Wother]
18 | : 'D'
| ^~~
But this grammar has a state machine that unambiguously implements its logic:
State0:
when 'I' => goto State1
State1:
when ';' => goto State2
State2:
when 'I' => goto State1
when 'D' => goto State3
when END => goto <FINISH>
State3:
when ';' => goto State4
State4:
when 'D' => goto State3
when END => goto <FINISH>
I am sure it is possible to reformulate the grammar such that the above problems would go away, but there should be no need to do this.
Bison should compile any grammar that unambiguously defines a state machine that can parse it, without issuing unnecessary shift/reduce conflicts.
The text was updated successfully, but these errors were encountered:
Hi,
Your grammar is not LALR(1) and not even LR(1). Bison implements LALR(1) and LR(1) (and IELR(1)), so these conflicts are expected.
Bison cannot easily massage grammars, because it would also need to adjust the actions accordingly. So, sorry, but indeed you'll have to reformulate your grammar anyway. For instance
%token END
%%
top
: body END
;
body
: RepeatI
| RepeatI RepeatD
;
RepeatI
: 'I' ';'
| 'I' ';' RepeatI
;
RepeatD
: 'D' ';'
| 'D' ';' RepeatD
;
%%
Bison should compile any grammar that unambiguously defines a state machine that can parse it
I would also want it to report when a grammar is ambiguous. The only problem is that this is an undecidable problem :-)
This grammar fails with shift/reduce conflicts:
Failure message:
But this grammar has a state machine that unambiguously implements its logic:
I am sure it is possible to reformulate the grammar such that the above problems would go away, but there should be no need to do this.
Bison should compile any grammar that unambiguously defines a state machine that can parse it, without issuing unnecessary shift/reduce conflicts.
The text was updated successfully, but these errors were encountered: