**Do not post examples already provided here** There are two restrictions on the

Question

**Do not post examples already provided here**

There are two restrictions on the type of grammars that can be used with a recursive descent parser. The first is that the grammar cannot have any left recursive productions. Give an example of a left recursive production and explain why such productions would be a problem. The second restriction is that the grammar must not require more than one token look ahead. Give an example of a production that does not have this property. Explain why this restriction is necessary for recursive descent parsing.

Explanation / Answer

1. Let the grammar be A-> Ab/b.

Let us see how top down parser works, recursive descent parser is a kind of top down parser. It works by replacing non- terminals by their production rules to achieve the string of terminals.

It is 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.

Considering how the parser will work here, reading first 'A', and then going to 'b', the parser wouldn't know which production to pick? Should it be Ab, that is, assuming there are multiple 'b's ahead or should it pick 'b', assuming that there is only one b ahead? Both these cases are ambiguous and might be wrong.

Also while expanding the non-terminal, A can be infinitely expanded to,

A->AAb->Abb->AAbb.... etc

The parser will attempt to solve all these possibilities, being caught in an infinite loop, and end up in exhausting memory.

Thus left recursion needs to be removed.

2.) Consider,

Looking at the grammar we can easily determine that abc and abcc both are valid inputs, the problem arises when you have the string abc to input, here we have to backtrack all the way up and this consumes time. The general problem here is that only that matching an input with grammar may result in large amount of backtracking, every new choice can have a different series of outcome and counting all them consumes lot of time. Thus providing single lookahead restricts the parser to make choice at a decision point and then commit to it. Such grammars are LL1 grammars.

Thus parser for LL1 grammar are easier to construct, reduces the chances of ambiguity, and saves time by not backtracking unneccessary.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.