Re: Q: regarding regular grammars ...

Henry Spencer <henry@zoo.toronto.edu>
30 Nov 1997 22:53:35 -0500

          From comp.compilers

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)
| List of all articles for this month |

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.