Week 2.1 There are two restrictions on the type of grammars that can be used wit

Question

Week 2.1

There are two restrictions on the type of grammars that can be used with a recursive descent parser 1. 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. 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.

Explanation / Answer

Recursive nonterminals in grammars are common and useful, and allow grammars to describe an infinite number of inputs. But left recursion is a particular form of recursion that cannot be directly handled by the simple LL(1) parsing algorithm. Left recursion just refers to any recursive nonterminal that, when it produces a sentential form containing itself, that new copy of itself appears on the left of the production rule. Because left recursion is a useful tool for grammar writers, anyone writing an LL(1) parser generator should make an effort to find a workaround for this weakness of the LL(1) algorithm. Fortunately, workarounds exist.

Take an example from the yacc manual for specifying a sequence of list of one or more item symbols:

We expect the first production (seq -> item) to be recognized when the first item is seen, and the second to be recognized for any additionalitem that follow in the sequence. (Throughout these examples, I'm ignoring the issue of what exactly terminates a list of item -- it is presumably defined by surrounding grammar not present in this fragment.)

The LL(1) parsing algorithm needs to know, for each non-terminal, what production to select based on looking at the next input token. In this example, when the parser decides it should expect a seq, it cannot choose which of these two productions should follow, since both productions can start (directly or indirectly) with an item. The situation is called "left recursion" because seq can repeatedly expand into itself on the left:

Indeed, if this grammar fragment were coded as a recursive descent parser, the function associated with non-terminal seq

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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