编译器正确性理论：优化与可接受错误分析

"这篇文档是2002年的一篇计算机科学电子笔记，主题聚焦于编译器正确性理论和优化的可接受性观点。作者Wolfgang Goerigk探讨了如何通过编译器中的转换来定义和区分程序的正确实现与可接受的错误。文章提出了将有限和无限错误分为可接受和不可接受两类，以此来模拟编译器处理运行时错误的现实需求。此外，文章还强调了正确实现的传递性和组合性，这对于多遍编译和模块化编译器设计至关重要。" 在编译器正确性理论中，作者关注的是如何确保编译器的输出能够保持源代码的正确性，尤其是在面对有限的运行时错误时。编译器的转换过程可能导致错误，但有些错误可能被视为不可避免，被定义为可接受的错误。这些错误通常发生在程序运行超出其前提条件指定的范围时。相反，不可接受的错误会导致混乱的程序行为，应当避免。 文章提出了一种通过特殊的组成图交换性来定义正确实现的方法，这种方法允许编译器在不同的应用领域内适当地保持正确性。这意味着用户可以调整编译器选项，以适应不同的性能或安全性需求。这种理论不仅适用于用户程序，也适用于编译器本身的实现，确保编译器的每个部分都正确地执行其预定功能。 在讨论可传递性时，Goerigk强调了正确实现的组合性和模块化。这在多遍编译中尤为重要，因为每一遍编译可能会引入新的转换，但整体的正确性不应受到影响。同样，对于编译器规范中的模块化设计，每一步转换的正确性必须独立于其他模块，同时又能正确地组合起来。 文章进一步扩展了这一理论，探讨了编译规范和编译程序实现之间的正确性关系。正确的编译器应该能够正确地编译规范，保持源代码的语义不变。通过这种方式，作者为评估和设计编译器提供了一个更精细的框架，允许区分不同层次的正确性需求，从而更好地支持编译器的优化和定制。 总结来说，这篇论文提供了对编译器正确性的一种新视角，引入了可接受错误的概念，并强调了正确实现的传递性和组合性在编译器设计中的重要性。这对于理解和改进编译器的正确性保证，以及在实际环境中安全有效地使用编译器具有重要的理论和实践价值。