Re: epsilon-free grammar

Erik Ernst <>
29 Sep 2001 10:56:15 -0400

          From comp.compilers

Related articles
epsilon-free grammar (Jan Horner) (2001-09-26)
Re: epsilon-free grammar (2001-09-29)
Re: epsilon-free grammar (Erik Ernst) (2001-09-29)
Re: epsilon-free grammar (Christian Bau) (2001-09-29)
Re: epsilon-free grammar (Geoff Wozniak) (2001-09-29)
Re: epsilon-free grammar (A Johnstone) (2001-09-30)
| List of all articles for this month |

From: Erik Ernst <>
Newsgroups: comp.compilers
Date: 29 Sep 2001 10:56:15 -0400
Organization: Department of Computer Science, University of Aalborg, Denmark
References: 01-09-113
Keywords: parse, theory
Posted-Date: 29 Sep 2001 10:56:15 EDT

>>>>> "Jan" == Jan Horner <> writes:

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

There is no general solution to that problem. Consider the language
{\epsilon}, i.e., the language consisting of just one word, namely the
empty string. This language is derived by the grammar

    S -> \epsilon

and it's easy to see that any grammar deriving this language must have
an occurrence of \epsilon in at least one of its derivation rules.


Erik Ernst
Department of Computer Science, University of Aalborg, Denmark

Post a followup to this message

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