2 ms·

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 eleganc

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 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.