Re: Making an NFA from a grammar

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

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