Week 2 There are two restrictions on the type of grammars that can be used with

Question

Week 2

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 ook 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

LL grammar is defined as follows:

A grammar is LL if and only if for any production A -> a|b, the following two conditions apply.

FIRST(a) and FIRST(b) are disjoint. This implies that they cannot both derive EMPTY

If b can derive EMPTY, then a cannot derive any string that begins with FOLLOW(A), that is FIRST(a) and FOLLOW(A) must be disjoint.

And I know that LL grammar can't be left recursive, but what is the formal reason? I guess left-recursive grammar will contradict rule 2, right? e.g., I've written following grammar:

Because FIRST(SA) = {a, empty} and FOLLOW(S) ={$, a}, then FIRST(SA) and FOLLOW(S) are not disjoint, so this grammar is not LL.

if a grammar contains left-recursive production, like:

Then somehow it must contain another production to "finish" the recursion,say:

And since FIRST(B) is a subset of FIRST(SA), so they are joint, this violates condition 1, there must be conflict when filling parse table entries corresponding to terminals both in FIRST(B) and FIRST(SA). To summarize, left-recursion grammar could cause FIRST set of two or more productions to have common terminals, thus violating condition 1.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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