编译原理实验指导书.doc

《编译原理实验指导书.doc》由会员分享，可在线阅读，更多相关《编译原理实验指导书.doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理实验指导书实验一 词法分析中南林业科技大学实验报告课程名称： 编译原理专业班级：2014级计算机科学与技术2班姓名：王晶学号：201445922017年5月5日-目录实验一 词法分析2实验二 LL(1)分析法11实验三 逆波兰式的产生及计算17实验四 LR(1)分析法24实验一 词法分析一、 实验目的编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义

2、的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、 实验题目如源程序为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，”

3、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) 标识符的识别：

4、字母| 下划线+( 字母/ 数字/ 下划线)(2) 关键字的识别：与标识符相同，最后查表 (3) 常数的识别 (4) 界符和算符的识别 3、 大多数程序设计语言的单词符号都可以用转换图来识别，如图1-1 图1-14、 词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）(1) 单词种别通常用整数编码，如1 代表关键字，2 代表标识符等 (2) 关键字可视其全体为一种，也可以一字一种。采用一字一种得分法实际处理起来较为方便。 (3) 标识符一般统归为一种 (4) 常数按类型（整、实、布尔等）分种 (5) 运算符可采用一符一种的方法。 (6) 界符一般一符一种的分法。 (二)超

5、前搜索方法1、 词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+” ，当前字符为“” ，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？ 显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符+ ，这时可知应将 解释为大于运算符。但此时，超前读了一个字符+ ，所以要回退一个字符，词法分析器才能正常运行。又比如：+ 分析为正号还是加法符号 (三)预处理预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。由一个预处理子程序来完成。四、 词法分析器的设计1、 设计方法：(1) 写出该语言的词法规则。 (2) 把词法规则转换为相

6、应的状态转换图。 (3) 把各转换图的初态连在一起，构成识别该语言的自动机 (4) 设计扫描器 2、 把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。 扫描器从初态出发，当识别一个单词后便进入终态，送出二元式 开始读标识符是字母掠过空格和回车符查保留字表是否查到换成属性字结束是数字是特殊符号error取数换成属性字换成属性字换成属性字YNYYYNNN图1-2 取单词程序框图五、 完整程序源代码#include #include #include #include FILE *fp;char cbuffer;char *key10=if,else,for,while,do

7、,return,break,continue,stdio.h,math.h;int atype,id=4;/char digittp20; /定义一个数字数组 char alphaprocess(char buffer);char digitprocess(char buffer);char otherprocess(char buffer);int search(char searchchar ,int wordtype);int main() if (fp=fopen(D:编译原理实验1.c,r)=NULL) /*只读方式打开一个文件if(p=fopen(H:Text.txt,r)=NUL

8、L)*/ printf(error); else cbuffer = fgetc(fp); /*fgetc( )函数：从磁盘文件读取一个字符*/ while (cbuffer!=EOF) if(cbuffer= |cbuffer=n|cbuffer=t) /*掠过空格和回车符和tab*/ cbuffer=fgetc(fp); else if(isalpha(cbuffer) /判断是字母 cbuffer=alphaprocess(cbuffer); else if (isdigit(cbuffer)|cbuffer=.) /判断为数字 ,或者浮点数 cbuffer=digitprocess(c

9、buffer); else cbuffer=otherprocess(cbuffer); /判断其为其他类型 return 0;char alphaprocess(char buffer) int atype; /*保留字数组中的位置*/ int i=-1; char alphatp20; while (isalpha(buffer)|(isdigit(buffer)|buffer=_|buffer=.) /读到的是字母数字下划线 . alphatp+i=buffer; buffer=fgetc(fp); /*读一个完整的单词放入alphatp数组中*/ alphatpi+1=0; /单词读完

10、置上结束符号 atype=search(alphatp,1); /*对此单词调用search函数判断类型*/ if(atype!=0) /判断函数返回值不是0，是保留字，输出1 printf(%s , 1)n,alphatp,atype-1); id=1; /保留字 else printf(%s ,2)n,alphatp); id=2; /返回值是0，标识符，第二类 return(buffer);int search(char searchchar ,int wordtype) /*判断单词是保留字还是标识符*/ int i=0; int p; switch (wordtype) case 1

11、:for (i=0;i=9;i+) if (strcmp(keyi,searchchar)=0) p=i+1; break; /*是保留字则p为非0且不重复的整数*/ else p=0; /*不是保留字则用于返回的p=0*/return(p); char digitprocess(char buffer) /读入数字 int i=-1;char digittp20; /定义一个数字数组 while (isdigit(buffer)|buffer=.|buffer=e) /读入一个完整的数字放在isdigit数组中 digittp+i=buffer; buffer=fgetc(fp); digi

12、ttpi+1=0; /数组结束 printf(%s ,3)n,digittp); /输出数字为第三类 id=3;return(buffer); char otherprocess(char buffer) /判断为其他字符的函数 char ch20; /定义一个字符数组 char ch120; char ch220; int i=0; ch0=buffer; /除了以上两类其他都读入 ch1=0; if(ch0=,|ch0=;|ch0=|ch0=|ch0=(|ch0=) /读入 ， ； （ ）字符时直接输出为第五类 printf(%s ,5)n,ch); buffer=fgetc(fp); i

13、d=4; return(buffer); if(ch0=#) /#define,#include关键字，第一类 buffer=fgetc(fp); while (isalpha(buffer) /读到的是字母 ch+i=buffer; buffer=fgetc(fp); chi+1=0; /单词读完置上结束符号 printf(%s , 1)n,ch); id=1; return(buffer); if(ch0=_) /以下划线开头的第二类标识符 buffer=fgetc(fp); while (isalpha(buffer) /读到的是字母 ch+i=buffer; buffer=fgetc(

14、fp); chi+1=0; /单词读完置上结束符号 printf(%s , 2)n,ch); id=2; return(buffer); if(ch0=|ch0=&|ch0=!) if(ch0=!) printf(%s ,4)n,ch); buffer=fgetc(fp); id=4; return(buffer);elsebuffer=fgetc(fp);ch1=buffer;if(ch0=ch1)printf(%s ,4)n,ch); buffer=fgetc(fp); id=4; return(buffer);elsech1=0;printf(%s ,5)n,ch); buffer=fg

15、etc(fp); id=4; return(buffer); if(ch0=*|ch0=/) /读入 * 、时输出为第4类运算符 printf(%s ,4)n,ch); buffer=fgetc(fp); id=4; return(buffer); if(ch0=|ch0=!|ch0=) /读入为 = ! 时，还要再判下一个读入的字符 buffer=fgetc(fp); / 再读入一个字符 if(buffer=) /如果下一个字符为= ch1=buffer; /把读到的字符加入数组ch ch2=0; printf(%s ,4)n,ch); /两个字符一起作为第4类运算符输出 else prin

16、tf(%s ,4)n,ch); /后面不是=的话直接作为第4类运算符输出 id=4; return(buffer); buffer=fgetc(fp); /继续读下一个字符 id=4; return(buffer); /返回下一个字符 if(ch0=+|ch0=-) buffer=fgetc(fp);ch1=buffer; ch2=0; if(ch0=ch1)/如果为 + - printf(%s ,4)n,ch); id=4; buffer=fgetc(fp); return(buffer); else if(id=4) /*在当前符号以前是运算符，则此时为正负号*/ if(isalpha(b

17、uffer)/如果-号后面是一位字符变量 ch1=0; printf(%s ,4) /-在字母前此时为单目运算符n,ch);id=4; else ch10=ch0; while (isdigit(buffer)|buffer=.|buffer=e) /读入一个完整的数字放在isdigit数组中 ch1+i=buffer; buffer=fgetc(fp); ch1i+1=0; /数组结束 printf(%s ,3)n,ch1); /输出数字为第三类 id=3; buffer=fgetc(fp); return(buffer); else /此时为加减号，只用输出一个，可是上面多读了一个，需要回

18、退 ch1=0; printf(%s ,4)n,ch); /buffer=fgetc(fp);此时 不用再读下一个字符了，直接返回当前buffer id=4; return(buffer); 六实验结果输入的源代码如下：在原来实现的基本功能的基础上实现了输出头文件，以下划线开头的标识符，与，或，非逻辑运算符，多位浮点数，负多位浮点数，科学计数法，负科学技术法，自增自减运算符，在字母前面的正负号为单目运算符，等功能，运算结果如下所示 实验二 LL（1）分析法一、实验目的：根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理

19、解。二、实验题目实验规定对下列文法，用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

20、)=#,) T t tSelect (TFS)=(,i Ss1 s s1 s1Select (S*FS)=*Select (S)=#,) + F f1 fSelect (F(E)=(Select (Fi)=i三、 算法流程图四、完整程序代码#include #include #include typedef struct type/*产生式类型定义 */ char origin;/*大写字符 */char array5;/*产生式右边字符 */int length;/*字符个数*/ type; void print();/*输出分析栈 */ void print1();/*输出剩余串*/ /各

21、变量定义： char ch,x; char A20;/*分析栈*/ char B20;/*剩余串*/ char v120=i,+,*,(,),#;/*终结符 */ char v220=E,G,T,S,F;/*非终结符 */ int j=0,k=0,b=0,top=0,l;/*L为输入串长度 */ int m=0,n=0; int flag,finish; type e,t,g,g1,s,s1,f,f1;/*结构体变量*/ type cha; type C1010;/*预测分析表数组*/ int main()e.length=2;g.length=2;g1.length=1;t.length=2

22、;s.length=3;s1.length=1;f.length=3;f1.length=1; /*把文法产生式赋值结构体*/e.origin=E;/e结构体变量的变量赋值 strcpy(e.array,TG);/ E:=TGg.origin=G;/g结构体变量的变量赋值 strcpy(g.array,+TG);/G:=+TGg1.origin=G;/g1结构体变量的变量赋值 g1.array0=;/G:=t.origin=T;/t结构体变量 的变量赋值 strcpy(t.array,FS);/T:=FSs.origin=S;/s结构体变量的变量赋值 strcpy(s.array,*FS);/

23、S:=*FS s1.origin=S;/s1结构体变量的变量赋值 s1.array0=;/S:=f.origin=F;/f结构体变量的变量赋值 strcpy(f.array,(E);/F:=(E)f1.origin=F;/f1结构体变量的变量赋值 f1.array0=i;/F:=ifor(m=0;m=4;m+)/*初始化分析表,5行5列*/for(n=0;n=5;n+)Cmn.origin=Null;/*全部赋为空*/ /*填充分析表*/ C00=e;C03=e; C11=g;C14=g1;C15=g1; C20=t;C23=t; C31=s1;C32=s;C34=C35=s1; C40=f1

24、;C43=f; do/*读入分析串*/ scanf(%c,&ch); if (ch!=i) &(ch!=+) &(ch!=*)&(ch!=()&(ch!=)&(ch!=#) /输入串一定要为i，+，*，（，），# printf(输入串中有非法字符n); exit(1);/非正常退出 Bj=ch; /如果输入合法就读入数组 b j+; while(ch!=#);/如果当前字符不是结束符# ,就一直读入 l=j;/*分析串长度*/ ch=B0;/*当前分析字符*/ Atop=#; A+top=E;/*#,E进栈*/ printf(步骤tt分析栈 tt剩余字符 tt所用产生式 n); do x=At

25、op-;/*x为当前栈顶字符*/输出栈顶字符 printf(%d,k+); printf(tt); for(j=0;j=5;j+)/*判断是否为终结符*/ if(x=v1j) /如果栈顶字符为任意一个终结符 flag=1; break; /设置标志位为1 if(flag=1)/*如果是终结符*/ if(x=#)/如果栈顶只剩下#,说明分析完毕该结束了 finish=1;/*结束标记*/ printf(acc!n);/*接受*/ getchar();/返回字符串#分析栈 getchar();/返回字符串#字符串 exit(0);/正常退出 if(x=ch)/如果当前栈顶字符 等于数组B中的终结符

26、 ,说明匹配 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

27、(j=0;j=0;j-)/*产生式逆序入栈*/A+top=cha.arrayj; if(Atop=)/*为空则不进栈*/ top-; while(x!=0);return 0;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);五、实验结果实验三 逆波兰式的产生及计算一、实验目的将用中缀

28、式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值二、实验题目如输入如下：21+（42-2）*15+6 ）-18#输出为：原来表达式： 21+（42-2）*15+6 ）- 18# 后缀表达式：21&42&2&-15&*6&+18&- 计算结果：609三、算法流程图图3-1 生成逆波兰式的程序流程图读入一个逆波兰算术表达式Ch=当前输入符号程序结束YNCh是运算符Ch=#NY将该字符入栈根据运算符的特点从栈顶部取出若干个运算对象进行该运算，将运算结果入栈图3-2 计算逆波兰式的程序流程图四、 完整程序代码#include#include#include#i

29、nclude#define max 100char strmax; /用于存放原来的表达式int top; /栈顶指针char stackmax; /定义栈，用于计算逆波兰式char exmax; /存放后缀表达式double _stackmax; /定义栈，用于计算逆波兰式子int flagmax; /用于区分+、-号的含义，0表示运算符，1表示正负号/生成逆波兰式void trans() memset(flag,0,sizeof(flag); /flag初始值设为0 char ch=str0;/ch是读入数组的第一个 int i=1,t=0;/t用来记录目标传长度 top=0; while

30、(ch!=#)/如果不是结束符 switch(ch)/逐个判断当前输入符号 case (:/如果当前是左括号 top+;/入栈 stacktop=ch; break; case ):/如果当前是右括号 while(stacktop!=()/如果栈顶不是左括号 ext=stacktop;/栈顶元素写到目标数组 top-;/如果栈顶元素刚好是左括号，直接弹出站 t+; top-; break; case : case : while(stacktop=|stacktop=) /设置,运算符优先级为最高 ext=stacktop;top-;t+;/如果是乘方运算符，乘方运算符出栈 top+;/如果不不是的话就入栈 stacktop=ch; break; case +: case -: /当ch为+、-号是，若前面相邻字符不是)或数字且后面相邻字符是数字时表示正负号 if(isdigit(stri) & !isdigit(stri-2) & stri-2!=) flagt=1; /标记符号为正负号 ext+=ch;/正负号直接进入目标数组 ch=stri+;/读取下一个数 while(ch=0&ch=9)|ch=.) /判别小数点 ext=ch;/如果当前字符是数字或者小数点，直接放到目标数组 t+