parsing - 确定性上下文无关语法与上下文无关语法？

Question

我正在阅读我的比较语言课的笔记，我有点困惑......

上下文无关语法和确定性上下文无关语法有什么区别？我正在专门阅读有关 CFG 的解析器是 O(n^3) 和 DCFG 的编译器是 O(n) 的具体情况，并且并不真正理解时间复杂度的差异如何如此之大（更不用说我仍然对使 CFG 成为 DCFG 的特征感到困惑）。

非常感谢您！

Answer 1

从概念上讲，它们很容易理解。上下文无关文法是可以用 BNF 表达的文法。DCFG 是可以编写可用解析器的子集。

在编写编译器时，我们只对 DCFG 感兴趣。原因是“确定性”大致意味着要在解析中的任何点应用的下一个规则由到目前为止的输入和有限数量的前瞻确定。Knuth 在 1960 年代发明了 LR() 编译器，并证明它可以处理任何 DCFG。从那时起，一些改进，特别是 LALR(1) 和 LL(1)，已经定义了可以在有限内存中解析的语法，以及我们可以用来编写它们的技术。

如果我们知道 BNF 是其中一种语法，我们也有自动从 BNF 派生解析器的技术。Yacc、Bison 和 ANTLR 都是熟悉的例子。

我从未见过 NDCFG 的解析器，但在解析中的任何时候，它都可能需要考虑整个输入字符串以及可以应用的每个可能的解析。不难看出为什么它会变得相当大和缓慢。

---

我应该指出，许多真正的语言是不完美的，因为它们不是完全上下文无关的，不是明确的或偏离理想的 DCFG。C/C++ 是一个很好的例子，但还有很多其他例子。这些语言通常由特殊用途的规则处理，例如语义或句法谓词、特殊情况回溯或其他对性能没有影响的“技巧”。

---

评论指出，某些类型的 NDCFG 很常见，许多工具提供了处理它们的方法。一个常见的问题是模棱两可。通过引入简单的局部语义规则来解析歧义语法相对容易，但当然这只能生成可能的解析树之一。NDCFG 的通用解析器可能会生成所有解析树，并且可能允许在任意条件下过滤这些树。我一个都不知道。

左递归不是 NDCFG 的一个特性。它对 LL() 解析器的设计提出了特别的挑战，但对 LR() 解析器没有问题。