parsing - 用于解析编程语言的 CKY

Question

使用 CKY 图表解析算法来解析编程语言的语法是不是一个好主意（要知道它多用于解析自然语言的语法）？

Answer 1

CKY 可以解析任何上下文无关的语言，但与其他语言相比，时间复杂度并不高。CKY 要求语法为乔姆斯基范式，这会增加语法的大小并影响运行时间。对于快速而肮脏的解析器来说，这是一种不错的方法，但是当您尝试扩展到更大的输入或复杂的语法时，您会遇到问题。

如果您正在寻找一种易于理解且实现起来相对简单的解析算法，请查看 Parsing Expression Grammars (PEG)。他们可以识别大量的上下文无关语言，以及一些上下文敏感性有限的语言。一旦你有了一个工作的 PEG 解析器，就很容易添加 memoization，它为你提供了一个在线性时间内运行的 Packrat 解析器。关于PEGs、Packrat的学术论文，以及这个允许左递归语法的扩展都是可以理解的。