jison icon indicating copy to clipboard operation
jison copied to clipboard

LALR(1) implementation is not LALR(1)

Open nederhof opened this issue 3 years ago • 0 comments

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)?

nederhof avatar Dec 27 '22 16:12 nederhof