[lojban] Re: parsing with error detection and recovery

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

On Thu, Aug 17, 2006 at 04:37:52PM -0500, Chris Capel 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. 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.