CKY用於解析編程語言

Question

使用CKY圖表解析算法來解析編程語言的語法（知道它主要用於解析自然語言的語法）是否是一個好主意？

Answer 1

CKY可以解析任何上下文無關的語言，但與替代方案相比，時間複雜性並不高。 CKY要求語法採用喬姆斯基標準格式，這可能會炸燬語法的大小並且也會影響運行時間。對於一個快速而且髒的解析器來說，這是一個好方法，但當您嘗試擴展到更大的輸入或複雜的語法時，會遇到問題。

如果您正在尋找一種相對易於實現的可理解的解析算法，請查看解析表達式語法（PEG）。他們可以識別上下文無關語言的大部分子集，以及一些上下文敏感度有限的語言。一旦你有一個工作PEG分析器，很容易添加memoization，它給你一個線性時間運行的Packrat解析器。關於PEGs，Packrat和this extension的學術論文允許左遞歸語法都是可以理解的。