From rlpowell@digitalkingdom.org Tue Nov 09 11:03:26 2004
Received: with ECARTIS (v1.0.0; list lojban-list); Tue, 09 Nov 2004 11:03:26 -0800 (PST)
Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.34)
	id 1CRbGZ-00042F-Bz
	for lojban-list@lojban.org; Tue, 09 Nov 2004 11:02:55 -0800
Date: Tue, 9 Nov 2004 11:02:55 -0800
To: lojban-list@lojban.org
Subject: [lojban] Re: Computer grammar question: non-left recursive RPN?
Message-ID: <20041109190255.GW20718@chain.digitalkingdom.org>
Mail-Followup-To: lojban-list@lojban.org
References: <20041107081848.GW18082@chain.digitalkingdom.org> <1099989949.419083bdf00a0@imp3-q.free.fr>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1099989949.419083bdf00a0@imp3-q.free.fr>
User-Agent: Mutt/1.5.6+20040722i
From: Robin Lee Powell <rlpowell@digitalkingdom.org>
X-archive-position: 8969
X-ecartis-version: Ecartis v1.0.0
Sender: lojban-list-bounce@lojban.org
Errors-to: lojban-list-bounce@lojban.org
X-original-sender: rlpowell@digitalkingdom.org
Precedence: bulk
Reply-to: lojban-list@lojban.org
X-list: lojban-list

On Tue, Nov 09, 2004 at 09:45:49AM +0100, Jo l'apache wrote:
> 
> rp-expression = rp-operand rp-operand operator
> rp-operand = operand / rp-expression
> 
> here is the version without left-recursion
> 
> rp-expression = rp-operand rp-operand operator
> rp-operand    = rp-operand' rp-operand
> rp-operand'   = () | rp-operand operator

Nope.

rp-operand    = rp-operand' rp-operand

which can be expanded to:

rp-operand    = ( () | rp-operand operator) rp-operand

which can be expanded to:

rp-operand    = rp-operand | rp-operand operator rp-operand

which is left recursive in both cases.

-Robin

-- 
http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/
Reason #237 To Learn Lojban: "Homonyms: Their Grate!"
Proud Supporter of the Singularity Institute - http://singinst.org/