LR Parsing: More Elegant Than You Think

Both LL and LR parsers share a fundamental flaw for error reporting; they are both prefix parsers. They will parse the input until it fails to be a valid prefix of the language represented by the grammar. However, it is rare that this coincides with the place where the actual error was made.

The difference in information available here at the end of the valid prefix is less about the difference between LL and LR parsing and more about the difference between LL and LR grammars. An LR parser parsing an LL grammar is able to recover the same information as an LL parser at the point of error. And for non-LL grammars, it is easy to extend an LR parser with additional context information by splitting states (see http://gallium.inria.fr/~fpottier/publis/fpottier-reachabili...).

Parsing algorithms that do not produce prefix parsers (e.g. precedence parsing) are often able to produce more logical error messages with less work, because they continue making actions after the input is no longer a valid prefix, and this can amount to gathering more information about the error. For the same reason, LR-family parsers that perform default reductions (e.g. LALR parsers, or any minimal state LR parser) often perform reductions (but not shifts) after the point of error, and produce better error messages than canonical LR parsers.

My favorite approach to error recovery is Richter's approach of error intervals (https://dl.acm.org/citation.cfm?id=4019), which uses alternating prefix/suffix parsers to find minimal error regions in the input that can not occur as a substring of any valid input. This has no dependence on the grammar or parsing technique. It was not (widely?) known at the time that Richter wrote his paper, but suffix parsing of LR grammars is linear time.

OTOH, top-down parsers LL(0), LL(1), LL(k) are far easier to maintain because there’s a straightforward correspondence of BNF to code. It’s not necessarily the fanciest

I fixed up operator precedence in a hobby project a few weeks ago, and found a really fun way to do it that turned out to require almost no code (but half a page of comments :-).

Basically I just parsed left to right, ignoring precedence (making everything right-associative and equal precedence) and then fixed up the precedence in a simple term rewriting pass after the fact.

The worst-case asymptotic complexity isn't super (quadratic for chains of multiplications, I think) but the code was so satisfying to write and the parser code itself is unbelievably simple.

Oh man I love to abuse term rewriting, I get so much mileage out that one little function...

Looking at the source, it's a bunch of JavaScript with what looks like the content in a very mildly obfuscated form, e.g.

    ["non-optimal"],["al","go","rithm"],["that"],["you"],["un","

...unless of course the whole page is a demo of using an LR parser to consume that oddly formatted content and output HTML, in which case I apologise. But a <noscript> with an explanation would be better than a blank page.

At the moment the layouting als breaks the expected behaviour when selecting the text (double-click usually selects a word, but on this website it selects a seemingly arbitrary sentence fragment). But this doesn’t matter because copy&paste is broken anway, since all spaces are removed (but random hyphens are instead included. uhm.)

Furthermore, the layout engine seems to attempt some microtypography corrections implemented by pdfTeX but does so relatively badly (dashes protrude too far, other punctuation doesn’t protrude at all; punctuation is broken incorrectly across lines; ). In sum, I’m not convinced this layout is actually even better than the browser’s, even ignoring the bugs.