Re: Resolving shift/reduce conflicts?
> On 2 Feb 2021, at 07:50, Christoph Grüninger wrote: > > Dear Bisons, > > I have another issue within the CMake parser code. When using the > attached cmDependsJavaParser.y with Bison 3.7.5, i get the following > warning: 4 shift/reduce conflicts [-Wconflicts-sr]. When adding > -Wcounterexamples I get the output below. Ok, I understand the issue and > Bison is right. > But what should I do to get rid of the problem? One way is to add precedences %left, %right, %nonassoc, to the tokens immediately before and after the parsing dot . in the conflicting rules. If there are no such tokens, the grammar must be rewritten, or using GLR.
Re: Resolving shift/reduce conflicts?
I don't know how familiar you are with this, so apologies if I'm stating
the obvious.
General observations:
1 - start by writing a skeleton with no actions; this makes it easier to
find conflicts. When you're done, add the actions
2 - this is *way*, *way* too verbose. You don't need tokens for ';',
'{', '}', etc - just write them explicitly in the description; this
makes it much easier to read. Get rid of all the $$. Move all the
common body actions out to routines at the bottom of the file, etc.
yyGetParser->SetCurrentCombine("") is just noise.
3 - if you have an optional ';' in your description, try not to repeat
the body twice, once with a ';', and once without:
MethodDeclaration
: MethodHeader jp_SEMICOL
| MethodHeader MethodBody
| MethodHeader MethodBody jp_SEMICOL
this is asking for conflicts, and is too verbose. Try (4) for the
conflicts, and/or this to reduce verbosity:
MethodDeclaration
: MethodHeader jp_SEMICOL
| MethodHeader MethodBody opt_semicolon
See also ConstructorDeclaration, etc.
4 - I think your fundamental problem is that your semicolon handling is
too complicated; I'm surprised that you only have 4 conflicts. Statement
terminators are always difficult. My procedure is to move this to the
top level, as far as possible. I can't easily explain why, but this does
seem to make it much easier to write without conflicts (and to handle
error recovery). If you're lucky, you end up with something like this,
with no other terminators in your description:
statement
: statement_a ';'
| statement_b ';'
| statement_c ';'
| /* empty */ ';'
| ...
;
5 - turn the counter examples into real source code that demonstrates
the problem - that makes it much easier for us to see the issue, and may
make the resolution clearer.
Re: Resolving shift/reduce conflicts?
I reran the full counterexamples report with the latest bison: bison -Wcounterexamples --report=counterexamples --report-file=bisonreport.txt cmDependsJavaParser.y the counterexamples now show rule numbers too cmDependsJavaParser.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr] cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_SEMICOL [-Wcounterexamples] Example: ClassBodyDeclarations MethodHeader MethodBody • jp_SEMICOL Shift derivation ClassBodyDeclarations ↳ 79: ClassBodyDeclarations ClassBodyDeclaration ↳ 80: ClassMemberDeclaration ↳ 85: MethodDeclaration ↳ 97: MethodHeader MethodBody • jp_SEMICOL Example: ClassBodyDeclarations MethodHeader MethodBody • jp_SEMICOL Reduce derivation ClassBodyDeclarations ↳ 79: ClassBodyDeclarations ClassBodyDeclaration ↳ 79: ClassBodyDeclarations ClassBodyDeclaration ↳ 83: TypeDeclaration ↳ 80: ClassMemberDeclaration ↳ 52: jp_SEMICOL ↳ 85: MethodDeclaration ↳ 96: MethodHeader MethodBody • this was the first of 4 conflicts btw I think the report displays some conflicts twice - looks like a bug to me but not relevant here rules 96 and 97 from the report are: 95 MethodDeclaration: MethodHeader jp_SEMICOL 96 | MethodHeader MethodBody 97 | MethodHeader MethodBody jp_SEMICOL I know you said you understand the issue but I'll just point it out for anyone else looking for help the issue is the semicolon can be handled by a reduce in rule 96 then process lookahead - or shift the semicolon the rules seem to be for an optional semicolon - but they are ambiguous If we say in the absence of a semicolon MethodBody is terminated by the end of line - you could fix the ambiguity by introducing an EOL token and changing rule 96 to: 96 | MethodHeader MethodBody EOL I looked at the other 3 conflicts too - I think these too can be fixed by eliminating or modifying some of the rules involved but needs familiarity with the semantics of the grammar On 2/2/2021 1:50 AM, Christoph Grüninger wrote: Dear Bisons, I have another issue within the CMake parser code. When using the attached cmDependsJavaParser.y with Bison 3.7.5, i get the following warning: 4 shift/reduce conflicts [-Wconflicts-sr]. When adding -Wcounterexamples I get the output below. Ok, I understand the issue and Bison is right. But what should I do to get rid of the problem? Bye Christoph bison --name-prefix=cmDependsJava_yy --defines=cmDependsJavaParserTokens.h -Wcounterexamples -ocmDependsJavaParser.cxx cmDependsJavaParser.y cmDependsJavaParser.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr] cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_SEMICOL [-Wcounterexamples] Example: ClassBodyDeclarations MethodHeader MethodBody . jp_SEMICOL Shift derivation ClassBodyDeclarations `-> ClassBodyDeclarations ClassBodyDeclaration `-> ClassMemberDeclaration `-> MethodDeclaration `-> MethodHeader MethodBody . jp_SEMICOL Reduce derivation ClassBodyDeclarations `-> ClassBodyDeclarations ClassBodyDeclaration `-> ClassBodyDeclarations ClassBodyDeclaration `-> TypeDeclaration `-> ClassMemberDeclaration `-> jp_SEMICOL `-> MethodDeclaration `-> MethodHeader MethodBody . cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples] Example: jp_THIS . jp_DOT Identifier Shift derivation FieldAccess `-> jp_THIS . jp_DOT Identifier Reduce derivation FieldAccess `-> Primary jp_DOT Identifier `-> PrimaryNoNewArray `-> jp_THIS . cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples] Example: jp_THIS . jp_DOT Identifier jp_PARESTART jp_PAREEND Shift derivation MethodInvocation `-> jp_THIS . jp_DOT Identifier jp_PARESTART ArgumentListopt jp_PAREEND `-> %empty Reduce derivation MethodInvocation `-> Primary jp_DOT Identifier jp_PARESTART ArgumentListopt jp_PAREEND `-> PrimaryNoNewArray`-> %empty `-> jp_THIS . cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_SEMICOL [-Wcounterexamples] Example: ClassBodyDeclarations Modifiersopt ConstructorDeclarator Throwsopt ConstructorBody . jp_SEMICOL Shift derivation ClassBodyDeclarations `-> ClassBodyDecla
