From nobody@digitalkingdom.org Thu Aug 17 14:13:52 2006 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 17 Aug 2006 14:13:53 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpBF-0002mK-FW for lojban-list-real@lojban.org; Thu, 17 Aug 2006 14:13:33 -0700 Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpBF-0002mD-6Q for lojban-list@lojban.org; Thu, 17 Aug 2006 14:13:33 -0700 Date: Thu, 17 Aug 2006 14:13:33 -0700 To: lojban-list@lojban.org Subject: [lojban] Re: parsing with error detection and recovery Message-ID: <20060817211332.GH17767@chain.digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <737b61f30608151434h6ed71ec2k123f043c1ad59838@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <737b61f30608151434h6ed71ec2k123f043c1ad59838@mail.gmail.com> User-Agent: Mutt/1.5.12-2006-07-14 From: Robin Lee Powell X-archive-position: 12484 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 Tue, Aug 15, 2006 at 04:34:57PM -0500, Chris Capel wrote: > So, my question is this: is there an easy way to prove the > equivalence of PEG parser A with the parts of parser B that apply > only to valid input? I'm not aware of any way to prove equivalence of any two PEGs, ever. I'm not even aware of a way to do that with CFGs. Furthermore, what you just said sounds like: I have these two PEGs with known-different behaviour. How do I prove they are the same? To which I'd answer, "Umm, you don't, because they aren't". In other words, I don't think your question is solvable, or even makes any sense. Having said that, I think the original idea is a great one, and I'm looking forward to the results. I have a large collection of test cases you could use to test practical equivalence. -Robin -- http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/ Reason #237 To Learn Lojban: "Homonyms: Their Grate!" Proud Supporter of the Singularity Institute - http://singinst.org/ 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.