69 views
Consider the statements: (i) Every regular grammar is LL(1) (ii) Every LL(1) grammar is LALR(1) (iii) All LR(0) grammars are LL(k) (iv) A context-free grammar without left factoring and left recursion can be ambiguous Which of the above statement/s is/are TRUE?
(i) only
(i) and (iii) only
(ii) and (iv) only
(iv) only
| 69 views
+2

ii and iv are true

i is false as a regular grammar can also be ambiguous

for clarification on iv, go through the explanations here https://gateoverflow.in/906/gate2003-16

+1
no, ii is not true. every LL(1) grammar is LR(1), but not necessarily LALR(1).

only iv is true.
0

yes   your ans. is correct. but statement 3.  All LR(0) grammars are LL(k)  why this statement is false

and can you explain why  statement 4 is correct.

0
Hmm okay
0

@Pavan Shetty

ambiguity and left recursion and left factoring are independent conditions... one doesn't lead to other. hence iv is true.

only iv is true.

refer this:-

by (273 points)
(i) Every regular grammar is LL(1)

- No, because regular grammar can be ambiguous/ left recursive/left factored.

(ii) Every LL(1) grammar is LALR(1)

- No, It's opposite.

(iii) All LR(0) grammars are LL(k)

- No, both are different types of parser. LR(0) just need to be unambiguous but LL(1) needs to be unambiguous + Not left recursive + not left factored.

(iv) A context-free grammar without left factoring and left recursion can be ambiguous

- True.
by Junior (887 points)