Is Grammar LALR?

Question

Say that the same grammar is not LR (1), can we say with certainty that the grammar is also not LALR?

If not, what are the conditions for a grammar to be LALR? (or what conditions make the grammar not LALR)

Thanks for the help!

Answer 1

LALR (1) ⊂ LR (1), so yes, we can assume that. Two grammars express languages ​​in a similar way, but LR (1) tracks a larger left state than LALR (1). Wed These lectures discussing the differences in state between two representations.

In general, the parser generators will handle all the details of creating shift shift steps for you; the difference is that generators based on larger grammars are more likely to find a conflict-free parsing strategy.

Answer 2

This document compares both.

Answer 3

Here is a simple grammar that is LR (1) but not LALR (1):

G -> SS -> c X t -> c Y n -> r Y t -> r X n X -> a Y -> a 

The parser generator LALR (1) gives you the state machine LR (0). The parser generator LR (1) gives you the state machine LR (1). With this grammar, the state machine LR (1) has one more state than the state machine LR (0).

The state machine LR (0) contains this state:

 X -> a . Y -> a . 

The state machine LR (1) contains these two states instead of the one shown above:

 X -> a . { t } Y -> a . { n } X -> a . { n } Y -> a . { t } 

The problem with LALR is that states are created first without any outside observer knowledge. Then, learning or created heads are studied after the creation of states. Then LALR has this single state, and the look-a-head, which are usually added later, will look like this:

 X -> a . { t, n } Y -> a . { n, t } 

Can anyone see the problem here? If the forecast is "t", which abbreviation will you choose? This is ambiguous! In this way, the LALR (1) parser generator provides you with a reduce-reduce conflict report that can confuse an inexperienced grammar writer.

That's why I made LRSTAR a LR (1) parser generator. It can handle the above grammar.