29 Sep 2001 10:57:07 -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: | Christian Bau <christian.bau@isltd.insignia.com> |

Newsgroups: | comp.compilers |

Date: | 29 Sep 2001 10:57:07 -0400 |

Organization: | Insignia Solutions plc |

References: | 01-09-113 |

Keywords: | parse, theory |

Posted-Date: | 29 Sep 2001 10:57:06 EDT |

Jan Horner wrote:

*>*

*> How can I get a EPSILON-free grammar (from a grammar)? I want to*

*> left-factorize that grammar. I'm reading the Aho-Sethi book but can*

*> find any solution.*

First find all symbols from which eps can be derived. eps can be

derived from X if either there is a rule X->eps or if there is a rule

X->ABCDE... and eps can be derived from A, and from B, and from C, and

from D, and from E etc.

Now you have to do two things: Remove all the rules that allow

derivation of eps, and add some new rules so that nothing is lost from

the language. This is actually quite simple: Remove all rules of the

form X->eps. Then for every X from which eps can be derived, take all

the rules that have X on the right hand side, and add a new rule where

that X is removed from the right hand side. If X is on the right hand

side of a rule several times, add new rules that cover every possible

way of removing X from the right hand side. (Note: If you started with a

rule A->BXX, you would add rules A->BX, A->BX and A->B. That makes it

quite obvious that your grammar is ambiguous. But your grammar was

ambiguous in the first place).

Your language is unchanged with a single exception: In the new grammar

eps cannot be derived from the start symbol. If eps could be derived

from the start symbol in the original grammar then rename S to S', and

add two rules S->S' and S->eps. Usually such a grammar is still called

epsilon-free, and of course you need one rule with eps on the right hand

side if you want to be able to derive eps at all. Before I forget it, if

your grammar was ambiguous but only because you could derive eps from

the start symbol in different ways, then it has now been changed to be

not ambiguous.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.