Re: Q: regarding regular grammars ...

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
grammars
(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
volume is
from 1988, and is the volume of most interest to you. It has the
subtitel
"Languages and parsing". The second volume is from 1990 and has the
subtitel
"LR(k) and LL(k) parsing"


Karsten Nyblad
karsten@tdr.dk
Tele Danmark R&D
--

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