Re:Ohm: Parsing Made Easy
by panic on Tuesday October 17, 2017 @01:58PM
(#15493095)
Theorem 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?
Re:Ohm: Parsing Made Easy
by zzzcpan on Tuesday October 17, 2017 @02:25PM
(#15493394)
Any 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.
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?