The Gateway to Computer Science Excellence
0 votes
68 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
in Compiler Design by (77 points) | 68 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.

2 Answers

0 votes

 only iv is true.

refer this:-

 

by (265 points)
0 votes
(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)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,465 answers
195,380 comments
100,305 users