The Gateway to Computer Science Excellence
+42 votes
6.5k views

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

  1. Removing left recursion alone
  2. Factoring the grammar alone
  3. Removing left recursion and factoring the grammar
  4. None of the above
in Compiler Design by Veteran (52.2k points) | 6.5k views
+5
S->Sa/a  here to convert into LL(1) need to be remove left recursive

for this S->ab/a here to convert LL(1) remove left factoring

then if i take a grammer which not having both left recursive and left factoring for example S->AB/a ;A->a,B->epsilon  then but still not parse by LL(1) bcz it is ambiguous so for that we have to be fulfill all three condition then we can convert into LL(1) surely  so D
+4
$S->A | B$
$A-> a$
$B-> a$

The above mentioned grammar has neither left recursion nor common prefixes, still it's not LL(1).

(D) is the correct option!
0
there is nothing so complicated they asked only ;

if we take any random CFG then what happens?

LL(1) parser not parse all D_CFG like ambiguous and left recursive CFG's etc. so we easily say option ( D ) should be correct.
+2
LL(1) parser does not parse left recursive, ambiguous, non-deterministic grammar because they create conflict in parsing table for sure but these are necessary but not sufficient condition because even a DCFG is free from left recursion, ambiguous, non-determinism still for some reason the parsing table may contain conflict, and no matter how much we try, conflicts in LL(1) parsing table can never be removed for some grammars..

9 Answers

0 votes
S->Sa/a  here to convert into LL(1) need to be remove left recursive

for this S->ab/a here to convert LL(1) remove left factoring

then if i take a grammer which not having both left recursive and left factoring for example S->AB/a ;A->a,B->epsilon  then but still not parse by LL(1) bcz it is ambiguous so for that we have to be fulfill all three condition then we can convert into LL(1) surely  so D
by (405 points)

Related questions

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,645 questions
56,601 answers
195,854 comments
102,227 users