5 ms·

LR Parsing: More Elegant Than You Think

160 points by jhpriestley 8y ago

isaachier 8y ago
What language is being used in the snippets?
- jhpriestley 8y ago
  Javascript
  - isaachier 8y ago
    Lol I thought it might be. The dialect has changed a lot since I last dabbled in JS.
    - ninjakeyboard 8y ago
      It's come a very long way.
      - rimliu 8y ago
        Not really.
dbcurtis 8y ago
1. Web site is just a blank white page on mobile Safari. 2. LR parsing is elegant in the mathematical sense of the word, but use in production leads to regret. 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. I contend that giving good error messages is the most important factor in user-friendliness of any parser. Look up "precedence climbing" -- a recursive descent parser with expressions handled by precedence climbing is going be an easier path to a production parser with good diagnostics, IMHO.
- fao_ 8y ago
  By precedence climbing are you referring to TDOP (Top-Down Operator Precedence)?
  - dbcurtis 8y ago
    No, let me copy and paste the first hit from Google: https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions...
    - taftster 8y ago
      From your link: > Update (2016-11-02): Andy Chu notes that precedence climbing and TDOP are pretty much the same algorithm, formulated a bit differently. I tend to agree, and also note that Shunting Yard is again the same algorithm, except that the explicit recursion is replaced by a stack. So, let's be careful about pasting a "first hit from Google" that you might not be discussing close to the same thing.
- 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.
yuchi 8y ago
The code snippets use JS in a very non idiomatic way — which makes this post interesting IMHumbleO There are few mutations that could be removed to have a clearer/purer functional approach, BTW
WallWextra 8y ago
I recently was looking at the original LR paper by Knuth, and for the first time noticed that it said "Case Institute of Technology" at the top. i.e. he discovered it as an undergrad.
- pmiller2 8y ago
  To be fair, there was a lot more not terribly complex yet still foundational stuff to be discovered then.
andreareina 8y ago
The layout engine is making the lines too long, which combined with hard line breaks means that this is what I get: ************************ *** ************************ ***** ************************ ** ************************ ****
- klmr 8y ago
  Honestly, the custom layouting on this website is cute but I wish the author would ship proper HTML code instead and accept the slightly (if that!) inferior layouting of the browser engine. 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.

160 points by jhpriestley 8y ago

isaachier 8y ago

What language is being used in the snippets?

jhpriestley 8y ago
Javascript
- isaachier 8y ago
  Lol I thought it might be. The dialect has changed a lot since I last dabbled in JS.
  - ninjakeyboard 8y ago
    It's come a very long way.
    - rimliu 8y ago
      Not really.

dbcurtis 8y ago

1. Web site is just a blank white page on mobile Safari. 2. LR parsing is elegant in the mathematical sense of the word, but use in production leads to regret. 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. I contend that giving good error messages is the most important factor in user-friendliness of any parser. Look up "precedence climbing" -- a recursive descent parser with expressions handled by precedence climbing is going be an easier path to a production parser with good diagnostics, IMHO.

fao_ 8y ago
By precedence climbing are you referring to TDOP (Top-Down Operator Precedence)?
- dbcurtis 8y ago
  No, let me copy and paste the first hit from Google: https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions...
  - taftster 8y ago
    From your link: > Update (2016-11-02): Andy Chu notes that precedence climbing and TDOP are pretty much the same algorithm, formulated a bit differently. I tend to agree, and also note that Shunting Yard is again the same algorithm, except that the explicit recursion is replaced by a stack. So, let's be careful about pasting a "first hit from Google" that you might not be discussing close to the same thing.
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.

yuchi 8y ago

The code snippets use JS in a very non idiomatic way — which makes this post interesting IMHumbleO There are few mutations that could be removed to have a clearer/purer functional approach, BTW

WallWextra 8y ago

I recently was looking at the original LR paper by Knuth, and for the first time noticed that it said "Case Institute of Technology" at the top. i.e. he discovered it as an undergrad.

pmiller2 8y ago
To be fair, there was a lot more not terribly complex yet still foundational stuff to be discovered then.

andreareina 8y ago

The layout engine is making the lines too long, which combined with hard line breaks means that this is what I get: ************************ *** ************************ ***** ************************ ** ************************ ****

klmr 8y ago
Honestly, the custom layouting on this website is cute but I wish the author would ship proper HTML code instead and accept the slightly (if that!) inferior layouting of the browser engine. 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.