Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LALR(1) implementation is not LALR(1) #403

Open
nederhof opened this issue Dec 27, 2022 · 0 comments
Open

LALR(1) implementation is not LALR(1) #403

nederhof opened this issue Dec 27, 2022 · 0 comments

Comments

@nederhof
Copy link

jison --version
0.4.18

Not sure what is implemented, but it isn't LALR(1):

%lex

%%

"b" return 'B' 
"e" return 'E'
           
<<EOF>> return 'EOF';
                            
/lex  
                                                                     
%start top
                                                 
%% 

top
    : a EOF 
    ;                          
a                         
    : b             
    | e                
    ;                                          
b                       
    : c B
    ;                                                                  
c                                                            
    : e
    ;                                                                                              
e                                          
    : E
    ;

This grammar is SLR(1) and therefore LALR(1). Predictably no conflicts arise with:

jison -p slr test.jison

But:

jison -p lalr test.jison
[....]
States with conflicts:
State 4
a -> e . #lookaheads= EOF B
c -> e . #lookaheads= EOF B

This may be the same bug as #342 from 2017, where it was reported: "Provisionally fixed in the https://github.com/GerHobbelt/jison fork" but this version (installed using npm install jison-gho -g) has the same problem:

jison --version
0.6.1-215
jison -p lalr test.jison
States with conflicts:
State 4    (B @ c -> e .)
a -> e .                               #lookaheads= [EOF]  [B]
c -> e .                               #lookaheads= [EOF]  [B]

However the online demo at:

https://gerhobbelt.github.io/jison/try/

does not have this problem and neither SLR(1) nor LALR(1) flag up any conflicts. Only LR(0) flags up a conflict, as expected as the grammar is not LR(0).

Is there any way to install a fixed version (the one from the online demo)?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant