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

Question

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

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

非常感谢您！

Answer 1

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

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

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

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

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

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

左递归不是 NDCFG 的功能。它对 LL() 解析器的设计提出了特殊的挑战，但对 LR() 解析器来说没有问题。