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

编译原理实验指导书太原科技大学计算机学院 2006-3-1序编译原理是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计和算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。为了配合编译原理课程的教学，考虑到本课程的内容和特点，本指导书设置了七个综合性实验，分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化，以支持编译程序的各个阶段，基本涵盖了编译原理课程的主要内容。本指导书可作为编译原理课程的实验或课程设计内容，在课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C+的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。目 录实验一 词法分析实验二 NFA的确定化实验三 非递归预测分析实验四 算符优先分析器的构造实验五 LR分析实验六 语义分析和中间代码生成实验七 基于DAG的基本块优化III实验一 词法分析1 实验目的与任务对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状态转换图设计词法分析器的基本方法。2实验要求利用该词法分析器完成对源程序字符串的词法分析。输出形式是源程序的单词符号二元式的代码，并保存到文件中。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)*NUMdigit digit*lettera | | z | A | | Zdigit 0 | | 9如果关键字、标识符和常数之间没有确定的算符或界符作间隔，则至少用一个空格作间隔。空格由空白、制表符和换行符组成。(3) 设计词法分析器的步骤： 首先根据上面单词符号表及ID和NUM的正规定义式，构造出状态转换图； 定义相关的变量和数据结构。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：char *KEY_WORDS8=main,int,char,if,else,for,while；用以存放单词符号二元式的数据结构可如下定义：#define MAXLENGTH 255 /* 一行允许的字符个数 */ union WORDCONTENT /* 存放单词符号的内容 */ char T1MAXLENGTH; /* 存放标识符 */ int T2; /* 存放整型常数的拼数 */ char T3; /* 存放其他符号 */;typedef struct WORD /* 单词符号二元式 */ int code; /* 存放种别编码 */ union WORDCONTENT value; WORD; 按照编译程序一遍扫描的要求，把词法分析器Scaner作为一个独立的子程序来设计，通过对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,;) (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，任意输入一个NFA 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(); /* 把栈顶元素弹出并送入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将“并行”地模拟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的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-1515-3-3-否是否否是是DDeD.DDeD025314DFA M的状态转换图如下。实验三 非递归预测分析1实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。2实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。3实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1 程序 表达式；2 |表达式；程序3 表达式 表达式 + 项4 |项5 项 项 * 因式6 |因式7 因式 num_or_id8 |(表达式)将该语言的文法转换为如下的LL(1)文法：1 prgm expr;prgm 8 term factor term2 prgm prgm 9 term *factor term 3 prgm 10 term 4 expr term expr 11 factor (expr) 5 expr 12 factor num6 expr +term expr 13 system_goal prgm7 expr 该LL(1)文法的LL(1)分析表如下： TNNum+*();#prgm111prgm2223expr4455expr677term88term1091010factor1211system_goal131313对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注（Num+);*#4625130终结符（#为输入结束标志）Exprexprtermtermfactorprgmprgmsystem_goal258260259262261256257263非终结符（2）文法及其LL(1)分析表的数据结构文法的产生式可用数组Yy_pushtab存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。数组Yy_d的具体内容及表示如下：0 1 2 3 4 5 6# ； + * （ ） Num-10-1-10-1021-1-11-11-14-1-1343-1-1-1-17-17-165-1-16-1-1-1-1-110-111-1998-19-1-112-1-112-112prgm 256 prgm 257 expr 258 term 259 expr 260factor 261term 262system_goal 263数组Yy_pushtab的具体内容及表示如下：257,1,258,0prgm ; expr256,0prgm0260,259,0expr term0260,259,2,0expr term +0262,261,0term factor262,261,2,0term factor *5,258,4,0) expr (06,0Num256,0prgm0123456789101112Yyp00Yyp01Yyp02Yyp03Yyp04Yyp05Yyp06Yyp07Yyp08Yyp09Yyp10Yyp11Yyp12（3）预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：初始化；/* 把开始符号的常数值压入分析站，输入指向第一个输入符号 */while(分析栈非空) if(栈顶常数表示一个终结符)if(该常数与输入符号的常数不等)报语法错；else 把一个数从栈顶弹出；advance读下一输入符号；else /* 栈顶的常数表示一个非终结符 */what_to_do=Yy_d栈顶常数当前输入符号的常数；if(what_to_do= -1)报语法错；else 把栈顶元素弹出栈；把Yy_pushtabwhat_to_do中列出的全部常数压入分析栈；请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。（4）用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。综合分析过程可用下表表示。栈（符号）栈（数值）输入串What_to_dosystem_goalprgmprgm ; exprprgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr termprgm ; expr prgm ; expr term +prgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr term prgm ; expr prgm ; prgm 263256257 1 258257 1 260 259257 1 260 262 261257 1 260 262 6257 1 260 262 257 1 260 257 1 260 259 2257 1 260 259 257 1 260 262 261257 1 260 262 6257 1 260 262257 1 260 257 1 260 262257 1+2；#1+2；#1+2；#1+2；#1+2；#1+2；#+2；#+2；#+2；#2；#2；#2；#；#；#；#120371195711962（5）请考虑如何设计并实现LL(1)分析表的自动生成程序。实验四 算符优先分析器的构造1. 实验目的与任务（1）理解自底向上的语法分析的基本思想。（2）理解算符优先文法的概念。（3）掌握算符分析表和优先函数的构造。（4）掌握算符优先分析器的工作原理和工作流程。2. 实验原理算符优先分析法是一种简单、直观、广为使用的语法分析方法，这种方法特别适用于程序设计语言中的表达式的分析。算符优先分析法就是仿照算术表达式的运算过程而提出的一种自底向上的语法分析方法，它可以分析算符优先文法，分析的基本思想是：根据文法终结符之间的优先关系，通过比较相邻算符的优先次序来确定句型中的最左素短语，并进行归约。所谓的算符优先文法是指：对算符文法中任意两个终结符对a、b之间至多有一种优先关系成立的文法，而算符文法G中的任何一个产生式中都不包含两个非终结符相邻的情况。对于满足这样条件的文法，我们就可以用算符优先分析法对其进行分析。确定了符合要求的文法之后，自底向上的分析方法的关键就是如何在当前句型中寻找可归约的子串，算符优先分析法在归约过程中，通过终结符之间的优先关系确定当前的句型中的最左素短语，与非终结符无关，只需知道把当前句型中的最左素短语归约为一非终结符，不必知道该非终结符的名字是什么，这样也就去掉了单非终结符的归约，一旦找到最左素短语，就将它归约成一个非终结符。在算符优先分析法分析过程中，可以设置一个栈S，用来存放归约或者待形成最左素短语的符号串，用一个工作单元a存放当前读入的输入字符，归约成功的标志是当读入的输入字符是句子的结束符号#时，栈S中只剩下#N。3. 实验内容给定一个上下文无关文法G：const，var01 ,:integer;var01 ,:real;var01 ,:boolean;begin ;beginend; end.:=+-+-*/（）if then else (andor) while ()(andor) () do =abcz ABCZ0129编写程序，构造上述文法G的算符优先分析器，使其能实现如下功能：（1）扫描单词的内部表示形式，按语言的语法规则识别出语法单位（语句等）；（2）对各语法单位进行语法检查；（3）若发现单词的组成有错误时，输出有关的出错信息。实验五 LR分析1实验目的与任务设计一个LR分析器，实现对表达式语言的分析，加深对LR语法分析方法的基本思想的理解，掌握LR分析器设计与实现的基本方法。2实验要求建立文法及其LR分析表表示的数据结构，设计并实现一个LALR(1)的分析器，对源程序经词法分析后生成的二元式代码流进行分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。3实验内容（1）文法描述及其LALR(1)分析表描述表达式语言的文法G如下：0. S E1. E E+T2. E T3. T T*F4. T F5. F (E)6. F ID该文法的LALR(1)分析表如下：分析表状态动作Action表（Yy_action）转移Goto表（Yy_goto）#ID+*()SETF0-S1-S2-3451R6-R6R6-R6-2-S1-S2-6453A-S7-4R2-R2S8-R2-5R4-R4R4-R4-6-S7-S9-7-S1-S2-1058-S1-S2-119R5-R5R5-R5-10R1-R1S8-R1-11R3-R3R3-R3- SN = 移进并转移到状态N A = accept接受RN = 按第N条产生式进行规约 - = error转移（2）LR分析器总控程序框架如下：push(0);advance();while(Actiontossym!=accept)if(Actiontossym=-) error();else if (Actiontossym=SN)push(N);advance();else if（Actiontossym=RNact(N);pop(产生式N的右部的符号个数);push(Goto新tos产生式N的左部符号)；accept();上述算法中的有关函数与符号的意义如下：accept()：返回成功状态，LR分析器停止工作；act(N)：执行利用产生式N的归约的动作，通常为产生代码；advance()：丛输入流读下一单词到sym；error()：出错处理；pop(N)：从栈顶弹出N个符号（状态）；push(N)：把状态N压入状态栈；sym：当前输入的单词符号；tos：栈顶状态号。（3）存放LR分析表的数据结构 实现方法一：用一个二维整数数组表示数组元素为表示动作的整数。数组的行下标为状态号，列下标用来表示终结符与非终结符的整数表示。数组元素可作如下约定：正整数：表示移进动作，如S6用数6表示；负整数：表示归约动作，如R5用数-5表示；0：表示接受，通常为按产生式0归约；状态号也用整数表示；用不可能是状态号的较大的整数表示错误转移。请将上述LALR(1)分析表用这种表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测试。 实现方法二：采用压缩表示法动作Action表的每一行用一个数组表示，数组的第一个元素是本数组中存放的数偶个数，第二个元素到最后一个元素都以终结符，动作的数偶的形式存放。再用一个以状态号为下标的下标数组，每个元素含一个指向数偶数组的指针。若数组元素的值为NULL，则表示从此状态无转移弧发出。若分析表有几行相同，则只需保存一行，其它元素则都指向存放这一行表的数组即可。转移Goto表也按同样方式组织，只是这个行数组的数偶为非终结符，下一状态号。每个行数组Yyan表示动作表Yy_action的一行，每个行数组Yygn表示转移表Yy_goto的一行。假定上述表达式文法G中终结符及非终结符的整数值为：终结符： # ID + * ( ) 非终结符： S E T F 整数值： 0 1 2 3 4 5 整数值： 0 1 2 3Yy_action数组是以状态号为下标的下标数组，每个元素含有指向数组Yyan的指针；下标数组Yy_goto的每个元素含有指向数组Yygn的指针。表达式文法G的LALR(1)分析表的具体压缩表示如下： Yy_action.024, 21, 1Yya000.145, -63, -62, -60, -6Yya001.2.320, 02, 7Yya003.445, -22, -20, -23, 8Yya004.545, -43, -42, -40, -4Yya005.625, 92, 7Yya006.7.8.945, -53, -52, -50, -5Yya009.1045, -12, -10, -13, 8Yya010.1145, -35, -32, -30, -3Yya011Yyg000.033, 52, 41, 3Yyg000NULL1.233, 52, 41, 6Yyg002NULL3NULL4NULL5NULL6.723, 52, 10Yyg007.813, 11Yyg008NULL9NULL10NULL11以上分析表用C语言程序描述如下：/* Yy_action表*/int Yya000=2,4,2,1,1;int Yya001=4,5,-6,3,-6,2,-6,0,-6;int Yya003=2,0,0,2,7;int Yya004=4,5,-2,2,-2,0,-2,3,8;int Yya005=4,5,-4,3,-4,2,-4,0,-4;int Yya006=2,5,9,2,7;int Yya009=4,5,-53,-5,2,-5,0,-5;int Yya010=4,5,-1,2,-1,0,-1,3,8;int Yya011=4,5,-3,3,-3,2,-3,0,-3;int Yy_action= Yya000, Yya001, Yya000, Yya003, Yya004, Yya005, Yya006, Yya000, Yya000, Yya009, Yya010, Yya011 ;/* Yy_goto表*/int Yyg000=3,3,5,2,4,1,3;int Yyg002=3,3,5,2,4,1,6;int Yyg007=2,3,5,2,10;int Yyg008=1,3,11;int Yy_goto=Yyg000, NULL, Yyg002, NULL, NULL, NULL,NULL, Yyg007, Yyg008, NULL, NULL, NULL;/* 为了进行归约，使用一个Yy_lhs数组，其值为代表产生式左部符号的* 整数，数组的下标为产生式号*/ int Yy_lhs7= /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2, /* 4 */ 2, /* 5 */ 3, /* 6 */ 3 ;/* Yy_reduce数组元素的值为产生式右部符号的个数，* 以产生式号为数组的下标索引*/int Yy_reduce=/* 0 */ 1,/* 1 */ 3,/* 2 */ 1,/* 3 */ 3,/* 4 */ 1,/* 5 */ 3,/* 6 */ 1;根据以上数组结构，构造函数Yy_next()，其功能是在给定状态和输入符号下，求出应采取的动作或转向的下一状态。int Yy_next(table,cur_state,symbol)int *table; /* 要查的表 */int cur_state; /* 行号 */int symbol; /* 列号 */int *p=tablecur_state;int i;if(p)for(i=(int)*p+ ; -i0 ; p+=2)if(symbol = = p0)return(p1);return YYF; /* 出错指示 */;指针p指向Yyan数组或Yygn数组，由参数table的值而定。如果table指向Yy_action，则p指向Yyan数组；若table指向Yy_goto，则p指向Yygn数组据。根据上述LALR(1)分析表压缩表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测试。实验六 语义分析和中间代码生成1实验目的与任务通过设计一个简单的语义分析和中间代码生成器，加深对语法制导翻译方法的理解，掌握将语法分析所识别的语法范畴变换为中间代码的语义翻译方法。2实验要求采用递归下降语法制导翻译方法，构造语义分析和中间代码生成器，实现对算术表达式、赋值语句、条件语句、循环语句进行语义分析，生成四元式中间代码的序列。3实验内容（1）待分析的语言为C语言的一个子集，其文法用扩充的BNF描述如下：程序 main( ) 语句块语名块 语句串语句串 语句 ；语句 ；语句 赋值语句 | 条件语句 | 循环语句赋值语句 ID = 表达式条件语句 if （条件）语句块 循环语句 while（条件）语句块条件 表达式 关系运算符 表达式表达式 项 + 项 | - 项 项 因子 * 因子 | / 因子 因子 ID | NUM |（表达式）关系运算符 | | = | = | !=上面语名块产生式中的和是终结符号，加引号以示区别。（2）通过为上面文法中的每一个非终结符构造一个递归子程序，设计一个递归下降分析器。（3）在条件、表达式、赋值语句、条件语句、循环语句的递归子程序中，加入语义分析和生成四元式的代码。构造下面的语义过程：int gen(op,arg1,arg2,result)：该函数是将四元式（op, arg1,arg2,result）送到四元式表中。char * newtemp()：该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2int merg(p1,p2)：该函数将以p1和p2为头指针的两条四元式链合并为一条链，合并后的链首为返回值。int bp(p,t)：该函数的功能是把指针p所链接的每个四元式的第四区段都填为t。实验的输入和输出输入是语法分析提供的正确的单词串，输出是四元式序列。例如，对于语句串i = 2 * 3 + 4;if ( i8 ) j = 10;while（ j0）k = k + 1;j = j - 1;输出的四元式序列如下：1.（*，2，3，T1）2.（+，T1，4，T2）3.（=，T2， ，i）4.（j，i，8，6）5. (j， ， ，7)6.（，10， ，j）7.（j，j，0，9）8.（j， ， ，14）9.（+，k，1，T3）10.（，T3， ，k）11.（，j，1，T4）12.（，T4， ，j）13.（j， ， ，7）14. 实验七 基于DAG的基本块优化1实验目的与任务了解基本块的DAG表示及其应用，掌握局部优化的基本方法。2实验要求设计一个转换程序，把由四元式序列表示的基本块转换为DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。最后再从所得到的DAG出发，按原来生成DAG各个结点的顺序，重建四元式序列形式的基本块。3实验内容（1）DAG的结点类型只考虑0型、1型和2型，如下表所示。类型四元式DAG结点0型（=，B， ，A） AB1型(op，B， ，A) op2型(op，B，C，A)(= ，B，C，A)(jrop，B，C，A)BCrop312BC=312BCop312 （2）由基本块构造DAG算法如下：while(基本块中还有未处理过的四元式) 取下一个四元式Q;newleft=newright=0;if(getnode(B)= =NULL)makeleaf(B);newleft=1; switch(Q的类型)case 0 :n= getnode(B);insertidset(n，A);break;case 1: if(isconsnode(B)p=calcons(Q.op，B);if(newleft= =1) /* getnode(B)是处理Q时新建结点 */delnode(B);if(n=getnode(p)= =NULL)makeleaf(p);n=getnode(p)；elseif(n=