Re: Q: regarding regular grammars ... (A Johnstone)
5 Dec 1997 01:13:52 -0500

          From comp.compilers

Related articles
Q: regarding regular grammars ... (Michael Roach) (1997-11-24)
Re: Q: regarding regular grammars ... (Henry Spencer) (1997-11-28)
Re: Q: regarding regular grammars ... (Karsten Nyblad) (1997-11-29)
Re: Q: regarding regular grammars ... (Jos A. Horsmeier) (1997-11-29)
Re: Q: regarding regular grammars ... (Henry Spencer) (1997-11-30)
Re: Q: regarding regular grammars ... (1997-12-05)
| List of all articles for this month |

From: (A Johnstone)
Newsgroups: comp.compilers
Date: 5 Dec 1997 01:13:52 -0500
Organization: Royal Holloway, University of London
References: 97-11-136 97-11-164
Keywords: lex

Michael Roach wrote:
: > 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.

Karsten Nyblad ( wrote:
: Yes, it is wrong. Regular grammar are a superset of context free
: grammars
: (CFG). Even the class of langauges of CFG's is larger than the class of
: languages of regular expressions.

I think Karsten has misread the original question - Michael was
talking about regular grammars not context free grammars. Contrary to
Karsten's claim, regular grammars are a subset of CFG not a
superset. It is easy to convert from a RE to a RG grammar as long as
the RE doesn't use extended notions like variables (these things are
not really RE's, formally).

I find the Parsing Theory twin volume set recommended by Karsten good
for some theory but less good for everyday queries. The most readable
reference I know is Dick Grunne's book on parsing published a few
years ago by Ellis Horwood and now sadly out of print, but obtainable
from your library, perhaps? Personally I find the treatment in the
dragon book repetetive and disorganised.


Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
    Email Tel: 01784 443425 Fax: 01784 439786

Post a followup to this message

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