编译原理实验指导书
目 录 相关问题说明 1 实验题 2 实验1 词法分析（2课时）
3 实验2 语法分析（2课时）
5 实验3 语义分析（2课时）
7 实验4 代码生成（2课时）
9 参考书目 11 相关问题说明 本课程共有4个实验，本课程中所实现的程序为普通C或C++程序，在Windows环境下，属于控制台应用程序。
提交实验成果：
1.实验成果包括：
n 源程序。用学号加姓名方式命名项目或源程序所在目录，例如，学号：090510xxx，姓名：某某，目录名就是：090510xxx某某。只要源程序，不要编译后文件。
n 实验报告。
2.实验报告由班干部收齐后在实验后下一次上课时交给我（最后一个实验除外），源程序发我邮箱。
实验成果评价标准：
1.及时提交实验成果，过期再交，不计成绩。
2.实验成果和他人雷同者，不计成绩。
3.实验报告采用手写方式，书写格式按照计算机与信息工程系要求执行，不按要求办事的，不计成绩。
4.实验成果不完整的，即缺源程序或实验报告者，不计成绩。
5.实验报告内容充实，能够真实反映实验情况的，酌情加分。
6.实验报告字迹工整的，酌情加分。
7.存在其他加分的可能性。
实验时间和地点：
班级 周次 星期 节次 实验室 信管051 7,9,11,13,16 1 1-2 东7-405 软件工程062 14 1 1-2 东7-405 软件工程071 18 1 1-2 东7-405 计算机062 7,9,11,12,14,16,17 1 1-2 东7-406 信息管理071 18 1 1-2 东7-406 信息管理061 16 1 1-2 东7-408 信息管理071 4,7,11,13,15,17 1 1-2 东7-408 软件工程061 9,14 1 1-2 东7-408 信息管理062 16 1 1-2 东7-412 软件工程071 11,12,13,14,15 1 1-2 东7-412 软件工程062 9 1 1-2 东7-412 计算机051 13,14,15,16 1 1-2 东7-413 物流管理082 7,8,9,10,11,12,13,14,15,16 1 1-2 东8-405 广告学081 7,8,9,10,11,12,13,14,15,16 1 1-2 东8-409 信息管理051 13,14,15,16,17,18 1 3-4 东7-405 计算机052 13,14,15,16 1 3-4 东7-406 信管061 11,12,17,18 1 3-4 东7-406 网络工程091 8,9,11,12 2 5-6 东8-413 信管052 7,9,11,13,16 1 3-4 东7-412 信管061 15 1 3-4 东7-412 计科051 4,6,8,10,12,14,16,18 1 3-4 东7-413 计算机应用081 17 1 3-4 东7-413 艺术设计084 14 1 3-4 东8-405 计算机应用081 4,5,6,7,8,9,10,11,12,13,14,15,16 1 3-4 东8-409 信息与计算科学061 11,12,13,14 1 中午 东7-405 软件工程081 8,9,10,11,12,13,14,15 1 中午 东7-406 软件工程061 9,10,11,12,13,14 1 中午 东7-408 软件工程062 9,10,11,12,13,14 1 中午 东7-412 软件工程071 13,14,15,16 1 中午 东7-413 计算机063 7,9,11,12,14,16,17 1 中午 东8-405 计算机应用082 4,5,6,7,8,9,10,11,12,13,14,15,16,17 1 中午 东8-409 艺术设计084 13,15 1 5-6 东7-405 计算机061 10,12,14,16 1 5-7 东7-405 电信科学082 7,8,9,10,11,12,13,14,15,16 1 5-6 东7-406 计算机053 13,14,15,16 1 5-6 东7-408 艺术设计084 7,8,9,10,11,12 1 5-6 东7-408 信息与计算081 8,9,10,11,12,13,14,15 1 5-6 东7-412 艺术设计084 16 1 5-6 东7-412 信息管理052 13,14,15,16,17,18 1 5-6 东7-413 艺术设计081 7,8,9,10,11,12,13,14,15,16 1 5-6 东8-405 国际贸易081 7,8,9,10,11,12,13,14,15,16 1 5-6 东8-409 信管062 11,12,15,17,18 1 7-8 东7-406 电信科学081 13,14 1 7-8 东7-406 电信科学081 15,16 1 7-8 东7-408 信息与计算科学062 11,12,13,14 1 7-8 东7-408 艺术设计083 7,8,9,10,11,12,13,14,15,16 1 7-8 东7-412 软件工程072 13,14,15,16 1 7-8 东7-413 电信科学081 7,8,9,10,11,12 1 7-8 东7-413 艺术设计082 7,8,9,10,11,12,13,14,15,16 1 7-8 东8-405 金融学081 7,8,9,10,11,12,13,14,15,16 1 7-8 东8-409 信管051 18 2 1-2 东7-405 计算机应用081 17 2 1-2 东7-408 计算机应用081 5,6,7,8,9,10,11,12,13,14,15,16 2 1-2 东7-412 计科052 4,6,8,10,12,14,16,18 2 1-2 东7-413 计算机051 14,15 2 1-2 东8-405 计算机科学081 8,9,10,11,12,13,14,15 2 1-2 东8-409 计算机应用082 5,6,7,8,9,10,11,12,13,14,15,16,17 2 3-4 东7-405 计算机061 17 2 3-4 东7-406 网络工程081 8,9,10,11,12,13,14,15 2 3-4 东7-406 软件工程061 14,15,16 2 3-4 东7-408 计科051 17 2 3-4 东7-408 计科051 14,15,16 2 3-4 东7-412 计科051 8,9,11,12,13 2 3-4 东7-413 计算机052 14,15 2 3-4 东7-413 计算机061 7,9,11,12,14,16 2 3-4 东8-405 计科(成)6,8,10,12,14 2 3-4 东8-409 信管052 18 2 中午 东7-405 软件工程062 14,15,16 2 中午 东7-412 信管051 5,6,8,10,12,13,14,15,16 2 5-6 东7-405 信息管理061 8,9,10,11,12,13,14,15 2 5-6 东7-406 软件工程072 18 2 5-6 东7-406 软件工程072 11,12,13,14,15 2 5-6 东7-408 信管051 17 2 5-6 东7-413 计科052 8,9,11,12,13 2 5-6 东7-413 信息管理082 8,9,10,11,12,13,14,15 2 5-6 东8-405 管理类0807 7,8,9,10,11,12,13,14,15,16 2 5-6 东8-409 信管052 5,6,8,10,12,13,14,15,16 2 7-8 东7-405 信息管理062 8,9,10,11,12,13,14,15 2 7-8 东7-406 信管052 17 2 7-8 东7-413 计科053 8,9,11,12,13 2 7-8 东7-413 电气类0806 8,9,10,11,12,13,14,15 2 7-8 东8-405 艺术设计086 7,8,9,10,11,12,13,14,15,16 2 7-8 东8-409 公选 6,7,8,9,10,11,12 2 9-11 东7-408/12 信息管理051 8,9,14,15,16 3 1-2 东7-405 信息管理061 11,16 3 1-2 东7-408 软件工程061 6,9,13,14 3 1-2 东7-408 信息管理062 11,16 3 1-2 东7-412 软件工程062 6,9,13,14 3 1-2 东7-412 计科053 4,6,8,10,12,14,16,18 3 1-2 东7-413 广告051 3,7 3 1-2 东7-413 广告学082 7,8,9,10,11,12,13,14,15,16 3 1-2 东8-409 信管052 10,11,13,16,18 3 3-4 东7-405 计算机071 18 3 3-4 东7-406 计算机071 11,12,13,14,15 3 3-4 东7-408 计科052 17 3 3-4 东7-408 计科052 14,15,16 3 3-4 东7-412 广告052 3,7 3 3-4 东7-413 信息管理072 17 3 3-4 东7-413 计算机053 14,15 3 3-4 东8-405 信息管理071 15,16,17 3 中午 东7-405 信管051 18 3 中午 东7-405 汉语言061 5,7,11,13,15 3 中午 东7-406 网络工程071 11,12,13,14,15,18 3 中午 东7-408 计算机063 10,11,12,13,14 3 中午 东7-409 计算机061 13,15,17 3 中午 东7-412 计算机063 15,16,17 3 中午 东7-413 软件工程061 4,6,8,10,12,14,15,16 3 中午 东8-405 软件工程082 8,9,10,11,12,13,14,15 3 中午 东8-409 信管051 10,11,13,16 3 5-6 东7-405 行政管理071 5,7,11,13,15 3 5-6 东7-406 信息管理052 7,8 3 5-6 东7-413 行政管理061 10,11,12,13 3 5-7 东7-413 信息管理072 15,16,17 3 5-7 东7-413 电气类0807 8,9,10,11,12,13,14,15 3 5-6 东8-405 行政管理081 7,8,9,10,11,12,13,14,15,16 3 5-6 东8-409 计算机062 17 3 6-8 东7-408 计算机062 13,15 3 6-8 东7-412 汉语言062 5,7,11,13,15 3 7-8 东7-406 软件工程062 4,6,8,10,12,14,15,16 3 7-8 东7-408 信息管理052 7,8,9 3 7-8 东7-413 行政管理062 10,11,12,13 3 8-10 东7-413 校公选 7,8,9,10,11,12 3 9-11 东7-408/12 计算机063 13,15,17 3 9-11 东7-412 软件工程061 6,7,8,9,10,11,12,13 4 1-2 东7-405 信息管理072 17,18 4 1-2 东7-405 计算机061 10,11,12,13,14 4 1-2 东7-409 信息管理072 4,7,11,13,15 4 1-2 东7-412 计算机061 15,16,17 4 1-2 东7-413 信息管理081 8,9,10,11,12,13,14,15 4 1-2 东8-405 电气类083 8,9,10,11,12,13,14,15 4 1-2 东8-409 网络工程092 8,9,11,12 2 5-6 东8-415 实验题 编译整数四则运算表达式，将整数四则运算表达式翻译为汇编语言代码。
整数四则运算文法：
词法：
1． 运算符：+-* / 2． 界符：()3． num是非负整数。
4． 空白包括空格、换行符和水平制表符。用来分开运算符、界符和num。也可以不包括换行符，这时换行符就成为表达式的终结标志。
实验1 词法分析（2课时）
实验目的：了解词法分析器的功能和输出形式，掌握词法分析器设计原理和方法。
实验内容：设计并实现整数四则运算表达式的词法分析程序。
实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。
实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。
实现要点与提示：
需要实现的词法分析程序的功能是，接受一个表达式，输出该表达式中的各类单词符号。测试词法分析程序时，可以按照一定格式输出各类单词符号。
单词符号的种类和所属类型可定义如下 typedef enum Symbol { ERR =-1, END, NUM, PLUS, MINUS, TIMES, SLASH, LPAREN, RPAREN } Symbol;对运算符和界符只需处理种类编码即可，而对num需要处理其对应的具体属性信息。ERR表示词法分析错，END表示表达式分析结束。例如1+2*(3+4)所对应的单词符号序列为 NUM: 1 + NUM: 2 *(NUM: 3 + NUM: 4)词法分析函数的原型如下 Symbol gettoken();实现的具体方法可参考文献[1]中44-46页。这里不涉及Reserve、InsertId和InsertConst。在实现过程中可能会用到isdigit、isspace、getchar、ungetc、atoi等函数，使用时注意包含相关头文件。
状态转换图如下 实验2 语法分析（2课时）
实验目的：理解自上而下分析法的基本思想，理解递归下降分析法的基本思路，掌握构造递归下降子程序的方法。
实验内容：运用递归下降子程序法，实现整数四则运算表达式的语法分析程序。
实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。
实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。
实现要点与提示：
需要实现的语法分析程序的功能是，接受一个表达式，分析该表达式，并根据输入正确与否给出相应信息。测试时，如果输入的表达式分析正确，则输出表示分析正确的信息；
否则，输出表示分析错误的信息。
分析程序由一组递归过程组成，文法中每个非终结符对应一个过程。在分析过程中，语法分析程序需要调用实验1所实现的词法分析程序。
几个全局过程和变量：
ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号。
SYM，IP当前所指的输入符号。
ERROR，出错处理子程序。
每个非终结符有对应的子程序的定义，在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。
例：给定文法G(E)：
E→TE＇ E＇→+TE＇ |ε T→FT＇ T＇→*FT＇ |ε F→(E)| i 对应的递归子程序为 PROCEDURE E;BEGIN T;E＇ END;PROCEDURE E＇;IF SYM=‘+’ THEN BEGIN ADVANCE;T;E＇ END;PROCEDURE T;BEGIN F;T＇¢ END;PROCEDURE T＇;IF SYM=‘*’ THEN BEGIN ADVANCE;F;T＇¢ END;PROCEDURE F;IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE;E；
IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR;主程序为：
PROGRAM PARSER;BEGIN ADVANCE;E;IF SYM <>’#’ THEN ERROR END.或者对应的递归子程序为：
PROCEDURE E;BEGIN T;E＇ END;PROCEDURE T;BEGIN F;T＇ END;PROCEDURE E＇;IF SYM=‘+’ THEN BEGIN ADVANCE;T;E＇ END ELSE IF SYM<>‘#’ AND SYM<>’)’ THEN ERROR;PROCEDURE T＇;IF SYM=‘*’ THEN BEGIN ADVANCE;F;T¢ END ELSE IF SYM<>‘#’ AND SYM<>’)’AND SYM<>’+’ THEN ERROR;PROCEDURE F;IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE;E;IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR 主程序为：
PROGRAM PARSER;BEGIN ADVANCE;E END;具体实现语法分析程序时，ADVANCE的功能由实验1中的gettoken实现。程序中可设置一个全局变量nexttoken，与SYM对应，保存调用gettoken时的返回结果。ERROR的一种简单实现是输出错误提示，然后调用exit，使程序立即终止执行。
实现整数四则运算表达式的语法分析程序时，可在上面例子的基础上修改扩充。
实验3 语义分析（2课时）
实验目的：理解属性文法，理解语法制导翻译的基本思想和方法。
实验内容：设计并实现实现整数四则运算的递归下降翻译器。
实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。
实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。
实现要点与提示：
需要实现的语义分析程序的功能是，接受一个表达式，分析该表达式，并在分析的过程中建立该表达式的抽象语法树。由于四则运算表达式的抽象语法树可基本上看作是二叉树，因此中序遍历序列应该和输入的表达式一样——除了没有括号之外。可输出中序遍历序列检测程序功能是否正确。如果每个分支节点用一个临时变量标记，则对四则运算表达式的抽象语法树进行后序遍历，可以得到输入表达式所对应的四元式序列（实验4要用到这样的四元式序列）。例如输入1+2*(3+4)，对应的抽象语法树的中序遍历序列、四元式序列分别为 1 + 2 * 3 + 4 和 + 3 4 T1 * 2 T1 T2 + 1 T2 T3 抽象语法树的一种类型定义为 typedef int ValType;typedef struct ASTNode { Symbol sym;ValType val;struct ASTNode * arg1, *arg2;} ASTNode, *AST;创建节点的操作为 ASTNode *mknode(Symbol op, ASTNode *arg1, ASTNode *arg2);返回新创建的一个运算节点，标号是op，域arg1和arg2分别指向一棵子树。
ASTNode *mkleaf(Symbol sym, ValType val);返回新创建的一个数节点，标号为num，域val用于存放数的值。
建立抽象语法树的语义规则为 E ::= E1 + T E.nptr := mknode(‘+’, E1.nptr, T.nptr)E ::= E1 – T E.nptr := mknode(‘-’, E1.nptr, T.nptr)E ::= T E.nptr := T.nptr T ::= T1 * F T.nptr := mknode(‘*’, T1.nptr, F.nptr)T ::= T1 / F T.nptr := mknode(‘/’, T1.nptr, F.nptr)T ::= F T.nptr := F.nptr F ::=(E)F.nptr := E.nptr F ::= num F.nptr := mkleaf(num, num.val)消除左递归的翻译模式为 E ::= T {E＇.i:=T.nptr} E＇ {E.nptr:=E＇.s} E＇::= + T {E＇1.i:=mknode(‘+’,E＇.i,T.nptr)} E＇1 {E＇.s:=E1.s} E＇::=-T {E＇1.i:=mknode(‘-’,E＇.i,T.nptr)} E＇1 {E＇.s:=E1.s} E＇::= ε {E＇.s:= E＇.i} T ::= F {T＇.i:=F.nptr} T＇ {T.nptr:=T＇.s} T＇::= * F {T＇1.i:=mknode(‘*’,T＇.i,F.nptr)} T＇1 {T＇.s:=T1.s} T＇::= / F {T＇1.i:=mknode(‘/’,T＇.i,F.nptr)} T＇1 {T＇.s:=T1.s} T＇ ::= ε {T＇.s:= T＇.i} F ::=(E){F.nptr:=E.nptr} F ::= num {F.nptr:=mkleaf(num,num.val)} 递归下降翻译器的设计可参考文献[1]中156-158页。具体实现时，可以以实验2中所实现的语法分析程序为基础进行修改，实现表达式的递归下降翻译器。
实验4 代码生成（2课时）
实验目的：理解代码生成过程中的基本问题。
实验内容：设计并实现表达式的代码生成程序。
实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。
实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。
实现要点与提示：
需要代码生成程序的功能是，以实验3的语义分析程序的四元式输出作为输入，输出汇编语言程序。例如1+2*(3+4)对应的输出为.386.MODEL FLAT ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD INCLUDE io.h;header file for input/output cr EQU 0dh;carriage return character Lf EQU 0ah;line feed.STACK 4096;reserve 4096-byte stack.DATA;reserve storage for data t DWORD 40 DUP(?)label1 BYTE cr, Lf, “The result is “ result BYTE 11 DUP(?)BYTE cr, Lf, 0.CODE;start of main program code _start: mov eax, 3 add eax, 4 mov t+0, eax mov eax, 2 mov ebx, t+0 mul ebx mov t+4, eax mov eax, 1 add eax, t+4 mov t+8, eax mov eax, t+8 dtoa result, eax;convert to ASCII characters output label1;output label and sum INVOKE ExitProcess, 0;exit with return code 0 PUBLIC _start;make entry point public END;end of source code 输出的汇编代码借鉴了文献[2]中的格式。假定将上面的汇编程序保存到文expression.asm中，将expression.asm复制到汇编器所在目录。然后在命令提示符下，在汇编器所在目录依次执行 ml /c /coff expression.asm link /debug /subsystem:console /entry:start /out: expression.exe expression.obj io.obj kernel32.lib expression 就会得到 The result is 15 注意，上面link那一行应该连续输入。为方便起见，在汇编器所在目录下有一个批处理文件compile.bat。执行 compile expression 可完成上面三步所能完成的任务。
所生成的汇编代码中 t DWORD 40 DUP(?)定义了40个双字（占4字节大小），用作临时变量，可根据需要调整大小。更好的方法是在栈中分配临时变量。
生成代码时，只需考虑如何生成_start:和dtoa result, eax之间的汇编码。开头到_start:部分和dtoa result, eax到结尾部分的汇编码可以按所给的例子原样输出。
通过分析、对比1+2*(3+4)的四元式序列和汇编码的对应关系，考虑如何将四元式翻译为汇编码。需要特别注意寻址方式问题，乘法和除法的翻译。
所给汇编程序例子中各个成分的含义，可以参考文献[2]。目录中有文献[2]的英文版电子书。
参考书目 [1] 陈火旺等.程序设计语言编译原理（第3版）.北京：国防工业出版社，2009.1 [2] Richard C.Detmer.80x86汇编语言与计算机体系结构（英文版）.北京：机械工业出版社，2004.11
