Re: Parsing Expression Grammar (PEG) vs. SBP (scannerless GLR)
Adam Megacz <megacz <at> cs.berkeley.edu>
2009-04-04 05:28:40 GMT
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:
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
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