计算机13-3班实验报告胡红旗

1、编译原理实验计算机与信息学院专业班级： 计算机科学与技术 13-3 班学生及学号2013211713胡课程教学班号 0002 班任课教师实验指导教师 实验地点第二、六机房2014 2015 学年第二 学期实验一词法分析设计一、实验功能：1）2）3）4）从源程序文件中读入字符。统计行数和列数用于错误单词的定位。删除空格类字符，包括回车、制表符空格。按拼写单词，并用（内码，属性）二元式表示。(属性值token的机内表示)5） 如果发现错误则出错6） 根据需要是否填写标识符表供以后各阶段使用。二、程序结构描述：keywords数组数组数组函数函数关键字optr separator算数运算符分界符Is

2、Key 判断是否是关键字，返回true 或false IsLetter 判断是否是字母，返回true 或false函数IsDigit 判断是否是数字，返回true 或false函数IsFloat 判断是否是小数，返回true 或false函数IsOptr 判断是否是算数运算符，返回true 或false函数 IsSeparator 判断是否是分界符，返回true 或false主函数:数组表达式字符串，然后对表达式字符进行相应处理主函数流程图：词法分析子程序简化框图三、实验结果实验总结：词法分析器是编译的基础，是后续如语法分析的重要的前提，所以必须要掌握。通过对词法分析器的编写，我对词法分析器有

3、了更清楚的认识，知道了具体在实践中，词法分析器是什么，虽然自己写的程序并不是很好，但是基本可以实现词法分析器的功能，同时对编译原理词法分析器中的有关概念，原理等也有了更具体的掌握。附录:源程序 #include #include #includeusing namespak;td;string keywords8=do,end,for,if,prf,scanf,then,while; string optr4=+,-,*,/;string separator6=,;,(,); bool IsKey(string ss) i;for(i=0;i=a)&(c=A)&(c=0&c=9)return

4、true; return false;/数字判断函数/判断是否是小数 bool IsFloat(string ss)k = 0;for(m = 0; m 1) return true; else return false;bool IsOptr(string ss) i; for(i=0;i4;i+)if(!strcmp(optri.c_str(),ss.c_str() return true ;return false;/算术运算符判断函数 bool IsSeparator(string ss) i; for(i=0;i6;i+)if(!strcmp(separatori.c_str(),s

5、s.c_str() return true;return false;/分界符判断函数main()/*string cc = 123; num = 0;for(y=0;ycc.length();y+)num += (ccy - 0) *(10.0,2-y);coutnumendl;*/coutplease input a program end with #endl; char a;j,t=0;char instring100; for(j=0;j100;j+)instringj=0; i=0;doa=getchar(); instringi+=a;while(a!=#);line=1,row

6、=0;string st=;for(j=0;j100;j+)if(instringj= )|(instringj=t) /空格，tab 健else if(instringj=n) line+;row=0;/换行行数加一处理else if(IsLetter(instringj)|instringj=_)st=; row+;/关键字、标识符的处理while(IsLetter(instringj)|IsDigit(instringj)|instringj=_)st+=instringj; j+;if(IsKey(st)/判断是否为关键字 查询关键字表；coutstt(st,1)ttt(line,ro

7、w)endl;关键字else/否则为标示符coutstt(st,6)tt标t(line,row)endl; j-;else if(IsDigit(instringj)/无符号整数处理st=;row+;while(IsDigit(instringj) | instringj = .)st+=instringj; j+;if(!(IsLetter(instringj)|instringj=_)识符/num = 0;hi xiaoshufor(y=0;yst.length();y+)num += (sty - 0) *(10.0,2-y);if(IsFloat(st)coutstterrorterr

8、ort(line,row)endl;j-;elsecoutstt(st,5)tt常数t(line,row)endl;j = j - k;else if(IsLetter(instringj)|instringj=_) while(IsLetter(instringj)|IsDigit(instringj)|instringj=_)st+=instringj; j+;coutstterror,terrort(line,row)endl;j-;elsest=; st+=instringj;if(IsOptr(st) /算术运算符处理row+; if(IsSeparator(st)|(instrin

9、gj+1=)|(instringj+1=t)|(instringj+1=n)|(instringj+1=)coutstt(st,3)tt算术运算符 (line,row)endl;else if(instringj = +) & (instringj+1 = +)cout+terrorterrort(line,row)endl;j+;else if(instringj = -) & (instringj+1 = -)cout-terrorterrort(line,row)endl;j+;elsewhile(!(IsSeparator(st)|(instringj+1= )|(instringj+

10、1=t)|(instringj+1=n)|(instringj+1=)st+=instringj+1; j+;coutstterrorterrort(line,row)endl;else if(IsSeparator(st)/分隔符处理row+;coutstt(st,2)ttt(line,row)endl;else switch(instringj)row+;case= : row+;cout=t(=,4)tt 关系运算符t(line,row) :row+;j+;if(instringj=)分界符cout=t(=,4)ttt(line,row)endl;else coutt(,4)tt 关系运

11、算符t(line,row)endl;j-;break;case :row+;j+;关系运算符if(instringj=)cout=t(=,4)tt(line,row)coutt(,4)ttt(line,row)endl;关系运算符elsecoutt(,4)tt 关系运算符t(line,row)endl;j-;break; case # :break;case 0:break;default:row+;coutinstringjterrorterrort(line,row)TG（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i二、程序结构

12、描述：模块结构：定义部分：定义常量、变量、数据结构。初始化：设立 LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；控制部分：从键盘输入一个表达式符号串；利用 LL(1)分析算法进行表达式处理：根据 LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。程序各个部分的实现：数组 Vn数组 Vt非终结符数组；终结符数组；数组 A存放作为栈使用；数组 B存放分析串；LL(1)分析程序流程三、实验结果：四、实验总结：通过对词 LL(1)语法分析程序的编程，初步理解了语法分析器的作用，了解了语法分析器的功能，也初步掌握了语法分析器的原理和

13、构造方法，虽然程序并不是完全有自己编写，但是还是经过自己的努力完成了一个LL(1)语法分析程序。语法分析是编译过程的部分，所以须要掌握，否则就学不好编译原理。通过对语法分析器的编写，加深了我对语法分析的理解和掌握，对也有了一定的提高。附录：源程序 #include #include #include #include#include编译原理的学习有很大的帮助。同时，对程序开发能力using namespastring ss;/td;动作char A20; char B20;char v120=i,+,-,*,/,(,),#;char v220=E,G,T,S,F;j=0,b=0,top=0,l

14、;/*L 为输入串长度 */typedef struct type/*产生式类型定义*/char origin;/*大写字符 */char array7;/*产生式右边字符 */length;/*字符个数*/type;type e,t,g,g0,g1,s,s0,s1,f,f1;/*结构体变量 */type C1010;/*/分析表void pr()/*输出分析栈 */a;/*指针*/ for(a=0;a=top+1;a+)prf(%c,Aa); prf(tt);void pr1()/*输出剩余串*/j;for(j=0;jb;j+)/*输出对齐符*/ prf( );for(j=b;j=l;j+)

15、prf(%c,Bj); prf(ttt);main()m,n,k=0,flag=0,finish=0; char ch,x;type cha;/*用来接受 Cmn*/*把文法产生式赋值结构体*/ 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;g0.origin=G; strcpy(g0.array,-TG); g0.length=3; g1.origin=G; g1.array0=; g1

16、.length=1; s.origin=S; strcpy(s.array,*FS); s.length=3; s0.origin=S; strcpy(s0.array,/FS); s0.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=7;n+) Cmn.origin=N;/*全部赋为空*/*填充分析表*/ C00=e;

17、C05=e; C11=g;C12=g0; C16=g1;C17=g1;C20=t;C25=t; C31=s1;C32=s1;C33=s; C34=s0; C36=s1;C37=s1;C40=f1;C45=f;coutpleast input a program end with #endl; doscanf(%c,&ch); Bj=ch;j+;while(ch!=#); l=j;/*分析串长度*/ch=B0;/*当前分析字符*/Atop=#; A+top=E;/*#,E进栈*/prf(步骤tt 分析栈 tt 剩余字符 t 所用产生式t 动作dox=Atop-;/*x 为当前栈顶字符*/ prf

18、(%d,k+);prf(tt);for(j=0;j=7;j+)/*判断是否为终结符*/ if(x=v1j)flag=1; break;if(flag=1)/*如果是终结符*/if(x=#)n);finish=1;/*结束标记*/cout分析成功!endl;/*接受 */ getchar();getchar();exit(1);if(x=ch)prpr pr();1();f(%c 匹配n,ch);ch=B+b;/*下一个输入字符*/flag=0;else/*出错处理*/prpr pr();1();f(%c 出错n,ch);/*输出出错终结符*/exit(1);else/*非终结符处理*/for(

19、j=0;j=4;j+) if(x=v2j)m=j;/*行号*/ break;for(j=0;j,cha.origin);/*输出产生式*/for(j=0;jcha.length;j+)prf(%c,cha.arrayj);/prf(n); cout=0;m-)if(cha.arraym != )ss += cha.arraym;if( ss != )coutpop,push(ss);else cout=0;j-)A+top=cha.arrayj;/*产生式逆序入栈*/if(Atop=)/*为空则不进栈*/ top-;coutendl;else/*出错处理*/prpr pr();1();f(%c

20、 出错n,x);/*输出出错非终结符*/exit(1);while(finish=0); return 0;实验三 LR(1)分析法 实验原理LR（1）分析法实验设计及算法(1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。二、程序结构LR 分析器由三个部分组成：

21、其中:SP 为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用 GOTOi，X=j 表示，规定当栈顶状态为i，遇到当前文法符号为X 时应转向状态j，X 为终结符或非终结符。ACTIONi，a规定了栈顶状态为 i 时遇到输入符号a 应执行。动作有四种可能：(1)移进：actioni，a= Sj：状态j 移入到状态栈，把a 移入到文法符号栈，其中i,j 表示状态号。归约：actioni，a=rk：当在栈顶形成句柄时，则归约为相应的非终结符 A，即文法中有A- B 的产生式，若 B 的长度为 R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R 个符号，即栈指针SP 减去 R，并把A 移入

22、文法符号栈内， j=GOTOi,A移进状态栈，其中i 为修改指针后的栈顶状态。接受 acc:当归约到文法符号栈中只剩文法的开始符号S 时，并且输入符号串已结束即当前输入符是#，则为分析成功。报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。三、实验结果：四、实验总结LR 分析法是一个有效的自下而上的分析技术，是可用于一类上下无关文法的语法分析，但是 LR 也是比较难以理解的一个分析法，无论是 action 还是goto,我认为都比较难。通过对LR 分析器的编写，可以更好的理解LR 分析法，理解 LR 的一些基本概念，基本原理，action 以

23、及goto 表的建立，分析的过程等，我都有了很好的理解，无论是对 action 表的动作，还是goto 表的状态转化，都要相应的掌握，LR 分析法，是一个重要的分析技术，是编译原理中很重要的一部分，掌握LR 分析法，对编译原理的学习有很大的帮助。附录：源程序#includeusing namespatd;constMaxLen = 20; constLength = 20; char ch;char Y;char strTokenLength; bool flag = true;po=0;step = 1;class stackpublic:stack()count = 0;stack()bo

24、ol empty()const if(count = 0)return true;return false;bool full()constif(count = MaxLen) return true;return false;bool get_top(char &c)const/获取栈顶符号 if(empty()return false;elsec = dount-1;return true;bool push(const char c)/压栈 if(full()return false;dount+ = c;return true;bool pop()/出栈 if(empty()retur

25、n false; count-;return true;void out()/输出栈中元素for(i=0;icount;i+)coutdatai;coutt;void out_1()for(i=0;icount;i+)cout(coutt;)datai;private:count;/栈长度char dataMaxLen;/栈中元素;stack S,X;/状态栈与符号栈void pr(for(i,char*c)/输出剩余的输入串j=i;jLength;j+)coutcj;coutt;void Goto(if(i = 0)i,char c)if(c = E)S.push(1);cout,GOTO(

26、0,E)=1 入栈endl;else if(c = T)S.push(2);cout,GOTO(0,T)=2 入栈endl;else if(c = F)S.push(3);cout,GOTO(0,F)=3 入栈endl;elseflag = false;else if(i = 4) if(c = E)S.push(8);cout,GOTO(4,E)=8 入栈endl;else if(c = T)S.push(2);cout,GOTO(4,T)=2 入栈endl;else if(c = F)S.push(3);cout,GOTO(4,F)=3 入栈endl;elseflag = false;el

27、se if(i = 6) if(c = T)S.push(9);cout,GOTO(6,T)入栈endl;else if(c = F)S.push(3);cout,GOTO(6,F)=3 入栈endl;elseflag = false;else if(i=7)if(c=F)S.push(10);cout,GOTO(7,F)=10 入栈endl;elseflag = false;void Action_0()/状态为 0 if(ch = i)coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION0,i=S5,状态 5 入栈endl;

28、S.push(5);X.push(ch);ch = strTokenpo+;else if(ch = () coutstep+t;S.out_1();X.out();pr(po-1,strToken);coutACTION0,(=S4,状态 4 入栈endl; S.push(4);X.push(ch);ch = strTokenpo+;elseflag = false;void Action_1()/状态为 1 if(ch = +)coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION0,+=S6,状态 6 入栈endl; S.pu

29、sh(6);X.push(ch);ch = strTokenpo+;else if(ch = #) flag = false;coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutAcc:分析成功endl;elseflag = false;void Action_2()/状态为 2 if(ch = *)coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION2,*=S7,状态 7 入栈endl; S.push(7);X.push(ch);ch = strTokenpo+;else if

30、(ch = + | ch = ) | ch = #) coutstep+t;S.out_1();X.out();X.pop(); X.push(E);pr(po-1,strToken);coutT 规约; S.pop();S.get_top(Y);Goto(Y),E);elseflag = false;void Action_3()/状态为 3if(ch = + | ch = * | ch= ) | ch = #) coutstep+t;S.out_1();X.out();X.pop(); X.push(T);pr(po-1,strToken);coutF 规约; S.pop();S.get_

31、top(Y);Goto(Y),T);elseflag = false;void Action_4_6_7(if(ch = i)x)/状态为 4,6,7coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION;coutx,i=S5,状态 5 入栈endl; S.push(5);X.push(ch);ch = strTokenpo+;else if(ch = () coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION;coutx,(=S4,状态 4 入栈endl; S.pus

32、h(4);X.push(ch);ch = strTokenpo+;elseflag = false;void Action_5()/状态为 5if( (ch = +) | (ch = *) | (ch = ) | (ch = #) coutstep+t;S.out_1();X.out();X.pop(); X.push(F);pr(po-1,strToken);couti 规约; S.pop();S.get_top(Y);Goto(Y),F);elseflag = false;void Action_8()/状态为 8 if(ch = +)coutstep+t; S.out_1();X.out

33、();pr(po-1,strToken);coutACTION8,+=S6,状态 6 入栈endl; S.push(6);X.push(ch);ch = strTokenpo+;else if(ch = ) coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION8,)=S11,状态 11 入栈endl; S.push(11);X.push(ch);ch = strTokenpo+;elseflag = false;void Action_9()/状态为 9 if(ch = *)coutstep+t; S.out_1();X.out();pr(po-1,strToken);coutACTION9,*=S7,状态 7 入栈endl; S.push(7);X.push(ch)