4 ms·

How do LR(1) parsers compare to PEG?

wcrichton 11y ago
LR(1)-parseable context free grammars are more convenient to write than parsing expression grammars in my experience, partially because PEGs are completely unambiguous. PEG parsers often exist just because it's easier to implement them. Also, LR(1) parsers and LALRPOP generally operate on token streams and not plain strings, whereas PEG parsers need to encode lexing within the grammar, which is a pain. So if you were writing a compiler, I would recommend using an LR(1) parser over a PEG parser.
- chrisseaton 11y ago
  Your points aren't incorrect, but I'd consider many of your negative points to be positives. I'd say PEGs are easier to write as they're unambiguous. It's easy to understand what they do. I work on languages for a living, and I still have trouble wrapping my head around what an LR parser is doing. LR parsers often exist just because that's how we've done things for decades and it's what everyone knows from their university language courses. LR parser operate on a stream of tokens, so you have to force a distinction between syntax and parsing, which isn't always natural and just seems like unnecessary complication. If you were writing a compiler, I'd recommend a PEG.
  - haberman 11y ago
    > I'd say PEGs are easier to write as they're unambiguous. While that is technically true, it doesn't solve the actual issue of ambiguity, it just defines it away. If you have a case in your language where two syntax rules both match, it's confusing to users because you have to arbitrarily decide that one of them is correct. The best-known example of this is the dangling else ambiguity: https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else Sure, PEGs by definition are unambiguous, but only because they arbitrarily decide that the first option always "wins." The language itself might still be ambiguous, but you aren't aware of it because the parser always chooses the first option. Put another way, with PEGs you never know if: a -> b / c; is equivalent to: a -> c / b; You also don't know if there are rules that are entirely unreachable. Besides this, packrat parsing (the PEG parsing algorithm) is significantly more expensive than LR/LR parsing. Packrat parsing takes O(input length) memory -- significantly more than the O(tree depth) space of LL/LR. I talk more about these issues in my blog article: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...
    - craftkiller 11y ago
      Hey, thanks for the great blog posts but your blogging platform is frustrating to use on mobile because you have the swipe left/right to change articles in addition to code blocks that don't wrap. I'm having about a 10% success rate on horizontal scrolling in the code blocks on chrome on android, and the other 90% I'm unintentionally loading a different article. Just something to consider. Personally I'd drop the swipe navigation since I'm far more likely to use a search bar or index to find posts rather than flip through like a magazine. Thanks again, you did a better job explaining ll and lr than any of my professors did.
      - haberman 11y ago
        Thanks for the feedback and I'm so sorry it's so frustrating. I just tweaked my Blogger theme to just use the desktop theme on mobile -- hopefully this will be an improved experience!
        craftkiller 11y ago
        thanks!
- andolanra 11y ago
  PEGs can sometimes be pretty unintuitive. For example, consider the grammar ("a" / "aa") "a" in a traditional BNF setting, this grammar could match the string aa or the string aaa. However, this PEG will only accept the string aa, and cannot match the string aaa. (This is because of how backtracking works in PEGs—or, more precisely, how it doesn't work. With the input string aaa, we'll first try to match ("a" / "aa") against the input in a left-biased way, which succeeds because "a" matches. Then we'll try to match the second expression—"a"—which also matches. Now we are done with the grammar but still have the last a in the input, so the grammar fails. There were untried alternatives, but they only appeared in earlier parts of the grammar which had already 'succeeded', so we never go back and try them.) Additionally, both LR and PEG parsers take linear time to parse a given input, but PEG/packrat parsing has much larger constant factors. On small examples, this might not be a big deal (what's 0.2 seconds compared to 0.02 seconds when loading a file?) but when doing large amounts of parsing it can definitely be a minus on the PEG/Packrat side.

LR(1)-parseable context free grammars are more convenient to write than parsing expression grammars in my experience, partially because PEGs are completely unambiguous. PEG parsers often exist just because it's easier to implement them. Also, LR(1) parsers and LALRPOP generally operate on token streams and not plain strings, whereas PEG parsers need to encode lexing within the grammar, which is a pain. So if you were writing a compiler, I would recommend using an LR(1) parser over a PEG parser.

chrisseaton 11y ago
Your points aren't incorrect, but I'd consider many of your negative points to be positives. I'd say PEGs are easier to write as they're unambiguous. It's easy to understand what they do. I work on languages for a living, and I still have trouble wrapping my head around what an LR parser is doing. LR parsers often exist just because that's how we've done things for decades and it's what everyone knows from their university language courses. LR parser operate on a stream of tokens, so you have to force a distinction between syntax and parsing, which isn't always natural and just seems like unnecessary complication. If you were writing a compiler, I'd recommend a PEG.
- haberman 11y ago
  > I'd say PEGs are easier to write as they're unambiguous. While that is technically true, it doesn't solve the actual issue of ambiguity, it just defines it away. If you have a case in your language where two syntax rules both match, it's confusing to users because you have to arbitrarily decide that one of them is correct. The best-known example of this is the dangling else ambiguity: https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else Sure, PEGs by definition are unambiguous, but only because they arbitrarily decide that the first option always "wins." The language itself might still be ambiguous, but you aren't aware of it because the parser always chooses the first option. Put another way, with PEGs you never know if: a -> b / c; is equivalent to: a -> c / b; You also don't know if there are rules that are entirely unreachable. Besides this, packrat parsing (the PEG parsing algorithm) is significantly more expensive than LR/LR parsing. Packrat parsing takes O(input length) memory -- significantly more than the O(tree depth) space of LL/LR. I talk more about these issues in my blog article: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...
  - craftkiller 11y ago
    Hey, thanks for the great blog posts but your blogging platform is frustrating to use on mobile because you have the swipe left/right to change articles in addition to code blocks that don't wrap. I'm having about a 10% success rate on horizontal scrolling in the code blocks on chrome on android, and the other 90% I'm unintentionally loading a different article. Just something to consider. Personally I'd drop the swipe navigation since I'm far more likely to use a search bar or index to find posts rather than flip through like a magazine. Thanks again, you did a better job explaining ll and lr than any of my professors did.
    - haberman 11y ago
      Thanks for the feedback and I'm so sorry it's so frustrating. I just tweaked my Blogger theme to just use the desktop theme on mobile -- hopefully this will be an improved experience!
      - craftkiller 11y ago
        thanks!
andolanra 11y ago
PEGs can sometimes be pretty unintuitive. For example, consider the grammar ("a" / "aa") "a" in a traditional BNF setting, this grammar could match the string aa or the string aaa. However, this PEG will only accept the string aa, and cannot match the string aaa. (This is because of how backtracking works in PEGs—or, more precisely, how it doesn't work. With the input string aaa, we'll first try to match ("a" / "aa") against the input in a left-biased way, which succeeds because "a" matches. Then we'll try to match the second expression—"a"—which also matches. Now we are done with the grammar but still have the last a in the input, so the grammar fails. There were untried alternatives, but they only appeared in earlier parts of the grammar which had already 'succeeded', so we never go back and try them.) Additionally, both LR and PEG parsers take linear time to parse a given input, but PEG/packrat parsing has much larger constant factors. On small examples, this might not be a big deal (what's 0.2 seconds compared to 0.02 seconds when loading a file?) but when doing large amounts of parsing it can definitely be a minus on the PEG/Packrat side.