From rlpowell@digitalkingdom.org Fri Apr 09 13:15:43 2004 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 To: lojban-list@lojban.org Subject: [lojban] Re: Official parser and "lo ni'a zu crino" 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 From: Robin Lee Powell 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 Precedence: bulk Reply-to: lojban-list@lojban.org X-list: lojban-list 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