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:
- replace recursive productions new productions in recursion on right. use new non-terminal symbol that.
- add production empty right side new non-terminal.
- 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
Post a Comment