编译原理实验报告合肥工业大学版

1、word编译原理实验报告合肥工业大学计算机科学与技术实验一 词法分析设计1、 实验功能：对输入的txt文件内的内容进行词法分析：由文件流输入test.txt中的内容，对文件中的各类字符进行词法分析打印出分析后的结果；二、程序结构描述：源代码见附录1、 利用Key进行构造并存储关键字表；利用optr进行构造并存储运算符表；利用separator进行构造并存储分界符表；2、 bool IsKey(string ss) 判断是否是关键字函数假设是关键字返回true,否那么返回false; bool IsLetter(char c) 判断当前字符是否字母，假设是返回true,否那么返回false;bo

2、ol IsDigit(char c) 判断当前字符是否是数字，假设是返回true,否那么返回false；bool IsOptr(string ss) 判断当前字符是否是运算符，假设是返回true，否那么返回false；bool IsSeparator(string ss) 判断当前字符是否是分界符，假设是返回true，否那么返回false；void analyse(ifstream &in) 分析函数构造；关系运算符通过switch来进行判断；三、实验结果实验总结：词法分析的程序是自己亲手做的，在实现各个函数时花了不少功夫，1、 要考虑到什么时候该退一字符，否那么将会导致字符漏读甚至造

3、成字符重复读取。2、 在实现行数和列数打印时要考虑到row+和line+应该放在什么位置上才可以，如当读取一个n时line要增加一，而row需要归0处理，在读取某一字符串或字符后row需要加一；3、 对于关系运算符用switch结构进行选择判断即可解决一个字符和两个字符的运算符之间的差异；4、 将自己学过的知识应用到实践中是件不怎么容易的事情，只有亲身尝试将知识转化成程序才能防止眼高手低，对于知识的理解也必将更加深刻。实验二 LL(1)分析法1、 实验原理： 1、写出LL1分析法的思想：当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下的分析程序，这个分析程序是有一组递归

4、过程组成的，每个过程对应文法的一个非终结符。实现LL(1)分析的一种有效的方法是使用一张分析表和一个站进行联合控制。预测分析表是一个MA,a形式的矩阵，存储着分析规那么；栈STACK用于存放文法符号。从栈顶取符号，按照分析表给出的规那么进行有步骤的分析。2. 实验要求实现的文法：1E->TG2G->+TG|TG3G->4T->FS5S->*FS|/FS6S->7F->(E)8F->i2、 程序结构：各个模块：1定义局部：定义常量、变量、数据结构。 2初始化：设立LL(1)分析表、初始化变量空间包括堆栈、结构体、数组、临时变量等；

5、0;3控制局部：从键盘输入一个表达式符号串； 4利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈或其他操作，输出分析结果，如果遇到错误那么显示错误信息。程序各个局部的实现：(1) Vn存储非终结符数组； Vt存储终结符数组； char strTokenLength;/存储规约表达式 struct LL/ll(1)char *c分析表的构造字初始化 Class stack实现栈的要求功能：初始化，判断空满，入栈出栈等； Run()函数实现LL(1)文法分析的函数：先将表达式字符入栈，#最先入栈底，依次取栈顶符号，查和符号栈和分析表，进行相应的操作。 3、

6、 实验结果：测试方法：运行程序，输入需要分析的语句测试结果如下：4、 实验总结：1、 出现以下两种情况说明遇到了语法错误:(1) 栈顶的终结符与当前的输入符号不匹配。(2) 非终结符A处于栈顶，面临输入符号为a,但分析表M中MA,a为空。发现错误后要尽快的从错误中恢复过来使分析能继续进行下去。2、对于符号的入栈出栈，哪个应该先入栈，栈顶是哪个元素需要搞清楚，不然得到的结果肯定不对。实验三 LR(1)分析法一实验原理LR1分析法实验设计思想及算法 (1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不

7、同时，分析表将不同，分析表又可以分为动作表ACTION和状态转换GOTO表两个局部，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。二、程序结构u LR分析器由三个局部组成：u 其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi，X=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。u ACTIONi，a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进： actioni，a= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中

8、i,j表示状态号。(2)归约： actioni，a=rk：当在栈顶形成句柄时，那么归约为相应的非终结符A，即文法中有A- B的产生式，假设B的长度为R(即|B|=R)，那么从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc: 当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，那么为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，那么报错，说明输入端不是该文法能接受的符号串。3、 实验结果：程序测试：输入需

9、要规约的字符串测试结果：4、 实验总结1、 与算符优先分析方法比拟，用LR分析时，设计特定出错处理子程序比拟容易，因为不会发生不正确的归约。在分析表的每一个空项内，可以填入一个指示器，指向特定的出错处理子程序，第一类错误的处理一般采用插入、删除或修改的方法，但要注意，不能从栈内移去任何那种状态，它代表已成功地分析了程序中的某一局部。2、LR分析法的归约过程是标准推导的逆过程，所以LR分析过程是一种标准归约过程。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句

10、柄。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它LR类分析器的根底。因此，首先应学好LR(0)工程集标准族构造的根本原理和方法。当K=1时，已能满足当前绝大多数高级语言编译程序实现的需要。SLR(1)分析是为学习LR(1)分析做准备，LR(1)工程集族的构造是LALR(1)分析器的构造原理和根底。LALR(1) 分析器是当前大多数高级程序设计语言编译程序所采用的语法分析技术，也是编译程序语法分析器自动构造工具YACC的实现根本原理。由此，LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法都必须深入理解和掌握。3、经过以

11、上三个实验的锤炼，不得不说自己编译原理这门课的认识又提高了一个阶层，对编译原理的知识运用更加深入，编写过程中遇到不少的问题，结合课本及强大的网络资源，在完成的过程中得到很多收获，不仅来自于对知识点的了解更加深入，更是对自己编程能力的一次很好的锻炼，希望有更多这样实验的时机。4、本人很希望在完成实验后，老师可以根据自己讲的课本，将自己所写的程序花一段时间来讲解，我想这样会对不会编写的是一种教学，对会了的同学是一种典范效应，可以让我们有个目标追求，这样我们收获了的也会更加准确与丰富。附录：实验一源代码：#include<iostream>#include<fstream>#

12、include<string> using namespace std;string key8="do","end","for","if","printf","scanf","then","while"string optr4="+","-","*","/" string separator6=",",""

13、,"","","(",")"char ch; /判断是否为保存字 bool IsKey(string ss) int i; for(i=0;i<8;i+) if(!strcmp(keyi.c_str(),ss.c_str() return true; return false;/字母判断函数 bool IsLetter(char c) if(c>='a')&&(c<='z')|(c>='A')&&(c<=&

14、#39;Z') return true; return false; /数字判断函数 bool IsDigit(char c) if(c>='0'&&c<='9') return true; return false; /运算符判断函数 bool IsOptr(string ss) int i; for(i=0;i<4;i+) if(!strcmp(optri.c_str(),ss.c_str() return true ; return false;/分界符判断函数 bool IsSeparator(string ss

15、) int i; for(i=0;i<6;i+) if(!strcmp(separatori.c_str(),ss.c_str() return true;return false;void analyse(ifstream &in) string st=""char ch;int line=1,row=0;while(in.get(ch) st="" if(ch=' ')|(ch='t') /空格，tab健 elseif(ch='n') line+;row=0; /换行行数加一处理 else

16、 if(IsLetter(ch) /关键字、标识符的处理 row+; while(IsLetter(ch)|IsDigit(ch) st+=ch; in.get(ch); in.seekg(-1,ios:cur);/文件指针光标后退一个字节 if(IsKey(st) /判断是否为关键字 查询关键字表； cout<<st<<"t("<<st<<","<<1<<")"<<'t'<<'t'<<"

17、;关键字"<<'t'<<"("<<line<<","<<row<<")"<<endl; else /否那么为标示符 cout<<st<<"t("<<st<<","<<2<<")"<<'t'<<'t'<<"标识符"

18、;<<'t'<<"("<<line<<","<<row<<")"<<endl; else if(IsDigit(ch) /无符号整数处理 row+; while(IsDigit(ch) st+=ch; ch=in.get(); in.seekg(-1,ios:cur); cout<<st<<"t("<<st<<","<<3<<

19、")"<<'t'<<'t'<<"常数"<<'t'<<"("<<line<<","<<row<<")"<<endl; / break; else st="" st+=ch; if(IsOptr(st)/运算符处理 row+; cout<<st<<"t("<<

20、st<<","<<4<<")"<<'t'<<'t'<<"运算符"<<"("<<line<<","<<row<<")"<<endl; else if(IsSeparator(st)/分隔符处理 row+; cout<<st<<"t("<<st<

21、<","<<5<<")"<<'t'<<'t'<<"分界符"<<'t'<<"("<<line<<","<<row<<")"<<endl; else switch(ch)row+; case'=' : row+;cout<<"="<

22、<"t("<<"="<<","<<"6"<<")"<<'t'<<"t关系运算符"<<'t'<<"("<<line<<","<<row<<")"<<endl; case'>' :row+;ch=in.get

23、(); if(ch='=') cout<<">="<<'t'<<"("<<">="<<","<<"6"<<")"<<'t'<<"t关系运算符"<<'t'<<"("<<line<<","&l

24、t;<row<<")"<<endl; else cout<<">"<<"t("<<">"<<","<<"6"<<")"<<'t'<<"t关系运算符"<<'t'<<"("<<line<<",&q

25、uot;<<row<<")"<<endl; in.seekg(-1,ios:cur); break; case'<' :row+;ch=in.get(); if(ch='=')cout<<"<="<<'t'<<"("<<"="<<","<<"6"<<")"<<&quo

26、t;t关系运算符"<<'t'<<"("<<line<<","<<row<<")"<<endl; else if(ch='>') cout<<"<>"<<'t'<<"("<<"<>"<<","<<"6&quo

27、t;<<")"<<'t'<<"t关系运算符"<<'t'<<"("<<line<<","<<row<<")"<<endl; elsecout<<"<"<<"t("<<"<"<<","<<"

28、6"<<")"<<"t"<<"t关系运算符"<<'t'<<"("<<line<<","<<row<<")"<<endl; in.seekg(-1,ios:cur); break; default :row+; cout<<ch<<'t'<<"t$无法识别字符"&

29、lt;<'t'<<"("<<line<<","<<row<<")"<<endl; int main() ifstream in; in.open("test.txt",ios:in); cout<<"关键字1 标识符2 常数3 运算符4 分隔符5关系运算符6"<<endl; if(in.is_open() analyse(in); in.close(); system("

30、;pause"); else cout<<"文件操作出错"<<endl; 实验二源代码：#include<iostream>using namespace std;const int MaxLen=20; /初始化栈的长度 const int Length=20;/初始化数组长度 char Vn5='E','G','T','S','F'/非终结符数组 char Vt8='i','(',')','

31、+','-','*','/','#'/终结符数组 char ch,X;/ch读当前字符，X获取栈顶元素 char strTokenLength;/存储规约表达式 struct LL/ll(1)分析表的构造字初始化 char*c;LL E8="TG","TG","error","error","error","error","error","error"LL G8=&

32、quot;error","error","null","+TG","-TG","error","error","null"LL T8="FS","FS","error","error","error","error","error","error"LL S8="error&quo

33、t;,"error","null","null","null","*FS","/FS","null"LL F8="i","(E)","error","error","error","error","error","error"class stack/栈的构造及初始化 public: stack();

34、/初始化 bool empty() const;/是否为空 bool full() const;/是否已满 bool get_top(char &c)const;/取栈顶元素 bool push(const char c);/入栈 bool pop();/删除栈顶元素 void out();/输出栈中元素 stack()/析构 private: int count;/栈长度 char dataMaxLen;/栈中元素 ;stack:stack() count=0;bool stack:empty() const if(count=0) return true; return false

35、;bool stack:full() const if(count=MaxLen) return true; return false;bool stack:get_top(char &c)const if(empty() return false; else c=datacount-1; return true; bool stack:push(const char c) if(full() return false; datacount+=c; return true;bool stack:pop() if(empty() return false; count-; return

36、true;void stack:out() for(int i=0;i<count;i+) cout<<datai; cout<<'t'int length(char *c) int l=0; for(int i=0;ci!='0'i+) l+; return l;void print(int i,char*c)/剩余输入串的输出 for(int j=i;j<Length;j+) cout<<cj; cout<<'t' void run() bool flag=true;/循环条件 in

37、t step=0,point=0;/步骤、指针 int len;/长度 cout<<"输入规约的字符串："<<endl; cin>>strToken; ch=strTokenpoint+;/读取第一个字符 stack s; s.push('#');/栈中数据初始化 s.push('E'); s.get_top(X);/取栈顶元素 cout<<"步骤t"<<"分析栈t"<<"剩余输入串tt"<<&quo

38、t;所用产生式t"<<"动作"<<endl; cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<'t'<<"初始化"<<endl; while(flag) if(X=Vt0)|(X=Vt1)|(X=Vt2)|(X=Vt3)|(X=Vt4)|(X=Vt5)|(X=Vt6) /判断是否为终结符不包括# if(X=ch)/终结符,识别，进行下一字符规约 s.pop(); s

39、.get_top(X); ch=strTokenpoint+; cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<'t'<<"GETNEXT(I)"<<endl; else flag=false; else if(X='#')/规约结束 if(X=ch) cout<<step+<<'t' s.out(); print(point-1,strToken); cout&

40、lt;<X<<"->"<<ch<<'t'<<"结束"<<endl; s.pop(); flag=false; else flag=false; else if(X=Vn0) /非终结符E for(int i=0;i<8;i+)/查分析表 if(ch=Vti) if(strcmp(Ei.c,"error")=0)/出错 flag=false; else /对形如 X->X1X2的产生式进行入栈操作 s.pop(); len=length(

41、Ei.c)-1; for(int j=len;j>=0;j-) s.push(Ei.cj); cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<X<<"->"<<Ei.c<<'t'<<"POP,PUSH(" for(int j=len;j>=0;j-) cout<<Ei.cj; cout<<")"<<en

42、dl; s.get_top(X); else if(X=Vn1) /同上，处理 G for(int i=0;i<8;i+) if(ch=Vti) if(strcmp(Gi.c,"null")=0) s.pop(); cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<X<<"->"<<""<<'t'<<"POP"<<

43、endl; s.get_top(X); else if(strcmp(Gi.c,"error")=0) flag=false; else s.pop(); len=length(Gi.c)-1; for(int j=len;j>=0;j-) s.push(Gi.cj); cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<X<<"->"<<Gi.c<<'t'<<&qu

44、ot;POP,PUSH(" for(int j=len;j>=0;j-) cout<<Gi.cj; cout<<")"<<endl; s.get_top(X); else if(X=Vn2) /同上 处理 T for(int i=0;i<8;i+) if(ch=Vti) if(strcmp(Ti.c,"error")=0) flag=false; else s.pop(); len=length(Ti.c)-1; for(int j=len;j>=0;j-) s.push(Ti.cj); c

45、out<<step+<<'t' s.out(); print(point-1,strToken); cout<<X<<"->"<<Ti.c<<'t'<<"POP,PUSH(" for(int j=len;j>=0;j-) cout<<Ti.cj; cout<<")"<<endl; s.get_top(X); else if(X=Vn3)/同上 处理 S for(int i=

46、0;i<8;i+) if(ch=Vti) if(strcmp(Si.c,"null")=0) s.pop(); cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<X<<"->"<<""<<'t'<<"POP"<<endl; s.get_top(X); else if(strcmp(Si.c,"error&

47、quot;)=0) flag=false; else s.pop(); len=length(Si.c)-1; for(int j=len;j>=0;j-) s.push(Si.cj); cout<<step+<<'t' s.out(); print(point-1,strToken); cout<<X<<"->"<<Si.c<<'t'<<"POP,PUSH(" for(int j=len;j>=0;j-) cout<

48、;<Si.cj; cout<<")"<<endl; s.get_top(X); else if(X=Vn4) /同上 处理 F for(int i=0;i<7;i+) if(ch=Vti) if(strcmp(Fi.c,"error")=0) flag=false; else s.pop(); len=length(Fi.c)-1; for(int j=len;j>=0;j-) s.push(Fi.cj); cout<<step+<<'t' s.out(); print(p

49、oint-1,strToken); cout<<X<<"->"<<Fi.c<<'t'<<"POP,PUSH(" for(int j=len;j>=0;j-) cout<<Fi.cj; cout<<")"<<endl; s.get_top(X); else /出错处理 flag= false; int main() cout<<"实验二"<<endl; run(); sy

50、stem("pause"); return 0;实验三源代码：#include<iostream>using namespace std;const int MaxLen=20; /初始化栈的长度 const int Length=20;/初始化数组长度char ch,Y;/全局变量，ch用于读当前字符，Y用于获取栈顶元素 char strTokenLength;/存储规约表达式bool flag=true;/循环条件 int point=0,step=1;/步骤、指针class stack/栈的构造及初始化 public: stack();/初始化 bool

51、empty() const;/是否为空 bool full() const;/是否已满 bool get_top(char &c)const;/取栈顶元素 bool push(const char c);/入栈 bool pop(); void out();/输出栈中元素 void out1(); stack()/析构 private: int count;/栈长度 char dataMaxLen;/栈中元素 ;stack l,r;/l代表符号栈，r代表状态栈 stack:stack() count=0;bool stack:empty() const if(count=0) retu

52、rn true; return false;bool stack:full() const if(count=MaxLen) return true; return false;bool stack:get_top(char &c)const if(empty() return false; else c=datacount-1; return true; bool stack:push(const char c) if(full() return false; datacount+=c; return true;bool stack:pop() if(empty() return false; count-; return true;void stack:out() for(int i=0;i<count;i+) cout<<datai; cout<<'t'void stack:out1() for(int i=0;i<count;i+) cout<<int(datai); cout<<'t&