compiler-construction - 明确的上下文无关语法

Question

我正在阅读上下文无关语法，我遇到了模棱两可的语法。如果 CFG 生成的语言具有多于 1 个解析树，则 CFG 是一种二义性语法。有什么方法可以找出或证明语法是明确的。一般来说，我可以测试一些由 CFG 生成的语言，并检查是否从该语言生成了超过 1 个解析树，以表明语法是模棱两可的。但是我如何检查或证明给 CFG 是明确的？

Answer 1

CFG 的模糊性问题在一般情况下是不可判定的。但是，有一些方法可以检查语言是否可能有歧义。如果您想了解它的理论，请查看这篇文章；对于更实用的东西，请考虑this或this。