parsing - 解析需要大量前瞻的案例

Question

大多数解析可以通过仅查看下一个符号（用于词法分析的字符，用于正确解析的标记）来完成，而其余大多数情况可以通过仅查看一个符号来处理。

是否有任何实际案例 - 对于实际使用的编程语言或数据格式 - 需要几个或无限多个前瞻（或等效回溯）符号？

Answer 1

我记得，Fortran 是一种需要大前瞻缓冲区的语言。解析 Fortran 需要（理论上）无界前瞻，尽管大多数实现限制了语句行的长度，这限制了前瞻缓冲区的大小。

另外，请参阅为什么不能使用 LR(1) 解析器解析 C++？. 特别是引用：

“C++ 语法是模棱两可的，依赖于上下文的，并且可能需要无限前瞻来解决一些歧义”。

Answer 2

Knuth 证明了任何 LR(k) 文法都可以机械地转换为 LR(1) 文法。此外，AFAIK，任何 LR(k) 语法都可以按与解析字符串的长度成比例的时间进行解析。因为它包括 LR(1)，所以我看不出用 k > 1 来实现 LR(k) 解析有什么用处。

我从未研究过 LR(k)->LR(1) 转换，因此在某些情况下它可能并不实用。