On Mon, Feb 14, 2011 at 2:43 AM, Samium Gromoff _deepfire@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