Re: epsilon-free grammar

A Johnstone <>
30 Sep 2001 22:40:30 -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: A Johnstone <>
Newsgroups: comp.compilers
Date: 30 Sep 2001 22:40:30 -0400
Organization: Royal Holloway, University of London
References: 01-09-113 01-09-124
Keywords: parse, theory
Posted-Date: 30 Sep 2001 22:40:30 EDT

Erik Ernst <> wrote:
: 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.

Although trivially true, I don't think this is a very helpful
response. For a grammar G that generates a language L(G) that includes
the empty string, it is easy to make an epsilon-free grammar G' that
generates L(G)/{ (epsilon) } using the standard algorithm. You then
just unite the empty string back in by adding the production
S'->(epsilon) where S' is the start rule of G'. So, epsilon removal is
possible where L(G) does not contain epsilon, and where L(G) does
contain epsilon we have exactly one instance of an epsilon rule right
at the top of the grammar. This is enough to support most
parsing-domain activities that need epsilon free grammars. The point
is that Erik's 'at least one' could have been written 'at most one'
which is a stronger statement.

As a previous poster pointed out though, if you're an LL(1) person
trying to achieve left-factored epsilon free grammars then you'd
better watch out because in general you're going to be disapointed.

Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email Tel:+44(0)1784 443425 Fax:+44(0)1784 439786

Post a followup to this message

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