Is the grammar LALR?

Lets say the same grammar is not LR(1), can we safely say that the grammar is not LALR too?

if not, what are the conditions for a gram开发者_StackOverflow社区mar to be LALR? (or what are the conditions that make a grammar not LALR)

Thanks for the help!

LALR(1) ⊂ LR(1), so yes, we can assume that. The two grammars express languages in a similar manner, but LR(1) keeps track of more left state than LALR(1). Cf. These lecture notes, which discuss the differences in state between the two representations.

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

This document compares both.

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

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

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

The LR(0) state machine contains this state:

X -> a . 
Y -> a .

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

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

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

The problem with LALR is that the states are made first without any knowledge of the look-a-heads. Then the look-a-heads are examined or created after the states are made. Then LALR has this one state and the look-a-heads, which are usually added later, will look like this:

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

Can anybody see a problem here? If the look-ahead is 't', which reduction do you choose? It's ambiguous ! So the LALR(1) parser generator gives you a reduce-reduce conflict report which can be confusing to the inexperienced grammar writer.

That is why I made LRSTAR an LR(1) parser generator. It can handle the above grammar.