From rlpowell@digitalkingdom.org Tue Nov 09 11:01:18 2004 Received: with ECARTIS (v1.0.0; list lojban-list); Tue, 09 Nov 2004 11:01:18 -0800 (PST) Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.34) id 1CRbEV-0003nd-Lf for lojban-list@lojban.org; Tue, 09 Nov 2004 11:00:47 -0800 Date: Tue, 9 Nov 2004 11:00:47 -0800 To: lojban-list@lojban.org Subject: [lojban] Re: Computer grammar question: non-left recursive RPN? Message-ID: <20041109190047.GV20718@chain.digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <20041107081848.GW18082@chain.digitalkingdom.org> <1624C623-3213-11D9-9684-000D9329C984@online.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1624C623-3213-11D9-9684-000D9329C984@online.fr> User-Agent: Mutt/1.5.6+20040722i From: Robin Lee Powell X-archive-position: 8968 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 06:49:14AM +0100, Rapha?l Poss wrote: > Le 7 nov. 04, ? 09:18, Robin Lee Powell a ?crit : > >Lojban has a reverse polish (i.e. postfix math) mode built in. > > > >The ABNF form of this rule is: > > > >rp-expression = rp-operand rp-operand operator > > > >rp-operand = operand / rp-expression > > > >which does exactly what you'd expect. > > > >I can't figure out a way to convert this into a version without > >left recursion. I've got: > > > >rp-expression = operand rp-expression-tail > >rp-expression-tail = rp-expression operator rp-expression-tail / () > > > >(where () is the empty production), but I'm not at all certain > >it's equivalent, and the parse trees it produces look very wrong > >(i.e. not left recursive at all). > > > >Help? > > (I assume from the ABNF grammar above that a RP expression has at > least 2 operands and 1 operator) *Excatly* 2 operands per operator. > What about : > > rp-expression = operand operand rp-tail > rp-tail = operand rp-tail / operator Umm, that's just: rp-expression = operand operand+ operator These are nested reverse polish notation expressions; very different. For example: 1 2 + 3 4 + + is (1 + 2) + (3 + 4) -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/