4 ms·

That's not an issue for associative operators, so long as you keep track of precedence. x * (x * x) == (x * x) * x. But it may become an issue for more general

That's not an issue for associative operators, so long as you keep track of precedence. x * (x * x) == (x * x) * x. But it may become an issue for more general grammars that need to handle left-recursion in a non-associative fashion. The issue is that a top-down grammar cannot handle left-recursion, since it naturally leads to infinite recursion when being parsed from the top down. I actually had to handle the left-recursion problem for a PEG I wrote in-house--right now I'm trying to convince my boss to let me open-source it :)

barrkel 17y ago
The way I would normally handle what would otherwise be left recursion in a top-down parser is to introduce loops. term ::= factor ( ('*' | '/') factor )* ; If you introduce regex-like closure operators to model loops, life gets much easier, and you can build your trees the right way around. How applicable this is to PEGs is another matter though. I generally write my parsers by hand, and I parse expressions with operator precedence.
- cynicalkane 17y ago
  This can be done in PEGs, using term rewriting or simple tree rewriting to create a PEG construct like the loop you described. But doing so subverts the elegance of PEG parser, and I'm unaware of a way to make it suffice as a general solution.
  - barrkel 17y ago
    The thing is, LL(1) is almost always all you need in practice. Left recursion doesn't buy you a lot more in practice than the loops I describe. But I also don't think PEGs are particularly elegant - I think the translation of LL(1) (including loops) to recursive descent is perfectly straightforward, and I think backtracking combined with memoization is a hack. And for stuff that LL(1) can't handle, I think GLR is a better approach.
    - cynicalkane 17y ago
      You misunderstand PEGs. In the simplest version, each rule can be seen as a function that calls other rules, passing along a memo table as it goes. It's entirely stateless and functional, except for the memo table. In addition, each function is only a few lines. Backtracking isn't a hack--it's the natural result of statelessness. There's no cursor that needs to be backtracked.
      - barrkel 17y ago
        I think you don't understand my objection. It's that backtracking is very seldom necessary at all in the first place, whether or not you get rid of the time cost of it. It's like doing something inefficient in the name of source code elegance, then patting yourself on the back when you got rid of the big-O inefficiency. My point is that you needn't have been so inefficient to begin with, and that the more efficient approaches don't suffer unduly from inelegance, and to top it all off, they have a lower constant factor.
        deleted 17y ago
        [deleted]
        cynicalkane 17y ago
        The advantage of PEGs is that they are easily understood, easy to code, and easy to code for. In 99% of applications nowdays, these are the only considerations. Performance is a secondary concern or not a concern at all. Given this, the user shouldn't have to worry about backtracking, ambiguity, or lookahead. Asking the user to have to worry about this stuff, when he doesn't have to, is not good software design. Not all of us are writing high performance parsers for complicated languages.

barrkel 17y ago

The way I would normally handle what would otherwise be left recursion in a top-down parser is to introduce loops. term ::= factor ( ('*' | '/') factor )* ; If you introduce regex-like closure operators to model loops, life gets much easier, and you can build your trees the right way around. How applicable this is to PEGs is another matter though. I generally write my parsers by hand, and I parse expressions with operator precedence.

cynicalkane 17y ago
This can be done in PEGs, using term rewriting or simple tree rewriting to create a PEG construct like the loop you described. But doing so subverts the elegance of PEG parser, and I'm unaware of a way to make it suffice as a general solution.
- barrkel 17y ago
  The thing is, LL(1) is almost always all you need in practice. Left recursion doesn't buy you a lot more in practice than the loops I describe. But I also don't think PEGs are particularly elegant - I think the translation of LL(1) (including loops) to recursive descent is perfectly straightforward, and I think backtracking combined with memoization is a hack. And for stuff that LL(1) can't handle, I think GLR is a better approach.
  - cynicalkane 17y ago
    You misunderstand PEGs. In the simplest version, each rule can be seen as a function that calls other rules, passing along a memo table as it goes. It's entirely stateless and functional, except for the memo table. In addition, each function is only a few lines. Backtracking isn't a hack--it's the natural result of statelessness. There's no cursor that needs to be backtracked.
    - barrkel 17y ago
      I think you don't understand my objection. It's that backtracking is very seldom necessary at all in the first place, whether or not you get rid of the time cost of it. It's like doing something inefficient in the name of source code elegance, then patting yourself on the back when you got rid of the big-O inefficiency. My point is that you needn't have been so inefficient to begin with, and that the more efficient approaches don't suffer unduly from inelegance, and to top it all off, they have a lower constant factor.
      - deleted 17y ago
        [deleted]
      - cynicalkane 17y ago
        The advantage of PEGs is that they are easily understood, easy to code, and easy to code for. In 99% of applications nowdays, these are the only considerations. Performance is a secondary concern or not a concern at all. Given this, the user shouldn't have to worry about backtracking, ambiguity, or lookahead. Asking the user to have to worry about this stuff, when he doesn't have to, is not good software design. Not all of us are writing high performance parsers for complicated languages.