Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Grammar that is LR(1) but not LL(1)

This might look like a basic question to some of you but I expect intelligent replies here.

Why can't a LR(1) grammar with left recursion or the LR(1) grammar that is not left factored be LL(1)?

like image 414
Prasoon Saurav Avatar asked Apr 12 '10 14:04

Prasoon Saurav


People also ask

How do I know if I have LL 1 grammar or not?

Some simple checks to see whether a grammar is LL(1) or not. Check 1: The Grammar should not be left Recursive. Example: E --> E+T. is not LL(1) because it is Left recursive. Check 2: The Grammar should be Left Factored.

When the grammar is said to be LL 1 or LR 1?

A grammar whose parsing table has no multiply-defined en- tries is said to be LL(1) which stands for: scanning the input from Left to right producing a Leftmost derivation and using 1 input symbol of lookahead at each step to make parsing action decisions.

Can an ambiguous grammar be LL 1?

Ambiguous grammars are not LL(1) but unambiguous grammars are not necessarily LL(1) Having a non-LL(1) unambiguous grammar for a language does not mean that this language is not LL(1). But there are languages for which there exist unambiguous context-free grammars but no LL(1) grammar.

Can a left recursive grammar be LL 1?

If a grammar contain left recursion it can not be LL(1) Eg - S -> Sa | b S -> Sa goes to FIRST(S) = b S -> b goes to b, thus b has 2 entries hence not LL(1) 3. If a grammar is ambiguous then it can not be LL(1) 4.


1 Answers

Because you can never expect the termination of the string in LR(1) with left recursion.

like image 124
zs2020 Avatar answered Oct 20 '22 10:10

zs2020