计算机编译技术考试复习资料

计算机编译技术考试复习资料引言编译技术是计算机科学领域的核心课程之一，它连接了高级程序设计语言与计算机硬件，揭示了程序从源码到可执行文件的奇妙旅程。本复习资料旨在梳理编译技术的核心概念、基本原理和关键算法，帮助同学们构建清晰的知识框架，为考试做好充分准备。请注意，编译技术涉及较多抽象概念和形式化方法，理解其内在逻辑并辅以适量练习是掌握这门学科的关键。一、编译程序概述1.1编译程序的定义与作用编译程序，简称为编译器，是一种特殊的程序。它以某种高级程序设计语言（源语言）编写的程序（源程序）作为输入，而以另一种低级语言（目标语言，通常是机器语言或汇编语言）的程序（目标程序）作为输出。其核心作用在于将人类易于理解和编写的高级语言代码，转换为计算机能够直接执行的机器指令，从而架起了从软件设计到硬件执行的桥梁。1.2编译过程的阶段划分一个典型的编译过程通常被逻辑地划分为若干个相继的阶段，每个阶段将源程序的一种表示形式转换为另一种表示形式，并逐步进行语义和语法的检查，最终生成目标代码。虽然不同编译器的实现细节可能有所差异，但大致可分为以下几个主要阶段：*词法分析（LexicalAnalysis）：又称扫描器，负责从源程序中识别出具有独立意义的最小语法单位——单词符号（Token），如关键字、标识符、常量、运算符、界符等。同时，它还会滤掉源程序中的注释和空白字符。*语法分析（SyntaxAnalysis）：又称parser，以词法分析输出的单词符号序列为输入，根据源语言的语法规则（通常用上下文无关文法描述），分析并确定这些单词符号之间的语法结构关系，通常用语法树（SyntaxTree）或分析树（ParseTree）来表示这种结构。*语义分析（SemanticAnalysis）：在语法分析的基础上，对语法结构正确的源程序进行上下文相关性质的审查，以及类型检查、类型转换、变量作用域分析等工作，确保源程序的语义符合语言定义的规范。*中间代码生成（IntermediateCodeGeneration）：在语义分析之后，有些编译器会生成一种介于源语言和目标语言之间的中间表示形式。这种中间代码通常结构简单、含义明确，且与具体机器无关，便于进行后续的代码优化和目标代码生成。常见的中间代码形式有四元式、三元式、间接三元式、逆波兰式（后缀表达式）和抽象语法树（AST）等。*代码优化（CodeOptimization）：对中间代码进行等价变换，旨在改善代码的质量，如提高运行速度、减少存储空间占用等。优化可以在不同层次进行，如局部优化、循环优化和全局优化。*目标代码生成（TargetCodeGeneration）：将经过优化的中间代码转换为特定目标机器的机器语言或汇编语言代码。这一阶段需要充分考虑目标机器的指令系统、寄存器分配、存储布局等特性。除了上述六个主要逻辑阶段外，编译过程还包括贯穿始终的表格管理和错误处理。表格管理用于记录源程序中的各种信息（如变量名、类型、作用域、函数参数等），供各阶段查询和使用。错误处理则负责在编译的各个阶段检测出源程序中的语法或语义错误，并进行适当的处理（如报告错误位置和性质，尝试恢复编译过程等），以保证编译能够继续进行或友好地终止。1.3编译程序的构造构造一个完整的编译程序是一项复杂的系统工程。为了提高开发效率和编译器的质量，人们常采用一些自动化的工具来辅助完成部分阶段的工作。例如：*词法分析器生成器：如Lex(或其GNU版本Flex)，它们接受用正则表达式描述的单词符号规则，自动生成相应的词法分析器。*语法分析器生成器：如Yacc(或其GNU版本Bison)，它们接受用上下文无关文法描述的语法规则，自动生成相应的语法分析器。这些工具极大地减轻了编译器开发者的负担，使得他们可以将更多精力集中在语义分析、代码优化等更复杂的环节。二、词法分析2.1词法分析的任务词法分析是编译过程的第一阶段，其主要任务包括：1.扫描源程序：按字符流的顺序读取源程序。2.识别单词符号：根据词法规则，将字符流分解为一个个单词符号（Token）。3.过滤无关字符：忽略源程序中的空格、制表符、换行符等空白字符，以及注释。4.记录单词信息：为识别出的每个单词符号赋予其类别（如关键字、标识符、常数等）和值（如标识符的名字、常数的数值），并将这些信息以某种形式（如Token序列）传递给语法分析阶段。5.发现并报告词法错误：如无法识别的字符序列。2.2单词符号的分类源程序中的单词符号通常可以分为以下几类：*关键字（保留字）：如`if`,`else`,`while`,`int`,`float`等，是语言预先定义的具有特定含义的单词，用户不能将其用作标识符。*标识符：用于表示变量、常量、函数、数组等名字的符号。*常数：如整数、实数、字符常量、字符串常量等。*运算符：如`+`,`-`,`*`,`/`,`=`,`==`,`>`,`<`等。*界符（分隔符）：如`(`,`)`,`{`,`}`,`[`,`]`,`;`,`,`,`.`等，用于分隔其他单词符号或组织程序结构。2.3词法分析器的设计与实现词法分析器的核心是如何有效地识别各类单词符号。这通常借助于有限自动机（FiniteAutomaton,FA）理论。有限自动机是一种数学模型，它能够准确地识别由正则文法所描述的语言，而大多数程序设计语言的单词符号都可以用正则文法来定义。*确定有限自动机（DFA）：对于每一个状态和输入符号，有且仅有一个确定的后继状态。DFA易于用程序实现，因此词法分析器通常基于DFA来构造。*非确定有限自动机（NFA）：允许在某个状态下，对于某个输入符号有多个可能的后继状态，或者对于ε（空输入）也可以进行状态转换。NFA比DFA更容易直接从正则表达式构造出来。实际构造词法分析器时，通常的步骤是：1.用正则表达式描述各类单词符号的词法规则。2.将正则表达式转换为等价的NFA。3.将NFA确定化为DFA（子集构造法）。4.对DFA进行最小化（Hopcroft算法或Moore算法），以简化状态数量，提高效率。5.根据最小化的DFA编写词法分析器的代码。三、语法分析3.1语法分析的任务语法分析的主要任务是：以词法分析器输出的单词符号序列为输入，根据源语言的语法规则（通常由上下文无关文法描述），判断该序列是否构成一个语法上正确的句子（即源程序的语法结构是否符合语言规范）。如果符合，则以某种形式（如语法树）来表示该句子的语法结构；如果不符合，则报告语法错误的位置和性质。3.2上下文无关文法（CFG）上下文无关文法是描述程序设计语言语法的强有力工具。一个上下文无关文法G定义为一个四元组：G=(V_N,V_T,P,S)其中：*V_N：非终结符（Non-terminal）的集合，这些符号表示语法范畴或语法单位，如`<表达式>`,`<语句>`等。*V_T：终结符（Terminal）的集合，这些符号是语言的基本符号，对应于词法分析器输出的单词符号。*P：产生式（Production）的集合，每个产生式是形如A→α的规则，其中A∈V_N，α∈(V_N∪V_T)*。产生式表示了从非终结符A可以推导出符号串α。*S：开始符号（StartSymbol），S∈V_N，它是文法中最大的语法范畴，代表我们所要定义的语言。由文法G所产生的语言L(G)，是指从开始符号S出发，通过应用一系列产生式可以推导出的所有终结符符号串的集合。3.3语法树与二义性*语法树（推导树）：是描述上下文无关文法推导过程的一种图形表示。树中的每个节点标记一个文法符号。根节点标记开始符号S。对于每个非终结符节点A，它的孩子节点从左到右依次标记产生式A→α中的符号α。*二义性（Ambiguity）：如果一个文法存在某个句子，它对应两棵或两棵以上不同的语法树（或存在两个或两个以上不同的最左推导或最右推导），则称该文法是二义性的。二义性文法会给语法分析带来困难，因为同一个句子可能有不同的语法解释。在实际应用中，通常需要通过附加规则（如优先级、结合性规则）或重写文法来消除二义性。3.4语法分析方法语法分析方法多种多样，大致可分为两大类：自上而下分析法和自下而上分析法。3.4.1自上而下分析法自上而下分析法的基本思想是：从开始符号S出发，根据文法的产生式，尝试推导出与输入单词符号序列完全匹配的句子。如果能够成功，则分析成功；否则，分析失败。*递归下降分析法：一种直观的自上而下分析方法。它为文法中的每个非终结符编写一个递归过程（或函数），该过程根据当前非终结符的产生式来决定如何分解输入串。为了避免回溯，递归下降分析法通常要求文法是LL(1)文法。*预测分析法（LL(1)分析法）：一种不带回溯的自上而下分析法。它使用一张预测分析表（LL(1)分析表）和一个分析栈来进行分析。LL(1)中的第一个"L"表示从左到右扫描输入串，第二个"L"表示最左推导，"1"表示分析时每一步只需向前查看一个输入符号。构造LL(1)分析表需要计算文法中非终结符的FIRST集合和FOLLOW集合：*FIRST(A)：从非终结符A开始推导，所能推导出的所有开头终结符的集合，若A能推导出ε，则ε也在FIRST(A)中。*FOLLOW(A)：在文法的所有句型中，紧跟在非终结符A之后出现的终结符的集合，若A是句型的尾符号，则#（表示输入串结束符）也在FOLLOW(A)中。一个文法是LL(1)文法，当且仅当对于其每个非终结符A的任意两个不同产生式A→α和A→β，满足：1.FIRST(α)∩FIRST(β)=∅。2.若β能推导出ε，则FIRST(α)∩FOLLOW(A)=∅；反之亦然。3.4.2自下而上分析法自下而上分析法的基本思想是：从输入单词符号序列开始，逐步进行归约（即反向应用产生式），将当前的符号串归约为文法的开始符号S。如果能够成功归约到S，则分析成功；否则，分析失败。*算符优先分析法：一种简单直观的自下而上分析法，它只考虑算符（终结符）之间的优先关系和结合性，而忽略非终结符的具体名称。它适用于表达式的分析，但表达能力有限。*LR分析法：一类功能强大且广为使用的自下而上分析法，包括SLR(1)、LR(1)和LALR(1)等变种。LR中的"L"表示从左到右扫描输入串，"R"表示最右推导的逆过程（即最左归约），"1"表示分析时每一步通常只需向前查看一个输入符号。LR分析法使用一个分析栈、一张LR分析表（包含动作表ACTION和状态转移表GOTO）和一个状态机来进行分析。其核心是LR项目集规范族的构造。LR分析法的优点是分析能力强（能处理大部分程序设计语言的文法）、效率高且能及时发现语法错误。四、语义分析与中间代码生成4.1语义分析的任务语义分析主要处理源程序的语义信息，确保程序各部分之间的意义是一致的、符合语言定义的。其主要任务包括：*类型检查：检查运算对象的类型是否符合运算符的要求，如整型数不能与字符串进行算术运算。*类型转换：当运算对象的类型与运算符要求的类型不一致，但语言允许时，进行自动类型转换（隐式转换），如某些语言中int型可以转换为float型。*变量声明与作用域检查：确保变量在使用前已经声明，并且在其作用域内被访问。*数组维数和下标类型检查。*函数调用时实参与形参的个数、类型和顺序是否匹配的检查。*其他静态语义检查：如某些语言中不允许的递归定义等。4.2属性文法与语法制导翻译为了在语法分析的同时进行语义分析和中间代码生成，通常采用语法制导翻译（Syntax-DirectedTranslation,SDT）技术。属性文法（AttributeGrammar）是描述SDT的有力工具。*属性文法：在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干个属性，并为每个产生式配备一组语义规则，用于计算该产生式中各文法符号的属性值。*属性：分为综合属性（SynthesizedAttribute）和继承属性（InheritedAttribute）。*综合属性：由子节点的属性值计算父节点的属性值，自底向上传递信息。*继承属性：由父节点和/或兄弟节点的属性值计算子节点的属性值，自顶向下或横向传递信息。语法制导翻译就是在语法分析过程中，当使用某个产生式进行推导或归约时，执行相应的语义规则，完成属性值的计算和中间代码的生成等工作。4.3中间代码的常见形式中间代码应具备结构简单、含义明确、与机器无关、易于优化和转换为目标代码等特点。常见的中间代码形式有：*抽象语法树（AST）：是语法树的简化形式，它去掉了语法树中那些仅用于辅助语法分析的节点，更直接地反映了源程序的语法结构和语义信息。*后缀表达式（逆波兰式）：将运算符写在运算对象之后，其最大特点是不需要括号来标识运算的优先级和结合性，易于计算机求值。*四元式（Quadruple）：一种更接近目标代码的中间表示，通常形式为(op,arg1,arg2,result)，其中op是运算符，arg1和arg2是运算对象，result是运算结果的存放位置。*