parsing - 需要无限前瞻的语法？

Question

我一直在阅读不同类型的解析器，并且在几篇论文中，人们提到了需要无限前瞻的语法，但从未给出示例。是否有一些我应该注意的典型例子？

Answer 1

很容易提出需要无限前瞻的明确语法。考虑以下简单的一个：

• S → SX
• S → SY
• SX → XB x
• SY → YB y
• X → 一个
• Y → 一个
• 乙→乙
• B→BB

在这里，我们无法决定是否将首字母减少a到X或Y直到我们一直阅读到输入的末尾。但这并不太有趣，因为语言本身显然可以使用 LR(1) 语法进行解析。

还有一些语言不存在 LR(k) 语法。我认为规范的例子是所有偶数长度回文序列的语言（字母大小至少为两个），它具有明确的语法：

• P2 → a P2 a
• P2 → b P2 b
• P2 → ε

至少应该直观地清楚，为什么这需要无限前瞻：在输入正好经过一半之前，我们无法知道何时进行任何归约，但在看到所有输入之前，我们无法知道输入的长度.