grammar conflict in LALR, but works in SLR and LR(1). Bison also works.

[pjincz]

Hi friend, Thank you for your awesome project.

I wrote a jison file, but it not works. After all, I got following snippet to reproduce the problem.

%token ID

%%

stmt
    : type ID ';'
    | expr ';'
    ;

type
    : ID
    ;

expr
    : ID
    ;

This snippet works fine in SLR and LR. Also works fine in BISON (both LALR, IELR, LR) I'm a new of yacc, I can not found out where the problem is. But due to BISON and SLR work fine. I think maybe this is an issue.

Can you help me?

Thank you

[GerHobbelt]

Yes, it is. This is the same problem as #205. Looking into it.

On Feb 1, 2017 9:50 PM, "Chizhong Jin" notifications@github.com wrote:

Hi friend, Thank you for your awesome project.

I wrote a jison file, but it not works. After all, I got following snippet to reproduce the problem.

%token ID

%%

stmt : type ID ';' | expr ';' ;

type : ID ;

expr : ID ;

This snippet works fine in SLR and LR. Also works fine in BISON (both LALR, IELR, LR) I'm a new of yacc, I can not found out where the problem is. But due to BISON and SLR work fine. I think maybe this is an issue.

Can you help me?

Thank you

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/zaach/jison/issues/342, or mute the thread https://github.com/notifications/unsubscribe-auth/AAYkHjU4NY1fDfHqvnkmzv82_Y32dblwks5rYPAqgaJpZM4L0XrO .

[GerHobbelt]

Provisionally fixed in the https://github.com/GerHobbelt/jison fork in the next build. (Have to nail #343 before this build/release will be available!)

See commits:

• SHA-1: 7670e5ff34ebc122858cb7717557dac5ede44957 * fixing the correct set of valid inputs for the example grammar for #205

• SHA-1: d6c4ee7349c574ec4febd39ff478da591c87f778 * added second test grammar for #205 with the epsilon rules related by a non-empty rule instead to check if this is epsilon-rule related or a fundamental LALR issue (which got reported as #342 while I was looking at this one)

• SHA-1: 95b7326823edf6f2abadb043b72e7d1708207319 * an add the reported test grammar for #342 for good measure...

• SHA-1: cbc039306abf3fb7bb915584f0254893f37a6b70 fix for #205/#342: when we encounter an unresolvable conflict in LALR mode, we tag the relevant production (it turns out tagging the state as well corrupts* the parse table; something to look into later when my head is clearer as I don't see why, right now) and rerun the state machine generation process, where we make sure the UNION operator for the conflicting production WILL NOT merge it with other productions which may have the same FOLLOW set as this conflicting rule. As such, we fundamentally are 'locally' breaking LALR principles and turning them into LR-style behaviour for the conflict zone alone.

  (Side Note To Self: I recall having seen a short 1-column letter to the ACM (published by the ACM) from a few decades ago which mentioned that the algorithm used here is flawed, but cannot track it down in my library, darn it! So no reference to check if there's more amiss then this (#342 + #205). Also would like to check myself if this is IELR 're-invented', either in part or whole? Now I am curious... (Never got more than the abstract for that one and bison code isn't exactly obvious to me either.) Doubly dang-it! |:-( )

• SHA-1: 1f12e1d6d05098d29a226da16b1c8eed32fdac5d * move lingering debug logging behind the devDebug check, report the number of unresolved conflicts as part of the -I output at the end of a jison run and clean up the corresponding conflict counting while we re-run the state machine generation in jison when such conflicts have been found... (more work for #205 + #342) Also augment the test set fed into the #342 test grammar to make sure it behaves exactly as desired.

• SHA-1: ee720df3c2f17d971f37b7cdae23e329a55d77f5 Adjusted the examples for #205/342 to showcase the latest kernel optimizations too: when there's no match, i.e. a parse error, then the parser still invokes parseError() like in the old days and has it throw an exception if you don't override it, but you can also make it return false to turn the parser into a true matcher*, returning true or false whether the input parses correctly or not! See examples/issue-205-2.jison.

• SHA-1: 8b87a19e671f1f73c6541c908f83ff3c29dcaf03 * when the LALR compiler is executing the fix-it round already, it should exit the loop without repeating the conflict-fix-attempt notice as that should only appear after the first (and unsuccessful) round.

[pjincz]

:) Thank you very much