Quiz remove left recursion from the grammar

Chapter 12 - 3
Parsing Techniques

LL(k) grammar

• An LL(k) grammar has the property that a parser can be constructed to scan an input string from left to right and build a leftmost derivation by examining next k input symbols to determine the unique production for each derivation step.

Consider the language {anb | n ∊ N}.

(1) It has the LL(1) grammar S → aS | b.

(3)
Solution. S → aaaS \| aab \| ab \| b.

• Answer: Any derivation starts with S ➾ AB. The next derivation step uses one of the productions A → aAb or A → Λ, depending on whether the scanned input letter is a or not. The argument is the same for B-productions.

•	It is not LL(1): Let the input be ab. The first letter a tells us to start with S ➾aSb.The letter a in aSb matches the first input letter, so we look ahead to the second input letter b.This tells us we must use S → T to get S ➾ aSb ➾ aTb.

The look ahead remains at b, so we can’t determine whether it is the last b of the input string.

The lookahead remains at bb, so we can’t determine whether these are the last two b’s of the input string. So we don’t know whether to choose T → bT or T → Λ for the next step. Thus the grammar is not LL(2).

• Note: The previous two examples show that {ambn | m ≤ n} is LL(1) but {ambn | m ≥ n} is not LL(k) for any k.

Quiz

S → abR

R → S | cT | Λ

• A left-recursive grammar is one which has a derivation of the form

A ➾+ Ax

•

LL(k) case: If the input string is ba…a with ka’s, the lookahead is ba…a with k – 1 a’s. So the derivation after k –1 steps is S ➾ Sa ➾Saa ➾ … ➾ Sa…a. Now, the input string could be ba…a (length k) or ba…a (length k + 1). Therefore we don’t know which production to choose next.

S → Sa | b.

• Solution. S → bT
T → aT | Λ.

S → Saa | aab | aac.

• Solution: S → aabT | aacT T → aaT | Λ.

Example

• Example (Removing indirect left recursion). Consider the following grammar.

S → bbT | aT

T → abT | Λ.

Now remove the direct left recursion: S → bbT | aT
T → AabT | Λ
A → SAa | b.

S → aSC | b

C → cC | d.

• A procedure is associated with each nonterminal. We’ll use the following procedure for LL(1) grammars to match a symbol with the lookahead symbol.

match(x): if lookahead = x
then lookahead := next input symbol else error
fi.

• Write recursive descent procedures for the following LL(1) grammar.

S → aaM
M → bT | cT
T → aaT | Λ.

• We’ll start with an example showing how to use the table to parse a string. Then we’ll discuss how to construct the table.

• Example. Consider the following LL(1) grammar and its corresponding parse table.

	a	b	$