compiler construction - Left recursion elimination -


i'm attempting eliminate left recursion cfg eliminating indirect recursion direct recursion algorithm shows.

i'll using grammar:

a = a | b c | b c | d d 

when i = 1, , j = 1 looking @ replacing productions of form a -> r with:

a -> δ1 γ | δ2 γ | .. | δk γ

so when @ a -> a matches, should replace with

a -> a | b c a | b c | d d   

which im sure wrong

can point me in right direction how replace productions when replacing production itself?

note : also, i'm stuck on first rule have omitted others simplicity

any appreciated

[update]found close original greek symbols could. also, perhaps approaching in wrong direction. when i=1 , j=1, aj -> a | b c | b c | d d, should using aj -> b c | d d if get:

a -> b c | b c b c | d d | d d b c | b c | d d 

as eliminate recursion in production. better direction?

this recipe:

a → aα1 | ... | aαm | β1 | ... | βn 

should transformed to:

a → β1 a' | ... | βn a' a' → α1 a' | ... | αm a' | ε 

that is:

  1. replace recursive productions new productions in recursion on right. use new non-terminal symbol that.
  2. add production empty right side new non-terminal.
  3. append new non-terminal symbol right of non-recursive productions.

for grammar:

a = a | b c | b c | d d 

you obtain:

a  = b c a' | d d a' a' = a' | b c a' | ε 

Comments

Popular posts from this blog

Delphi Wmi Query on a Remote Machine -