Re: Making an NFA from a grammar

"Joachim Durchholz" <joachim_d@gmx.de>
17 Aug 2001 00:12:13 -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: "Joachim Durchholz" <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 17 Aug 2001 00:12:13 -0400
Organization: Compilers Central
References: 01-08-008
Keywords: parse, lex
Posted-Date: 17 Aug 2001 00:12:12 EDT

compiler <meson@cyber.net.pk> wrote:
> Is there any algorithm,
> which when given a grammar, converts it back to an NFA, IFF the
> grammar represents a regular language.


Take a look at the Dragon book. It gives all the recipes for a tool
chain from a grammar to the final DFA. The only potential catch is
that it may assume that the grammar has a form that you cannot
guarantee (but if the grammar is regular it should be possible to
convert it).


I suspect it's possible to transform any grammar into the canonical form
that you want by substituting all nonterminals except the last one. I.e.
if you have
    A -> ... B ... C
    B -> asdf
    B -> hjkl
then transform this into
    A -> ... asdf ... C
    A -> ... hjkl ... C
Repeat the substitution until all grammar rules are in canonical form.
IIRC a non-regular language will have a rule of the form
    A -> ... A ...
after enough rounds of substitution, so the algorithm can terminate with
a "not a regular language" error message at that point.


You'll probably want to introduce some heuristics to keep the number of
generated rules under control.


Everything just off the top of my head and with little knowledge of the
state of the art in the area, so YMMV.


Regards,
Joachim


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.