There are two restrictions on the type of grammars that can be used with a recur
ID: 3876453 • Letter: T
Question
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
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.
Answer:
A recursive descent parser is a kind of top-down parser. LL parsing is used for it, which parses the input from left to right, and uses a leftmost derivation. The parser cannot parse a grammar that contains left recursion because the grammar will go into an infinite loop.
For example, a simple LL(1) parser written in C is as follows.
By using term() above, a multiplying function is as below.
The grammar above can be expressed as "<mexpr> -> term * mexpr" in CFG; however, in case of "<mexpr> -> mexpr * term", the grammar will go into an infinite loop as following the function.
2)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.
Answer:
The grammar requires only one token look ahead to prevent from backtracking that lowers execution efficiency. You can avoid backtracking by changing expression (a) to (b) as follows.
(a)
(b)
LL(k) parsing (for k > 1) which requires two or more tokens look ahead, but the method is impractical because of inefficiency.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.