## Elimination: Left Recursion

Again Elimination: left recursion is the Important topic of the Compiler Design. Additionally, we had described it very well.

- A grammar is said to be left recursive if it has a non-terminal A such that there is a

derivation A→Aα for some string α. - Top-down parsing methods cannot handle left-recursive grammar, so a transformation

that eliminates left recursion is needed.

**The Algorithm to Elimination: left recursion**

1. Assign an ordering A1,…, An to the nonterminals of the grammar.

2. for i:=1 to n do

begin

for j:=1 to i−1 do−1

begin

replace each production of the form Ai→Aiɣ

by the productions Ai ->δ1ɣ | δ2ɣ |…..| δkɣ

where Aj -> δ1 | δ2 |…..| δk are all the current Aj productions;

end

eliminate the intermediate left recursion among the Ai-production end.

Example 1: Consider the following grammar, on sider

- E→E+T/T

T→T*F/F

F→(E)/id

Eliminate immediate left recursion from above grammar then we obtain,

E→TE’

E’→+TE’ | ε

T→FT’

T’→*FT’ | ε

F→(E) | id

Example 2: Consider the following grammar, more onside

- S→Aa | b

A→Ac | Sd | ε

Here, non-terminal S is left recursive because S→Aa→Sda, but it is not immediately left,

recursive.

S→ Aa | b

A→Ac | Aad | bd | ε

Now, remove left recursion

S→Aa | b

A→ bdA’ | A’

A→ cA’ | adA’ | ε

**Left factoring: Elimination: left recursion**

Left factoring is a grammar transform that is useful for producing a grammar suitable for predictive parsing.

**The algorithm to left factor a grammar**

Input: Grammar G

Output: An equivalent left factored grammar.

1. For each non-terminal A find the longest prefix α common to two or more of its alternatives.

2. If α!= E, i.e., there is a non-trivial common prefix, replace all the A productions A→αβ1| αβ2|…………..| αβn| ɣ where ɣ represents all alternatives that do notβ begin with α by

A==> α A’| ɣ

A’==>β1|β2|………….| n|………….|β

Here A’ is a new non-terminal. Repeatedly apply this transformation until no two

alternatives for a non-terminal have a common prefix.

- EX1: Perform left factoring on following grammar,

A→ xByA | xByAzA | a

B→b

Left factored, the grammar becomes

A→ xByAA’ | a

A’→zA | Є

B→ b - EX2: Perform left factoring on following grammar,

S→iEtS | iEtSeS | a

E→b

Left factored, the grammar becomes

S→ iEtSS’ | a

S’→eS | Є

E→b

**Related Search**

Compiler Design, Recursive Decent Parsing, Ad-hoc, Free Study.

## Leave a Reply