9 ms·

I'm aware of ordered choice in PEGs. I'm not entirely convinced that's a real problem in practice (or am missing some compelling example). E.g. regular expressi

I'm aware of ordered choice in PEGs. I'm not entirely convinced that's a real problem in practice (or am missing some compelling example). E.g. regular expressions can be ambiguous too, but are still used very extensively and people tend to not complain about them. Is longest match - a common resolution to multiple matches in regexps - also problematic? I'm also wondering if this specific complaint wrt ambiguity can be easily addressed by just implementing an analyzer that identifies ambiguities in a PEG grammar by evaluating `|` as alternative choice.

yxhuvud 9y ago
Regarding your regexp question, it depends on what implementation of regexp you use. If you go by the formal definition and the state machine parsers optimized for that, then multiple matches is not problematic for finding the longest match. It can be if using some common extensions though, that change the running time to exponential. See https://blog.codinghorror.com/regex-performance/ https://blog.codinghorror.com/regex-performance/ for example.
- shalabhc 9y ago
  I'm not talking about performance though. I'm talking about the fact that when given an ambiguous regexp, most engines match it happily and return the longest match, instead of erroring out saying 'ambiguous input provided'. This is not considered problematic in practice (or I don't hear criticisms about this at least). Contrast with the the criticism of PEGs - that they don't report 'ambiguous input' but just go ahead and match using ordered choice.
  - yxhuvud 9y ago
    Ah, that is what you mean. Then the answer is that they are used for different things. PEGs are typically used to parse a string, while regexps are typically used to recognize a pattern. Where regexps are used for parsing, then ambiguity is definitely a problem that very often will have to be resolved by rewriting the regexp to be less accepting.
  - tomp 9y ago
    In practice, most Regexes fit on a line, and while not trivial to read, they don't involve a deep tree-like structure. Grammars, on the other hand, do, and ambiguity can be very sublte.

yxhuvud 9y ago

Regarding your regexp question, it depends on what implementation of regexp you use. If you go by the formal definition and the state machine parsers optimized for that, then multiple matches is not problematic for finding the longest match. It can be if using some common extensions though, that change the running time to exponential. See https://blog.codinghorror.com/regex-performance/ https://blog.codinghorror.com/regex-performance/ for example.

shalabhc 9y ago
I'm not talking about performance though. I'm talking about the fact that when given an ambiguous regexp, most engines match it happily and return the longest match, instead of erroring out saying 'ambiguous input provided'. This is not considered problematic in practice (or I don't hear criticisms about this at least). Contrast with the the criticism of PEGs - that they don't report 'ambiguous input' but just go ahead and match using ordered choice.
- yxhuvud 9y ago
  Ah, that is what you mean. Then the answer is that they are used for different things. PEGs are typically used to parse a string, while regexps are typically used to recognize a pattern. Where regexps are used for parsing, then ambiguity is definitely a problem that very often will have to be resolved by rewriting the regexp to be less accepting.
- tomp 9y ago
  In practice, most Regexes fit on a line, and while not trivial to read, they don't involve a deep tree-like structure. Grammars, on the other hand, do, and ambiguity can be very sublte.