[pro] Is cl-yacc going to cut it?

[Scott L. Burson]

On Mon, Feb 14, 2011 at 2:43 AM, Samium Gromoff
<_deepfire at feelingofgreen.ru> wrote:
> I'm surprised that nobody has mentioned OMeta/ometa2 as of yet.
>
> It has this boolean functionality you speak of:

I wasn't familiar with it.  Based on a quick glance I don't think it
can handle boolean grammars in their full generality.  It's PEG-based,
and as I understand, PEGs cannot handle all context-free grammars.
The full boolean grammar formalism, on the other hand, is a strict
superset of context-free.

The big difference in practice is what is happening at runtime.  PEGs
are deterministic; SBP, on the other hand, is GLR-based, meaning that
it is constructing multiple possible parse trees simultaneously,
discarding the ones that don't work out.  If a string is ambiguous
under the given grammar, GLR will actually return all the possible
parses (there's a reasonably compact representation for this called a
"parse forest").  PEG by definition will only ever give one parse.

Of course, either of those could be a desirable property, depending on
what you're trying to parse and why.

-- Scott