From rlpowell@digitalkingdom.org Thu Oct 23 12:30:59 2008 Received: with ECARTIS (v1.0.0; list llg-board); Thu, 23 Oct 2008 12:30:59 -0700 (PDT) Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.69) (envelope-from ) id 1Kt5tb-0003ci-Mn for llg-board@lojban.org; Thu, 23 Oct 2008 12:30:59 -0700 Date: Thu, 23 Oct 2008 12:30:59 -0700 From: Robin Lee Powell To: llg-board@lojban.org Subject: [llg-board] Re: A request to spend money. Message-ID: <20081023193059.GA31898@digitalkingdom.org> Mail-Followup-To: llg-board@lojban.org References: <20081022214253.GD23512@digitalkingdom.org> <20081022223521.GB31254@mercury.ccil.org> <20081022225329.GG23512@digitalkingdom.org> <20081022232701.GH23512@digitalkingdom.org> <20081023011215.GI23512@digitalkingdom.org> <20081023035133.GE4608@mercury.ccil.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.18 (2008-05-17) X-archive-position: 433 X-ecartis-version: Ecartis v1.0.0 Sender: llg-board-bounce@lojban.org Errors-to: llg-board-bounce@lojban.org X-original-sender: rlpowell@digitalkingdom.org Precedence: bulk Reply-to: llg-board@lojban.org X-list: llg-board Ah, *that's* what you were looking for. You should have just asked. :) "Hey Robin, who benefits in each case, and why?", for example. There are multiple kinds of formal grammars. CFGs are the most common, well-understood kind. The challenge is specifically about making a CFG version of Lojban. If we had a complete CFG version of Lojban, the advantage is that it would be *trivial* to make a Lojban parser in any language at any time. So, big advantage to the community there, IMO. The only parser that currently uses a completely formalized grammar is camxes, which uses PEGs. PEGs are not CFGs; they are not nearly as well understood or as broadly implemented. Parsers based on them are slower and use more memory. So, we'd prefer to have a CFG grammar instead of a PEG grammar if we can, but I don't believe a CFG grammar to be possible. Having a proof to the contrary would mean that those of use who have been investigating this issue (in my case, for *years*) could stop arguing about it. Just for the record, ZOI can't be done in CFGs or PEGs; it can only be done in a context-sensitive grammar, which is about as informal as formal grammars get: a CSG can contain any kind of rule at all. This is not a supposition; I could write the proof myself if the issue was in any doubt at all (it isn't, that I'm aware of). There are no parser generators for CSGs, and probably never will be. This means that every parser implementor will have to write some code to deal with ZOI. That's OK, though, because the *amount* of code required is tiny; two lines, generally. So no matter what we do, ZOI will be listed as an exception. -Robin On Thu, Oct 23, 2008 at 11:04:35AM -0400, Matt Arnold wrote: > Robin, John, thank you. > > From what you've said, I can work out a hypothesis about who > benefits and how they benefit. If it is proven that a formal > grammar that can encode elidable terminators is impossible, the > benefit is the satisfaction of curiosity of many in the Lojban > community. But if such a grammar is created, the benefit is that > we can more easily write a more complete Lojban parser in any > computer language. > > -Matt > > > On Wed, Oct 22, 2008 at 11:51 PM, John Cowan wrote: > > Matt Arnold scripsit: > > > >> I don't understand that either. I thought code, by virtue of being > >> code, has to be rigorously formalized in order for a computer to be > >> able to understand the instructions. That can't be what you mean, so > >> I'm confused. > > > > That's true in one sense. But there are two kinds of formal description: > > a program is a formal description of what the computer is to do, blow by > > blow, like a recipe or knitting instructions. A formal grammar, on the > > other hand, is a formal description of what the input to a program > > looks like, without any specification of how the program is to verify > > its input against that grammar. Given a grammar, it's possible to construct > > a program that detects that grammar and complains when the input violates it. > > However, not every formal grammar is usable in constructing such a program; > > it may need help from auxiliary programs. > > > > A PEG grammar is something in between: it specifies the valid inputs, but also > > an order in which its rules are to be tried. The YACC and BNF grammars have > > no such notion. > > > > I hope that helps. > > > > -- > > John Cowan http://ccil.org/~cowan cowan@ccil.org > > Arise, you prisoners of Windows / Arise, you slaves of Redmond, Wash, > > The day and hour soon are coming / When all the IT folks say "Gosh!" > > It isn't from a clever lawsuit / That Windowsland will finally fall, > > But thousands writing open source code / Like mice who nibble through a wall. > > --The Linux-nationale by Greg Baker > > > > > > > > -- They say: "The first AIs will be built by the military as weapons." And I'm thinking: "Does it even occur to you to try for something other than the default outcome?" -- http://shorl.com/tydruhedufogre http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/