4 ms·
Unfortunately, ambiguity for CFGs is undecideable. If you don't want to accept grammars that may be ambiguous, you lose generality. If you want generality, yo
by loup-vaillant 12y ago
Unfortunately, ambiguity for CFGs is undecideable. If you don't want to accept grammars that may be ambiguous, you lose generality. If you want generality, you have to let some ambiguous grammar slip. And I'm not even talking about inherently ambiguous languages.
In the end, you have to wait for the input to see whether you triggered an ambiguity or not. And what if you did? Stopping the whole thing and giving an error message may not be acceptable in some cases. Sometimes, you do have to chose a parse tree no matter what.
Which is why prioritised choice is so appealing to me. It gives control to the user, should any ambiguity arise. It also allows the user to write deliberately ambiguous grammars, simply because they're simpler. Finally, I suspect some actual languages, like Markdown, are either impossible or very inconvenient to formalize without prioritised choice.
- haberman 12y ago> If you don't want to accept grammars that may be ambiguous, you lose generality. [...] Yes, this was the entire point of my message. > Which is why prioritised choice is so appealing to me. It gives control to the user, should any ambiguity arise. I agree that prioritized choice is a nice tool for resolving ambiguities. But I don't like PEGs, because everything has to be defined in terms of prioritized choice. That means you don't know if there are ambiguities are not.