Re: epsilon-free grammar

Erik Ernst <eernst@cs.auc.dk>
29 Sep 2001 10:56:15 -0400

          From comp.compilers
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)
| List of all articles for this month |
From: Erik Ernst <eernst@cs.auc.dk>
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 <no_email@gmx.at> 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.




    regards,


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