java - 在 Java 中验证给定上下文无关语法的字符串

Question

有人如何验证字符串是否是上下文无关语法的一部分？不仅仅是虚拟的，而是为它构建一个算法？

给定一个带有规则的上下文无关文法，例如

• V-> v1v2
• v1->1 | 1v1
• v2-> 2 | 2v2

很明显，这是语言 1^n 2^n。但是，您将如何使用算法来验证它是否确实如此。我正在尝试在 java 中完成此操作。

Answer 1

您可能想研究Earley 算法或CYK 算法，这两种算法用于确定字符串是否由上下文无关文法生成。Earley 算法对于任何长度为 n 的字符串在时间 O(n ³ ) 上运行，而不管文法中的产生式规则（尽管大 O 表示法中的常数项取决于文法），而 CYK 算法要求文法首先转换为乔姆斯基范式以保证 O(n ³ ) 运行时间。

希望这可以帮助！