29 Nov 1997 00:28:53 -0500

Related articles |
---|

Q: regarding regular grammars ... mcr@visi.com (Michael Roach) (1997-11-24) |

Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-28) |

Re: Q: regarding regular grammars ... karsten@tdr.dk (Karsten Nyblad) (1997-11-29) |

Re: Q: regarding regular grammars ... jos@and.nl (Jos A. Horsmeier) (1997-11-29) |

Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-30) |

Re: Q: regarding regular grammars ... adrian@dcs.rhbnc.ac.uk (1997-12-05) |

From: | "Jos A. Horsmeier" <jos@and.nl> |

Newsgroups: | comp.compilers |

Date: | 29 Nov 1997 00:28:53 -0500 |

Organization: | AND Software B.V. Rotterdam |

References: | 97-11-136 |

Keywords: | lex |

Michael Roach wrote:

*> Could someone please shed some light on how regular grammars could be*

*> used to specify automata, or transducers, instead of using regular*

*> expressions? I think I've confused myself by reading into some papers.*

*>*

*> I thought regular expressions were regular grammars, is that assumption*

*> wrong? And if so, could you explain the differences or point me to some*

*> references. Thanks.*

The class of languages described by regular expressions (RE), type 3

(regular) grammars (RG) and the class of languages accepted by NFAs

or DFAs are all equal. It's quite easy to construct an NFA given a

RG -- all rules of a RG are of the following form:

1: S_1 ---> t S_2

2: S_1 ---> S_2

3: S_1 ---> t

4: S_1 ---> <epsilon>

given a RG, construct a NFA as follows:

- for every S_i add a vertex <S_i> to the NFA

- add one 'accepting' vertex <S_a>

- for every type 1 rule, add an edge <S_1> ---> t ---> <S_2>

- for every type 2 rule, add an edge <S_1> ---> <S_2>

- for every type 3 rule, add an edge <S_1> ---> t ---> <S_a>

- for every type 4 rule, add an edge <S_1> ---> <S_a>

The transformation from a NFA to a DFA can be found in any reasonable

textbook

(the Dragon book (a _good_ book ;-) comes to mind ...)

kind regards,

Jos aka jos@and.nl

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.