30 Nov 1997 22:53:35 -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: | Henry Spencer <henry@zoo.toronto.edu> |

Newsgroups: | comp.compilers |

Date: | 30 Nov 1997 22:53:35 -0500 |

Organization: | SP Systems, Toronto |

References: | 97-11-136 97-11-164 |

Keywords: | lex |

Karsten Nyblad <karsten@tdr.dk> wrote:

*>Yes, it is wrong. Regular grammar are a superset of context free*

*>grammars (CFG).*

By whose definition? The definition of regular grammars that I learned,

a long time ago, is that they are CFGs in which all rules are of one of

two forms:

N ::= T

N ::= M T

where N and M are nonterminal symbols and T is a terminal symbol. (It

makes no substantial difference if the second RHS is "T M" instead.)

This is a severe subset of CFGs -- in fact, regular grammars are Chomsky's

type 3, where CFGs are type 2 and completely unrestricted grammars are

type 0. Regular grammars are equivalent in power to classical textbook

regular expressions, which is how regular expressions got their name.

See, for example, pages 38-41 of the classic "Compiler Construction, an

Advanced Course", ed. Goos&Hartmanis, Springer-Verlag 1974.

--

| Henry Spencer

| henry@zoo.toronto.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.