LL(1) AND LALR(1)

Question

As I know that LL(1) and LALR(1) grammars are incomperable ,but if a grammar is LL(1) then, it may be LALR(1) if the following conditions hold.

1.A ε-free LL(1) grammar is also a SLR(1) grammar and thus LALR(1) too.

2. A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar.

3. A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1).

can anyone explain each point with example. and what is this "non-empty derivation/empty derivation"?

Comments

I thought someone had explained them. But this place is empty. Please explain if, someone, really know how these results are derived.

---

@Arjun sir @srestha mam

Can anyone one of you explain us mainly 2 & 3 point !!

Some discussion similar to these points went through here also  https://gateoverflow.in/945/gate2003-57

Source: LL grammar

---

It means

$LL1=LALR1$  (when $LL1$ has empty derivation )

$LL1\subset LALR1$ (when $LL1$ has non-empty derivation )

---

@srestha   $ma'am$

LL1=LALR1  (when LL1 has empty derivation )
 

But in the statement it is mentioned that LL(1) having only empty derivations may or may not be LALR(1)

 

And ma'am what does empty derivation means:

Does it mean's that whether we perform RMD or LMD, at the end we are not getting any terminal string.

Answer 1

1.A ε-free LL(1) grammar is also a SLR(1) grammar and thus LALR(1) too.

Since the grammar is LL(1), we can conclude that it is unambiguous, non-left recursive and left factored. 

Since it is unambiguous, therefore we will never reach a point while parsing where we’ll have 2 choices for reduction, therefore RR conflict of SLR(1) not possible.

Now we have to think that how will ε-free help us in avoiding SR conflict.

Since it is ε-free we’ll never reach a point where we are confused that whether we need to shift the terminal symbol or reduce ε to the non-terminal.

 

2. A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar.

All logic stays the same as done in the 1st statement. Just one additional point it that here we can look ahead and make a decision whether to shift or reduce. Hence LALR(1).

 

3. A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1).

Can anyone please give an example of such grammar. Will such grammar make any sense?