Re: [lojban] Re: parsing with error detection and recovery

["Chris Capel" <pdf23ds@gmail.com>]

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? 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)