compiler-theory - 为什么编译器不能完全解决死代码检测问题？

Question

我在 C 或 Java 中使用的编译器具有死代码预防功能(当一行永远不会被执行时发出警告)。我的教授说编译器永远无法完全解决这个问题。我想知道这是为什么。我不太熟悉编译器的实际编码，因为这是一个基于理论的类(class)。但我想知道他们检查了什么(例如可能的输入字符串与可接受的输入等)，以及为什么这是不够的。

Answer 1

死代码问题与 Halting problem 有关。 .

艾伦图灵证明，不可能编写一个通用算法来给定一个程序并能够决定该程序是否针对所有输入停止。您也许可以为特定类型的程序编写这样的算法，但不能为所有程序编写。

这与死代码有何关系？

停止问题可以简化为查找死代码的问题。也就是说，如果您找到一种可以检测任何程序中的死代码的算法，那么您可以使用该算法来测试任何程序是否会停止。既然这已被证明是不可能的，那么为死代码编写算法也是不可能的。

如何将死代码算法转换为停止问题算法？

简单:在要检查是否停止的程序末尾添加一行代码。如果您的死代码检测器检测到该行已死，那么您就知道程序不会停止。如果没有，那么您就知道您的程序已停止(到达最后一行，然后到达您添加的代码行)。

<小时/>

编译器通常会检查那些可以在编译时证明已失效的东西。例如，依赖于在编译时可确定为假的条件的 block 。或 return 之后的任何语句(在同一范围内)。

这些是特定情况，因此可以为它们编写算法。也许可以为更复杂的情况编写算法(例如检查条件在语法上是否矛盾并因此始终返回 false 的算法)，但这仍然无法涵盖所有​​可能的情况。