编译原理实验报告.doc

中南林业科技大学实验报告课程名称： 编译原理专业班级：2012级计算机科学与技术2班姓 名： 陈晓燚 学 号： 201245802015年 7 月 8日实验一 词法分析一、实验目的编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验题目如源程序为c语言。输入如下一段：main()int a=-5,b=4,j;if(a=b) j=a-b; else j=b-a;要求输出如下：（2，”main”）（5，”（”） （5，”）”）（5，”） （1，”int”） （2，”a”）（4，”=”） （3，”-5”） （5，”,”）（2，”b”） （4，”=”） （3，”4”）（5，”,”） （2，”j”） （5，”;”）（1，”if”） （5，”（”） （2，”a”）（4，”=”） （2，”b”） （5，”）”）（2，”j”） （4，”=”） （2，”a”）（4，”-”） （2，”b”） （5，”;”）（1，”else”） （2，”j”） （4，”=”）（2，”b”） （4，”-”） （2，”a”）（5，”;”） （5，”）三、实验理论依据(一)识别各种单词符号1、 程序语言的单词符号一般分为五种：(1) 关键字（保留字/ 基本字）if 、while 、begin(2) 标识符：常量名、变量名(3) 常数：34 、56.78 、true 、a 、(4) 运算符：+ 、- 、* 、/ 、 、and 、or 、.(5) 界限符：， ； （ ） /*2、 识别单词：掌握单词的构成规则很重要 (1) 标识符的识别：字母| 下划线+( 字母/ 数字/ 下划线)(2) 关键字的识别：与标识符相同，最后查表 (3) 常数的识别 (4) 界符和算符的识别 3、 大多数程序设计语言的单词符号都可以用转换图来识别，如图1-1 图1-14、 词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）(1) 单词种别通常用整数编码，如1 代表关键字，2 代表标识符等 (2) 关键字可视其全体为一种，也可以一字一种。采用一字一种得分法实际处理起来较为方便。 (3) 标识符一般统归为一种 (4) 常数按类型（整、实、布尔等）分种 (5) 运算符可采用一符一种的方法。 (6) 界符一般一符一种的分法。 (二)超前搜索方法1、 词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+” ，当前字符为“” ，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？ 显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符+ ，这时可知应将 解释为大于运算符。但此时，超前读了一个字符+ ，所以要回退一个字符，词法分析器才能正常运行。又比如：+ 分析为正号还是加法符号 (三)预处理预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。由一个预处理子程序来完成。四、词法分析器的设计1、 设计方法：(1) 写出该语言的词法规则。 (2) 把词法规则转换为相应的状态转换图。 (3) 把各转换图的初态连在一起，构成识别该语言的自动机 (4) 设计扫描器 2、 把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。 扫描器从初态出发，当识别一个单词后便进入终态，送出二元式 开始读标识符是字母掠过空格和回车符查保留字表是否查到换成属性字结束是数字是特殊符号error取数换成属性字换成属性字换成属性字ynyyynnn图1-2 取单词程序框图5、 程序代码#include#include#includefile *fp;char cbuffer;char *key14=main,if,else,for,while,do,return,break,continue,int,float,double,boolean,long;int atype,id=4;/判断单词是保留字还是标识符int search(char searchchar,int wordtype)int i=0;int p;switch(wordtype)case 1:for(i=0;i=13;i+)if(strcmp(keyi,searchchar)=0)/是保留字则p为非0且不重复的整数p=i+1;break;else p=0; /不是保留字则用于返回的p=0return(p);char digitprocess(char buffer)int i=-1;char digittp20;while(isdigit(buffer)|buffer=.)digittp+i=buffer;buffer=fgetc(fp);digittpi+1=0;printf(%s,常数)n,digittp);id=3;return buffer;char alphaprocess(char buffer)int atype;/保留字数组中的位置int i=-1;char alphatp20;while(isalpha(buffer)|(isdigit(buffer)|buffer=_)alphatp+i=buffer;buffer=fgetc(fp);/读一个完整的单词放入alphatp数组中alphatpi+1=0;/对此单词调用search函数判断类型atype=search(alphatp,1);if(atype!=0)printf(%s,(基本保留字,%d)n,alphatp,atype-1);id=1;elseprintf(%s,标识符)n,alphatp);id=2;return buffer;char otherprocess(char buffer)char ch20;ch0=buffer;ch1=0;if(ch0=,|ch0=;|ch0=|ch0=|ch0=(|ch0=)printf(%s,分隔符)n,ch);buffer=fgetc(fp);id=4;return(buffer);if(ch0=|ch0=!|ch0=)buffer=fgetc(fp);if(buffer=)ch1=buffer;ch2=0;printf(%s,运算符)n,ch);elseprintf(%s,运算符)n,ch);id=4;return(buffer);buffer=fgetc(fp);id=4;return(buffer);if(ch0=+|ch0=-)/在当前符号以前是运算符，则此时为正负号if(id=4)buffer=fgetc(fp);/如果是-53显示结果为（-5，3）（3,3）/*ch1=buffer;ch2=0;*/显示为（-53,3）int i=1;while(isdigit(buffer)chi=buffer;buffer=fgetc(fp);i+;chi=0;printf(%s,常数)n,ch);id=3;buffer=fgetc(fp);return(buffer);/添加+ -功能if(id=2)buffer=fgetc(fp);if(buffer=ch0)ch1=buffer;ch2=0;printf(%s,运算符)n,ch);id=4;buffer=fgetc(fp);return(buffer);ch1=0;printf(%s,运算符)n,ch);buffer=fgetc(fp);id=4;return(buffer);void main()/以只读方式打开一个文件if(fp=fopen(example.c,r)=null)printf(error);else/fgetc()函数：从磁盘文件读取一个字符cbuffer=fgetc(fp);while(cbuffer!=eof)/掠过空格和回车符if(cbuffer= |cbuffer=n)cbuffer=fgetc(fp);elseif(isalpha(cbuffer)/如果该字符是字母cbuffer=alphaprocess(cbuffer);elseif(isdigit(cbuffer)/如果该字符是数字cbuffer=digitprocess(cbuffer);else/是其他字符cbuffer=otherprocess(cbuffer);6、 实验结果 7 实验增加内容：判断了小数的情况；添加了自增，自减运算。实验二 ll（1）分析法一、实验目的根据某一文法编制调试ll(1)分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析ll(1)分析法的理解。二、实验题目实验规定对下列文法，用ll（1）分析法对任意输入的符号串进行分析： （1）e:=tg（2）g:=+tg（3）g:=（4）t:=fs（5）s:=*fs（6）s:=（7）f:=(e)（8）f:=i若输入串为i+i*i# ，则输出为：#ei+i*i#gti+i*i#gsfi+i*i#gsii+i*i#gs+i*i#g+i*i#gt+i*i# tfs2. +7 g+tg6 s5 i4 fi3 etg1 产生式 剩余串 分析栈 步骤ll(1)的分析表为： i + * ( ) # 说 明 e e eselect(etg)=(,i ggg1g1select (g+tg)=+select (g)=#,) t t tselect (tfs)=(,i ss1 s s1 s1select (s*fs)=*select (s)=#,) + f f1 fselect (f(e)=(select (fi)=i3、 程序代码#include#include#include#includechar a20;/分析串char b20;/剩余串char v120=i,+,*,(,),#;/终结符char v220=e,g,t,s,f;/非终结符int j=0,b=0,top=0,l;/l为输入串的长度/生产式类型定义typedef struct type/大写字符char origin;/产生式右边字符char array5;/字符个int length;type;/结构体变量type e,t,g,g1,s,s1,f,f1;/预测分析表type c1010;/输出分析栈void print()int a; /指针for(a=0;a=top+1;a+)printf(%c,aa);printf(tt);/输出剩余串void print1()int j;/输出对齐符for(j=0;jb;j+)printf( );for(j=b;j=l;j+)printf(%c,bj);printf(ttt);void main()int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/把文法产生式赋值结构体e.origin=e;strcpy(e.array,tg);e.length=2;t.origin=t;strcpy(t.array,fs);t.length=2;g.origin=g;strcpy(g.array,+tg);g.length=3;g1.origin=g;g1.array0=;g1.length=1;s.origin=s;strcpy(s.array,*fs);s.length=3;s1.origin=s;s1.array0=;s1.length=1;f.origin=f;strcpy(f.array,(e);f.length=3;f1.origin=f;f1.array0=i;f1.length=1;/初始化分析表for(m=0;m=4;m+)for(n=0;n=5;n+)cmn.origin=n;/全部赋为空/填充分析表c00=e; c03=e; c11=g;c14=g1; c15=g1; c20=t;c23=t; c31=s1; c32=s;c34=c35=s1; c40=f1; c43=f;/读入分析串doscanf(%c,&ch);if(ch!=i)&(ch!=+)&(ch!=*)&(ch!=()&(ch!=)&(ch!=#)printf(输入串中有非法字符n);exit(1);bj=ch;j+;while(ch!=#);/分析串长度l=j;/当前分析字符ch=b0;/# e入栈atop=#;a+top=e;printf(步骤tt分析栈tt剩余字符tt所用生产式n);do/x为当前栈顶字符x=atop-;printf(%d,k+);printf(tt);/判断是否为终结符for(j=0;j=5;j+)if(x=v1j)flag=1;break;/如果是终结符if(flag=1)if(x=#)finish=1;/结束标志printf(acc!n);/接受getchar();getchar();exit(1);if(x=ch)print();print1();printf(%c匹配n,ch);/下一个输入字符ch=b+b;flag=0;/恢复标记else/出错处理print();print1();printf(%c出错n,ch);/输出出错终结符exit(1);else/非终结符处理for(j=0;j=4;j+)if(x=v2j)m=j;/行号break;for(j=0;j,cha.origin);/输出产生式for(j=0;j=0;j-)/产生式逆序入栈a+top=cha.arrayj;if(atop=)/为空则不进栈top-;elseprint();print1();printf(%c出错n,x);exit(1);while(finish=0);4、 实验结果：实验三 逆波兰式的产生及计算一、实验目的将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值二、实验题目如输入如下：21+（42-2）*15+6）-18#输出为：原来表达式： 21+（42-2）*15+6）- 18# 后缀表达式：21&42&2&-15&*6&+18&- 计算结果：609三、算法流程图开始从左到右扫描中缀表达式结束运算分量error退栈输出当前运算符与栈顶运算符比较优先级nyyn运算符左括号(右括号）栈为空栈为空入栈error入栈栈顶为（退栈栈为空栈顶为（退栈输出入栈y输出yy当前大nyynynnnnyn退栈输出ny图3-1 生成逆波兰式的程序流程图读入一个逆波兰算术表达式ch=当前输入符号程序结束ynch是运算符ch=#ny将该字符入栈根据运算符的特点从栈顶部取出若干个运算对象进行该运算，将运算结果入栈图3-2 计算逆波兰式的程序流程图四、程序代码#include#include#include#includefloat stack60;int top=0;float compute(char com)int d=0;int p=0;char ch=comp;while(ch=comp)!=#)switch(ch)case +:stacktop-1=stacktop-1+stacktop;top-;+p;break;case -:stacktop-1=stacktop-1-stacktop;top-;+p;break;case *:stacktop-1=stacktop-1*stacktop;top-;+p;break;case /:if(stacktop!=0)stacktop-1=stacktop-1/stacktop;elseprintf(n除零错误!n);exit(0);/异常退出top-;+p;break;case :/添加计算乘方stacktop-1=pow(stacktop-1,stacktop);top-;+p;break;case :+p;break;default:/*d=0;while(ch=0&ch=0&ch=0&chs（1）s-bb（2）b-ab（3）b-b2、lr(1)分析表为：状态actiongotoab#sbs0s3s412s1accs2s6s75s3s3s48s4r3r3s5r1s6s6s79s7r3s8r2r2s9r2(1)若输入baba#，则输出为：步骤 状态栈 符号栈 输入串 action goto 1 0 # baba# s4 2 04 #b aba# r3 23 02 #b aba# s64 026 #ba ba# s75 0267 #bab a# error(2)若输入bb#，则输出为：步骤 状态栈 符号栈 输入串 action goto 1 0 # bb# s4 2 04 #b b# r3 23 02 #b b# s74 027 #bb # r3 55 025 #bb # r1 16 01 #s # acc三、算法流程图errorys0进状态栈、#进符号栈开始输出状态栈、输出符号栈输出输入串、查动作表当前符号进栈y查状态转换表新的状态进栈读字符移进按某产生式归约y符号栈、状态栈的元素相应退栈归约后的符号进栈查状态转换表、新的状态进栈结束n归约n是否分析终止n四、程序代码#include #include char *action103=s3#,s4#,null, /*action表*/ null,null,acc, s6#,s7#,null, s3#,s4#,null, r3#,r3#,null, null,null,r1#, s6#,s7#,null, null,null,r3#, r2#,r2#,null, null,null,r2#; int goto1102= 1,2, /*goto表*/ 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0; char vt3=a,b,#; /*存放非终结符*/ char vn2=s,b; /*存放终结符*/ char *lr4=e-s#,s-bb#,b-ab#,b-b#;/*存放产生式*/ int a10; char b10,c10,c1; int top1,top2,top3,top,m,n; void main() int g,h,i,j,k,l,p,y,z,count; char x,copy10,copy110; top1=0;top2=0;top3=0;top=0; a0=0;y=a0;b0=#; count=0;z=0; printf(请输入表达式n); /*输出状态栈、输出符号栈、输出输入串*/ do scanf(%c,&c1); ctop3=c1; top3=top3+1; while(c1!=#); print