3 ms·

PEGs don't have grammar ambiguities. Every PEG is deterministic. Grammar ambiguities are resolved by ordered choice. If there are two ways to parse something,

PEGs don't have grammar ambiguities. Every PEG is deterministic. Grammar ambiguities are resolved by ordered choice. If there are two ways to parse something, the first way will be tried first. If it succeeds, the ordered choice short-circuits and the second way is ignored. So you can resolve, say, the classic dangling else problem by ordering your choices correctly.

silentbicycle 17y ago
Right, and PEGs only have one level of backtracking, so you don't have potentially massive slowdown due to backtracking several levels and re-trying everything along the way. While the backtracking behavior is different, choice order affects PEG rules similarly to Prolog.
barrkel 17y ago
I know all of that. My point is that the if/else problem really is an ambiguity (i.e. it is a language bug, not just a problem you have to get around in parsing), and problems similar to it crop up when your tool doesn't alert you to first/follow conflicts, in LL(1) parlance. That PEGs encode the implementation strategy inside the declarative grammar is a flaw, in my opinion, not a benefit.
- cynicalkane 17y ago
  In programming, ambiguity is bad! Explicitly encoding disambiguation rules in the grammar is a good thing, just like it's a good thing in functional pattern matching, in Prolog... I'd be interested to hear any reason why you would want to not disambiguate a grammar in any language designed to be computer-recognizable.
  - barrkel 17y ago
    Here, read this: http://compilers.iecc.com/comparch/article/05-09-114 http://compilers.iecc.com/comparch/article/05-09-114 In particular: "Yes, this is "the" problem with PEG's. / implies ordering of the search (parsing) space. You need to order your / operators so that special cases (e.g. longer matches), so that they appear first. Unfortunately, if you don't do this, nothing will tell you you have a problem with your grammar, it will simply not parse some inputs. To me this implies that if one wants to use a PEG to parse some input, then one must exhaustively test the parser." Hopefully the thread therein will describe my issue better than I have thus far.
    - scott_s 17y ago
      Indeed it does, and Chris Clark very nicely summarizes the advantages and disadvantages of PEG vs other parsers. Nice find.

silentbicycle 17y ago

Right, and PEGs only have one level of backtracking, so you don't have potentially massive slowdown due to backtracking several levels and re-trying everything along the way. While the backtracking behavior is different, choice order affects PEG rules similarly to Prolog.

barrkel 17y ago

I know all of that. My point is that the if/else problem really is an ambiguity (i.e. it is a language bug, not just a problem you have to get around in parsing), and problems similar to it crop up when your tool doesn't alert you to first/follow conflicts, in LL(1) parlance. That PEGs encode the implementation strategy inside the declarative grammar is a flaw, in my opinion, not a benefit.

cynicalkane 17y ago
In programming, ambiguity is bad! Explicitly encoding disambiguation rules in the grammar is a good thing, just like it's a good thing in functional pattern matching, in Prolog... I'd be interested to hear any reason why you would want to not disambiguate a grammar in any language designed to be computer-recognizable.
- barrkel 17y ago
  Here, read this: http://compilers.iecc.com/comparch/article/05-09-114 http://compilers.iecc.com/comparch/article/05-09-114 In particular: "Yes, this is "the" problem with PEG's. / implies ordering of the search (parsing) space. You need to order your / operators so that special cases (e.g. longer matches), so that they appear first. Unfortunately, if you don't do this, nothing will tell you you have a problem with your grammar, it will simply not parse some inputs. To me this implies that if one wants to use a PEG to parse some input, then one must exhaustively test the parser." Hopefully the thread therein will describe my issue better than I have thus far.
  - scott_s 17y ago
    Indeed it does, and Chris Clark very nicely summarizes the advantages and disadvantages of PEG vs other parsers. Nice find.