Re: epsilon-free grammar

Erik Ernst <eernst@cs.auc.dk> 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.


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

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