Re: Definition of a regular grammar

Peter Gammie <peteg@cs.mu.OZ.AU>
11 Mar 2002 02:07:51 -0500

          From comp.compilers

Related articles
Definition of a regular grammar colinjunk@hotmail.com (Colin Manning) (2002-03-09)
Re: Definition of a regular grammar peteg@cs.mu.OZ.AU (Peter Gammie) (2002-03-11)
Re: Definition of a regular grammar stefan@infoiasi.ro (ANDREI Stefan) (2002-03-11)
Re: Definition of a regular grammar jle@forest.owlnet.rice.edu (2002-03-11)
Re: Definition of a regular grammar robin@kitsite.com (2002-03-11)
Re: Definition of a regular grammar pfroehli@ics.uci.edu (Peter H. Froehlich) (2002-03-17)
| List of all articles for this month |

From: Peter Gammie <peteg@cs.mu.OZ.AU>
Newsgroups: comp.compilers
Date: 11 Mar 2002 02:07:51 -0500
Organization: Compilers Central
References: 02-03-040
Keywords: parse, theory
Posted-Date: 11 Mar 2002 02:07:51 EST

Colin,


On 9 Mar 2002, Colin Manning wrote:


> I had always assumed that any grammar (Type 3) that contained only
> productions of the form
> A->Bx
> A->xB
> A->x
> had to be regular.


I think you'll find that either left recursion or right recursion (your
second and first rules respectively) alone gives the regular languages -
having both gives you the context free languages.


cheers
peter


Post a followup to this message

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