29 Nov 1997 00:17:18 -0500

Related articles |
---|

Q: regarding regular grammars ... mcr@visi.com (Michael Roach) (1997-11-24) |

Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-28) |

Re: Q: regarding regular grammars ... karsten@tdr.dk (Karsten Nyblad) (1997-11-29) |

Re: Q: regarding regular grammars ... jos@and.nl (Jos A. Horsmeier) (1997-11-29) |

Re: Q: regarding regular grammars ... henry@zoo.toronto.edu (Henry Spencer) (1997-11-30) |

Re: Q: regarding regular grammars ... adrian@dcs.rhbnc.ac.uk (1997-12-05) |

From: | Karsten Nyblad <karsten@tdr.dk> |

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

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.