用于分析编程语言的CKY

Question

使用CKY图表解析算法来解析编程语言的语法(知道它主要用于解析自然语言的语法)是个好主意吗？

Answer 1

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

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