[lojban] Re: parsing with error detection and recovery

[Robin Lee Powell <rlpowell@digitalkingdom.org>]

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?

To which I'd answer, "Umm, you don't, because they aren't".

In other words, I don't think your question is solvable, or even
makes any sense.

Having said that, I think the original idea is a great one, and I'm
looking forward to the results.

I have a large collection of test cases you could use to test
practical equivalence.

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