编译技术实验指导书.doc

编译技术实验指导书计算机科学与工程学院前言编译技术是计算机科学与技术、软件工程等专业的一门理论性较强的专业课，旨在培养大学生的计算机专业素质和基本编译程序设计的能力。通过实验教学，使学生加深对所学知识的理解，掌握编译程序构造原理和实现技术。它的目的和任务是：让学生掌握编译程序的基本原理和实现技术，提高学生对程序设计语言的理解，让学生了解将高级程序设计语言源程序翻译成计算机能处理的目标代码语言的整个过程，培养学生的编译程序设计的能力。编译程序的设计包括词法分析程序的设计、语法分析程序的设计、语义分析程序的设计和中间代码生成程序的设计等。本实验指导书是金成植编著的编译程序构造原理和实现技术的配套教材。编者根据计算机课程实践性强等特点，编写了本实验教程，帮助学生有计划地系统地上机实践。根据教学内容和教学目标，实验指导书设计了八次实验，实验学时16学时，每个实验2学时。学生应按照实验指导书的要求，完成指定的实验任务，并及时提交实验报告。要求学生在每次实验之前做好预习，实验后按要求写出实验报告。在每次实验过程中教师要考核学生每次实验的完成情况。一、 为保证实验效果学生应做到：1、遵守实验室的规章制度，爱护教学设备。2、学生必须按时上机下机。 3、禁止做与实验无关的内容，禁止利用实验学时玩计算机游戏；4、每次实验前学生应做好预习，实验后按时提交实验报告。二、 实验报告的要求：1、明确实验的目的及要求；2、记录下相应编译阶段的程序设计的思想、程序代码及运行的结果；3、说明实验中出现的问题和解决过程；4、写出实验的体会和实验过程中没解决的问题。 由于编者水平有限，书中难免有错，敬请大家批评指正。辽宁科技大学计算机学院科学系11年2月目 录实验一 词法分析器的手工构造 . . .3实验二 词法分析器的自动生成 . .10实验三 递归下降语法分析程序设计. 18实验四 LL(1)语法分析程序设计. . . 22实验五 LR语法分析器程序设计 . .27实验六 说明语句的语法制导翻译. .32实验七 中间代码生成程序设计. .35实验八 微小编译器的设计 . 37实验一 词法分析器的手工构造实验类型：验证性 实验要求：必修一、实验目的：通过本次实验，使学生掌握词法分析的构造原理及实现技术，会编写简单程序设计语言的词法分析器。二、实验要求：1、通过词法分析基本原理和基本技术的学习，参照给定的词法分析程序样例，验证一个简单语言的词法分析程序，加深对词法分析基本原理和基本技术的理解。2、从文件读入源程序，经预处理后进行词法分析，输出为单词串，即由（词法信息，语义信息）所组成的二元组序列；有一定检查词法错误的能力。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。3、上机时间：2学时。三、实验原理1、 词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词的Token序列。词法分析器的单词符号可表示成的二元式(单词种别码，单词符号的属性值)。本实验中，基本字、符号词采用一词一类的方式，标识符、常数采用的是一类一个类码的方式。2、 单词的BNF表示 字母字母数字串 字母字母数字串|数字字母数字串|下划线字母数字串| 数字数字串 数字数字串 | + | * | + | =界符- , | ；| ( | ) | # 3、状态转换图识别标识符的状态转换图识别实常数和整常数的状态转换图四、实验内容 请参照给定的C词法分析程序的样例，编写下列给定的源程序的VC+词法分析程序，屏幕显示结果。begininteger r ;r = r +10 ; end 五、词法分析器的手工构造样例程序#include #include #include #include #include const short WORDLEN=20;struct code_valchar code;char valWORDLEN;/预处理函数原型void pro_process(char *);/扫描函数原型code_val scanner(char *);/拼接函数原型void concat(char ,char);/查保留字表函数char reserve(char );/主函数void main()char buf4048=0;/扫描缓冲区/预处理pro_process(buf);/显示bufcoutbufendl;/单词识别ofstream coutf(Lex_r.txt,ios:out);code_val t;/临时变量dot=scanner(buf);/调用一次扫描器获得一个单词二元式coutt.codett.valendl;/屏幕显示单词二元式 coutft.codett.valendl;/单词二元式输出至文件 while(t.code!=#);coutEnd of lexical analysis!=a & bufi=a & bufi=0 & bufi=0 & bufi=0 & bufi=0 & bufi=0 & bufi=0 & bufi=9)concat(token,bufi+);t.code=y;strcpy(t.val,token);return t;/返回当前单词实常数(.123)的二元式else/单个.错误词形couttokenendl;exit(0);/其余单词switch(bufi)case ,:t.code=,;break;case ;:t.code=;break;case (:t.code=(;break;case ):t.code=);break;case =:t.code=;break;case +:if(buf+i=+)t.code=$;elset.code=+;i-;break;case *:t.code=*;break;case #:t.code=#;break;default:/错误字符coutbufiendl;exit(0);/end of switchi+;/指向下个单词return t;/返回当前单词的二元式/拼接函数，原token=BEG, bufi+=I, 调用后token=BEGI。void concat(char token,char c)for(int i=0;tokeni;i+);tokeni=c;token+i=0;char reserve(char token)const char *table=begin,end,integer,real;const char code=ac;for(int i=0;i=A & cur_c=Z) cur_c+=32;/大写变小写if(cur_c=t | cur_c=n) cur_c= ;/空格bufi+=cur_c ;break;case true:if(old_c=* & cur_c=/)/离开注释in_comment=false;/end of switchold_c= cur_c;/保留前一个字符/end of whilebufi=#; 实验二 词法分析器的自动生成实验类型：验证性 实验要求：必修一、 实验目的通过本次实验，使学生掌握利用状态转换矩阵实现状态迁移，从而实现词法分析器的自动生成，完成对一个简单程序的单词的识别。二、 实验要求1、构造描述每个单词的正规式，根据正规式Pi构造最终形成识别全部单词的NFA M。对NFA M确定化构造DFA M。利用DFA M识别一个简单程序设计语言的单词，屏幕输出单词的二元组序列。2、提交实验报告，报告内容如下：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。3、上机时间：2学时。三、 实验原理1、自动生成过程概述构造描述每个单词的正规式Pi(1iN)。根据正规式Pi构造NFA Mi(1iN)，假定初态均为0。在构造NFA Mi的同时，逐步并且最终形成识别全部单词的NFA M。NFA M确定化重新标记，构造DFA M。2、实例（模型语言的词法）模型语言字符集a.z，0.9，+，=，*，, ，; ，(，)，# 模型语言单词集基本字：begin、end、integer、real标识符：以字母开始的数字字母串无符号整常数：数字串运算符：+、* 、+、=界符： , 、; 、( 、) 、# 单词编码基本字：begin (,NUL、end(,NUL)、integer (a,NUL)、real (c,NUL)标识符：(i,字符串)无符号整常数：(x,字符串)运算符:=(=,NUL)、+(+,NUL)、*(*,NUL)、+($,NUL)界符：,(,NUL)、;(;,NUL)、( ( (,NUL)、) ( ),NUL)、#(#,NUL)3、实例解构造正规式（令= a|b|c|d|z ，= 0|1|2|3|4|5|6|7|8|9）标识符： (|)* 无符号整常数： *运算符 ： 单词本身（例=的正规式为=，+的正规式为+）界符： 单词本身（例;的正规式为;）基本字通常是由字母构成，符合标识符规则，将基本字作为一种特殊标识。构造NFA MNFA M确定化IIII=I+I*I,I;I(I)I#01,12,132,14,1534,5678910111,12,1312,1312,132,14,1514,1534,5166789101112,1312,1312,1314,1514,1516重新标记，构造DFA M状态/字符 =+*,;()#0123456789101111121234135678910111111121213四、实验内容参照给定算法，构造一个识别简单程序设计语言单词的DFA。五、扫描器控制程序的实现算法#include #include #include #include #include const short WORDLEN=20;struct code_valchar code;char valWORDLEN;/单词编码表const char *table=begin,end,integer,real,=,+,+,*,;,(,),#;const char code =ac=+$*,;()#;/DFA列字符const char COL_CHAR=a0=+*,;()# ;/状态转换矩阵（DFA）const int DFA11= /strlen(a0=+*,;()# )=111,2,3,4,5,6,7,8,9,10,0,11,11,0,12,0,0,0,0,13,0,0,0,0,0,0,11,11,0,12,0;/预处理函数原型void pro_process(char *);/扫描函数原型code_val scanner(char *);/主函数void main()char buf4048=0;/扫描缓冲区/预处理pro_process(buf);/显示bufcoutbufendl;/单词识别ofstream coutf(Lex_r.txt,ios:out);code_val t;/临时变量dot=scanner(buf);/调用一次扫描器获得一个单词二元式coutt.codett.valendl;/在屏幕显示单词二元式 coutft.codett.valendl;/将单词二元式输出至文件while(t.code!=#);coutEnd of lexical analysis!=a&token0=a&c=0&c=9)c=0;/const char COL_CHAR=a0=+*,;()# ;for(int i=0;i=(int)strlen(COL_CHAR);i+)if(c=COL_CHARi)return i;coutcendl;exit(0); /程序终止运行/拼接函数，原token=BEG, bufi+=I, 调用后token=BEGI。void concat(char token,char c)for(int i=0;tokeni;i+);tokeni=c;token+i=0;char search_table(char token)/根据token内容查单词二元式编码表，返回单词种别。/const char *table=/begin,end,integer,real,=,+,+,*,;,(,),#/;/const char code=ac=+$*,;()#;for(int i=0;i=A & cur_c=Z) cur_c+=32;if(cur_c=t | cur_c=n) cur_c= ;/空格bufi+=cur_c ;break;case true:if(old_c=* & cur_c=/)/离开注释in_comment=false;/end of switchold_c= cur_c;/保留前一个字符/end of whilebufi=#;实验三 递归下降语法分析程序设计实验类型：验证性 实验要求：必修一、实验目的：通过本次实验，使学生掌握递归下降分析的原理及实现技术，会编写简单程序的递归下降语法分析程序。二、实验要求：1、根据递归下降分析算法和给定的C语法分析程序的样例，编写指定的源程序的VC+语法分析程序，屏幕显示结果。2、有运行实例。即对于给定的文法和一个源程序，所编语法分析程序能正确判断此程序语法是否正确，有语法错误的要给出错误提示。3、提交实验报告，报告内容如下：目的、要求、算法描述、程序结构、主要变量名说明、程序清单、调试情况、设计技巧、心得体会。4、上机时间：2学时。三、实验原理和说明1、递归下降分析法的功能语法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2、递归下降分析法的前提给定文法必须是LL（1）文法，若不是需改造文法：消除二义性、消除左递归、提取左因子，确保文法为LL（1）文法。3、递归下降分析法设计思想及算法为GS的每个非终结符号U构造一个递归函数。假设产生式形如: A b1| b2| | bn，则按下面的方法编写子函数A( )： procedure A( ) begin if tokenPredict(Ab1) then q(b1) else if tokenPredict(Ab2) then q(b2) else if tokenPredict(Abn) then q(bn) else err( ) end 其中对bi =X1X2Xn，q(bi) = q(X1);q(X2);q(Xn); 如果XVN，q(X)= X 如果XVT，q(X)= Match(X) 如果X= e , q(e) = skip(空语句)四、实验内容根据递归下降分析算法和给定的C语法分析程序的样例，编写教材P86页3给定的文法G的递归下降语法分析程序，分析“（a,(a,a)）#”是否为该文法的句子，屏幕显示结果。五、递归下降分析算法对给定文法G：ET EE+TE|TFTT*FT|F(E)|i|x|y 对应的递归下降分析算法如下：void E(void)/ET Eif(t.code=i|t.code=x|t.code=y|t.code=()/ if (t.codefirst(T) T( );E1( );elsecoutfendlt.codet.codet.val; coutft.code;/读一个单词的二元 式并输出单词种别T( );E1( );else if(!(t.code=#|t.code=) /if(!t.codefollow(E)coutfendlendlt.code;void T(void)/TFTif(t.code=i|t.code=x|t.code=y|t.code=() /if(t.codefirst(F)F( );T1( );elsecoutfendlt.codet.codet.val;coutft.code; /读一个单词的二元式并输出单词种别F( );T1( );else if(!(t.code=#|t.code=)|t.code=+) /if(!t.codefollow(T)coutfendlt.codet.codet.val;coutft.codet.val;coutft.codet.val;coutft.code; /读一个单词的二元式并输出单词种别elsecoutft.codeendl;exit(0);elsecoutfendlt.codeendl;exit(0);实验四 LL(1)语法分析程序设计实验类型：验证性 实验要求：必修一、实验目的通过本次实验，使学生掌握LL(1)语法分析的原理及实现技术，会编写简单程序的LL(1)语法分析程序。二、实验要求1、应用LL(1)分析法设计一个简单程序的语法分析器。2、提交实验报告，报告内容包括实验目的、要求、算法描述、程序结构、主要变量名说明、程序清单、调试情况、设计技巧、心得体会。3、上机时间：2学时。三、数据结构及算法描述1、数据结构M:二维数组，存放预测分析表。stack:符号栈，初始时为#S（S为开始符号）。 X:表示栈顶符号 t.code:当前处理单词种别2、算法描述预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事（ XPop(stack) ），控制程序每次执行下述三种可能的动作之一。若X 和 t.code 均为 #，则分析成功，输入串为合法句子，终止分析过程。若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等，则读入下一个单词二元式；若X和t.code不相等，则报错。若X是非终结符，则查预测分析表。若MXt.code存放着一条关于X的一个产生式，那么把产生式右部符号串按反序压入stack栈。若右部符号串为空字，则意味着无任何文法符号进栈；否则出错。四、实验内容：对给定文法G：0.ETD1.D+TD2.D3.TFS4.S*FS 5.S6.F(E)7.Fi8.Fx9.Fy应用LL(1)分析法设计一个由单词种别构成的源程序“i+i#”的语法分析器。五、预测分析控制程序样例#include #include #include #include struct code_valchar code;char val20;const char *p =/指向产生式右部符号串TD,+TD,FS,*FS,(E),i,x,y; const char T =+*( )ixy#;/分析表的列符const char NT =EDTSF;/分析表的行符，行符为EETTF。const int M 8=/*在预测分析表M中存放指针数组p的下标x，设Mij=x，通过pMij=px获取右部符号串。*/-1,-1,0,-1,0,0,0,-1,/p0指向第0个产生式右部符号串TD，-1表示出错。1,-1,-1,2,-1,-1,-1,2, -1,-1,3,-1,3,3,3,-1,5,4,-1,5,-1,-1,-1,5,-1,-1,6,-1,7,8,9,-1;/函数原型int lin(char );/非终结符转换为行号int col(char );/终结转换为列号bool isNT(char);/isNT判断是否是非终结符bool isT(char);/isT判断是否是终结符。void main(void)int i,j=0;ifstream cinf(lex_r.txt,ios:in);/从文件lex_r.txt输入数据ofstream cout(par_r.txt,ios:out);/结果输出至文件par_r.txt（cout重定义）struct code_val t;/定义结构变量，存放单词二元式。cinft.codet.val;/读一个单词的二元式char stack20=#,E;int top=1;/栈赋初值char X= ; /用于显示，并非必要。coutsteptstacktXtt.codeendl; /用于显示，并非必要。coutj);/用于显示，并非必要。while(1)coutt;/用于显示，并非必要。for(i=0;i=top;i+)coutstacki; /用于显示，并非必要。coutt tt.codeendl;/用于显示，并非必要。X=stacktop-;/出栈cout+j)t; /用于显示，并非必要。for(i=0;i=top;i+)coutstacki;/用于显示，并非必要。couttXtt.codeendl; /用于显示，并非必要。if(X=#)if(X=t.code)couttAccendl;break;/跳出循环elsecoutXtt.codet.codet.val;/读下一单词二元式elsecoutXtt.codeendl;exit(0);continue;/end of if(isT(X)if(isNT(X)/是否是非终结符if(Mlin(X)col(t.code)=-1)coutXtt.code=0;i-)stack+top=*(pMlin(X)col(t.code)+i);continue;/end of if(isNT(X)coutXendl;exit(0);/end of while/end of mainint lin(char c) /将EDTSF分别转换为01234for(int i=0;i(int)strlen(NT);i+)if(c=NTi)return i;coutcendl;exit(0);int col(char c)/将+* ()ixy#分别转换为01234567for(int i=0;i(int)strlen(T);i+)if(c=Ti)return i;coutcendl;exit(0);bool isNT(char c)/是否是非终结符for(int i=0;i(int)strlen(NT);i+)if(c=NTi)return true;return false;bool isT(char c) /是否是终结符（不包括#）for(int i=0;i(int)strlen(T)-1;i+)if(c=Ti)return true;return false;实验五 LR语法分析器程序设计实验类型：验证性 实验要求：必修一、实验目的：通过本次实验，使学生掌握LR语法分析的原理及实现技术，会编写简单程序的LR语法分析程序。二、实验要求：1、根据LR语法分析算法，编写一个LR语法分析程序。2、有运行实例。即对于给定的文法和一个源程序，所编语法分析程序能正确判断此程序语法是否正确，有语法错误的要给出错误提示。3、提交实验报告，报告内容如下：目的、要求、算法描述、程序结构、主要变量名说明、程序清单、调试情况、设计技巧、心得体会。4、上机时间：2学时。三、实验的数据结构和算法描述1、数据结构LR分析表状态栈在归约时，控制程序应按原路径折回，故在分析过程中需将所经历的状态记录下来，以便获得折回点。设置状态栈，用于记录分析过程中所经历的状态，即路径。符号栈用于记录路径的符号，它和状态栈等高。符号栈的设置是为了便于说明，实际语法分析器无符号栈。产生式右部符号串长度因每个状态仅识别一个符号，退回的状态数和构成句柄的字符数相等，故需存储产生式右部符号串长度。产生式左部符号归约后，根据左部符号进入下一状态。2、算法描述分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示，控制程序的算法归纳如下：移进若MStopt.code=sj，说明句柄尚未形成，应执行移进操作。s表示移进，j为状态号，将j移入状态栈，将t.code移入符号栈，j成为新的栈顶状态Stop。读下一个单词。归约若MStopt.code=rk，说明句柄已出现在栈顶，应该用编号为k的产生式A进行归约。假设，LEN()=r，MStop-rA=j。首先将栈顶r个元素出栈，然后将j和A分别移入状态栈和符号栈，j成为新的栈顶状态Stop。当前处理单词不变。接受MStopt.code=Acc，表示输入串是一个合法句子，程序终止运行。出错MStopt.code=空白，表示出错，最简单处理为程序终止运行。四、实验内容1、验证教材P112-114的LR分析器的控制程序。2、完成1的要求后，可对教材中的算法进行改进，