Re: Resolving shift/reduce conflicts?

[Zartaj Majeed]

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
>      `-> ClassBodyDeclarations ClassBodyDeclaration
>                                `-> ConstructorDeclaration
>                                    `-> Modifiersopt ConstructorDeclarator
> Throwsopt ConstructorBody . jp_SEMICOL
>    Reduce derivation
>      ClassBodyDeclarations
>      `-> ClassBodyDeclarations
>                                   ClassBodyDeclaration
>          `-> ClassBodyDeclarations ClassBodyDeclaration
>                                   `-> TypeDeclaration
>                                    `-> ConstructorDeclaration
>                                       `-> jp_SEMICOL
>                                        `-> Modifiersopt
> ConstructorDeclarator Throwsopt ConstructorBody .
> 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 .