30 Sep 2001 22:40:30 -0400

Related articles |
---|

epsilon-free grammar no_email@gmx.at (Jan Horner) (2001-09-26) |

Re: epsilon-free grammar torbenm@gna.diku.dk (2001-09-29) |

Re: epsilon-free grammar eernst@cs.auc.dk (Erik Ernst) (2001-09-29) |

Re: epsilon-free grammar christian.bau@isltd.insignia.com (Christian Bau) (2001-09-29) |

Re: epsilon-free grammar gzw@home.com (Geoff Wozniak) (2001-09-29) |

Re: epsilon-free grammar adrian@sartre.cs.rhbnc.ac.uk (A Johnstone) (2001-09-30) |

From: | A Johnstone <adrian@sartre.cs.rhbnc.ac.uk> |

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 <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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.