algorithm - 编译器的Big-O

Closed. This question needs to be more focused。它当前不接受答案。












想要改善这个问题吗？更新问题，使它仅关注editing this post的一个问题。

7年前关闭。



Improve this question




是否有人了解编译器的典型big-O复杂性？

我知道它必须是>= n(其中n是程序中的行数)，因为它需要至少扫描每行一次。

我认为对于程序语言也必须是>= n.logn，因为该程序可以引入O(n)变量，函数，过程和类型等，并且在程序中引用这些变量时，将需要O(log n)来查找每个引用。

除了我对编译器体系结构的非正式理解已经达到极限之外，我不确定前向声明，递归，功能语言和/或其他技巧是否会增加编译器的算法复杂性。

因此，总而言之:

对于“典型”过程语言(C，pascal，C#等)，对于有效设计的编译器(作为行数的度量)，存在局限性big-O。

对于“典型”功能语言(lisp，Haskell等)，对于有效设计的编译器(作为行数的度量)，存在局限性big-O。

最佳答案

该问题目前无法回答。编译器的复杂性当然不会用源文件中的代码行或字符来衡量。这将描述解析器或词法分析器的复杂性，但是编译器的其他部分甚至都不会触摸该文件。

解析后，所有内容都将以各种AST的形式，以更结构化的方式表示源文件。编译器将具有许多中间语言和许多，每种语言都有其自己的AST。各个阶段的复杂性取决于AST的大小，它与字符数甚至与先前的AST根本不相关。

考虑到这一点，我们可以将大多数语言在线性时间内解析为字符数并生成一些AST。简单的操作(例如类型检查)通常是带有O(n)叶子的树的n。但是随后，我们将把这个AST转换为一个形式，该形式具有的节点数可能比原始树上的节点数大，两倍，三倍甚至指数级。现在，我们再次在树上运行单遍优化，但这可能是相对于原始AST的O(2^n)，主知道字符数是多少!

我认为您几乎找不到对于编译器来说有些复杂的n应该是什么f(n)的可能性。

作为棺材上的钉子，编译某些语言是不确定的，包括Java，C#和Scala(事实证明，名义子类型+变量导致不确定的类型检查)。当然，C++的模板系统是完整的，这使得可判定的编译等效于停止问题(不可判定)。 Haskell +一些扩展无法确定。还有很多其他我想不到的东西。这些语言的编译器没有最坏情况的复杂性。

关于algorithm - 编译器的Big-O，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21564859/