4 ms·
> The problem with bottom-up parsers of any flavor, LR included, is that when you encounter a syntax error there is no context information, or context is diffic
by cwzwarich 8y ago
> The problem with bottom-up parsers of any flavor, LR included, is that when you encounter a syntax error there is no context information, or context is difficult to infer, which makes creating a sensible error message less fun than poking yourself in the eye repeatedly with a sharp stick.
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-reachability-cc2016.pdf 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 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.
- dbcurtis 8y agoInteresting. I will have to check out the link.
- mehrdadn 8y agoI'm unfamiliar with precedence parsing but what attracted me to (G)LR was its running time. What is the running time guarantee of a precedence parser for LR(k) and general (including potentially ambiguous) context-free grammars?
- cwzwarich 8y agoOperator precedence parsing is linear time, but it only produces a parser for a very limited set of grammars, the epsilon-free LR(1) grammars with no consecutive nonterminals. Precedence parsing is typically combined with another parsing method to parse a non-operator part of a grammar, or it is used with preprocessing filters that insert extra marker tokens to work around the limitations. Most programming languages have grammars that are very close to being operator precedence languages, so in the early days of parsing there were a lot of attempts to extend precedence parsing to handle more general grammars. After SLR/LALR parsing was developed, most of this work stopped.
- mehrdadn 8y agoThanks! That sounds awfully limiting if I'm being honest, even if a language is 'mostly' well-behaved... I can't say I can see how you could use preprocessing to get around the limitations since it would seem that doing so properly would require already parsing the input. It sounds like a nice method for when it works but it doesn't really sound like it would substitute for LR?
- oso2k 8y agoNot really limiting. Crockford used it in jslint [0][1][2] to parse JavaScript, and OIL Shell also uses it [3] to parse a shell language. [0] https://youtu.be/Nlqv6NtBXcA https://youtu.be/Nlqv6NtBXcA [1] https://crockford.com/javascript/tdop/tdop.html https://crockford.com/javascript/tdop/tdop.html [2] https://en.wikipedia.org/wiki/Operator-precedence_parser https://en.wikipedia.org/wiki/Operator-precedence_parser [3] https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html