Step by step elimination of this indirect left recursion
Asked Answered
S

2

14

I've seen this algorithm one should be able to use to remove all left recursion. Yet I'm running into problems with this particular grammar:

A -> Cd
B -> Ce
C -> A | B | f

Whatever I try I end up in loops or with a grammar that is still indirect left recursive.

What are the steps to properly implement this algorithm on this grammar?

Simferopol answered 14/4, 2013 at 14:2 Comment(1)
This should be migrated to cstheory.stackexchange.com since this has nothing to do with programming, only CS theory.Coughlin
F
31

Rule is that you first establish some kind of order for non-terminals, and then find all paths where indirect recursion happens.

In this case order would be A < B < C, and possible paths for recursion of non-terminal C would be

C=> A => Cd

and

C=> B => Ce

so new rules for C would be

C=> Cd | Ce | f

now you can simply just remove direct left recursion:

C=> fC'
C'=> dC' | eC' | eps

and the resulting non-recursive grammar would be:

A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps
Flounder answered 10/1, 2014 at 14:24 Comment(0)
S
11

Figured it out already.

My confusion was that in this order, the algorithm seemed to do nothing, so I figured that must be wrong, and started replacing A -> Cd in the first iteration (ignoring j cannot go beyond i) getting into infinite loops.

1) By reordering the rules:

C -> A | B | f 
A -> Cd
B -> Ce

2) replace C in A -> Cd

C -> A | B | f 
A -> Ad | Bd | fd
B -> Ce

3) B not yet in range of j, so leave that and replace direct left recursion of A

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ce

4) replace C in B -> Ce

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ae | Be | fe

5) not done yet! also need to replace the new rule B -> Ae (production of A is in range of j)

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> BdA'e | fdA'e | Be | fe

6) replace direct left recursion in productions of B

C -> A | B | f 
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> fdA'eB' | feB'
B'-> dA'eB' | eB' | epsylon

woohoo! left-recursion free grammar!

Simferopol answered 14/4, 2013 at 14:34 Comment(3)
Can't you simply C -> fD with D -> eps | dD | eDLuhey
hah, yes, you're right! though the above was good practice for the algorithm, that would indeed have been the simplest rewrite. thank you. Is there any general rule you used to get that, or is just common sense that comes from practice? ;)Simferopol
There is typo error in step-5, first production of B. It should be BdA'eMolality

© 2022 - 2024 — McMap. All rights reserved.