我正在阅读我的比较语言课的笔记，我有点困惑...
上下文无关文法与确定性上下文无关文法有什么区别？我正在专门阅读有关CFG的解析器是O(n ^ 3)以及DCFG的编译器是O(n)的说法，但我真的不了解时间复杂度的差异有多么大(更不用说我对于将CFG转换为DCFG的特性仍感到困惑)。
提前非常感谢您!
最佳答案
从概念上讲，它们很容易理解。上下文无关的语法是可以用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()解析器没有问题。
关于parsing - 确定性上下文无关语法与上下文无关语法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22522173/