From lojban-out@lojban.org Thu Aug 17 14:56:31 2006 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com Received: (qmail 80184 invoked from network); 17 Aug 2006 21:48:18 -0000 Received: from unknown (66.218.66.172) by m38.grp.scd.yahoo.com with QMQP; 17 Aug 2006 21:48:18 -0000 Received: from unknown (HELO chain.digitalkingdom.org) (64.81.49.134) by mta4.grp.scd.yahoo.com with SMTP; 17 Aug 2006 21:48:18 -0000 Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpfn-0003FJ-HK for lojban@yahoogroups.com; Thu, 17 Aug 2006 14:45:07 -0700 Received: from chain.digitalkingdom.org ([64.81.49.134]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1GDpfN-0003DT-Su; Thu, 17 Aug 2006 14:44:45 -0700 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 17 Aug 2006 14:44:33 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpex-0003Cg-UI for lojban-list-real@lojban.org; Thu, 17 Aug 2006 14:44:16 -0700 Received: from rlpowell by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpex-0003CZ-L4 for lojban-list@lojban.org; Thu, 17 Aug 2006 14:44:15 -0700 Date: Thu, 17 Aug 2006 14:44:15 -0700 Message-ID: <20060817214415.GJ17767@chain.digitalkingdom.org> Mail-Followup-To: lojban-list@lojban.org References: <737b61f30608151434h6ed71ec2k123f043c1ad59838@mail.gmail.com> <20060817211332.GH17767@chain.digitalkingdom.org> <737b61f30608171437l78935d36s1b1e71b299cf8f91@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <737b61f30608171437l78935d36s1b1e71b299cf8f91@mail.gmail.com> User-Agent: Mutt/1.5.12-2006-07-14 X-archive-position: 12488 X-ecartis-version: Ecartis v1.0.0 Errors-to: lojban-list-bounce@lojban.org X-original-sender: rlpowell@digitalkingdom.org X-list: lojban-list X-Spam-Score: -3.1 (---) To: lojban@yahoogroups.com X-Originating-IP: 64.81.49.134 X-eGroups-Msg-Info: 1:0:0:0 X-eGroups-From: Robin Lee Powell From: Robin Lee Powell Reply-To: rlpowell@digitalkingdom.org Subject: [lojban] Re: parsing with error detection and recovery X-Yahoo-Group-Post: member; u=116389790; y=XAPZrK0W-lffRu_m0G8nggwzaMBnpA0rzmz3cJ_UyLHPYyhxbA X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 26915 On Thu, Aug 17, 2006 at 04:37:52PM -0500, Chris Capel wrote: > On 8/17/06, Robin Lee Powell wrote: > >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? > > That's not what I'm trying to do though. Here's another way to > state it. Is there a way to prove that grammar B (derived though > specific rules from A) will always yield the same result as A, but > only on input strings that are completely and successfully parsed > by A? In effect, that B only differs from A where A fails? In > other words, that B is a strict superset of A? Ah, "strict superset" makes sense to me. I still don't know how to prove it, although I'm sure you could convince me it was true in a particular case. -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.