From lojban-out@lojban.org Thu Jul 13 08:52:02 2006 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com Received: (qmail 23966 invoked from network); 13 Jul 2006 15:52:01 -0000 Received: from unknown (66.218.67.35) by m38.grp.scd.yahoo.com with QMQP; 13 Jul 2006 15:52:01 -0000 Received: from unknown (HELO chain.digitalkingdom.org) (64.81.49.134) by mta9.grp.scd.yahoo.com with SMTP; 13 Jul 2006 15:52:01 -0000 Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1G13Q4-0004a3-Ka for lojban@yahoogroups.com; Thu, 13 Jul 2006 08:48:04 -0700 Received: from chain.digitalkingdom.org ([64.81.49.134]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1G13OT-0004ZH-9a; Thu, 13 Jul 2006 08:46:26 -0700 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 13 Jul 2006 08:46:14 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1G13Nv-0004Yv-Gc for lojban-list-real@lojban.org; Thu, 13 Jul 2006 08:45:51 -0700 Received: from ug-out-1314.google.com ([66.249.92.172]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1G13Nt-0004Yo-OE for lojban-list@lojban.org; Thu, 13 Jul 2006 08:45:51 -0700 Received: by ug-out-1314.google.com with SMTP id k3so333722ugf for ; Thu, 13 Jul 2006 08:45:48 -0700 (PDT) Received: by 10.67.29.12 with SMTP id g12mr193282ugj; Thu, 13 Jul 2006 08:45:47 -0700 (PDT) Received: by 10.67.30.12 with HTTP; Thu, 13 Jul 2006 08:45:47 -0700 (PDT) Message-ID: Date: Thu, 13 Jul 2006 11:45:47 -0400 In-Reply-To: <44B664C6.3010403@ropine.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20060713003616.GD18359@chain.digitalkingdom.org> <20060713013545.GF18359@chain.digitalkingdom.org> <20060713025542.GH18359@chain.digitalkingdom.org> <925d17560607130709u3fef60c5ubd8f638c795685c0@mail.gmail.com> <44B664C6.3010403@ropine.com> X-Spam-Score: -2.3 (--) X-archive-position: 12176 X-ecartis-version: Ecartis v1.0.0 Errors-to: lojban-list-bounce@lojban.org X-original-sender: jonored@gmail.com X-list: lojban-list X-Spam-Score: -2.3 (--) To: lojban@yahoogroups.com X-Originating-IP: 64.81.49.134 X-eGroups-Msg-Info: 1:0:0:0 X-eGroups-From: "Jonathan Gibbons" From: "Jonathan Gibbons" Reply-To: jonored@gmail.com Subject: [lojban] Re: Is Lojban a CFG? (was Re: [lojban-beginners] Re: Enumerating in Lojban) X-Yahoo-Group-Post: member; u=116389790; y=B0UbDPnUvXZqshcdtQNmW9r8Q80jGIi4jPEwaH1zOdArZF9CHQ X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 26603 Just a couple quick points, more when I have time; On 7/13/06, Seth Gordon wrote: > CFG and PEG are not just two different ways to express the same grammar. > For example, a pure CFG can't determine how to parse "if a then if b > then s1 else s2" (is the "else" connected to the first "if", or the > second?); since PEGs are always unambiguous, they can. While a pure CFG cannot determine a unique parse tree for that, it can determine whether or not it is in the language. But that's more just a nuance; CFGs define a language, and a language is just a set of strings, whereas PEGs are set up to specify a one-to-one association between a language and a set of parse trees as well as a language. > > Another complication is that the tools that build parsers from CFGs > cannot handle any arbitrary CFG; there are constraints on the > permissible grammars that are necessary to make the state tables manageable. Only some of them are limited, because the algorithms that make them more limited make them run much faster. There exist algorithms that combine the ability to parse arbitrary CFGs with the effeciency of the restricted versions when on inputs that they can handle; Generalised LR, for instance, does this. It runs in O(n) time on LR inputs, and O(n^3) on any input; to be impresice, which spot in between is determined by the degree to which it is not LR. -Jonathan 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.