From lojban-out@lojban.org Fri Apr 09 13:16:29 2004 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com Received: (qmail 55825 invoked from network); 9 Apr 2004 20:16:29 -0000 Received: from unknown (66.218.66.166) by m22.grp.scd.yahoo.com with QMQP; 9 Apr 2004 20:16:29 -0000 Received: from unknown (HELO chain.digitalkingdom.org) (64.81.49.134) by mta5.grp.scd.yahoo.com with SMTP; 9 Apr 2004 20:16:29 -0000 Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.30) id 1BC2QN-0002Mx-Jd for lojban@yahoogroups.com; Fri, 09 Apr 2004 13:16:27 -0700 Received: from dsl081-049-134.sfo1.dsl.speakeasy.net ([64.81.49.134] helo=chain.digitalkingdom.org) by chain.digitalkingdom.org with esmtp (Exim 4.30) id 1BC2Pi-0002Lx-Ch; Fri, 09 Apr 2004 13:15:46 -0700 Received: with ECARTIS (v1.0.0; list lojban-list); Fri, 09 Apr 2004 13:15:43 -0700 (PDT) Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.30) id 1BC2Pa-0002Lk-5B for lojban-list@lojban.org; Fri, 09 Apr 2004 13:15:38 -0700 Date: Fri, 9 Apr 2004 13:15:38 -0700 Message-ID: <20040409201538.GS14789@digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <20040407124110.46977.qmail@web41903.mail.yahoo.com> <5.2.0.9.0.20040407062416.03375890@pop.east.cox.net> <20040407124110.46977.qmail@web41903.mail.yahoo.com> <5.2.0.9.0.20040408203833.037595d0@pop.east.cox.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <5.2.0.9.0.20040408203833.037595d0@pop.east.cox.net> User-Agent: Mutt/1.5.5.1+cvs20040105i X-archive-position: 7518 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: Official parser and "lo ni'a zu crino" X-Yahoo-Group-Post: member; u=116389790 X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 21992 On Thu, Apr 08, 2004 at 08:45:14PM -0400, Bob LeChevalier wrote: [the official parser] > (which unfortunately even with bugs has to remain a standard unless > you can prove that your alternate parser has the same grammar That's impossible. For one thing, I'm fairly certain that proving equivalence of two CFGs is equivalent to the halting problem. For another, the current 'grammar' isn't formalized at all in many major respects (the pre-processing and elidable terminators), so there's nothing to write a proof against. What I *am* doing is tens of thousands of lines of test cases intended to *demonstrate* the equivalence since, as I said, proof is impossible. > and that it is unambiguous to the same or higher degree than the YACC > grammar) Higher. *Much* higher. CFGs are ambiguous by nature, PEGs are unambiguous by nature. The proofs for the latter are available online, but as there is, definitionally, only one possible reading for a PEG against a given string a proof shouldn't even be neede. > (Note BTW that Nora's program is highly sensitive to any little > grammar changes, and Nora's program needs the output that the official > parser puts out with -t in order to work; I don't know if you are > planning a similar output format, but I hereby request it). I'm sorry, which program are you referring to? I'm certainly planning to output a parse tree of some kind. I can easily make something *like* the -t output, but as I don't understand how -t works I'm unwilling to guarantee a perfect match at this time. -Robin -- http://www.digitalkingdom.org/~rlpowell/ *** I'm a *male* Robin. "Many philosophical problems are caused by such things as the simple inability to shut up." -- David Stove, liberally paraphrased. http://www.lojban.org/ *** loi pimlu na srana .i ti rocki morsi