CODEWITHSUNDEEP
parsingcompiler-constructiontopdown
Mahdi
Mahdi

Reputation: 175

How to implement a left recursion eliminator?

How can i implement an eliminator for this?

 A := AB |
      AC |
      D  |
      E  ;

Upvotes: 1

Views: 840

Answers (2)

BCS
BCS

Reputation: 78683

Another form available is:

A := (D | E) (B | C)*

The mechanics of doing it are about the same but some parsers might handle that form better. Also consider what it will take to munge the action rules along with the grammar its self; the other form requires the factoring tool to generate a new type for the A' rule to return where as this form doesn't.

Upvotes: 0

aioobe
aioobe

Reputation: 421180

This is an example of so called immediate left recursion, and is removed like this:

A := DA' |
     EA' ;

A' := ε   |
      BA' |
      CA' ;

The basic idea is to first note that when parsing an A you will necessarily start with a D or an E. After the D or an E you will either end (tail is ε) or continue (if we're in a AB or AC construction).

The actual algorithm works like this:

For any left-recursive production like this: A -> A a1 | ... | A ak | b1 | b2 | ... | bm replace the production with A -> b1 A' | b2 A' | ... | bm A' and add the production A' -> ε | a1 A' | ... | ak A'.

See Wikipedia: Left Recursion for more information on the elimination algorithm (including elimination of indirect left recursion).

Upvotes: 4

Related Questions