《《编译原理》实验指导书——2012.doc》由会员分享，可在线阅读，更多相关《《编译原理》实验指导书——2012.doc（24页珍藏版）》请在金锄头文库上搜索。
1、编译原理实验指导书太原科技大学计算机学院 2006-3-1序编译原理是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计和算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。为了配合编译原
2、理课程的教学，考虑到本课程的内容和特点，本指导书设置了七个综合性实验，分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化，以支持编译程序的各个阶段，基本涵盖了编译原理课程的主要内容。本指导书可作为编译原理课程的实验或课程设计内容，在课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C+的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。目 录实验一 词法分析实验二 NFA的确定化实
3、验三 非递归预测分析实验四 算符优先分析器的构造实验五 LR分析实验六 语义分析和中间代码生成实验七 基于DAG的基本块优化解决党委自身和基层党支部存在的的突出问题，发挥各村、社区、机关单位党支部在当前城市征迁、园区建设、招商引资、服务群众、维护稳定的作用，我镇党委高度重视，制定了切合临淮实际的活动实施方案，按照中央规定的活动步骤和要求扎实有效的开展了基层组织建设年活动。III实验一 词法分析1 实验目的与任务对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状态转换图设计词法分析器的基本方法。2实验要求利用该词法分析器完成对源程序字符串的词法分析。输出形式是源程序的单词符号二元式的代
4、码，并保存到文件中。3实验内容(1) 假设该语言中的单词符号及种别编码如下表所示。单词符号及种别编码单词符号种别编码单词符号种别编码Main128Int229Char330If431Else5,32For6:33While7；34标识符ID1035整型常数NUM2036=2137+2238-2339*24！40/25&41(26&42)27|43(2) 关键字main int char if else for while都是小写并都是保留字。算符和界符：= + * / & ! & | , : ; ( )ID和NUM的正规定义式为：IDletter(letter | didit)*NUMdigi
5、t digit*lettera | | z | A | | Zdigit 0 | | 9如果关键字、标识符和常数之间没有确定的算符或界符作间隔，则至少用一个空格作间隔。空格由空白、制表符和换行符组成。(3) 设计词法分析器的步骤： 首先根据上面单词符号表及ID和NUM的正规定义式，构造出状态转换图； 定义相关的变量和数据结构。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：char *KEY_WORDS8=main,int,char,if,e
6、lse,for,while；用以存放单词符号二元式的数据结构可如下定义：#define MAXLENGTH 255 /* 一行允许的字符个数 */ union WORDCONTENT /* 存放单词符号的内容 */ char T1MAXLENGTH; /* 存放标识符 */ int T2; /* 存放整型常数的拼数 */ char T3; /* 存放其他符号 */;typedef struct WORD /* 单词符号二元式 */ int code; /* 存放种别编码 */ union WORDCONTENT value; WORD; 按照编译程序一遍扫描的要求，把词法分析器Scaner作为
7、一个独立的子程序来设计，通过对Scaner的反复调用识别出所有的单词符号； 当Scaner识别出一个单词符号时，则将该单词符号的二元式写入到输出文件中。若Scaner无法识别出一个单词符号时，则调用错误处理程序PrintError，显示当前扫描到的字符及其所在行、列位置，并跳过该字符重新开始识别单词符号。(4) 测试该设计词法分析器，可对下面的源程序进行词法分析： main() int i = 10;while(i) i = i - 1; 输出如下二元式代码序列：(1,main) (26,() (27,) (30,） (2,int) (10,i) (21,=) (20,10) (34,;) (
8、7,while) (26,( ) (10,i) (27,) (10,i) (21, =) (10,i) (23,-) (20,1) (34,;) (31,)实验二 NFA的确定化1实验目的与任务设计并实现将NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。2实验要求设计并实现计算状态集合I的闭包的算法_Closure(I)和转换函数Move(I,a)，并在此基础上实现子集构造算法Subset_Construction。利用该从NFA到DFA的转换程序Subset_Construction，任意输入一个N
9、FA N=（S,s0,F），输出一个接收同一语言的DFA M=（S,s0,F）。3实验内容(1) 令I是NFA N的状态集S的一个子集，I的闭包的_Closure(I)构造规则如下：(a) 若sI，则s_Closure(I)；(b) 若sI，则_Closure(s)_Closure(I)根据上面的规则，下面给出了一个计算I的闭包的算法_Closure(I)。SET S;SET_Closure(input)SET *input;S=input; /* 初始化 */push(); /* 把输入状态集中的全部状态压入栈中 */while(栈非空)Nfa_state i;pop(); /* 把栈顶元素
10、弹出并送入i */if(存在(i, )=j)if(j不在S中) 把i加到S中;把j压入栈中;return S; /* 返回_Closure(input)集合 */完成上述算法的设计。(2) 令I是NFA N的状态集S的一个子集，a, 转换函数Move(I,a)定义为：Move(I,a)= _Closure(J)其中，J=s|sI且(s,a)=s转换函数Move(I,a)的设计通过调用_Closure(input)实现，完成该函数的设计。(3) 从NFA N构造一个与其等价的DFA M的子集构造算法，就是要为DFA M构造状态转换表Trans，表中的每个状态是NFA N状态的集合，DFA M将“
11、并行”地模拟NFA N面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Construction的框架，请完成其设计过程。有关数据结构：States：是一个M的数组，每个状态有两个域，set域存放N的状态集合，flg域为一标识。Trans：是M的转移矩阵（输入字母表元素个数最大状态数），Transia=下一状态。I：M的当前状态号a：输入符号，aNstates：M的下一新状态号S：定义M的一个状态的N的状态集初始化：tates0.set=_Closure(N的初态)States0.flg=FALSENstates=1i=0S=Trans初始化为无状态-while(Statesi
12、的flg为FALSE)Statesi.flg=TRUE;for(每个输入符号a)S=_Closure(Move(Statesi.set,a);if(S非空)if(States中没有set域等于 S的状态)StatesNstates.set=S;StatesNstates.flg=FALSE;Transia= Nstates+;else Transia= States中一个set域为S的下标;此算法的输出M主要由Trans矩阵描述，其中省略了每个状态是否为终态的描述，应加以完善。(4) 测试用例对下图所示的NFA N用子集构造算法Subset_Construction确定化。eDDD.D013131264578291011181415161917NFA N的初态为12，DFA M的初态为_Closure(12)。整个转换过程可用下表来概括。DFA状态NFA状态_ClosureMove(D) Move(.) Move(e)终态NFADFANFADFANFADFA012345121,581510160,2,4,6,120,1,3,4,5,7,13,14,18,198,9159,10,11,13,14,18,1915,16,17,191,51,5101610161145458-2-
