Which of the following is true for the left recursive grammar

Question

Comments

Answer is given A , It is right answer. could D also be one possible answer?

Answer 1

 A recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the productions of the grammar.

It is said so because it's clear that recursive descent parser will go into infinite loop if the non-terminal keeps on expanding into itself.

Similarly, talking about a recursive descent parser,even with backtracking---When we try to expand a non-terminal, we may eventually find ourselves again trying to expand the same non-terminal without having consumed any input.

A-> Ab

Here,while expanding the non-terminal A can be kept on expanding into

A-> AAb -> AAAb -> ... -> infinite loop of A.

Hence, we prevent left-recursive productions while working with recursive-descent parsers.

Answer 2

Ansswer will be a And Left Recursive is a problem for Top down and not for Bottom up parser . So it can be used for parsing :)

Comments

Then Non determinism(Left factoring) is also problem for top down parser only not for bottom- up ?

what about ambiguity is it creates problem both for top down as well as bottom up (exept oprator precedence) ?

please explain.

---

What i need to explain

you are absolutely right what you said :)

---

Thanks for your help...

---

For ambiguity the reason may be left recursion or factoring but not always left recursed is ambiguous or left factored is ambigous

example :S->Sa | a is not ambiguous where as

S->Sa | SS| a  is  ambiguous

But both grammers are left recursed

Answer 3

ans is (c)

A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted to a weakly equivalent right-recursive form.