From lojban-out@lojban.org Sun Nov 07 11:18:04 2004 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com Received: (qmail 39128 invoked from network); 7 Nov 2004 19:18:03 -0000 Received: from unknown (66.218.66.216) by m20.grp.scd.yahoo.com with QMQP; 7 Nov 2004 19:18:03 -0000 Received: from unknown (HELO chain.digitalkingdom.org) (64.81.49.134) by mta1.grp.scd.yahoo.com with SMTP; 7 Nov 2004 19:18:03 -0000 Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.34) id 1CQsXL-00035w-W2 for lojban@yahoogroups.com; Sun, 07 Nov 2004 11:17:16 -0800 Received: from chain.digitalkingdom.org ([64.81.49.134]) by chain.digitalkingdom.org with esmtp (Exim 4.34) id 1CQsWc-00035H-Pl; Sun, 07 Nov 2004 11:16:30 -0800 Received: with ECARTIS (v1.0.0; list lojban-list); Sun, 07 Nov 2004 11:16:27 -0800 (PST) Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.34) id 1CQsWQ-00034y-NB for lojban-list@lojban.org; Sun, 07 Nov 2004 11:16:18 -0800 Date: Sun, 7 Nov 2004 11:16:18 -0800 Message-ID: <20041107191618.GC18082@chain.digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <258b0215cb.215cb258b0@imap.epfl.ch> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <258b0215cb.215cb258b0@imap.epfl.ch> User-Agent: Mutt/1.5.6+20040722i X-archive-position: 8960 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 X-list: lojban-list To: lojban@yahoogroups.com X-eGroups-Remote-IP: 64.81.49.134 X-eGroups-From: Robin Lee Powell From: Robin Lee Powell Reply-To: rlpowell@digitalkingdom.org Subject: [lojban] Re: Computer grammar question: non-left recursive RPN? X-Yahoo-Group-Post: member; u=116389790 X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 23365 On Sun, Nov 07, 2004 at 05:38:29PM +0100, GREGORY DYKE wrote: > As per promise, first a piece of code to illustrate how to make > the tree from the new grammar. > > > /** SumExpression = Term > * | SumExpression SumOp Term > */ > > ->LL(1) > SumExpression = Term {SumOp Term} That doesn't work for the RPN case. It works here because the operator is associative, but RPN has strict grouping. > > The ABNF form of this rule is: > > > > rp-expression = rp-operand rp-operand operator > > > > rp-operand = operand / rp-expression The easier to understand form is: rp-expression = rp-expression rp-expression operator / operand They are equivalent, except see below. > just one thing, can an rp-expression be just an operand? I would > have thought so... Apparently not, although my version does allow this. I have come up with a version that has no internal grammar at all (i.e. is purely iterative), but that is not much more satisfying. It is: rp-expression <- operand / operand operand (operator operand / operand operator)* operator It's based on my beliefe that any string that starts with two operands, ends in an operator, and has an equal number of operands and operators in the middle is a valid binary RPN string, but I have no proof of this. > Hey, wait! you need a stack to make the tree of rp-notation. You > can't do it in one-token lookahead (I presume the point of this > was to make it LL1)... No, the point was to make it work in a PEG grammar, which is LL(inf), sort of. > (take all this with a pinch of salt: I love this stuff and will > gladly look into it further, Please do. -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/