From lojban-out@lojban.org Mon Nov 08 12:12:16 2004 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com Received: (qmail 73097 invoked from network); 8 Nov 2004 20:12:16 -0000 Received: from unknown (66.218.66.218) by m3.grp.scd.yahoo.com with QMQP; 8 Nov 2004 20:12:16 -0000 Received: from unknown (HELO chain.digitalkingdom.org) (64.81.49.134) by mta3.grp.scd.yahoo.com with SMTP; 8 Nov 2004 20:12:16 -0000 Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.34) id 1CRFrk-00078B-4R for lojban@yahoogroups.com; Mon, 08 Nov 2004 12:11:52 -0800 Received: from chain.digitalkingdom.org ([64.81.49.134]) by chain.digitalkingdom.org with esmtp (Exim 4.34) id 1CRFoE-000743-8y; Mon, 08 Nov 2004 12:08:14 -0800 Received: with ECARTIS (v1.0.0; list lojban-list); Mon, 08 Nov 2004 12:08:00 -0800 (PST) Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.34) id 1CRFnr-00073q-7Y for lojban-list@lojban.org; Mon, 08 Nov 2004 12:07:51 -0800 Date: Mon, 8 Nov 2004 12:07:51 -0800 Message-ID: <20041108200751.GC20718@chain.digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <2756b2b539.2b5392756b@imap.epfl.ch> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <2756b2b539.2b5392756b@imap.epfl.ch> User-Agent: Mutt/1.5.6+20040722i X-archive-position: 8962 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: 23367 On Mon, Nov 08, 2004 at 02:21:23PM +0100, GREGORY DYKE wrote: > I have talked to the kind folks who are post-grads in the lab > where the compiler course was given. They have never heard of PEG > parsers That's hardly surprising, but they may want to look into them; it's a very elegant formalism. > and don't understand the problem: > > rp-notation is not LL(1). This is clear. (well, it is LL1, but you > can't easily generate the tree from it). > > rp-notation is however extremely simple to parse with a stack. > They say that if PEG is LL(inf) in theory, why can't it do shift > reduction like yacc? (I havn't looked into this, so I have no > clue...) I have no idea what shift reduction is. I could easily solve the problem by attaching code to the productions, which is what I think they are saying, but I'm trying to keep the grammar as general as possible, i.e. not tied to any particular parser generator or language. Yacc is LR, btw; totally different case. > > 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 > > I see nothing wrong with this. Except that it's wrong. > In fact, here is a demonstration of the proof of this grammar: Which is interesting, since people have provided counter-examples, such as: 1 2 3 + + + 4 5 + -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/