17 Aug 2001 00:12:13 -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: | "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.