From nobody@digitalkingdom.org Thu Aug 17 14:44:33 2006 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 To: lojban-list@lojban.org Subject: [lojban] Re: parsing with error detection and recovery 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 From: Robin Lee Powell X-archive-position: 12488 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, 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.