编译原理实验报告

《编译原理实验报告》由会员分享，可在线阅读，更多相关《编译原理实验报告（27页珍藏版）》请在装配图网上搜索。

1、编译原理实验报告 姓名： 学号： 班级： 学院： 南昌大学信息工程学院计算机系 2014年6月 目录 实验一 3 实验二 8 实验三 15 11 实验1词法分析程序的设计 学生姓名： 学 号： 专业班级：_ 实验成绩: 实验类型：□验证□综合口设计口创新实验日期: —、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、 实验内容 编制一个能够分析三种整数、标识符、主要运算符和主耍关键字的词法分析程序。 三、 实验要求 1、根据以下的正规式，编制正规文法，I田I出状态图； 标识符 V字母〉(V字母＞|v数字字符＞)* 十

2、进制整数 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、 根据状态图，

3、设计词法分析函数int scan(),完成以下功能： 1) 从文本文件中读入测试源代码，根据状态转换图，分析出一个单词, 2) 以二元式形式输出单词〈单词种类，单词属性〉 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字釆用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、 编写测试程序，反复调用函数scan(),输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows操作系统 Turbo C程序集

4、成环境或Visual C卄程序集成环境 五、实验步骤 1・根据正规式，画出状态转换图; 2. 根据状态图，设计词法分析算法； 3. 采用C语言，设计函数scan(),实现该算法; FILE *outputFile; 〃输出文件 4. 编制测试程序(主函数main)； 代码如下： # include # include # include #define SYMBOL CODE 0 //标识符编码0 #d

5、efine NUMCODE 1 //数字编码1 //可识别的关键字 char keywordstab[8] [30]= {{“main”},{“else"},rint”},{” return”},{“void”},{“while”}}; char ch; 〃接受字符 char name[30]={nn}; FILE *sourceFile; 〃源文件 void isNumber(); void isOthers(); void isKeyword(); void output_keyword() { printf(n 关键字:<%sJ%s>\n,\name,H-H);

6、 } void output_symbol() { printf(n 标识符:<%s,%s>\nH；,0,\name); } void output number() { printf(n 数字:<%s,%s>\n\n rename); } name[k]=,\0,; //初 void output_others() 始化变量名 { while(((ch>=W) && (chv=z)) printf(n 其他:<%s,%s>\nH,name/-n); ||((ch>=,A,) && (chv=Z)) || ch=< ：II (ch>0 } //

7、 && ch<9)) // 1 void scan() name[i++] = ch; // { 把标识符名字存入数组 sourceFile = fdpen(nprogram.txtn/rn); // ch = fgetc(sourceFile); //读 以读取方式打开源文件 取下一个字符 if< sourceFile == NULL) } i printf(nfile open error\nn); exit(O); for(i=0; i<8; i++) outputFile = fbpen(noutput.txt，7

8、，wH); // fbr(j=O; j<30; j++) 以写方式打开输岀文件 { // if(outputFile==NULL) 判断是否与关键字匹配 { if(name[j] == printfffile open error\nn); keywordstab [ i] [j ]) exit(O); flag = 0; } else ch = fgetc(sourceFile); // 读 { //如果与当刖关键字不 取字符 匹配则跳出内循环继续与下一个关键字匹 while(ch != EOF) 配 { //标识符以字母或下划线

9、开头 flag = 1; break; if((ch>=,a, && ch<=,z,) ||(ch>=A } && ch<=Z) || ch=l) Xjfl 1)1 ■ H isKeyword(); if(flag==0) // if(ch>=!0&& ch<=9) 如果是关键字则跳出外循环 isNumber(); break; else } isOthers(); if(flag=O) 〃是关键 } 字 fclose(sourceFile); { fclose(outputFile); output_keyword()

10、; //输出关 } 键字 邙艮于篇幅输出函数没有放上来） // 二 一 }else // 不 void isKeyword() 是关键字 { { int i=0, j=0, k=0; output_symbol(); //输出标 int flag = 0; 识符 fbr(k=O; k<30; k++) }  // void isNumber() case>: case』： int i=0; chi for(i=0; i<30; i++) f^etc(sourceFile); name[i]=t\0,; //初始化变量

11、 if(chl == J) 名 { i = 0; name[0]= while(ch>=f0&& ch<=9) ch; { name[l]= name[i++] = ch; —, ch = fgetc(sourceFile); ch } fgetc(sourceFile); // 读取下一个字符 output_number(); } output_othersO；break; // }else void isOthers() { { name[0]= char chi; ch; int i; fdr(i=O; i<30; i++)

12、 output_others(); name[i]-\Of; ch switch(ch) chl;break; { } case } case case: case case 40: // 换行符 case 7‘： ch fgetc(sourceFile); case break; case f: default: ch case y： fgetc(sourceFile); break; case } case } case [： // case T： name[0] = ch; void main() ch = fget

13、c(sourceFile); { scan(); o utput_others();break; } casev:  5、调试程序：检查输出结果是否正确。 program.txt - 记事本 文件(F)编辑(E)格式(O)查看(V)帮助(H) |if data+922>45 then data=data+01； else data=data~l； l "CAUsersKAdministratorXDesktopX^i^XDebugVscan.exe* continu > a > t -a ‘ d f ‘>2>5h ‘> > 1 > 1 ‘> ‘

14、>> io - 9 - uito" o - o - Go- o - 1 < ‘ 9 • • : + 1 > 1 : ••二 ：+ 1 ; : : = : ■ 1— 字符< Y < <字符 < 符< y <字符 y符<<:<$ 键讽他弄他P键识fe:lR- > ■ 3 e a s d 1 a t a d k ->y ,n ;a 六、思考题 1、 词法分析能否采用空格来区分单词？ 答：不能。程序中分割单词的不仅仅是空格，还可以是……等运算符 或界定符。 2、 程序设计中哪些环节影响词法

15、分析的效率？如何提高效率？ 答：例如在判断是否为关键字吋，方法是把单词全部读取并存放在一个字符数组后再逐 个与关键字表匹配，这样做可能效率比较低，若能在读取的同时判断可能会提高效率。 实验二 语法分析程序的设计（1） 学生姓名：— 学 号： 专业班级：— 实验类型：口验证□综合□设计口创新 实验日期：—实验成绩：— 一、 实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序 列进行语法检查和结构分析，进一步掌握常用的语法分析中预测分析方法。 二、 实验内容 设计一个文法的预测分析程序，判断特定表达式的正确性。 三、 实验要求 1、 给出

16、文法如下： G[E] E->T|E+T; T->F|T*F; F->i|（E）; 2、 根据该文法构造相应的LL（1）文法及LL（1）分析表，并为该文法设计预测分析程序, 利用C语言或C++语言或Java语言实现； 3、 利用预测分析程序完成下列功能： 1） 手工将测试的表达式写入文本文件，每个表达式写一行，用“「表示结束； 2） 读入文本文件中的表达式； 口 KX III 3） 调用实验一中的词法分析程序搜索单词； 4） 把单词送入预测分析程序，判断表达式是否正确（是否是给出文法的语言）， 若错误，应给出错误信息； 5） 完成上述功能，有余力的同学可以进一步完成通过程序

17、实现对非LL（1）文法到 LL （1）文法的自动转换（见实验二附加资料1）。 四、 实验环境 PC微机 Windows操作系统 Visual C++程序集成环境 五、实验步骤 1. 分析文法，将给出的文法转化为LL(1)文法; G[E] E->T|E+T; T->F|T*F; 对应的LL(1)文法为: E->TE1 El->+TEl | E; T->FT1; T1->*FT1 |E; F->i|(E); 2. 构造该文法中非终结符的FIRST集和FOLLOW集: FIRST(E) = { G i } FIRST(E1)={ +, E } FIRST(T)

18、 = {(,i } FIRST(T1)={ *, E } FIRST(F) = {(, i} FOLLOW(E) = {),# } FOLLOW(E1)={ ),# } FOLLOW(T) = { +,),# } FOLLOW(T1)={ +,),# } FOLLOW(F) = { *,+,),# } 3. 构造预测分析表: i + * ( ) # E E->TE1 E->TE1 El El->+TEl E1->E E1->E T T->FT1 T->FT1 T1 T1->E T1->*FT

19、1 T1->E T1->E F F->i F->(E) 注：在程序中用P代替E1,Q代替Tl。 4.学习预测分析程序的结构，设计合理的预测分析程序; 开始 花E入栈 横 宀如反陰入栈 Y 4.编写测试程序，包括表达式的读入和结杲的输出; FILE *inputFile; FILE *outputFile; 〃输入文件 〃输出文件

20、 char currentStr[ 10];// 用来存放输入的字符 串 char currentChar; //当前读取的字符 char tabData[5]; //从预测分析表中 匹配的产生式右部 char statement[50]; //用于存放读取的 语句 int index = 0; int finish = 0; int endFlag = 0; //文件结尾 int errorFlag = 0; //语法错误标志 int endOfStamnt = 0; //用于判断是否达 到语旬结尾 〃预测分析表：@表示错

21、误，K表示空串 char E [10][5] = rE",”iTPT+@”,"*@”,”(TP；)@",” #@"}; char El[10][5] = {”PTi@T++TPT*@T(@T)KT#K”}; char T [10][5] = {”TTiFQT+@”,”*@”,”(FQT)@T#@ 号； char Tl[10][5] = {”QTi@T+KT**FQT(@T)KT#K”}; char F [10][5] = {”FTiiT+@T*@T((E)T)@T#@”}; struct Stack//用来模拟符号栈 { int top;//栈顶指针 char strN

22、ame[MAX_STACK]; // 栈中存 放的符号串 } stack; 1/=========== void checkOneStatement() { char chtop; errorFlag = 0; finish = 0; stack.top = 0; tabData[0] = f\0!; push(#); push(E); currentChar = readNext();// 读取字 符 while(!finish) { showStack(); chtop = pop();〃 栈顶字符 printf(nchar=%c\tn,currentChar

23、); printf(ntabData=%s\nM,tabData); ififchtop == currentChar) { if(chtop ==#) { finish = 1;// finish printff 正确! \nn); break; I I ||1 currentChar = readNext(); } else if(chtop = #) { error(); exit(O); } else { int i; match(chtop,currentChar); if(tabData[l] == @) { error(); printf

24、f 错 误:%c\nn,currentChar); 27 finish = 1; }else { fdr(i=O; tabData[i]!=,\O,; i++); i--； while(i>0) if(tabData[i-] != K) push(tabData[i+l ]); }// end while(!finish) checkOneStatement();// 对一 条语句做语法检查 if(errorFlag) { printf(*语句：%s错误！ \nH,statement); fprintf(outputFile/ 语 句：%s 错误! \n

25、H,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;

26、六、测试数据 输入数据： 编辑一个文本文文件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〉 — <；,—> <1, 2> <；,—> <+厂> a 2> <)3-> <也-〉 <1, 3> <1,

27、5> <+,-> <1, 6> <*,-> <1, 7> O-> <；，—> ” 文件(Ei轄口 格式Qi (V：i 帮助(H) 农了——匸 <(厂> ai> 一》 <13 2> o-》 牡一〉 <1, 3> <小-> <+5 一〉 <1,3> <+,-> <(厂> <*.-> <1, 4> (V)帮助(H) <0, a> <+, -》 <0, b> <*,-> 〈(，-》 <0, c> <+, -》 <0, d> < C -》 < C -》 <0, ab3> <+$

28、 -〉 <0, de4> 牡一》 牡一》 <1, 5> <+, -》 〈1,1》 <;，一》 图：输入文件 然后调用本次实验的语法分析程序对词法分析的结果进行处理，结果如下: E cliar=i tabData= ttPT char=i tabData=iTP HPQF c}iar=i tabData=iFQ IIPQi char=i tabData=ii HPQ char=tt tabData=ii #P c

29、har=tt tabData=#K char=fl tabData=#K 正萌! 语句: 10；合法！ E char=i tabData= BPT cliar=i tabData=iTP HPQF char=i tabData=iFQ HPQi char=i tabData=ii 4PQ char=* tabData=ii ttP chapu脅 tabData=*K MPT + chai*=+ tabData=+*TP #PT chai=i tabData=+-|-TP H

30、PQF char=i tabData=iFQ HPQi char=i tabData=ii HPQ char=it tabData=ii P char=ti tabData=#K chai=it tabData=#K 正萌! 语句: 1+2；合法！ #E char=< tabData= HPT r-liA3* = <， =TTP 输出文件: outputfile.txt -记事本 | =‘ 句句句句句句句 m--语语语语语语 文件(Fj稠(E)格式(O)查看(V)帮助(H) 10；密

31、 1+2;合法！ 人 (1+2)*3+(5+6*7).合法！ ((1+2)*3+4;错误！ 1+2+3+(村+5),错误！ (a+b)*(c+d);合法! ((甜3十d巳4)*水5)+1「错误! 七、 实验总结 在本次实验过程中，通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序 所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中预测分析方法。 将书木上的理论知识运用到实验中，加深、巩固了对语法制导翻译原理的理解。 八、 思考题 如果使用递归下降分析法来进行语法分析，为什么文法必须先转化为LL(1)文法再做 递归下降分析？ 答：为了消除左递归和消除回

32、溯。 实验3语法分析程序的设计（2） 学生姓名： 学 号： 专业班级: 实验类型：□验证□综合口设计口创新实验日期: 实验成绩： 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序 列进行语法检查和结构分析，进一步掌握常用的语法分析中算符优先分析方法，并加深对语 法制导翻译原理的理解。 二、实验内容 设计一个文法的算符优先分析程序，判断特定表达式的正确性，并结合语法制导翻译原 理，构造相应语义规则，将语法分析所识别的正确的表达式翻译计算出结果。 三、实验要求 1、给出文法如下: G[E] E->T|E+T;

33、 T->F|T*F; F->i|（E）; 可以构造算符优先表如下: + * ( ) i + < c < > < 广 * > < ^\ > < / v ( < < < < ) > > s> i > > > 2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为 优先关系建立优先函数，这里选择直接存放； 1、给出算符优先分析算法如下： k:=l; S[k]:=#，； REPEAT 把下一个输入符号读进a中； IF S [k] e VT THEN j ~k ELSE j

34、:=k-l; WHILE S[j] > aDO BEGIN REPEAT Q~S[j]； IFS[j-l]eVTTHENj:=j-l ELSEj:=j-2 UNTIL S[j] < Q 把S[j+l]・・・S[k]归约为某个N； k:=j+l; S[k]:=N; END OF WHILE; IFS[j] < a OR S[j] = a THEN BEGIN k:=k+l;S[k]:=a END ELSE ERROR UNTIL a=# 4、 根据给出算法，利用适当的数据结构实现算符优先分析程序； 5、 利用算符优先分析程序完成下列功能： 1） 手工将测试的

35、表达式写入文本文件，每个表达式写一行，用“「表示结束； 2） 读入文本文件中的表达式； 3） 调用实验2中的词法分析程序搜索单词； 4） 把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语 言），若错误，应给出错误信息； 5） 完成上述功能，有余力的同学可以对正确的表达式计算出结果。 四、实验环境 PC微机 DOS操作系统或Windows操作系统 Turbo C程序集成环境或Visual C++程序集成环境 五、实验步骤 1、 分析文法中终结符号的优先关系； 2、 存放优先关系或构造优先函数； 3、 利用算符优先分析的算法编写分析程序； 4、 写测试程

36、序，包括表达式的读入和结果的输出； #include Mmalloc.hn #inc lude #include nstdio.hn //#define _DEBUG_ 0 〃是否打 印调试信息 〃存储算符优先关系表，大于为1，小 于为-1,等于为0,其它为2表示出错 int table[6][6]={ {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, 2」2,1}， {-1,-1,-1, 2,-1, 0}}; char E[6][4]={”E+

37、TTE+F「T+F「T+TTF +T,”F+F“}; char F[4][4F「(E)T(F)T(T)Ti”}; char T ⑵[4]={,,F*Fn；,T*Fn}; FILE *inputFile; 〃输入文件 FILE *outputFile; 〃输出文件 char currentStr[10]; //用来存放输 入的字符串 char currentChar; //当前读取的 字符 char tabData[5]; //从预测分析 表中匹配的产生式右部 char statement[50]; //用于存放读 取的语句 int index =

38、 0; int endFlag = 0; //文件结尾 // 打开文件读写流 void init() inputFile = fbpen(nwordfile.txtH,nrn); inputFile == NULL) { printf(ninputfile open error\nH); exit(O); } outputFile = fopen(noutputfile.txtn/wH); if( outputFile == NULL) { printf(Houtputfile open error\nH); exit(O); } f 「 v WW C

39、J1 //===—读取下一个输入字符 char readNext() { char ch; int i; fbr(i=O; i<10; i++) currentStr[i] =%); while((ch = fgetc(inputFile)) !=<) { if(ch == EOF) { endFlag = 1 ;retum f} }; ch = fgetc(inputFile); fbr(i=O; ch != i++) ch = fgetc(inputFile); } if(currentStr[O]=lOl || currentStr[O]==, V)

40、{ for(i=2; currentStrfi] != *0： i++) { statement[index++] = currentStrfi]; } return i; } else if(currentStr[O] == V) { statement[index++]= statement[index++] = \0; return #; } else { statement[index++] = currentStr[O]; return currentStr[O]; int match(char ch) { int t; switch(ch) {

41、 case 屮:t=0;bTeak; case wel’break; 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 table[i][j]; } //====„=对字符串归约 c

42、har reduce(char* c_ptr) { int ij； char* ch_ptr = c_ptr; if(* chjptr == ^^return F： for(i=0;i<6;i++) { for(j=0;j<3;j ++) { if(*ch_ptr != E[i][j])break; chjptr-H-； } if(j=3)return E; chjptr = cjptr; return } void error(char ch[J) { //printf(n错误 %s\iT,ch); } 〃=====核心函数 int judgeOne

43、Stamnt() { int errorFlag = 0;// 0 表示正确 int k=l J=0,i=0; char curChar,Q,N; char stack [20]; stack[k] = while(curChar!=#‘) { curChar = readNext(); if(endFlag)return 2; if(match(stack[k]) >= 0)// 非 终结符 j = k; else for(i=0;i<3;i++) { for0=0;j<3;j 卄) \ { W ij I if(*ch_ptr != F[i][j])break

44、; chjptr卄； } if(j==3)retum F; chjptr = cjptr; } for(i=0;i<2;i++) { for(j=0;j<3;j++) { if(*ch_ptr != T[i][j])break; ch_ptr++; j = k-l; #ifdef DEBUG_ for(i=l; i<=k; i++) { printf(n%cH,stack[i]); } printf(n\t%c ”,curChar); printf(n\tstate=%d\nn,getState(stack[ j],curChar)); # endif

45、while(getState(stack[j],curChar) ==1)//大于 { do{ Q = stackfj]; if(j=3)retum T; ch_ptr = c_ptr; if(match(stack[j-1 ]) >= 0) j-l; else j -= 2; if(judgeOneStamnt() == 0) }while(getState(stack[j],Q) >= 0); k=j+l; N = reduce( stack+k); if(N = W) { error(stack); errorFlag = 1 ;break;} el

46、se stack[k] =N; } if(getState(stack[j],curChar) <= 0)//小于或等于 { k+= 1; stack [k] = curChar; } else {error(n222n);errorFlag = 1;} } return errorFlag; printf(n%s 正 确 \nn,statement); fprintfifoutputF ile/ 语 句：%s 合法！ \nn,statement); }else if(endFlag) { printf(nend offile!\nH); }else {

47、 printf(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); (

48、(ab3+de4)**5)+l; 调用实验一的词法分析程序扫描输入语句输岀结果如下: 实验结果: 文件旧轄(Ej 鈕(O) W(v：i ^gh(H) < C ->~~~~— < (厂》 <131> <+宀 <1, 2> <).-> <也一》 <13 3> 牡-> <1, 4> < — <1,1> E <+3 <1, 2> <+5 一; <1, 3> <+,-> 〈也-> <1, 4> <+宀 <1,5> 0-> <+, -> <0, b>

49、一》 -> c> -> <0, d> 0. —》 <;, -> <0, ab3> 一》 <0, de4> 0. <1, 5> J* 0. 一》 图：输入文件 IB；正确 1+2；正确 <1+2>*3+<5+6*7>；正确 <<1+2 >*3+4；错误 1+2+3 + <*4+5>；错误 !* :正确 <

50、**5> +1 ； 错误 end o file? t Tress 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.);台法! (