|Q: regarding regular grammars ... email@example.com (Michael Roach) (1997-11-24)|
|Re: Q: regarding regular grammars ... firstname.lastname@example.org (Henry Spencer) (1997-11-28)|
|Re: Q: regarding regular grammars ... email@example.com (Karsten Nyblad) (1997-11-29)|
|Re: Q: regarding regular grammars ... firstname.lastname@example.org (Jos A. Horsmeier) (1997-11-29)|
|Re: Q: regarding regular grammars ... email@example.com (Henry Spencer) (1997-11-30)|
|Re: Q: regarding regular grammars ... firstname.lastname@example.org (1997-12-05)|
|From:||Karsten Nyblad <email@example.com>|
|Date:||29 Nov 1997 00:17:18 -0500|
|Organization:||Tele Danmark Research|
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.
Yes, it is wrong. Regular grammar are a superset of context free
(CFG). Even the class of langauges of CFG's is larger than the class of
languages of regular expressions. The standard example is the language
a^n b^n, i.e. a repeated n times followed by b repeated n times. This
language can be described as the CFG:
S -> a b
S -> a S b
It can not be described as a regular expression.
I think you need to learn some basic theory of languages, automata, etc.
An old classical text is
Introduction to automata theory, languages, and computation /
John E. Hopcroft, JeffreyD. Ullman.
- Reading, Mass. : Addison-Wesley, 1979. - x, 418 s.
Try asking you teacher/the librarian if they can find something newer.
if you are very interested in parsing theory, you could try:
"Parsing theory" by Soisalon-Soininen, E. and Sippu, S. The first
from 1988, and is the volume of most interest to you. It has the
"Languages and parsing". The second volume is from 1990 and has the
"LR(k) and LL(k) parsing"
Tele Danmark R&D
Return to the
Search the comp.compilers archives again.