4 ms·

Can someone summarize what PEG is? I read through the Wikipedia page but can't make heads or tails of it. What is this used for?

by geuis 15y ago

kevinburke 15y ago
PEG parsers get rid of the dangling else problem with recursive descent parsers where it's unclear in the following statement whether if e then s1 else if e then s2 else s3 the else s3 should be with the first if or the second if - usually you have to code special rules into your parser. It also allows for a worst-case linear time parse, and there are some language rules you can express with a PEG parser that you can't with a recursive descent parser.
- andrewflnr 15y ago
  Wouldn't you just have an end symbol for if statements, "end" or "}" or something? That's what I did in my little recursive parser. Maybe what I should ask is, how does a PEG parser resolve it?
  - chipsy 15y ago
    In a PEG you operate under the expectation that all rules will be tried exhaustively, so if one fails you just move on to the next, and if they all fail you drop back a level of recursion. Thus you can have rules like: "if <if-expr>" where if-expr can contain "<statements> else" or "<statements> if" or "then <statements>", where statements is a set of predefined keywords, another set of PEG rules, or a regular expression matcher. And then you can just expect that they'll all be tried at some point. The main issue with this, of course, is the one you raised, with endings and creating rules for delimiting new blocks. Although it's possible to define a good set of rules, it's still hard to distinguish between a continuation of a statement and the start of a new one, and in most cases you won't get a useful syntax error message using a naive PEG system like the one in PEG.js, because it'll just drop all the way to the top level and then fail at the first character without telling you how far/deep it got before the syntax broke. So in practice having end symbols is still useful to make the grammar operate sanely. PEG can also be used to execute a relatively flat pass that mostly produces tokens and simple expressions, while other methods are applied to the resulting tree to get the complete structure. This is an approach which I find a little less mind-bending than trying to cram everything into PEG rules, since you can use varying methods of parsing as the situation dictates.
tptacek 15y ago
PEG is a different way of specifying grammars and an different process for parsing them. If you're used to Bison/Yacc or LALR parsers modeled on Yacc (like Racc), the big things you notice with any PEG parser are: * You automatically get "EBNF"-style operators like "zero-or-more" or "one-or-more" instead of having to specify recursive nonterminals and epsilons. * You typically don't need a separate lexer; PEG parser productions resemble regular expressions. * PEGs use prioritized choice to deal with ambiguities such as dangling-else. PEG grammars are unambiguous. PEG parsers are much easier to build and work with than Yacc-style parsers. The learning curve on PEG is also way, way shorter than for shift-reduce parsers. You should probably be using PEG parsers whenever possible now.
- haberman 15y ago
  For a counterpoint: * you can get "EBNF"-style operators using traditional LL parsers like ANTLR. * Likewise, top-down parsers can have integrated lexing also. * The downside of prioritized choice is that you don't get any insight into what inherent ambiguities your grammar has. The dangling-else ambiguity in C (for example) is a real ambiguity that you have to tell your users about. Prioritized choice hides ambiguities and gives you no hint when you develop your grammars where the ambiguities are. * PEG-based parsers are less efficient than LL parsers. LL parsers are O(n) in time and O(d) in space (where n is the length of the input and d is the depth of the nesting). To parse a PEG in O(n) time the space complexity becomes O(n) (this is a packrat parser). To parse with O(d) space, time complexity becomes O(n^d) (as with lpeg). And the constant factor for LL parsing is much lower than with packrat parsing. I think the future is LL. When the tooling gets good enough with LL, I think that the primary motivation for PEGs (that they are easy to use) will evaporate.
  - tptacek 15y ago
    I knew someone would call me on this and chose my words carefully --- "LALR parsers modeled on Yacc" --- but am glad for the response. ANTLR is a pain in the ass to integrate; you can get a totally respectable PEG parser in 2k lines of C. What would you use for LL parsing?

Can someone summarize what PEG is? I read through the Wikipedia page but can't make heads or tails of it. What is this used for?

by geuis 15y ago

Can someone summarize what PEG is? I read through the Wikipedia page but can't make heads or tails of it. What is this used for?

kevinburke 15y ago

PEG parsers get rid of the dangling else problem with recursive descent parsers where it's unclear in the following statement whether if e then s1 else if e then s2 else s3 the else s3 should be with the first if or the second if - usually you have to code special rules into your parser. It also allows for a worst-case linear time parse, and there are some language rules you can express with a PEG parser that you can't with a recursive descent parser.

andrewflnr 15y ago
Wouldn't you just have an end symbol for if statements, "end" or "}" or something? That's what I did in my little recursive parser. Maybe what I should ask is, how does a PEG parser resolve it?
- chipsy 15y ago
  In a PEG you operate under the expectation that all rules will be tried exhaustively, so if one fails you just move on to the next, and if they all fail you drop back a level of recursion. Thus you can have rules like: "if <if-expr>" where if-expr can contain "<statements> else" or "<statements> if" or "then <statements>", where statements is a set of predefined keywords, another set of PEG rules, or a regular expression matcher. And then you can just expect that they'll all be tried at some point. The main issue with this, of course, is the one you raised, with endings and creating rules for delimiting new blocks. Although it's possible to define a good set of rules, it's still hard to distinguish between a continuation of a statement and the start of a new one, and in most cases you won't get a useful syntax error message using a naive PEG system like the one in PEG.js, because it'll just drop all the way to the top level and then fail at the first character without telling you how far/deep it got before the syntax broke. So in practice having end symbols is still useful to make the grammar operate sanely. PEG can also be used to execute a relatively flat pass that mostly produces tokens and simple expressions, while other methods are applied to the resulting tree to get the complete structure. This is an approach which I find a little less mind-bending than trying to cram everything into PEG rules, since you can use varying methods of parsing as the situation dictates.

tptacek 15y ago

PEG is a different way of specifying grammars and an different process for parsing them. If you're used to Bison/Yacc or LALR parsers modeled on Yacc (like Racc), the big things you notice with any PEG parser are: * You automatically get "EBNF"-style operators like "zero-or-more" or "one-or-more" instead of having to specify recursive nonterminals and epsilons. * You typically don't need a separate lexer; PEG parser productions resemble regular expressions. * PEGs use prioritized choice to deal with ambiguities such as dangling-else. PEG grammars are unambiguous. PEG parsers are much easier to build and work with than Yacc-style parsers. The learning curve on PEG is also way, way shorter than for shift-reduce parsers. You should probably be using PEG parsers whenever possible now.

haberman 15y ago
For a counterpoint: * you can get "EBNF"-style operators using traditional LL parsers like ANTLR. * Likewise, top-down parsers can have integrated lexing also. * The downside of prioritized choice is that you don't get any insight into what inherent ambiguities your grammar has. The dangling-else ambiguity in C (for example) is a real ambiguity that you have to tell your users about. Prioritized choice hides ambiguities and gives you no hint when you develop your grammars where the ambiguities are. * PEG-based parsers are less efficient than LL parsers. LL parsers are O(n) in time and O(d) in space (where n is the length of the input and d is the depth of the nesting). To parse a PEG in O(n) time the space complexity becomes O(n) (this is a packrat parser). To parse with O(d) space, time complexity becomes O(n^d) (as with lpeg). And the constant factor for LL parsing is much lower than with packrat parsing. I think the future is LL. When the tooling gets good enough with LL, I think that the primary motivation for PEGs (that they are easy to use) will evaporate.
- tptacek 15y ago
  I knew someone would call me on this and chose my words carefully --- "LALR parsers modeled on Yacc" --- but am glad for the response. ANTLR is a pain in the ass to integrate; you can get a totally respectable PEG parser in 2k lines of C. What would you use for LL parsing?