编译原理实验报告

编译原理实验报告姓名：学号：班级：学院：南昌大学信息工程学院计算机系2014年6月目录实验一3实验二8实验三1511实验1词法分析程序的设计学生姓名： 学 号： 专业班级：_实验成绩:实验类型：验证综合口设计口创新实验日期:、实验目的掌握计算机语言的词法分析程序的开发方法。二、实验内容编制一个能够分析三种整数、标识符、主要运算符和主耍关键字的词法分析程序。三、实验要求1、根据以下的正规式，编制正规文法，I田I出状态图；标识符V字母(V字母|v数字字符)*十进制整数 0| (1|2卩|4|5|6|7|8|9) (0|1|2卩|4|5|6|7|8|9) *如有余力，则进一步分析八进制和十六进制整数，其正规式如下:八进制整数0 (1|2卩|4|5|6|7)(0|1|2卩|4|5|6|7) *十六进制整数Ox (0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f) 1运算符和界符 关键字+ .*/ = = main if then else while do()； int(可根据需要添加)2、根据状态图，设计词法分析函数int scan(),完成以下功能：1) 从文本文件中读入测试源代码，根据状态转换图，分析出一个单词,2) 以二元式形式输出单词单词种类，单词属性其中单词种类用整数表示：0：标识符1：十进制整数2：八进制整数3：十六进制整数运算符和界符，关键字釆用一字一符，不编码其中单词属性表示如下：标识符，整数由于采用一类一符，属性用单词表示运算符和界符，关键字采用一字一符，属性为空3、编写测试程序，反复调用函数scan(),输出单词种别和属性。四、实验环境PC微机DOS操作系统或Windows操作系统Turbo C程序集成环境或Visual C卄程序集成环境五、实验步骤1根据正规式，画出状态转换图;2. 根据状态图，设计词法分析算法；3. 采用C语言，设计函数scan(),实现该算法;FILE *outputFile; 输出文件4. 编制测试程序(主函数main)； 代码如下：# include# include# include#define SYMBOL CODE 0/标识符编码0#define NUMCODE1/数字编码1/可识别的关键字char keywordstab8 30=“main”,“else,rint”,” return”,“void”,“while”;char ch;接受字符char name30=nn;FILE *sourceFile; 源文件void isNumber();void isOthers();void isKeyword();void output_keyword()printf(n 关键字:n,name,H-H);void output_symbol()printf(n 标识符:nH；,0,name);void output number()printf(n 数字:nn rename);namek=,0,;/初void output_others()始化变量名while(ch=W)&(chv=z)printf(n 其他:nH,name/-n);|(ch=,A,) & (chv=Z) | ch=0/& ch9)/1void scan()namei+ = ch;/把标识符名字存入数组sourceFile = fdpen(nprogram.txtn/rn); /ch = fgetc(sourceFile);/读以读取方式打开源文件取下一个字符if sourceFile = NULL)iprintf(nfile open errornn);exit(O);for(i=0; i8; i+)outputFile = fbpen(noutput.txt，7，wH); /fbr(j=O; j=,a, & ch=A& ch=!0& ch=9)如果是关键字则跳出外循环isNumber();break;elseisOthers();if(flag=O)是关键字fclose(sourceFile);fclose(outputFile);output_keyword();/输出关键字邙艮于篇幅输出函数没有放上来）/ 二一else/ 不void isKeyword()是关键字int i=0, j=0, k=0;output_symbol();/输出标int flag = 0;识符fbr(k=O; k:case：int i=0;chifor(i=0; i=f0& ch=9)ch;namel=namei+ = ch;,ch = fgetc(sourceFile);chfgetc(sourceFile); / 读取下一个字符output_number();output_othersO；break;/elsevoid isOthers()name0=char chi;ch;int i;fdr(i=O; i45 thendata=data+01； elsedata=datal；l CAUsersKAdministratorXDesktopXiXDebugVscan.exe*continua t-a d f 25h 1 1 io - 9 - uito o - o - Go- o - 1 1 : 二 ：+ 1 ; : : = : 1 字符 Y 字符 符 y 字符 y符:$ 键讽他弄他P键识fe:lR- 3 e a s d1 atadk -y ,n ;a六、思考题1、词法分析能否采用空格来区分单词？答：不能。程序中分割单词的不仅仅是空格，还可以是等运算符 或界定符。2、程序设计中哪些环节影响词法分析的效率？如何提高效率？答：例如在判断是否为关键字吋，方法是把单词全部读取并存放在一个字符数组后再逐 个与关键字表匹配，这样做可能效率比较低，若能在读取的同时判断可能会提高效率。实验二 语法分析程序的设计（1）学生姓名： 学 号： 专业班级：实验类型：口验证综合设计口创新 实验日期：实验成绩：一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中预测分析方法。二、实验内容设计一个文法的预测分析程序，判断特定表达式的正确性。三、实验要求1、给出文法如下：GEE-T|E+T;T-F|T*F;F-i|（E）;2、根据该文法构造相应的LL（1）文法及LL（1）分析表，并为该文法设计预测分析程序, 利用C语言或C+语言或Java语言实现；3、利用预测分析程序完成下列功能：1）手工将测试的表达式写入文本文件，每个表达式写一行，用“表示结束；2）读入文本文件中的表达式；口KX III3）调用实验一中的词法分析程序搜索单词；4）把单词送入预测分析程序，判断表达式是否正确（是否是给出文法的语言）， 若错误，应给出错误信息；5）完成上述功能，有余力的同学可以进一步完成通过程序实现对非LL（1）文法到 LL （1）文法的自动转换（见实验二附加资料1）。四、实验环境PC微机Windows操作系统Visual C+程序集成环境五、实验步骤1. 分析文法，将给出的文法转化为LL(1)文法;GEE-T|E+T;T-F|T*F;对应的LL(1)文法为:E-TE1El-+TEl | E;T-FT1;T1-*FT1 |E;F-i|(E);2. 构造该文法中非终结符的FIRST集和FOLLOW集:FIRST(E) = G i FIRST(E1)= +, E FIRST(T) = (,i FIRST(T1)= *, E FIRST(F) = (, iFOLLOW(E) = ),# FOLLOW(E1)= ),# FOLLOW(T) = +,),# FOLLOW(T1)= +,),# FOLLOW(F) = *,+,),# 3. 构造预测分析表:i+*()#EE-TE1E-TE1ElEl-+TElE1-EE1-ETT-FT1T-FT1T1T1-ET1-*FT1T1-ET1-EFF-iF-(E)注：在程序中用P代替E1,Q代替Tl。4.学习预测分析程序的结构，设计合理的预测分析程序;开始花E入栈横 宀如反陰入栈Y4.编写测试程序，包括表达式的读入和结杲的输出;FILE *inputFile;FILE *outputFile;输入文件输出文件char currentStr 10;/用来存放输入的字符串char currentChar;/当前读取的字符char tabData5;/从预测分析表中匹配的产生式右部char statement50;/用于存放读取的语句int index = 0;int finish = 0;int endFlag = 0;/文件结尾int errorFlag = 0;/语法错误标志int endOfStamnt = 0;/用于判断是否达到语旬结尾预测分析表：表示错误，K表示空串 charE105=rE,”iTPT+”,*”,”(TP；),” #;charEl105=”PTiT+TPT*T(T)KT#K”;charT105=”TTiFQT+”,”*”,”(FQT)T# 号； charTl105=”QTiT+KT*FQT(T)KT#K”;charF105=”FTiiT+T*T(E)T)T#”;struct Stack/用来模拟符号栈int top;/栈顶指针char strNameMAX_STACK; / 栈中存 放的符号串 stack;1/= void checkOneStatement()char chtop;errorFlag = 0;finish = 0;stack.top = 0; tabData0 = f0!; push(#); push(E);currentChar = readNext();/ 读取字 符while(!finish)showStack();chtop = pop(); 栈顶字符printf(nchar=%ctn,currentChar);printf(ntabData=%snM,tabData);ififchtop = currentChar)if(chtop =#)finish = 1;/ finish printff 正确! nn); break;I I|1currentChar = readNext();else if(chtop = #)error();exit(O);elseint i;match(chtop,currentChar);if(tabDatal = ) error();printff错误:%cnn,currentChar);27finish = 1;elsefdr(i=O;tabDatai!=,O,; i+);i-；while(i0)if(tabDatai- != K)push(tabDatai+l );/ end while(!finish)checkOneStatement();/ 对一 条语句做语法检查if(errorFlag)printf(*语句：%s错误！nH,statement);fprintf(outputFile/ 语 句：%s 错误! nH,statement);else if(!endFlag)printf(n语句:%s合法！nn,statement);fprintf(outputFile9n 语 句：%s 合法！ nn,statement);fclose(inputFile); fclose(outputFile);exit(0);= void main()while(!endFlag)index = 0;六、测试数据输入数据：编辑一个文本文文件expression.txt,在文件中输入如下内容:10；1+2；(1+2)*3+(5+6*7);(1+2)*3+4;1+2+3+(*4+5);(a+b)*(c+d);(ab3+de4)*5)+l;先调用实验-的词法分析程序扫描输入语句输出结果如下:口 11 回 | W4文件(F)希E) 搭式Q)ea(H) 1,10 a 2也- O- ”文件(Ei轄口 格式Qi(V：i 帮助(H) 农了匸 ai一 o- 牡一 h 一 i, 1三+$ -決 +5 一 h 一 (V)帮助(H)+, -(，- +, - C - C - +$ -牡一牡一+, - 1,1;，一图：输入文件然后调用本次实验的语法分析程序对词法分析的结果进行处理，结果如下:Ecliar=itabData=ttPTchar=itabData=iTPHPQFciar=itabData=iFQIIPQichar=itabData=iiHPQchar=tttabData=ii#Pchar=tttabData=#Kchar=fltabData=#K正萌!语句:10；合法！Echar=itabData=BPTcliar=itabData=iTPHPQFchar=itabData=iFQHPQichar=itabData=ii4PQchar=*tabData=iittPchapu脅tabData=*KMPT +chai*=+tabData=+*TP#PTchai=itabData=+-|-TPHPQFchar=itabData=iFQHPQichar=itabData=iiHPQchar=ittabData=iiPchar=titabData=#Kchai=ittabData=#K正萌!语句:1+2；合法！#Echar=tabData=HPTr-liA3* = T|E+T;T-F|T*F;F-i|（E）;可以构造算符优先表如下:+*()i+ c / v(si2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为 优先关系建立优先函数，这里选择直接存放；1、给出算符优先分析算法如下： k:=l;Sk:=#，；REPEAT把下一个输入符号读进a中；IF S k e VT THEN j k ELSE j:=k-l;WHILE Sj aDOBEGINREPEATQSj；IFSj-leVTTHENj:=j-l ELSEj:=j-2UNTIL Sj Q把Sj+lSk归约为某个N；k:=j+l;Sk:=N;END OF WHILE;IFSj a OR Sj = a THENBEGINk:=k+l;Sk:=aENDELSE ERRORUNTIL a=#4、根据给出算法，利用适当的数据结构实现算符优先分析程序；5、利用算符优先分析程序完成下列功能：1）手工将测试的表达式写入文本文件，每个表达式写一行，用“表示结束；2）读入文本文件中的表达式；3）调用实验2中的词法分析程序搜索单词；4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语 言），若错误，应给出错误信息；5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境PC微机DOS操作系统或Windows操作系统Turbo C程序集成环境或Visual C+程序集成环境五、实验步骤1、分析文法中终结符号的优先关系；2、存放优先关系或构造优先函数；3、利用算符优先分析的算法编写分析程序；4、写测试程序，包括表达式的读入和结果的输出；#include Mmalloc.hn#inc lude#include nstdio.hn/#define _DEBUG_ 0 是否打 印调试信息存储算符优先关系表，大于为1，小 于为-1,等于为0,其它为2表示出错 int table66=1,-1,-1,1,-1,1,1,1,-1,1,-1,1,-1，-1，-1，0,-1, 2, 1,1,2,1，2,1,1,1, 22,1，-1,-1,-1, 2,-1, 0;charE64=”E+TTE+FT+FT+TTF +T,”F+F“;char F44F(E)T(F)T(T)Ti”;char T 4=,F*Fn；,T*Fn;FILE *inputFile; 输入文件FILE *outputFile;输出文件char currentStr10;/用来存放输入的字符串char currentChar;/当前读取的字符char tabData5;/从预测分析表中匹配的产生式右部char statement50;/用于存放读取的语句int index = 0;int endFlag = 0;/文件结尾/打开文件读写流void init()inputFile=fbpen(nwordfile.txtH,nrn);inputFile = NULL) printf(ninputfile open errornH); exit(O); outputFile=fopen(noutputfile.txtn/wH);if( outputFile = NULL) printf(Houtputfile open errornH); exit(O); fv WW CJ1/=读取下一个输入字符char readNext()char ch;int i;fbr(i=O; i10; i+) currentStri =%);while(ch = fgetc(inputFile) !=)if(ch = EOF) endFlag = 1 ;retum f;ch = fgetc(inputFile);fbr(i=O; ch !=i+)ch = fgetc(inputFile);if(currentStrO=lOl|currentStrO=, V)for(i=2; currentStrfi != *0： i+) statementindex+ = currentStrfi;return i;else if(currentStrO = V)statementindex+= statementindex+ = 0; return #;elsestatementindex+=currentStrO;return currentStrO;int match(char ch)int t;switch(ch)case 屮:t=0;bTeak;case welbreak;case ,f:t=2;break;case ):t=3;break;case i:t=4;break;case #:t=5;bTeak;default:t=-l;/用于判断非终 结符return t;currentStrfi = ch;/=查算符优先表表int getState(char Si, char a)int i=match(Si), j=match(a); return tableij;/=对字符串归约char reduce(char* c_ptr)int ij；char* ch_ptr = c_ptr;if(* chjptr = return F：for(i=0;i6;i+)for(j=0;j= 0)/ 非 终结符j = k;elsefor(i=0;i3;i+)for0=0;j3;j 卄) W ij Iif(*ch_ptr != Fij)break;chjptr卄；if(j=3)retum F;chjptr = cjptr;for(i=0;i2;i+)for(j=0;j3;j+)if(*ch_ptr != Tij)break;ch_ptr+;j = k-l;#ifdef DEBUG_ for(i=l; i= 0) j-l; else j -= 2;if(judgeOneStamnt() = 0)while(getState(stackj,Q) = 0);k=j+l;N = reduce( stack+k);if(N = W)error(stack);errorFlag = 1 ;break;else stackk =N;if(getState(stackj,curChar) =0)/小于或等于k+= 1;stack k = curChar;elseerror(n222n);errorFlag = 1;return errorFlag;printf(n%s 正 确nn,statement);fprintfifoutputF ile/语句：%s 合法！ nn,statement);else if(endFlag)printf(nend offile!nH);elseprintf(n%s 错 误 nn,statement);fprintf(outputFile?H 语 句：%s 错误！ nn,statement);fclose(inputFile);exit(0);void main()init(); while(!endFlag) index = 0;六、测试数据输入数据：编辑一个文本文文件expression.txt,在文件中输入如下内容:10;1+2;(1+2)*3+(5+6*7); (1+2)*3+4; 1+2+3+(*4+5);(a+b)*(c+d); (ab3+de4)*5)+l;调用实验一的词法分析程序扫描输入语句输岀结果如下:实验结果:文件旧轄(Ej鈕(O)W(v：i gh(H) (厂+宀也一牡- E+3+5 一;也-+宀0-W(V)帮助(H)c一一-c-0.一0.J*0.一图：输入文件IB；正确 1+2；正确 *3+；正确 *3+4；错误 1+2+3 + ；错误 !* :正确 *5 +1 ； 错误 end o file?tTress any key to continue句句句句句句句 咼语语语语语语10;台逊1+2；合法！(1+2)*3+(5+6*7);合法！ (1+2)*3+4;错误！ 1+2+3+(*4+5) ;错误！ (a+b)* (c+d.);台法! (ab3+de4)*5)+l;错误!七、实验总结在木次实验过程中，通过设计、编制、调试一个算符优先的语法分析程序，实现对词法 分析程序所提供的单词序列进行语法检查和结构分析，我进一步掌握常用的语法分析中算符 优先分析方法，对书本上的理论知识有了更加深刻的认识，对自己的学习有很大的帮助。八、思考题算符优先关系表示的是一种什么样的关系，它在自下而上的分析中起到了什么作用？ 比较本实验和实验2,实现同样的功能，两种方法有什么不同？答：a算符优先关系表示的是定义了文法中出现的终结符之间的某种优先关系，借助这 种优先关系可以寻找可规约串。b实验2中用到的是LL(1)分析法中的预测分析法，是一种 自上而下的分析方法，就是从文法的开始符号出发向下推导出句子；而本实验的算符优先分 析法是自下而上的分析方法，即对输入的句子在适当的时候做规约，最终得到文法的开始符 号。