搜索
编译原理实 验 报 告 课程名称 编译原理实验 实验项目名称 编译器 学号 XXXXXXXXXX 班级 XXXXXX 姓名 XXX 专业 计算机 科学与技术 学生所在学院 计算机 科学与技术学院 指导教师 XXX 实验室名称地点 XXXXXX大学 计算机科学与技术学院 1一、实验概述 1. 实验名称 【编译器】 2. 实验目的 !理解编译器工作原理 !掌握编译器构造方法 !实现编译器编译 3. 实验类型 【设计】 4. 实验内容 !实现词法分析 !实现语法分析 !实现中间代码转换 !实现目标代码生成 二、实验环境 实验使用的操作系统：Window XP 编程环境：Visual C++ 6.0 三、实验过程 1. 原理分析 高级计算机语言便于人编写，阅读，维护。低阶机器语言是计算机能直接解2读、运行的。编译器将源程序（Source program）作为输入，翻译产生使用目标语言（Target language）的等价程序。源代码一般为高级语言 (High-level language)， 如Pascal、C、C++、C#、Java等，而目标语言则是汇编语言或目标机器的目标代码（Object code），有时也称作机器代码（Machine code）。 编译是从源代码（通常为高级语言）到能直接被计算机或虚拟机执行的目标代码（通常为低级语言或机器语言）的翻译过程。然而，也存在从低级语言到高级语言的编译器，这类编译器中用来从由高级语言生成的低级语言代码重新生成高级语言代码的又被叫做反编译器。也有从一种高级语言生成另一种高级语言的编译器，或者生成一种需要进一步处理的的中间代码的编译器（又叫级联）。 典型的编译器输出是由包含入口点的名字和地址，以及外部调用（到不在这个目标文件中的函数调用）的机器代码所组成的目标文件。一组目标文件，不必是同一编译器产生，但使用的编译器必需采用同样的输出格式，可以链接在一起并生成可以由用户直接执行的可执行程序。 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高级语言作为输入，输出也是高级语言的编译器。例如: 自动并行化编译器经常采用一种高级语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语言构造进行注释（如FORTRAN的DOALL指令）。 3编译器的前端主要负责解析（parse）输入的源代码，由语法分析器和语意分析器协同工作。语法分析器负责把源代码中的‘单词’（Token）找出来，语意分析器把这些分散的单词按预先定义好的语法组装成有意义的表达式，语句 ，函数等等。 例如“a = b + c;”前端语法分析器看到的是“a， =， b ， +， c;”，语意分析器按定义的语法，先把他们组装成表达式“b + c”，再组装成“a = b + c”的语句。 前端还负责语义（semantic checking）的检查，例如检测参与运算的变量是否是同一类型的，简单的错误处理。昀终的结果常常是一个抽象的语法树（abstract syntax tree，或 AST），这样后端可以在此基础上进一步优化，处理。 编译器后端主要负责分析，优化中间代码（Intermediate representation）以及生成机器代码（Code Generation）。 一般说来所有的编译器分析，优化，变型都可以分成两大类： 函数内（intraprocedural）还是函数之间（interprocedural）进行。很明显，函数间的分析，优化更准确，但需要更长的时间来完成。 编译器分析（compiler analysis）的对象是前端生成并传递过来的中间代码，现代的优化型编译器（optimizing compiler）常常用好几种层次的中间代码来表示程序，高层的中间代码（high level IR）接近输入的源程序的格式，与输入语言相关（language dependent），包含更多的全局性的信息，和源程序的结构；中层的中间代码（middle level IR）与输入语言无关，低层的中间代码(Low level IR)与机器语言类似。 不同的分析，优化发生在昀适合的那一层中间4代码上。 常见的编译分析有函数调用树（call tree），控制流程图（Control flow graph），以及在此基础上的 变量定义－使用，使用－定义链（define-use/use-define or u-d/d-u chain），变量别名分析（alias analysis），指针分析（pointer analysis），数据依赖分析（data dependence analysis）等。 程序分析结果是编译器优化（compiler optimization）和程序变形（compiler transformation）的前提条件。常见的优化和变形有：函数内嵌（inlining），无用代码删除（Dead code elimination），标准化循环结构（loop normalization），循环体展开（loop unrolling），循环体合并，分裂（loop fusion，loop fission），数组填充（array padding），等等。 优化和变形的目的是减少代码的长度，提高内存（memory），缓存（cache）的使用率，减少读写磁盘，访问网络数据的频率。更高级的优化甚至可以把序列化的代码（serial code）变成并行运算，多线程的代码（parallelized，multi-threadedcode）。 机器代码的生成是优化变型后的中间代码转换成机器指令的过程。现代编译器主要采用生成汇编代码（assembly code）的策略，而不直接生成二进制的目标代码（binary object code）。即使在代码生成阶段，高级编译器仍然要做很多分析，优化，变形的工作。例如如何分配寄存器（register allocatioin），如何选择合适的机器指令（instruction selection），如何合并几句代码成一句等等。 52. 设计思路 !词法分析阶段： 词法分析算法主要利用状态转换图生成一个词法分析器，对输入的程序进行词法分析，并将分析得到的单词造表。其中关键字表和界限符表的大小是由高级语言的子集决定的，可以用数组装载；而标识符表和常数表的大小取决于输入的待分析程序中的变量、过程名、常数的个数，所以要用指针组成动态链表来装载。当然为了方便，我们也把它定义成数组处理。算法根据C语言单词符号类型不同，现将其分为关键字、普通标示符、常数和界符这四类，为简化程序判定复杂程度，现引入界符一词，所谓界符就是就是成对出现的符号，比如{ }、[ ]、 、' ' 等等。扫描字符串过程以遍历单词类型的形式循环进行，即在未识别出具有独立意义的昀小语法单位并且尚未判定所扫描的字符串无效，无法识别之前，将所扫描的字符串先统一集中存储在一个字符串数组之中，而后，每识别出一个单词，若这个单词的类型是关键字、普通标示符、常数或界符中之一，那么就将此单词以文字说明的形式输出。 !语法分析阶段： 文法分析阶段所做的工作是用VC要建立一个针对LL(1)文法的编译器的编译器。本文既可以以定义好的文法书写的文件作为输入，其中包括语法及语义动作，鉴于输入文件的所用的文法可以用LL(1)分析，于是对输入的文件用递归下降的分析方法在内存中建立它的存储结构，然后分别计算所输入的文法的非终结符号是否可以生成空，每个非终结符号的first集合，每个非终结符号的follow6集合，以及每个规则的predict集合，接着判断任意一个非终结符号的任意两个规则的Predict集的交集是不是都为空，如果是则输入文法可以用递归下降法分析，否则不可以，用户应该对所输入的文法作适当的修改，使其满足LL(1)文法分析的要求，。如果所输入的文法可以用递归下降法分析，生成相应文法的语法分析程序。也可以自行添加文法，本课程设计有根据相应文法自动生成分析表和语法树，并将分析信息和结果保存到一个外部文件中的的功能，能灵活实现语法编译器的相应功能。 设计一个给定LL（1）语法分析器，输入一个句子，能由依据LL（1）分析表输出与句子对应的语法树。能对语法树生成过程进行模拟。动态模拟算法的基本功能是： 1）语法分析：打开或输入一个文法文件或句子，能对其进行语法分析，能显示器中间代码信息，当存在错误时，能显示出语法分析错误信息。主要判断文法是否为上下文无关文法，去掉形如A→A的有害产生式，去掉不可终止符及其产生式，去掉不可达符及其产生式。 2）LL(1)文法判别:打开(输入)一个形如E-abc的LL(1)文法，它通过对输入的文法求解FIRST集、FOLLOW集、SELECT集，昀后根据SELECT集是否相交来判断，如果SELECT集相交，测通过提取左公因子，消除左递归看是否可以构成LL(1)文法；如果SELECT集不相交，则该文法是LL(1)文法。接着消除左公共因子及左递归，对非LL(1)文法进行改造，使其可能成为LL(1)文法。它先对文法进行判断，看其是否含有左公共因子，若有则消除，若无则不作任何处理，7然后再判断文法是否含有直接或间接左递归，若有则消除，若无则不作任何处理。 3）预测分析： 打开(输入)一个形如E-abc的LL(1)文法，首先初始化栈，#进栈，E进栈作为文法开始的状态。根据产生式表的产生式生成每个非终结符的FIRST集及FOLLOW集。由一个算法生成预测分析表，该预测分析表是由一个二维数组M[n1][n2]构成。由定理可知：若a∈SELECT(A →α),则把A →α放于矩阵M[A,a]。而这里生成的二维数组M[n1][n2]与该定理类似。不过这里n1是指A在非终结符表中的序号，n2是指a在终结符表中的序号，而M[n1][n2]的值是指产生式A →α在产生式表中的序号。这样做就为下面的预测分析程序带来了方便。预测分析程序分为检测不合法输入模块和对输入字符串的语法分析模块。对输入字符串的语法分析是通过栈及产生式表和预测分析表的相关联系构建一个算法来对这个字符串进行语法分析。通过算法将栈顶元素与输入字符串的比对、出栈及相关产生式的推导的右部的逆序入栈等操作可完成对输入字符串的语法分析。 4）句子语法树；根据确认LL(1)文法，确认输入串是否为文法的句子，是，则形成该符号串的分析过程，并直观的显示分析过程。 !目标代码生成阶段： 1）将一个普通的中序表达式转换为逆波兰表达式的一般算法： 首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级昀低的运算符#，其中，中缀式应以此昀低优先级的运算符结束。可指定其他字符，不一定非#不8可。从中缀式的左端开始取字符，逐序进行如下步骤： （1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈 （2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1