4 ms·
> 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?
by 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 agoI 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 agoWell, 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.