编译原理大作业设计

1、塔里木大学课程设计2017届课程设计C语言编译器的设计与实现 学生姓名: 库尔班江.阿瓦克日 学 号: 5011212524 所属学院: 信息工程学院 专 业: 计算机科学与技术 班 级: 计算机17-1班 塔里木大学教务处制不要删除行尾的分节符，此行不会被打印编译原理大作业目录第1章 编译器概述21.1编译器概述2第2章 编译器设计42.1词法分析设计42.1语法分析设计62.1中间代码生成92.1语法翻译实现方法11第3章 数据结构说明123.1数据结构说明12第4章 编译程序运行测试154.1编译程序运行测试15参考文献18第1章 编译器概述黄金分割的 哈工大回归热大 【】个阿訇 妇孺诶

2、航天拖后腿航天皇太后 1.1 编译器概述编译器的任务是：输入 *.asm 源程序文件，输出 *.obj 目标代码文件和 *.lst 列表文件对输入的源程序进行扫描，找出所有词法和语法的错误，然后生成有待重定位的目标代码（中间文件）和提供查看信息的列表文件。中间文件后缀名为obj，是连接器的输入文件。一个编译器的整个工作流程是划分成一个一个阶段进行的，每个阶段都将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密联结在一起的。这几个阶段是：词法分析、语法分析、语义分析、中间代码生成。另外两个重要的工作：符号表格的管理和出错处理贯穿以上的所有阶段。编译过程中源程序的各种信息

3、被保留在种种不同的表格里。编译时自始至终涉及到表格的构造、查找和更新。如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些地方编译器还能自动校正错误，这些工作称之为出错处理。词法分析自左至右扫描源程序的字符串，并识别出一个个的单词（也称单词符号）。这里所谓的单词是指逻辑上紧密相连的按词的组成规则结合起来的一组字符，它们具有一定的意义。把每个单词的ASCII 码序列替换成所谓的机内表示Token 形式。这时还需要检查词法错误。词法分析阶段不依靠语法关系。语法分析扫描对象可能是源程序的AS

4、CII 码序列，也可能是词法分析后的Token 序列。前者情形，词法分析程序作为语法分析程序的子程序。语法分析的主要任务是检查源程序的形式语法错误。每当发现错误时将输出有关信息。很多编译程序在进行语法分析时同时完成其他工作，但要注意，如果语法有错误，那么其他工作也就白做。语义分析扫描的对象通常是语法分析后的结果。这时候，源程序的Token 序列已经变换成没有错误的符合语法的Token 生成树。对于编译器来说，它的任务是收集符号信息，登记在符号表格里，对伪指令的语义进行解释，完成相应的动作。伪指令的功能是改变编译器的状态并将一些必要的信息（如段定义，变量声明）加入到目标文件中去。另外，表达式的求

5、值，段的选择，地址计数器的计数，指令长度的计算等都在这个阶段中完成。语义分析阶段同样进行着对错误的处理。目标代码生成这时候的Token 流在形式上已经比较一致，符号信息都已经登记在各种表格里。这个阶段的任务是根据助记符的各种寻址方式决定它的目标代码。这一部分的工作与目标机的指令系统紧密相关。目标代码生成之后，还要根据obj 文件的格式把目标代码写入文件。最后还要产生列表文件，为用户提供源码与目标码的对照。第2章 编译器设计2.1 词法分析设计由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查，而将编译程序的重点放在中间代码生成阶段。词法分析器的功能是输入源程序，输出

6、单词符号。我们规定输出的单词符号格式为如下的二元式： (单词种别，单词自身的值)#define ACC -2#define syl_if 0#define syl_else 1#define syl_while 2#define syl_begin 3#define syl_end 4#define a 5#define semicolon 6#define e 7#define jinghao 8#define s 9#define L 10#define tempsy 11#define EA 12#define EO 13#define plus 14#define times 15#d

7、efine becomes 16#define op_and 17#define op_or 18#define op_not 19#define rop 20#define lparent 21#define rparent 22#define ident 23#define intconst 24函数说明 1 读取函数 readline( )、readch( )词法分析包含从源文件读取字符的操作，但频繁的读文件操作会影响程序执行效率，故实际上是从源程序文件” in.txt ”中读取一行到输入缓冲区，而词法分析过程中每次读取一个字符时则是通过执行 readch( )从输入缓冲区获得的；若缓冲

8、区已被读空，则再执行readline( )从 in.txt 中读取下一行至输入缓冲区。2 扫描函数 scan( ) 扫描函数 scan( )的功能是滤除多余空格并对主要单词进行分析处理，将分析得到的二元式存入二元式结果缓冲区。3 变量处理 find( )变量处理中首先把以字母开头的字母数字串存到 spelling 数组中，然后进行识别。识别过程是先让它与保留关键字表中的所有关键字进行匹配，若获得成功则说明它为保留关键字，即将其内码值写入二元式结果缓冲区；否则说明其为变量，这时让它与变量名表中的变量进行匹配(变量匹配函数find( )，如果成功，则说明该变量已存在并在二元式结果缓冲区中标记为此变

9、量(值填为该变量在变量名表中的位置)，否则将该变量登记到变量名表中，再将这个新变量存入二元式缓存数组中。4 数字识别 number( ) 数字识别将识别出的数字填入二元式结果缓存数组。5 显示函数 disp( )显示函数的功能在屏幕上输出词法分析的结果（即二元式序列程序），同时给出二元式个数及源程序行数统计。2.2 语法分析设计语法分析器的核心是三张 SLR 分析表以及针对这三张 SLR 分析表进行语义加工的语义动作。编译程序中语法分析处理及四元式生成部分主要是以二元式作为输入，并通过 SLR 分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。在

10、处理 if 和 while 语句时，需要进行真值或假值的拉链和返填工作，以便转移目标的正确填入。1. 控制语句的 SLR 分析表1 设计如下：将扩展文法G0)Sà S1)S à if e S else S2)S à while e S3)S à L 4)S à a;5)L à S6)L à SLstatic int action2011=/* 0 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 1, -1,/* 1 */ -1, -1, -1, -1, -1, -1, -1, -1,ACC, -1, -

11、1,/* 2 */ -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1,/* 3 */ -1, -1, -1, -1, -1, -1, -1, 7, -1, -1, -1,/* 4 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 9, 8,/* 5 */ -1, -1, -1, -1, -1, -1, 10, -1, -1, -1, -1,/* 6 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 11, -1,/* 7 */ 2, -1, 3, 4, -1, 5, -1, -1, -1, 12, -1,/* 8 */

12、-1, -1, -1, -1, 13, -1, -1, -1, -1, -1, -1,/* 9 */ 2, -1, 3, 4,105, 5, -1, -1, -1, 9, 14,/* 10*/ -1,104, -1, -1,104, -1, -1, -1,104, -1, -1,/* 11*/ -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 12*/ -1,102, -1, -1,102, -1, -1, -1,102, -1, -1,/* 13*/ -1,103, -1, -1,103, -1, -1, -1,103, -1, -1,/* 14*/

13、 -1, -1, -1, -1,106, -1, -1, -1, -1, -1, -1,/* 15*/ 2, -1, 3, 4, -1, 5, -1, -1, -1, 16, -1,/* 16*/ -1,101, -1, -1,101, -1, -1, -1,101, -1, -1;其中，前 9 列为 action 值，后 2 列为 goto 值；016 表示 17 个移进状态（ 即 Si）；-1表示出错；ACC 表示分析成功；而 100106 对应 7 个归约产生式：100 Sà S101 S à if e S else S102 S à while e S10

14、3 S à L 104 S à a;105 L à S106 L à SL2. 算术表达式的 LR 分析表 2 设计如下：0)S à E1)E à E+E2)E à E*E3)E à (E)4)E à i static int action1107=/* 0 */ 3, -1, -1, 2, -1, -1, 1,/* 1 */ -1, 4, 5, -1, -1,ACC, -1,/* 2 */ 3, -1, -1, 2, -1, -1, 6,/* 3 */ -1,104,104, -1,104,104, -

15、1,/* 4 */ 3, -1, -1, 2, -1, -1, 7,/* 5 */ 3, -1, -1, 2, -1, -1, 8,/* 6 */ -1, 4, 5, -1, 9, -1, -1,/* 7 */ -1,101, 5, -1,101,101, -1,/* 8 */ -1,102,102, -1,102,102, -1,/* 9 */ -1,103,103, -1,103,103, -1;3.布尔表达式的 SLR 分析表3 设计如下：0) Sà B1) B à i2) B à i rop i3) B à ( B )4) B à !

16、B5) A à B &&6) B à AB7) O à B |8) B à OBstatic int action21611=/* 0 */ 1, -1, 4, -1, 5, -1, -1, -1, 13, 7, 8,/* 1 */ 1, 2, -1,101, -1,101,101,101, -1, -1, -1,/* 2 */ 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,/* 3 */ -1, -1, -1,102, -1,102,102,102, -1, -1, -1,/* 4 */ 1, -1

17、, 4, -1, 5, -1, -1, -1, 11, 7, 8,/* 5 */ 1, -1, 4, -1, 5, -1, -1, -1, 6, 7, 8,/* 6 */ -1, -1, -1,104, -1, 9, 10,104, -1, -1, -1,/* 7 */ 1, -1, 4, -1, 5, -1, -1, -1, 14, 7, 8,/* 8 */ 1, -1, 4, -1, 5, -1, -1, -1, 15, 7, 8,/* 9 */ 105, -1,105, -1,105, -1, -1, -1, -1, -1, -1,/*10 */ 107, -1,107, -1,107,

18、 -1, -1, -1, -1, -1, -1,/*11 */ -1, -1, -1, 12, -1, 9, 10, -1, -1, -1, -1,/*12 */ -1, -1, -1,103, -1,103,103,103, -1, -1, -1,/*13 */ -1, -1, -1, -1, -1, 9, 10,ACC, -1, -1, -1,/*14 */ -1, -1, -1,106, -1, 9, 10,106, -1, -1, -1,/*15 */ -1, -1, -1,108, -1, 9, 10,108, -1, -1, -1;2.3 中间代码生成1. 布尔表达式 布尔表达式在

19、程序语言中有两个基本作用：一是用作控制语句（ 如 if -else 或 while语句）的条件式；二是用于逻辑演算，计算逻辑值。布尔表达式是由布尔算符（ &&、| 、！）作用于布尔变量（ 或常数）或关系表达式而形成的。关系表达式的形式是 E1 rop E2，其中 rop 是关系符（ 如<、=、>或），E1和 E2是算术式。在这里，我们只考虑前面给定文法所产生的布尔表达式：BB &&B | B | B | ! B | (B) | i rop i | i遵照我们的约定，布尔算符的优先顺序（ 从高到低）为：!、&&、|，并假定&&a

20、mp;和|都服从左结合规则。所有关系符的优先级都是相同的，而且高于任何布尔算符，低于任何算术算符，关系算符不得结合。表达式的真、假出口的确定：考虑表达式 B1 | B2 ，若 B1为真，则立即知道 B 也为真；因此，B1的真出口也就是整个 B 的真出口。若 B1?为假，则 B2必须被计值，B2的第一个四元式就是 B1的假出口。当然，B2的真、假出口也就是整个 B的真、假出口。类似的考虑适用于对 B1 && B2的翻译，我们将 B1 | B2和 B1 && B2 的翻译用下图表示，在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上。我们只

21、好把这种未完成的四元式的地址（ 编号）作为 B 的语义值暂存起来，待到整个表达式的四元式产生完毕之后再来回填这个未填入的转移目标。2. 条件语句对条件语句 if e S1 else S2 中的布尔表达式 e，其作用仅在于控制对 S1和 S2的选择。因此，作为转移条件的布尔式e，我们可以赋予它两种“ 出口”：一是“ 真”出T口，出向 S1；一是“ 假”出口，出向 S2。于是，e的代码F条件语句可以翻译成如图的一般形式。非终结符 e 具有两项语义值 e _TC 和e_FC，它们分别指出了尚待回填真、S2的代码假出口的四元式串。e 的“ 真”出口只有在往回扫描到if时才能知道，而它图 3-2 条件语

22、句的代码结构 的“ 假”出口则需到处理过 S1并且到达 else 才能明确。这就是说，必须把 e_FC 的值传下去，以便到达相应的 else时才进行回填。另外，当 S1语句执行完时意味着整个 if-else 语句也已执行完毕；因此，在 S1的编码之后应产生一条无条件转移指令。这条转移指令将导致程序控制离开整个 if-else 语句。但是，在完成 S2的翻译之前，这条无条件转移指令的转移目标是不知道的。甚至，在翻译完 S2之后，这条转移指令的转移目标仍无法确定。这种情形是由于语句的嵌套性所引起的。例如下面的语句：if e1 if e2 S1 else S2 else S3 在 S1的代码之后的那

23、条无条件转移指令不仅应跨越 S2而且应跨越 S3。这也就是说，转移目标的确定和语句所处的环境密切相关。3. 条件循环语句条件循环语句 while e S 通常被翻译成图的代码结构。布尔式 e 的“ 真”出口出向 S 代码段的第一个四元式。紧接 S 代码段之后应产生一条转向测试 e 的无条件转移指令。e 的“ 假”出口将导致程序控制离开整个 while 语句。e 的“ 假”出口目标即使在整个 while 语句翻译完之后也未必明确。例如： if e1 while e2 S1 else S2这种情况仍是由于语句的嵌套性引起的。所以，我们只好把它作为语句的语义值 S·CHAIN 暂留下来，以

24、便在处理外层语句时再伺机回填。2.4 语法翻译实现方法将上述语法翻译付诸实现过程中，我们仅保留了算术表达式和布尔表达式翻译的文法和语义动作；面对程序语句的翻译，由于改造后含有较多的非终结符且语义动作又相对简单，故仍恢复为改造之前的程序语句文法。由于总体上构造一个 SLR 分析表来实现语法分析及语义加工将使得所构造的 SLR 分析表过大，所以将其分为下面三部分处理：(1) 对算术表达式单独处理，即为算术表达式构造一个 SLR 分析表，并将赋值语句A=E 与算术表达式归为一类处理，处理之后的赋值语句仅看作为程序语句文法中的一个终结符 a。(2) 对布尔表达式也单独处理，并为其构造一个 SLR 分析

25、表，经 SLR 分析表处理后的布尔表达式看作为程序语句文法中的一个终结符 e。(3) 程序语句文法此时变为：S à if e S else S | while e S | L | a;L à SL | S此时为程序语句构造相应的 SLR 分析表就简单多了。前面的程序语句文法中所添加的非终结符是为了能及时回填有关四元式转移目标而引入的，在取消了这些非终结符后又如何解决及时回填转移目标的问题呢？我们采取的解决方法是增加两个数组 labelmark 和 labeltemp 来分别记录语句嵌套中每一层布尔表达式（ 如果有的话）e 的首地址以及每一层else（ 如果有的话）之前的四元

26、式地址（ 即无条件转出此层 if 语句的四元式）。也即，对程序语句的翻译来说：(1)在处理完布尔表达式 e 后，回填 if 或 while 语句的真值链；(2)在归约完每一个语句 S 之后检查符号栈，看在 S 之前的文法符号是否 if 或 while，若是则回填假值链（ 假值入口为语句 S 所对应的四元式序列之后；对 if 语句，此时已在该序列之后加入了一条无条件转移的四元式）；(3)在 if 语句中，else 前面要加入一个无条件转移的四元式转向 if 语句末尾；在 while语句尾要有一个无条件转移四元式转向 while 语句开头。第3章 数据结构说明3.1 数据结构说明编译程序中涉及到的

27、数据结构说明如下：char ch='0' /*从字符缓冲区中读取当前字符*/int count=0; /*词法分析结果缓冲区计数器*/static char spelling10=" " /*存放识别的字*/static char line81=" " /*一行字符缓冲区（ 最多 80 个字符）*/char *pline; /*字符缓冲区指针*/static char ntab110010; /*变量名表：共100项，每项长度为10*/struct ntab int tc; /*真值*/ int fc; /*假值*/ ntab2200;

28、/*在布尔表达式 ) 中保存有关布尔变量的真、假值*/int label=0; /*指向 ntab2 的指针*/struct rewords char sp10; int sy; ; /*匹配表的结构，用来与输入缓冲区中的单词进行匹配*/struct rewords rewords8= "if",syl_if, "else",syl_else, "while",syl_while, "",syl_begin, "",syl_end, "&&",op_and,

29、"|",op_or, "!",op_not; /*匹配表初始化，大小为8*/struct aa int syl; /*存放名字*/ int pos; /*存放名字所对应的值*/ buf100, /*词法分析结果缓冲区*/ n, /*读取二元式的当前字符*/ n1, /*当前表达式中的字符*/ E, /*非终结符*/ sstack100, /*算术或布尔表达式加工处理使用的符号栈*/ ibuf100, /*算术或布尔表达式使用的缓冲区*/ stack1000; /*语法分析加工处理使用的符号栈*/struct aa oth; /*四元式中空白位置*/struct fourexp char op10; struct aa arg1; struct aa arg2; int result; fexp200; /*四元式的结构定义*/int ssp=0; /*指向sstack栈指针*/struct aa *pbuf=buf; /*指向词法分析缓冲区的指针*/int nlength=0; /*词法分析中记录单词的长度*/int tt1=0; /*变量名表指针*/FILE *cfile; /*源程序文件，为结束符*