Re: epsilon-free grammar

Jan Horner wrote:
>
> How can I get a EPSILON-free grammar (from a grammar)? I want to
> left-factorize that grammar. I'm reading the Aho-Sethi book but can
> find any solution.


First find all symbols from which eps can be derived. eps can be
derived from X if either there is a rule X->eps or if there is a rule
X->ABCDE... and eps can be derived from A, and from B, and from C, and
from D, and from E etc.


Now you have to do two things: Remove all the rules that allow
derivation of eps, and add some new rules so that nothing is lost from
the language. This is actually quite simple: Remove all rules of the
form X->eps. Then for every X from which eps can be derived, take all
the rules that have X on the right hand side, and add a new rule where
that X is removed from the right hand side. If X is on the right hand
side of a rule several times, add new rules that cover every possible
way of removing X from the right hand side. (Note: If you started with a
rule A->BXX, you would add rules A->BX, A->BX and A->B. That makes it
quite obvious that your grammar is ambiguous. But your grammar was
ambiguous in the first place).


Your language is unchanged with a single exception: In the new grammar
eps cannot be derived from the start symbol. If eps could be derived
from the start symbol in the original grammar then rename S to S', and
add two rules S->S' and S->eps. Usually such a grammar is still called
epsilon-free, and of course you need one rule with eps on the right hand
side if you want to be able to derive eps at all. Before I forget it, if
your grammar was ambiguous but only because you could derive eps from
the start symbol in different ways, then it has now been changed to be
not ambiguous.

Return to the comp.compilers page.
Search the comp.compilers archives again.