grammar - 确定是否可以在 CFG 中模糊地派生字符串

Question

我知道给定一个特定的上下文无关语法，要检查它是否有歧义，需要检查是否存在任何可以以不止一种方式派生的字符串。这是不可判定的。

但是，我有一个更简单的问题。给定一个特定的上下文无关文法和一个特定的字符串，是否可以确定字符串是否可以从文法中模糊地导出？是否有通用算法来执行此检查？

Answer 1

是的，您可以使用任何通用的解析算法，例如 GLR (Tomita) parser , 一个 Earley parser ，甚至 a CYK parser ;所有这些都可以在 O(N³) 时间和空间内生成解析“森林”(即所有可能解析器的有向图)。创建解析森林比“解析”(即识别)要复杂一些，但维基百科文章中引用了已知的算法。

由于广义解析算法找到所有可能的解析，您可以放心，如果恰好为字符串找到一个解析，则该字符串没有歧义。

我会远离此算法的 CYK 解析，因为它需要将语法转换为 Chomsky 范式，这使得恢复原始解析树更加复杂。

Bison 会生成一个 GLR parser ，如果需要，您就可以使用该工具。但是，请注意，它不会优化解析森林的存储，因为它预计只会生成一个解析，因此您最终可能会得到指数级大小的数据结构(然后需要指数级的时间来构建)。不过，这通常只是病态语法的问题。此外，您还必须申报 custom %merge function在所有可能有歧义的产品上；否则，如果可以进行不止一次解析，Bison 生成的解析器将失败并出现“歧义解析”错误。