From nobody@digitalkingdom.org Thu Aug 17 14:38:13 2006 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 17 Aug 2006 14:38:13 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpYp-000361-2g for lojban-list-real@lojban.org; Thu, 17 Aug 2006 14:37:55 -0700 Received: from nf-out-0910.google.com ([64.233.182.186]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1GDpYn-00035u-Nh for lojban-list@lojban.org; Thu, 17 Aug 2006 14:37:54 -0700 Received: by nf-out-0910.google.com with SMTP id m19so1230782nfc for ; Thu, 17 Aug 2006 14:37:52 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=f7NrzZTPmqwIbVtUjYi4Cikrm68TrDQiDr7mzbtIBhTYsx7ZHpv17DtAFRT0oTQp+CgK6iJ2UEo54rg+iHI58oNHmT3vzcwJsMx/J6L6xOwnbhzVhtQhIRxLaq1/JjQdRIiPbxIedKzw5DfBmKyyZgIFjRbtO5V7/1WAQC+qz60= Received: by 10.49.8.4 with SMTP id l4mr3082811nfi; Thu, 17 Aug 2006 14:37:52 -0700 (PDT) Received: by 10.49.92.8 with HTTP; Thu, 17 Aug 2006 14:37:52 -0700 (PDT) Message-ID: <737b61f30608171437l78935d36s1b1e71b299cf8f91@mail.gmail.com> Date: Thu, 17 Aug 2006 16:37:52 -0500 From: "Chris Capel" To: lojban-list@lojban.org Subject: [lojban] Re: parsing with error detection and recovery In-Reply-To: <20060817211332.GH17767@chain.digitalkingdom.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <737b61f30608151434h6ed71ec2k123f043c1ad59838@mail.gmail.com> <20060817211332.GH17767@chain.digitalkingdom.org> X-Spam-Score: -2.4 (--) X-archive-position: 12485 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-list-bounce@lojban.org Errors-to: lojban-list-bounce@lojban.org X-original-sender: pdf23ds@gmail.com Precedence: bulk Reply-to: lojban-list@lojban.org X-list: lojban-list 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? In fact, I'm only looking for a way to prove this where B differs from A only in one specific, small, modification. Say, the addition of a rule and one reference to that rule in a new option at the end of an existing rule. Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet) 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.