From lojban-out@lojban.org Tue Oct 30 17:47:42 2007 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com X-Received: (qmail 7171 invoked from network); 31 Oct 2007 00:47:42 -0000 X-Received: from unknown (66.218.67.96) by m54.grp.scd.yahoo.com with QMQP; 31 Oct 2007 00:47:42 -0000 X-Received: from unknown (HELO mail6.sea5.speakeasy.net) (69.17.117.8) by mta17.grp.scd.yahoo.com with SMTP; 31 Oct 2007 00:47:42 -0000 X-Received: (qmail 31600 invoked from network); 31 Oct 2007 00:47:38 -0000 X-Received: from chain.digitalkingdom.org ([64.81.66.169]) (envelope-sender ) by mail6.sea5.speakeasy.net (qmail-ldap-1.03) with AES256-SHA encrypted SMTP for ; 31 Oct 2007 00:47:38 -0000 X-Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.67) (envelope-from ) id 1In1k8-0002Va-HU for lojban@yahoogroups.com; Tue, 30 Oct 2007 17:47:37 -0700 X-Received: from chain.digitalkingdom.org ([64.81.66.169]) by chain.digitalkingdom.org with esmtp (Exim 4.67) (envelope-from ) id 1In1je-0002PU-LI; Tue, 30 Oct 2007 17:47:11 -0700 X-Received: with ECARTIS (v1.0.0; list lojban-list); Tue, 30 Oct 2007 17:44:46 -0700 (PDT) X-Received: from nobody by chain.digitalkingdom.org with local (Exim 4.67) (envelope-from ) id 1In1hN-0002PN-66 for lojban-list-real@lojban.org; Tue, 30 Oct 2007 17:44:46 -0700 X-Received: from rv-out-0910.google.com ([209.85.198.185]) by chain.digitalkingdom.org with esmtp (Exim 4.67) (envelope-from ) id 1In1hH-0002P7-Rt for lojban-list@lojban.org; Tue, 30 Oct 2007 17:44:44 -0700 X-Received: by rv-out-0910.google.com with SMTP id b22so1907931rvf for ; Tue, 30 Oct 2007 17:44:38 -0700 (PDT) X-Received: by 10.114.146.1 with SMTP id t1mr5434323wad.1193791478116; Tue, 30 Oct 2007 17:44:38 -0700 (PDT) X-Received: by 10.114.24.4 with HTTP; Tue, 30 Oct 2007 17:44:38 -0700 (PDT) Message-ID: <737b61f30710301744x530646c8q748ccb5190ec3eee@mail.gmail.com> Date: Tue, 30 Oct 2007 19:44:38 -0500 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline X-Spam-Score: -0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / X-archive-position: 13887 X-ecartis-version: Ecartis v1.0.0 Errors-to: lojban-list-bounce@lojban.org X-original-sender: pdf23ds@gmail.com X-list: lojban-list X-Spam-Score: -0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / To: lojban@yahoogroups.com X-Originating-IP: 69.17.117.8 X-eGroups-Msg-Info: 1:12:0:0:0 X-eGroups-From: "Chris Capel" From: "Chris Capel" Reply-To: pdf23ds@gmail.com Subject: [lojban] PEG left recursive definitions X-Yahoo-Group-Post: member; u=116389790; y=D8O17s7Ea9C6ZXwrafZy4qLL_PrJtL2PRo-lNAyqhzGSgOrKmA X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 28366 Does the PEG currently use left recursive definitions? If not, would it be helpful if it could? For instance. Example input: x ? x : x To parse this, we could write expr <- tri-cond / x tri-cond <- expr '?' expr ':' expr x <- 'x' This would be translated to expr-1 <- x tri-cond <- expr-1 '?' expr ':' expr / expr-1 expr <- tri-cond / expr-1 x <- 'x' I'm currently writing a PEG parser in C# that I hope will be able to support indirect left recursion, among other nice features. I have a quasi-mathematical algorithm that I believe shows that any level or complexity of indirect left-recursion can be resolved, (if anyone's interested I can post it,) but I'm not sure how it's going to work out. It could make a mess of the grammar, or maybe make optimizations much harder, or who knows what. Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet) To unsubscribe from this list, send mail to lojban-list-request@lojban.org with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if you're really stuck, send mail to secretary@lojban.org for help.