Re: Q: regarding regular grammars ...

Karsten Nyblad <>
29 Nov 1997 00:17:18 -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: Karsten Nyblad <>
Newsgroups: comp.compilers
Date: 29 Nov 1997 00:17:18 -0500
Organization: Tele Danmark Research
References: 97-11-136
Keywords: DFA, 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.

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
volume is
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"

Karsten Nyblad
Tele Danmark R&D

Post a followup to this message

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