|Making an NFA from a grammar email@example.com (2001-08-02)|
|Re: Making an NFA from a grammar firstname.lastname@example.org (Martijn de Vries) (2001-08-15)|
|Re: Making an NFA from a grammar email@example.com (Joachim Durchholz) (2001-08-17)|
|Re: Making an NFA from a grammar firstname.lastname@example.org (2001-08-18)|
|From:||"Joachim Durchholz" <email@example.com>|
|Date:||17 Aug 2001 00:12:13 -0400|
|Posted-Date:||17 Aug 2001 00:12:12 EDT|
compiler <firstname.lastname@example.org> 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
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.
Return to the
Search the comp.compilers archives again.