[lojban] Re: Official parser and "lo ni'a zu crino"

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

On Thu, Apr 08, 2004 at 08:45:14PM -0400, Bob LeChevalier wrote:
[the official parser]
> (which unfortunately even with bugs has to remain a standard unless
> you can prove that your alternate parser has the same grammar 

That's impossible.  For one thing, I'm fairly certain that proving
equivalence of two CFGs is equivalent to the halting problem.  For
another, the current 'grammar' isn't formalized at all in many major
respects (the pre-processing and elidable terminators), so there's
nothing to write a proof against.

What I *am* doing is tens of thousands of lines of test cases intended
to *demonstrate* the equivalence since, as I said, proof is impossible.

> and that it is unambiguous to the same or higher degree than the YACC
> grammar)

Higher.  *Much* higher.  CFGs are ambiguous by nature, PEGs are
unambiguous by nature.  The proofs for the latter are available online,
but as there is, definitionally, only one possible reading for a PEG
against a given string a proof shouldn't even be neede.

> (Note BTW that Nora's program is highly sensitive to any little
> grammar changes, and Nora's program needs the output that the official
> parser puts out with -t in order to work; I don't know if you are
> planning a similar output format, but I hereby request it).

I'm sorry, which program are you referring to?

I'm certainly planning to output a parse tree of some kind.  I can
easily make something *like* the -t output, but as I don't understand
how -t works I'm unwilling to guarantee a perfect match at this time.

-Robin

-- 
http://www.digitalkingdom.org/~rlpowell/  ***  I'm a *male* Robin.
"Many philosophical problems are caused by such things as the simple
inability to shut up." -- David Stove, liberally paraphrased.
http://www.lojban.org/  ***  loi pimlu na srana .i ti rocki morsi