Re: Q: regarding regular grammars ...

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
--

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