Re: Making an NFA from a grammar

Martijn de Vries <martijn@shop.com>
15 Aug 2001 01:42:16 -0400

          From comp.compilers
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)
| List of all articles for this month |
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.