[lojban] Re: parsing with error detection and recovery

[Robin Lee Powell <lojban-out@lojban.org>]

On Thu, Aug 17, 2006 at 06:39:20PM -0300, Jorge Llamb?as wrote:
> On 8/17/06, Robin Lee Powell <rlpowell@digitalkingdom.org> 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?

Oh, probably, but I don't know how.

> Maybe what you mean is that there is no known method that will
> prove the equivalence or not of any arbitrary pair of PEGs. 

That is what I meant, yes.

-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.