4 ms·
It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a
by zzzcpan 9y ago
It's not hard to point out ambiguities, it's hard to fix them. That's why PEGs are nice, they don't make humans work as much, since fixing ambiguities is just a matter of precedence.
But I don't think the world of context-free grammars even matters that much.
- panic 9y agoPointing out ambiguities in a context-free grammar is an undecidable problem (http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf).
- zzzcpan 9y agoNo, that's not what your link proves and not what we are talking about.
- panic 9y agoTheorem 6.8.2 in the PDF: It is undecidable whether a context-free grammar is ambiguous. PEGs are unambiguous by construction, so I assumed we were talking about grammars which would be ambiguous as CFGs (replacing every ordered choice with a nondeterministic choice). What kind of ambiguity were you thinking about?
- zzzcpan 9y agoAny ambiguity that manifests itself as unreachable alternatives in PEGs can be detected for example. Doesn't matter if it's undecidable whether the whole grammar is ambiguous.