《编译原理》实验指导书2012

《编译原理》实验指导书太原科技大学计算机学院2006-3-1II序《编译原理》是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计和算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。为了配合《编译原理》课程的教学，考虑到本课程的内容和特点，本指导书设置了七个综合性实验，分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化，以支持编译程序的各个阶段，基本涵盖了《编译原理》课程的主要内容。本指导书可作为《编译原理》课程的实验或课程设计内容，在课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C++的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。III目录实验一词法分析...........................................................................................................................１实验二NFA的确定化..................................................................................................................３实验三非递归预测分析...............................................................................................................６实验四算符优先分析器的构造.............................................................................................１０实验五LR分析........................................................................................................................１２实验六语义分析和中间代码生成...........................................................................................１７实验七基于DAG的基本块优化............................................................................................１９１实验一词法分析1．实验目的与任务对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状态转换图设计词法分析器的基本方法。2．实验要求利用该词法分析器完成对源程序字符串的词法分析。输出形式是源程序的单词符号二元式的代码，并保存到文件中。3．实验内容(1)假设该语言中的单词符号及种别编码如下表所示。单词符号及种别编码单词符号种别编码单词符号种别编码Main1[28Int2]29Char3{30If4}31Else5,32For6:33While7；34标识符ID10＞35整型常数NUM20＜36=21＞＝37+22＜＝38-23＝＝39*24！＝40/25&41(26&&42)27||43(2)关键字mainintcharifelseforwhile都是小写并都是保留字。算符和界符：=+－*/&＜＜＝＞＞＝＝＝!＝&&||,:;{}[]()ID和NUM的正规定义式为：ID→letter(letter|didit)*NUM→digitdigit*letter→a|…|z|A|…|Zdigit→0|…|9如果关键字、标识符和常数之间没有确定的算符或界符作间隔，则至少用一个空格作间隔。空格由空白、制表符和换行符组成。(3)设计词法分析器的步骤：①首先根据上面单词符号表及ID和NUM的正规定义式，构造出状态转换图；②定义相关的变量和数据结构。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能２查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：char*KEY_WORDS[8]={″main″,″int″,″char″,″if″,″else″,″for″,″while″}；用以存放单词符号二元式的数据结构可如下定义：#defineMAXLENGTH255/*一行允许的字符个数*/unionWORDCONTENT{/*存放单词符号的内容*/charT1[MAXLENGTH];/*存放标识符*/intT2;/*存放整型常数的拼数*/charT3;/*存放其他符号*/};typedefstructWORD{/*单词符号二元式*/intcode;/*存放种别编码*/unionWORDCONTENTvalue;}WORD;③按照编译程序一遍扫描的要求，把词法分析器Scaner作为一个独立的子程序来设计，通过对Scaner的反复调用识别出所有的单词符号；④当Scaner识别出一个单词符号时，则将该单词符号的二元式写入到输出文件中。若Scaner无法识别出一个单词符号时，则调用错误处理程序PrintError，显示当前扫描到的字符及其所在行、列位置，并跳过该字符重新开始识别单词符号。(4)测试该设计词法分析器，可对下面的源程序进行词法分析：main(){inti=10;while(i)i=i-1;}输出如下二元式代码序列：(1,main)(26,()(27,))(30,{）(2,int)(10,i)(21,=)(20,10)(34,;)(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，任意输入一个NFAN=（S,Σ,δ,s0,F），输出一个接收同一语言的DFAM=（S’,Σ,δ’,s0’,F’）。3．实验内容(1)令I是NFAN的状态集S的一个子集，I的ε闭包的ε_Closure(I)构造规则如下：(a)若s∈I，则s∈ε_Closure(I)；(b)若s∈I，则ε_Closure({s})∈ε_Closure(I)根据上面的规则，下面给出了一个计算I的ε闭包的算法ε_Closure(I)。SETS;SETε_Closure(input)SET*input;{S=input;/*初始化*/push();/*把输入状态集中的全部状态压入栈中*/while(栈非空){Nfa_statei;pop();/*把栈顶元素弹出并送入i*/if(存在δ(i,ε)=j)if(j不在S中){把i加到S中;把j压入栈中;}}returnS;/*返回ε_Closure(input)集合*/}完成上述算法的设计。(2)令I是NFAN的状态集S的一个子集，a∈Σ,转换函数Move(I,a)定义为：Move(I,a)=ε_Closure(J)其中，J={s’|s∈I且δ(s,a)=s’}转换函数Move(I,a)的设计通过调用ε_Closure(input)实现，完成该函数的设计。(3)从NFAN构造一个与其等价的DFAM的子集构造算法，就是要为DFAM构造状态转换表Trans，表中的每个状态是NFAN状态的集合，DFAM将“并行”地模拟NFAN面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Construction的框架，请完成其设计过程。４有关数据结构：States[]：是一个M的数组，每个状态有两个域，set域存放N的状态集合，flg域为一标识。Trans[]：是M的转移矩阵（输入字母表Σ元素个数×最大状态数），Trans[i][a]=下一状态。I：M的当前状态号a：输入符号，a∈ΣNstates[]：M的下一新状态号S：定义M的一个状态的N的状态集初始化：tates[0].set=ε_Closure({N的初态})States[0].flg=FALSENstates=1i=0S=ФTrans初始化为无状态’-’while(States[i]的flg为FALSE){States[i].flg=TRUE;for(每个输入符号a∈Σ){S=ε_Closure(Move(States[i].set,a));if(S非空)if(States中没有set域等于S的状态){States[Nstates].set=S;States[Nstates].flg=FALSE;Trans[i][a]=Nstates++;}elseTrans[i][a]=States中一个set域为S的下标;}}此算法的输出M主要由Trans矩阵描述，其中省略了每个状态是否为终态的描述，应加以完善。(4)测试用例对下图所示的NFAN用子集构造算法Subset_Construction确定化。５NFAN的初态为12，DFAM的初态为ε_Closure({12})。整个转换过程可用下表来概括。DFA状态NFA状态ε_ClosureMove(’D’)Move(’.’)Move(’e’)终态NFADFANFADFANFADFA012345{12}{1,5}{8}{15}{10}{16}{0,2,4,6,12}{0,1,3,4,5,7,13,14,18,19}{8,9}{15}{9,10,11,13,14,18,19}{15,16,17,19}{1,5}{1,5}{10}{16}{10}{16}114545Φ{8}ΦΦΦΦ-2----Φ{15}ΦΦ{15}Φ-3--3-否是否否是是DFAM的状态转换图如下。εeεεεDεεεεεεεDDε.εDεεεεε013131264578291011181415161917DDeD.DDeD025314６实验三非递归预测分析1．实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。2．实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。3．实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1．程序→表达式；2．|表达式；程序3．表达式→表达式+项4．|项5．项→项*因式6．|因式7．因式→num_or_id8．|(表达式)将该语言的文法转换为如下的LL(1)文法：1prgm→expr;prgm’8term→factorterm’2prgm’→prgm9term’→*factorterm’3prg