From nobody@digitalkingdom.org Thu Aug 17 14:39:43 2006 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 17 Aug 2006 14:39:43 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1GDpaH-00037t-17 for lojban-list-real@lojban.org; Thu, 17 Aug 2006 14:39:25 -0700 Received: from py-out-1112.google.com ([64.233.166.176]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1GDpaG-00037i-1l for lojban-list@lojban.org; Thu, 17 Aug 2006 14:39:24 -0700 Received: by py-out-1112.google.com with SMTP id z74so1574249pyg for ; Thu, 17 Aug 2006 14:39:22 -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=lafpEc7BZ7SZm+QhYsQLrNXx475pchszEe2KdTnON8i+btgzwYo9wK/8Gdx4EIRKKmNZjGzQjmaYJYvAZ1h76NCFwqqxQWcOM/O908rhJtLsJXmbepVO3upAotY2jlUX9JJFzmWOeqfP7glsMLPJ3fXvxyQf9rHZKvLMNZ2bKf0= Received: by 10.35.45.1 with SMTP id x1mr4296548pyj; Thu, 17 Aug 2006 14:39:22 -0700 (PDT) Received: by 10.35.22.14 with HTTP; Thu, 17 Aug 2006 14:39:20 -0700 (PDT) Message-ID: <925d17560608171439h43b6194eu88cd63845e984bec@mail.gmail.com> Date: Thu, 17 Aug 2006 18:39:20 -0300 From: "=?ISO-8859-1?Q?Jorge_Llamb=EDas?=" 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: 12486 X-ecartis-version: Ecartis v1.0.0 Sender: lojban-list-bounce@lojban.org Errors-to: lojban-list-bounce@lojban.org X-original-sender: jjllambias@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. Surely that's too strong. Given: PEG1 text <- 'a' / 'b' PEG2 text <- a / b a <- 'a' b <- 'b' they can be proven to be equivalent? Maybe what you mean is that there is no known method that will prove the equivalence or not of any arbitrary pair of PEGs. But Chris might not need such a strong method anyway. > 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". No, he wants to prove that all the strings parsed by PEG A will be all and only the strings parsed by parser B which do not use any rule tagged as ERR. > In other words, I don't think your question is solvable, or even > makes any sense. I don't know if it's solvable, but the question does make sense to me. > Having said that, I think the original idea is a great one, and I'm > looking forward to the results. Me too. mu'o mi'e xorxes 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.