编译器设计难点

《编译器设计难点》由会员分享，可在线阅读，更多相关《编译器设计难点（11页珍藏版）》请在装配图网上搜索。

1、现代编译器的设计及其难点摘要：我们常用的计算机软件，都需要通过编译的方式，把使用高级计算机语言编写的代码 (比如 C 代码)编译( compile )成计算机可以识别和执行的二进制代码。在现代计算机系 统中，编译器的设计始终都是一个重点与难点。此文主要介绍了编译器的设计方法，交叉编 译的诞生及其应用。关键词：代码、编译器、交叉编译。 导论：首先谈谈编译器的主要功能及其设计步骤，然后对主机编译器进行研究，具体分析设 计步骤，思考什么时候要用到交叉编译。回顾：编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的 低级机器语言的程序。编译器将原始程序( Source progr

2、am )作为输入，翻译产生使用目标 语言( Target language )的等价程序。编译程序完成从源程序到目标程序的翻译工作，是 一个复杂的整体的过程。一个现代编译器的主要工作流程如下：源程序( source code )- 预处理器(preprocessor )编译器(compiler )汇编程序(assembler )目标程序(object code )f连接器(链接器，Linker )f可执行程序(execu tables )。从概念上来讲，一个编 译程序的整个工作过程是划分成阶段进行的， 每个阶段将源程序的一种表示形式转换成另一 种表示形式，各个阶段进行的操作在逻辑上是紧密连接在

3、一起的。 一般一个编译过程划分成 词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法( 如图 1)。图1但有的目的平台上不允许或不能够安装我们所需要的编译器， 而我们又需要这个编译器的某 些特征；或者目标平台上的资源贫乏，无法运行我们所需要编译器，此时就需要用到交叉编 译。什么是交叉编译呢，简单地说，就是在一个平台上生成另一个平台上的可执行代码。 这里需要注意的是所谓 平台，实际上包含两个概念：体系结构(Architecture)、操作系统(Operating System)。同一个体系结构可以运行不同的操作系统；同样，同一个操作系统 也可以在不

4、同的体系结构上运行。举例来说，我们常说 的 x86 Linux 平台实际上是 Intel x86 体系结构和 Linux for x86 操作系统的统称；而 x86 WinNT 平台实际上是 Intel x86 体系结 构和 Windows NT for x86 操作系统的简称。，例如：编译程序在宿主机 A 上运行，将应用程序的源程序生成目标机 B 的代码(如图 2)。 与主机编译相比，交叉编译受的限制更多，虽然在理论上我们可以做任何形式的交叉编译， 但事实上，由于受到专利、版权、技术的限制，并不总是能够进行交叉编译，尤其是在业余 条件下！举例来说，至今无法生成惠普公司专有的 som 格式的可

5、执行文件，因此我们根本无 法做目的平台为 HPPA-HPUX 的交叉编译。图2要进行交叉编译，需要在主机平台上安装对应的交叉编译工具链 ( cross compilation tool chain )，然后用这个交叉编译工具链编译我们的源代码， 最终生成可在目标平台上运行的代 码。常见的交叉编译例子如下：1、在 Windows PC 上，利用 ADS (ARM 开发环境)，使用 armcc 编译器，则可编译出针 对 ARM CPU 的可执行代码。2、在 Linux PC 上，利用 arm-linux-gcc 编译器，可编译出针对 Linux ARM 平台的可执 行代码。3、在 Windows

6、PC 上，利用 cygwin 环境，运行 arm-elf-gcc 编译器，可编译出针对 ARM CPU 的可执行代码。理论分析：编译器各阶段的分组 前端：依赖于语言并很大程度上独立于目标机器。一般包括语法分析、词法分析、符号表 的建立、语义分析、中间代码生成以及相关错误处理。后端：依赖于目标机器的阶段或某些阶段的某些部分。一般来说，后端完成的任务不依赖 于源语言而只依赖于中间语言。 主要包括代码优化、 代码生成以及相关的错误处理和符号表操作。下面对编译器的各个阶段进行详细分析：一、词法分析词法分析又称扫描器（Scanner ），是编译的第一个阶段，是语法分析的必要准备。词法分析器读入源程序，产

7、生语言的基本词法单元，还完成和用户接口的一些任务 词法分析的主要任务 ：对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词 规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算 符、界限符和常量等）。再把它们转换成长度统一的标准形式属性字（ Token）。在这一阶段，我们主要要掌握从正规式到有限自动机的构造方法。构造词法分析器的一般方法和步骤： 用正规式 对模式进行描述；2为每个正规式构造一个NFA，它识别正规式所表示的正规集；3将构造出的NFA转换成等价的DFA，这一过程也被称为确定化；4优化DFA，使其状态数最少，这一过程也被称为最小化；5 从优化

8、后的 DFA 构造词法分析器 。二、语法分析语法分析器的主要作用：（1）、根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树）的某种表示； （2）、检查输入中的语法错误，并调用出错处理器进 行适当出错处理。语法分析分为自上而下分析和自下而上分析：自上而下分析 ：就是从文法的开始符号出发，向下推导，推出句子，即从根出发，按前序生成结点，为输入串构造分析树。主旨：对任何输入串，试图用一切可能的方法， 从文法出发，自上而下，从左到右的为输入串建立一棵语法树，或者说，为输入串寻找 一个最左推导。分析方法：a、带回溯的分析方法；b、不带回溯的分析方法：（1）、递归下降预测分析程序；（2）、

9、非递归/表 驱动的预测分析程序。自下而上分析 ：从输入串开始，逐步进行“归约”，如果最后能得到文法的开始符号， 则输入串是句子，否则输入串有语法错误。即从树末端开始，构造语法树。核心：寻找句型中的“句柄”进行归约，用不同的方法寻找句柄，就可获得不同的分 析方法。分析方法：（1）、普通的“移进 -规约”，掌握短语、直接短语、句柄、素短语、最左素短语的概念。 自下而上方法主要包括以下四个动作：-移进：把下一个输入符号读到分析栈中。-归约：把分析栈顶的句柄归约为一非终结符。-接受：分析成功。-报错：处理错误。这一方法的 关键是确定当前句型的句柄。但有些上下文无关文法不能使用移进归约分析。 这些文法的

10、移进归约分析器可能面临两 种情况：-分析器根据栈中的所有内容和下一个输入符号不能决定是移进还是归约（移进归约冲突）-分析器不能决定按哪一个产生式进行归约（归约一归约冲突）所以引入方法（2）、算符优先分析 ，掌握算符之间的优先级， 会求非终结符的 FIRSTVT 集和 LASTVT 集 会求算符优先文法的算符优先关系表，会判断一个文法是否为算符优先文法，能 根据算符优先关系表进行算符优先分析。由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否 为可归约串时采取一些检查措施，但仍难完全避免使错误的句子得到正确的归约。所以引入方法（3）、LR 分析法， 是指从左向右扫描和自底

11、向上的语法分析，且在分析的每一步，只须 根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看 K 个输入符号， 就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）LR 指“从左向右扫描和构造最右推导的逆过程（规范归约）”。LR 分析法的优缺点：（1）适合文法类足够大，适用于几乎所有上下文无关文法（2）分析效率高（3）报错及时（4）可以自动生成（5）手工实现工作量大LR 分析法的关键是对 LR 类文法的分析表的构造LR 分析 与 算符优先分析 相比较：（1）LR 分析的 可归约串 是某个句型的句柄。

12、算符优先分析法的 可归约串 是某个句型的最左素短语。这样就去掉了单非终结符的归约过程。所以算符优先分析法的分析速度比 LR 快。（2）LR 分析是最右推导的逆过程，所以是规范归约，得到的语法分析树和被分析句 型的分析树完全相同。算符优先分析法不是规范归约，得到的语法分析树有可能和被分析句型的分析树不 同。（3）LR 分析比算符优先分析对文法的限制少，应用更广。三、语义分析代码的表示：表达式首先被编译为分析树然后转化为dag。每个函数的dag在代码表中被串起来，代码表表示了函数的代码。code 结构：struct code enum Blockbeg, Blockend, Local, Addr

13、ess, Defpoint,Label,Start,Gen, Jump,Switch kind;Code prev, next;union u;主要是语句的识别和 if 语句的识别 在循环、switch、goto语句中都用到了标号和跳转，标号使通过 definelab 函数定义的， 而跳转通过 branch 函数生成。 除语句识别外，还有声明的识别。声明的识别非常复杂， c 语言中声明的形式 很多，处理时大量的相互递归调用。 经过前端的分析后，将源程序转化为dag，并添加进代码表。四、中间代码生成编译器的后端通过function接口函数调用gencode和emitcode来遍历代码表。 wal

14、k和listnodes函数操作处理dag森林。 newnode 函数为节点分配内存并用它的参数只来初始化节点的域。 listnode 还负责删除公共子表达式。 代码生成需要综合平衡各种因素。功能强大的优化器可以产生更好的代码。但是他的速度太慢了。五、代码优化例如：id1:= id2 +id3 *60(1)(inttoreal60 -t1 )(2)( *id3 t1 t2 )(3)( +id2t2 t3 )(4)( :=t3 -id1 )变换(1) (* id3 60.0 t1 )( 2 )( + id2 t1 id1 )六、 目标代码生成 目标代码生成目标机汇编和机器指令。例如： a in R

15、0, i in R1, n in R2t1 = 2 * Ij = t1 + 1t3 = j nif t3 goto L0j = t1 + 3L0: t6 = ajreturn t6sll R1, 1, R1add R1, 1, Jcmp J,R2blt .LL3add R1, 3, J.LL3: ld R0+J, Rtretr(*, id3 60.0 t1 )(+, id2 t1 id1 )movf id3,R2mulf #60.0,R2movf id2,R1addf R2,R1movf R1,id1七、问题1、一个经常会被问到的问题就是，“既然我们已经有了主机编译器，那为什么还要交 叉编译呢？”2、另一个经常会被问到的问题就是：“既然可以交叉编译，那还要主机编译干吗？” 结论：编译器在各个阶段的设计都是及其重要的，缺一不可，在各编译阶段，需要选择一定 的方法进行分析， 在方法选择上要注意其广泛性和存在的困难， 尽可能的选择较优的进行分 析。而编译器设计存在的难点多半也是在词法分析、语法分析的分析方法上。参考文献：