Re: epsilon-free grammar

"Jan Horner" <no_email@gmx.at> 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.


You don't need an epsilon-free grammar to do left factorisation.
Nevertheless, here is how you remove epsilon productions:


  1) Pick a nonterminal N that has an epsilon production.


  2) Remove that production.


  3) All productions that have N once on the right-hand side are
        duplicated and the N is removed from one of the copies. Example:


A -> a N b


        becomes


A -> a N b
| a b


        In the general case, all productions that have N k times on the
        right-hand side are duplicated in 2^k copies such that all
        combinations of occurences of N being there or not are present.
        Example:


A -> a N b N c N d


        becomes


A -> a N b N c N d
| a N b N c d
| a N b c N d
| a N b c d
| a b N c N d
| a b N c d
| a b c N d
| a b c d


  4) If there are still epsilon-productions, go to step 1.




Note that, if the language accepts the empty string, this
transformation will remove this property. I.e., the transformed
grammer will accept L(G)\{epsilon}.


Note that the transformation will introduce productions that share a
prefix, causing more cases where left-facorisation is required. And
once you do left factorisation, you may reintroduce
epsilon-productions. Example:


    A -> a
        | a b


left-factorises to


    A -> a B
    B -> b | epsilon


which after epsilon-removal becomes


    A -> a B
        | a


    B -> b


There is no way to avoid both epsilon productions and overlapping
FIRST-sets for this language.


Torben Mogensen (torbenm@diku.dk)

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