Why does this Grammar work in LALR(1) but not LR(1)

359 views Asked by At

By all accounts, LR(1) should be more powerful in every way compared to LALR(1) since LR(1) builds a canonical collection of LR(1) items, and LALR(1) is just a better SLR(1) parser.

Then why does this grammar work successfully in an LALR(1) parser, but not in an LR(1) parser when I try this input:

int + int

For this grammar:

S' -> S
S -> Add

Add -> Mul
Add -> Add + Mul

Mul -> Const
Mul -> Mul * Mul

Const -> int
Const -> float

These are the JavaScript LR(1) and JavaScript LALR(1) parsers I used for this example: http://jsmachines.sourceforge.net/machines/lr1.html

http://jsmachines.sourceforge.net/machines/lalr1.html

UPDATE

The JSmachine site is pretty buggy. I used this site instead https://zaa.ch/jison/try/usf/index.html from the University of South Florida, but I was advised to use Bison to ensure correctness. As the top comment suggested, Mul -> Mul * Mul is pretty ambiguous so I updated the grammar accordingly

S' -> S
S -> Add

Add -> Mul
Add -> Add + Mul

Mul -> Const
Mul -> Mul * Const

Const -> int
Const -> float

adapted to BNF format:

%%
SS : S ;
S  : Add ;

Add : Mul
    | Add '+' Mul
    ;

Mul : Const
    | Mul '*' Const
    ;

Const : int
      | float
      ;
1

There are 1 answers

2
rici On BEST ANSWER

I'm not sure what you mean by "work" in your question. That online parser-generator reports shift-reduce conflicts for both the LR(1) and the LALR(1) algorithms, which is not suprising since your grammar includes the exponentially ambiguous

Mul -> Mul * Mul

Apparently, that site's LR(1) implementation handles errors with less grace than it's LALR(1) implementation. I'd say that it's a bug. But in any event, the grammar cannot produce either an LALR(1) or an LR(1) parser.