编译器设计难点.doc

现代编译器的设计及其难点 摘要：我们常用的计算机软件，都需要通过编译的方式，把使用高级计算机语言编写的代码（比如C代码）编译（compile）成计算机可以识别和执行的二进制代码。在现代计算机系统中，编译器的设计始终都是一个重点与难点。此文主要介绍了编译器的设计方法，交叉编译的诞生及其应用。关键词：代码、编译器、交叉编译。导论：首先谈谈编译器的主要功能及其设计步骤，然后对主机编译器进行研究，具体分析设计步骤，思考什么时候要用到交叉编译。回顾：编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低级机器语言的程序。编译器将原始程序（Source program）作为输入，翻译产生使用目标语言（Target language）的等价程序。编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。一个现代编译器的主要工作流程如下：源程序（source code）预处理器（preprocessor）编译器（compiler）汇编程序（assembler）目标程序（object code）连接器（链接器，Linker）可执行程序（executables）。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法（如图1）。 图1但有的目的平台上不允许或不能够安装我们所需要的编译器，而我们又需要这个编译器的某些特征；或者目标平台上的资源贫乏，无法运行我们所需要编译器，此时就需要用到交叉编译。什么是交叉编译呢，简单地说，就是在一个平台上生成另一个平台上的可执行代码。这里需要注意的是所谓 平台，实际上包含两个概念：体系结构（Architecture）、操作系统（Operating System）。同一个体系结 构可以运行不同的操作系统；同样，同一个操作系统也可以在不同的体系结构上运行。举例来说，我们常说 的x86 Linux平台实际上是Intel x86体系结构和Linux for x86操作系统的统称；而x86 WinNT平台实际上是 Intel x86体系结构和Windows NT for x86操作系统的简称。 ，例如：编译程序在宿主机A上运行，将应用程序的源程序生成目标机B的代码（如图2）。与主机编译相比，交叉编译受的限制更多，虽然在理论上我们可以做任何形式的交叉编译，但事实上，由于受到专利、版权、技术的限制，并不总是能够进行交叉编译，尤其是在业余条件下！举例来说，至今无法生成惠普公司专有的som格式的可执行文件，因此我们根本无法做目的平台为HPPA-HPUX的交叉编译。SOIOAB图2要进行交叉编译，需要在主机平台上安装对应的交叉编译工具链（cross compilation tool chain），然后用这个交叉编译工具链编译我们的源代码，最终生成可在目标平台上运行的代码。常见的交叉编译例子如下： 1、在Windows PC上，利用ADS（ARM 开发环境），使用armcc编译器，则可编译出针对ARM CPU的可执行代码。 2、在Linux PC上，利用arm-linux-gcc编译器，可编译出针对Linux ARM平台的可执行代码。 3、在Windows PC上，利用cygwin环境，运行arm-elf-gcc编译器，可编译出针对ARM CPU的可执行代码。理论分析：编译器各阶段的分组前端：依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表的建立、语义分析、中间代码生成以及相关错误处理。后端：依赖于目标机器的阶段或某些阶段的某些部分。一般来说，后端完成的任务不依赖于源语言而只依赖于中间语言。主要包括代码优化、代码生成以及相关的错误处理和符号表操作。下面对编译器的各个阶段进行详细分析：一、 词法分析词法分析又称扫描器（Scanner），是编译的第一个阶段，是语法分析的必要准备。词法分析器读入源程序，产生语言的基本词法单元，还完成和用户接口的一些任务词法分析的主要任务： 对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式属性字（Token）。在这一阶段，我们主要要掌握从正规式到有限自动机的构造方法。 构造词法分析器的一般方法和步骤： 用正规式对模式进行描述； 为每个正规式构造一个NFA，它识别正规式所表示的正规集； 将构造出的NFA转换成等价的DFA，这一过程也被称为确定化； 优化DFA，使其状态数最少，这一过程也被称为最小化； 从优化后的DFA构造词法分析器。二、 语法分析语法分析器的主要作用：（1）、根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树）的某种表示；（2）、检查输入中的语法错误，并调用出错处理器进行适当出错处理。语法分析分为自上而下分析和自下而上分析： 自上而下分析：就是从文法的开始符号出发，向下推导，推出句子，即从根出发，按前序生成结点，为输入串构造分析树。主旨：对任何输入串，试图用一切可能的方法，从文法出发，自上而下，从左到右的为输入串建立一棵语法树，或者说，为输入串寻找一个最左推导。分析方法：a、带回溯的分析方法； b、不带回溯的分析方法：（1）、递归下降预测分析程序；（2）、非递归/表驱动的预测分析程序。 自下而上分析：从输入串开始，逐步进行“归约”，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。即从树末端开始，构造语法树。 核心：寻找句型中的“句柄”进行归约，用不同的方法寻找句柄，就可获得不同的分析方法。 分析方法：（1）、普通的“移进-规约”，掌握短语、直接短语、句柄、素短语、最左素短语的概念。自下而上方法主要包括以下四个动作： 移进：把下一个输入符号读到分析栈中。 归约：把分析栈顶的句柄归约为一非终结符。 接受：分析成功。 报错：处理错误。这一方法的关键是确定当前句型的句柄。但有些上下文无关文法不能使用移进归约分析。这些文法的移进归约分析器可能面临两种情况： 分析器根据栈中的所有内容和下一个输入符号不能决定是移进还是归约（移进归约冲突） 分析器不能决定按哪一个产生式进行归约（归约归约冲突）所以引入方法（2）、算符优先分析，掌握算符之间的优先级，会求非终结符的FIRSTVT集和LASTVT集，会求算符优先文法的算符优先关系表，会判断一个文法是否为算符优先文法，能根据算符优先关系表进行算符优先分析。由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为可归约串时采取一些检查措施，但仍难完全避免使错误的句子得到正确的归约。所以引入方法（3）、LR分析法，是指从左向右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。 LR指“从左向右扫描和构造最右推导的逆过程（规范归约）”。LR分析法的优缺点：（1）适合文法类足够大，适用于几乎所有上下文无关文法（2）分析效率高（3）报错及时（4）可以自动生成（5）手工实现工作量大LR分析法的关键是对LR类文法的分析表的构造。LR分析 与 算符优先分析 相比较：（1）LR分析的 可归约串 是某个句型的句柄。 算符优先分析法的 可归约串 是某个句型的最左素短语。 这样就去掉了单非终结符的归约过程。 所以算符优先分析法的分析速度比LR快。（2） LR分析是最右推导的逆过程，所以是规范归约，得到的语法分析树和被分析句型的分析树完全相同。算符优先分析法不是规范归约，得到的语法分析树有可能和被分析句型的分析树不同。（3） LR分析比算符优先分析对文法的限制少，应用更广。三、语义分析 代码的表示：表达式首先被编译为分析树然后转化为dag。每个函数的dag在代码表中被串起来，代码表表示了函数的代码。code结构：struct code enum Blockbeg, Blockend, Local, Address, Defpoint, Label, Start, Gen, Jump, Switch kind;Code prev, next;union u; 主要是语句的识别和if语句的识别 在循环、switch、goto语句中都用到了标号和跳转，标号使通过definelab函数定义的，而跳转通过branch函数生成。 除语句识别外，还有声明的识别。声明的识别非常复杂，c语言中声明的形式很多，处理时大量的相互递归调用。 经过前端的分析后，将源程序转化为dag，并添加进代码表。四、 中间代码生成 编译器的后端通过function接口函数调用gencode和emitcode来遍历代码表。 walk和listnodes函数操作处理dag森林。 newnode函数为节点分配内存并用它的参数只来初始化节点的域。 listnode还负责删除公共子表达式。代码生成需要综合平衡各种因素。功能强大的优化器可以产生更好的代码。但是他的速度太慢了。五、 代码优化 例如： id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换 （1） ( *id360.0t1) ( 2）（ + id2 t1id1)六、 目标代码生成目标代码生成目标机汇编和机器指令。例如：a in R0, i in R1, n in R2 t1 = 2 * I j = t1 + 1t3 = j nif t3 goto L0 j = t1 + 3L0: t6 = ajreturn t6sll R1, 1, R1add R1, 1, J cmp J,R2 blt .LL3 add R1, 3, J .LL3: ld R0+J, Rtretr(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1七、问题1、一个经常会被问到的问题就是，“既然