[lojban] Re: parsing with error detection and recovery

["Chris Capel" <lojban-out@lojban.org>]

On 8/17/06, Chris Capel <pdf23ds@gmail.com> wrote:
> On 8/17/06, Robin Lee Powell <rlpowell@digitalkingdom.org> wrote:
> > 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.
>
> 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.

I think this is the same as proving that the added option would never
be reached on any valid input, which sounds doable to me for some
rules. Here's one case where it's clear: where the added rule is the
same as the first part of some earlier rule. For instance, wherever
you have

x <- y !z

you should be able to add

x <- y !z / x-err
ERR x-err <- y

without ever changing the result on valid input.

So I think this is one provably safe way (though I'm not sure I've
proved it here) to add error rules to a PEG grammer, and as a plus,
one that makes it easy to keep the error stuff separate. (In a
separate file, you could have "x <- x-err" and have " / x-err"
appended to the main file when compiling the grammar.) I bet there are
other ways too.

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)


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.