编译器的时间复杂度：Big-O

Question

编译器的时间复杂度：Big-O

algorithmcompiler-construction

6

有人了解编译器的典型大O复杂度吗？

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

我认为对于过程语言，它必须是>= n.logn，因为程序可以引入O(n)个变量、函数、过程和类型等，在程序中引用这些需要花费O(log n)的时间查找。

除此之外，我对编译器架构的非正式理解已经达到了极限，不确定前向声明、递归、函数式语言或其他技巧是否会增加编译器的算法复杂度。

因此，总结如下：

对于“典型”的过程语言（C、Pascal、C#等），作为衡量有效设计编译器的标准（以代码行数计），是否存在大O的限制？
对于“典型”的函数式语言（Lisp、Haskell等），作为衡量有效设计编译器的标准（以代码行数计），是否存在大O的限制？

- Penguino

4

代码行数并不是工作量的一个精确指标。一段代码可以被压缩成一行，但其复杂度可能与原本的几百行未压缩版本相同。 - nhahtdh

2

投票关闭原因为“过于宽泛”，因为编译器由许多部分组成，每个部分的复杂度可能不同，并且在不同的编译器中也可能不同。 - Bernhard Barker

2

@Dukeling，“太宽泛”并不意味着“涉及一些移动部件”，而是指“在问答格式中涵盖范围过大”，我认为后者不一定适用。关于编译器的好问题有成千上万个，其中答案至少需要涉及编译的主要阶段。这些问题也太宽泛了吗？ - user395760

扫描和解析都是O(N)，除非实现不当。符号表查找也是O(1)。如果有AST处理，优化，寄存器分配和代码生成可能会从O(N)开始，取决于内部复杂性。 - user207421

哦，还有一点：在C#中，方法类型推断算法通常是与要推断的类型参数数量成二次方关系，但有一种罕见的最坏情况，它是与n的四次方相关。由于实际上要推断的类型参数数量从来不会超过五到六个，所以这是无关紧要的。（我本可以编写实现始终为n平方，但那将是巨大的工作量，而且没有任何实际收益。） - Eric Lippert

显示剩余6条评论

3个回答

1

回想起我在编译器课程中所学的知识......这里可能有些细节不太准确，但总体来说应该是相当正确的。

大多数编译器实际上都有多个阶段，因此缩小问题范围会很有用。例如，代码通常会通过一个分词器运行，该分词器基本上只创建表示最小文本单元的对象。 var x = 1;将被拆分为关键字var、名称、赋值运算符和文字数字的令牌，然后是语句完成器(';')。大括号、括号等都有自己的令牌类型。

分词阶段大致为O(n)，但在关键字可以是上下文的语言中，这可能会变得复杂。例如，在C＃中，像from和yield这样的单词可能是关键字，但根据周围的内容也可以用作变量。因此，取决于语言中有多少这样的事情正在进行以及正在编译的特定代码，仅此第一阶段就可能具有O（n²）的复杂度。（虽然在实践中这种情况非常罕见。）

在分词后，接下来是解析阶段，您需要尝试匹配开放/关闭括号（或某些语言中的等效缩进），语句终止符等，并尝试理解这些标记。这是您需要确定给定名称是否表示特定方法、类型或变量的地方。明智地使用数据结构跟踪已在各种范围内声明了哪些名称可以使这个任务在大多数情况下几乎达到O(n)，但也有例外。

在我看过的一个视频中，Eric Lippert说正确的C#代码可以在用户击键之间编译。但如果您想提供有意义的错误和警告消息，则编译器必须做更多的工作。

解析后，可能会有许多额外的阶段，包括优化、转换为中间格式（如字节码）、转换为二进制代码、即时编译（以及可以在该点应用的额外优化）等。所有这些都可以相对快速地完成（大多数情况下可能是O(n)），但它是一个如此复杂的主题，以至于即使针对单个语言，回答这个问题也很困难，而且实际上不可能回答它适用于一类语言。

- StriplingWarrior

1

如果词法分析是O(n²)，那么有人没有做好他们的工作——要么是编译器编写者（通过在实现中被积极愚蠢），要么是语言设计师（通过制定高度模糊的语言）。非正则词法特征，如上下文关键字（我总是将其视为关键字并在解析期间解决使用问题）或显着的空格（缩进堆栈）可以通过一点额外的在线维护来解决，将复杂性保持在O(n)。另一方面，许多优化在实践中的复杂度比线性更差。 - user395760

1

"C#代码可以在用户按键之间的时间内编译。在C#或Java中，您可以跳过大多数优化，因为您始终可以依靠JIT编译器在运行时启动。对于“真正”的编译语言，优化所需的时间可能比解析时间长得多（我认为这些大多数在实践中具有近线性运行时间，但在某些人工输入实例上可能会崩溃）"。 - Niklas B.

1

@NiklasB。幸运的是，对于需要对按键做出反应的用例，您要么根本不需要生成代码（智能感知、捕获错误），要么不需要任何优化（调试）。此外，编译C++不仅需要时间，因为它针对机器码，语言设计也起着重要作用。 - user395760

1

@delnan：当然，Go是一个完美的例子，可以展示你可以在短时间内编写出优秀的代码。 - Niklas B.

2

我注意到Roslyn必须非常聪明地跳过所有不必要的工作，以实现在击键之间进行分析的性能目标。 Roslyn词法分析器和解析器都经过精心设计，以确保它们仅重新对上次击键实际更改的程序部分进行词法分析和语法解析，以便可以重复使用先前的分析结果。类似地，语义分析非常“懒惰”; 如果您键入foo.，则仅分析必要的程序部分以计算“foo是什么意思及其成员是什么？” - Eric Lippert

0

据我所知：这取决于编译器在解析步骤中使用的解析器类型。主要的解析器类型是LL和LR，两者具有不同的复杂度。

- DjLisT

7

语法分析仅是编译器中的一小部分。但无论如何，任何像样的语法分析器都是线性时间，因此这并没有提供太多见解。如果基于前瞻而不是回溯，LR始终是线性时间，LL也是如此，对于大多数其他实际选项也是如此。从渐近意义上讲（常数因素可能不同），语法分析不会成为瓶颈。 - user395760

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Gratzer · Accepted Answer

当前的问题无法回答。编译器的复杂性肯定不是以代码行数或源文件中字符数来衡量的。这只能描述解析器或词法分析器的复杂性，但编译器的其他部分甚至不会碰触该文件。

解析后，所有内容都将以代表更有结构的源文件的各种AST表示。编译器将具有许多中间语言，每种语言都有其自己的AST。各个阶段的复杂度将根据AST的大小而确定，这与字符计数或先前的AST没有任何关联。

考虑到这一点，我们可以在与字符数成线性的时间内解析大多数语言，并生成一些AST。诸如类型检查之类的简单操作通常对于具有n个叶子节点的树是O(n)。但然后我们将此AST转换为具有潜在的两倍、三倍甚至指数倍的节点数的形式。现在我们再次在树上运行单遍优化，但相对于原始AST，这可能是O(2^n)，而字符计数呢？谁知道呢！

我认为你会发现，即使是找到复杂度f(n)的n也很难。

作为铁证，包括Java、C＃和Scala在内的某些语言的编译是不可判定的（事实证明，名义子类型+方差导致不可判定的类型检查）。当然，C++的模板系统是图灵完备的，这使得可判定编译等效于停机问题（不可判定）。Haskell +一些扩展也是不可判定的。还有许多其他我想不起来的语言。对于这些语言的编译器，不存在最坏情况的复杂度。