15 Aug 2001 01:42:16 -0400

Related articles |
---|

Making an NFA from a grammar meson@cyber.net.pk (2001-08-02) |

Re: Making an NFA from a grammar martijn@shop.com (Martijn de Vries) (2001-08-15) |

Re: Making an NFA from a grammar joachim_d@gmx.de (Joachim Durchholz) (2001-08-17) |

Re: Making an NFA from a grammar vannoord@let.rug.nl (2001-08-18) |

From: | Martijn de Vries <martijn@shop.com> |

Newsgroups: | comp.compilers |

Date: | 15 Aug 2001 01:42:16 -0400 |

Organization: | XS4ALL Internet BV |

References: | 01-08-008 |

Keywords: | lex, parse |

Posted-Date: | 15 Aug 2001 01:42:16 EDT |

compiler <meson@cyber.net.pk> wrote:

*> In Sec 4.3 of Compilers Principles, Techniques, and Tools, the authors*

*> give an algorithm for converting an NFA into a grammar that generates*

*> the same language as recognized by the NFA. Is there any algorithm,*

*> which when given a grammar, converts it back to an NFA, IFF the*

*> grammar represents a regular language. I know it is easy for grammars*

*> of the sort A -> a B since this is the kind of grammar which the above*

*> mentioned algorithm generates, but is there an algorithm that does*

*> this for the general case? Where the grammar productions might not be*

*> in the for A -> a B but the grammar represents a regular language?*

As far as I know, a regular grammar may only contain productions of the

form "A -> a B" and "A -> a". So if you want to write an algorithm which

constructs an NFA out of a regular grammar you only need to consider these

two production forms.

Regards,

Martijn de Vries

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.