The Scannerless Boolean Parser ()

Bernhard Damberger | 3 Apr 2009 02:11

Parsing Expression Grammar (PEG) vs. SBP

I am curious as to what you think about the current rage in the parsing world
with PEGs (and Packrat parsing)?

Caveat: I don't know much about SBP or the boolean grammars.

I know PEGs are linear (in both time and memory). I noticed that SBP is  O(n^3
log n) in time. How about in memory?

The thing about PEGs that interests me is their application with regards to
extensible langauges and DSLs. It sounds like SBP might be good for an
extensible language.

Any insight or comments appreciated.

_bernhard

headers

Adam Megacz | 4 Apr 2009 07:28

Re: Parsing Expression Grammar (PEG) vs. SBP (scannerless GLR)

Bernhard Damberger <bernied <at> gmail.com> writes:
> I am curious as to what you think about the current rage in the
> parsing world with PEGs (and Packrat parsing)?

PEGs are quite nice.  Keep in mind, however, that in order to use them
the grammar writer must prioritize all choices; this can lead to very
subtle errors.  Terrence Parr puts it quite well:

  http://article.gmane.org/gmane.comp.parsers.peg.general/2

In contrast, advanced GLR parsers give you both prioritized choice and
nondeterministic choice.  The latter results in a runtime error
(ambiguity) when both alternatives match the string.

Adding exclusive choice -- wherein the parser generator must prove at
grammar compilation time that no string matches both alternatives --
would turn this runtime error into a compile-time error.  It's
undecidable in general, but tractible in many common cases.  Someday
I'd like to add it to SBP.

Bryan Ford gives an example of a CFG that PEGs cannot parse in his
ICFP'02 paper:

  S = "x" S "x" | "x"

> I know PEGs are linear (in both time and memory).
> I noticed that SBP is O(n^3 log n) in time.

Only for pathological grammars.  If you give SBP an LALR grammar, it

(Continue reading)