编译原理复习要点：概念、文法与二义性解析

"编译原理总复习" 编译原理是计算机科学中的核心领域，主要研究如何将高级编程语言转换为机器可以理解和执行的低级语言。这一过程涉及到多个复杂阶段，每个阶段都有其特定的任务和目的。 首先，编译程序是一种语言翻译工具，它将源代码（源语言）转换为目标代码（目标语言），目标代码通常为汇编语言或机器语言，可以直接被计算机执行。在实现过程中，编译程序本身也是用某种编程语言（实现语言）编写的，早期的编译器多使用机器语言编写，而现在则常使用高级语言如C++或Java。 编译程序通常分为前端和后端两个部分。前端主要负责理解源代码，包括词法分析（将字符流转化为有意义的词汇单元）、语法分析（构建抽象语法树，解析源代码的结构）、语义分析（确保代码符合语法规则并理解其意义）、以及中间代码生成（生成与特定硬件无关的中间表示）。前端阶段的这些步骤大多不依赖于目标机器的具体特性。 而后端则关注目标代码的生成和优化。它包括目标代码生成（将中间代码转化为目标机器代码）、代码优化（提升程序运行效率，例如消除冗余计算、减少存储需求等）以及表格管理和错误处理。后端的这些任务是针对特定目标机器的，以确保生成的代码能够高效地在该机器上运行。 语言的语法描述方法多样，可以使用自然语言描述，绘制语法图，或者使用形式化的描述方法，如巴科斯-瑙尔范式（BNF）和扩展的巴科斯-瑙尔范式（EBNF）。这些方法为编写编译器提供了规范和指导。 Chomsky文法是形式语言理论中的一个重要概念，由诺姆·乔姆斯基提出。一个Chomsky文法G由四部分组成：非终结符号集VN，终结符号集VT，产生式集P，以及开始符号S。这样的文法可以用来描述语言的结构。 在给定的文法E→X|E+X，X→Y|X*Y，Y→（E）|i中，由于所有的产生式都遵循从左到右的线性结构，且没有回溯或嵌套，所以它是2类文法，即上下文无关文法。这类文法在编译器设计中非常常见，因为大多数高级编程语言的语法都是上下文无关的。 文法的二义性是编译原理中的一个重要概念。如果一个句子可以通过多种不同的方式解析，生成多棵语法树，那么这个句子和对应的文法就是二义性的。二义性可能会导致程序含义模糊，增加理解和实现的难度。因此，在设计编程语言和编译器时，通常会避免或消除文法的二义性，以确保代码的清晰性和可预测性。