parsing - 线性时间通用解析器

Question

我已经阅读 Dick Grune 的解析技术第一版已经有一段时间了，这本书是 90 年代中期的，作者认为直到今天还没有发现这样的解析方法(线性时间通用解析)。

"we should like to have a linear-time general parsing method. Unfortunately no such method has been discovered to date." pg 76

有没有人开发过这样的方法？

Answer 1

没有设计出这样的方法。据我所知，CYK algorithm仍然是具有最佳最坏情况性能(O(n3))的通用解析算法。