3 ms·

I'm not sure how this can be a critism - you inherently need to decide between left and right recursion - and you can, and it is explicit in the ohm grammar: >

by e12e 9y ago

I'm not sure how this can be a critism - you inherently need to decide between left and right recursion - and you can, and it is explicit in the ohm grammar: > 4.1. Left Recursion > Another interesting thing to note about the new definition of "Exp" above is that it is recursive — i.e., its body contains an application of "Exp" itself. More specifically, it is left recursive, meaning that the recursive application is the first expression in the branch. > Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is the most straightforward way to express left associative operators, which is why left recursion is supported by Ohm. Ed: -- Or are you making some other, more subtle point? If so, maybe you can give an example? Ed2: @yxhuvud's reply links to an article with some examples like: L1 = ("a"|"aa")"a" L2 = ("aa"|"a")"a"

yxhuvud 9y ago
> you inherently need to decide between left and right recursion I assume that you mean that you have to do that to get a parser that can parse in linear time? Because it is certainly not true in the general case. But even if you mean that, it is wrong, as there are optimizations to the Earley parser that allows it to be linear on both grammars that contain both left- and right-recursive rules at the same time. (It can still be quadratic or worse on internal recursion, and on many ambiguous grammars).
- e12e 9y ago
  I meant that if you want your language to be unambiguous in what tree it produces, you have to choose (somehow not be ambiguous). You can be explicit in your grammar and semantics of your grammar, or you could throw away some set of "wrong" trees - or you can be implicit - allow your grammar (under certain semantic assumptions be ambiguous) - and assume left /right. But if the grammar and semantics allow (force) you to be explicit - I'm not sure I see it as a problem. I certainly see how allowing ambiguity with a warning/error would also be good. I'm on a cellphone now, and can't see if I can make useful/surprising grammar for the a/aa|a/aaa languages in ohm. Maybe it's just too minimal an example for me (why not: a|aaa or aa+ - or whatever one is trying to express? Is it, say about the language of pairs or triplets of "a"s?).
  - yxhuvud 9y ago
    Well, most parsers have made a global choice of left and right. If the choice is on rule or symbol level, then that would allow a lot more flexibility - probably to the point that it would be powerful enough to parse most things without tedious rewriting of the grammar.
tomp 9y ago
A good example of the kind of ambiguitiy I mean is the "dangling else" problem. Sure, for this example, the solution is easy - just declare whichever you want first! But in more complex grammars, conflicting rules can be declared very far away, and it can be highly non-obvious which should be prioritised, or that there even is a conflict! LR parser generators point out these conflicts (the infamous shift/reduce and reduce/reduce conflicts), which I find very useful.

by e12e 9y ago

yxhuvud 9y ago

> you inherently need to decide between left and right recursion I assume that you mean that you have to do that to get a parser that can parse in linear time? Because it is certainly not true in the general case. But even if you mean that, it is wrong, as there are optimizations to the Earley parser that allows it to be linear on both grammars that contain both left- and right-recursive rules at the same time. (It can still be quadratic or worse on internal recursion, and on many ambiguous grammars).

e12e 9y ago
I meant that if you want your language to be unambiguous in what tree it produces, you have to choose (somehow not be ambiguous). You can be explicit in your grammar and semantics of your grammar, or you could throw away some set of "wrong" trees - or you can be implicit - allow your grammar (under certain semantic assumptions be ambiguous) - and assume left /right. But if the grammar and semantics allow (force) you to be explicit - I'm not sure I see it as a problem. I certainly see how allowing ambiguity with a warning/error would also be good. I'm on a cellphone now, and can't see if I can make useful/surprising grammar for the a/aa|a/aaa languages in ohm. Maybe it's just too minimal an example for me (why not: a|aaa or aa+ - or whatever one is trying to express? Is it, say about the language of pairs or triplets of "a"s?).
- yxhuvud 9y ago
  Well, most parsers have made a global choice of left and right. If the choice is on rule or symbol level, then that would allow a lot more flexibility - probably to the point that it would be powerful enough to parse most things without tedious rewriting of the grammar.

tomp 9y ago

A good example of the kind of ambiguitiy I mean is the "dangling else" problem. Sure, for this example, the solution is easy - just declare whichever you want first! But in more complex grammars, conflicting rules can be declared very far away, and it can be highly non-obvious which should be prioritised, or that there even is a conflict! LR parser generators point out these conflicts (the infamous shift/reduce and reduce/reduce conflicts), which I find very useful.