编译原理实验报告一、实验目的及要求1.通过本次实验，加深对LL(1)预测分析法原理的认识和理解。

2.构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子。

3.了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

二、运行环境：硬件：windows xp软件：visual c++6.0三、实验内容1、分析使用LR(1)的优点：(1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。

(2)LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现。

(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。

(4)LR分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。

为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。

当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。

如果仅知道栈内的文法符号就能确定栈顶是什么句柄。

LR分析表的转移函数本质上就是这样的有限自动机。

不过，这个有限自动机不需要根据每步动作读栈，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。

2、LR分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。

对所有的LR分析器总控程序都是相同的。

(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

分析器的动作就是由栈顶状态和当前输入符号所决定。

四、程序源代码：//edge.h#ifndef HEAD_EDGE#define HEAD_EDGE#include<string>using namespace std;extern int SUM;extern string NODE,ENODE;class edge{public:edge();string getlf();string getrg();string getfirst();string getfollow();string getselect();string getro();int getrlen();void newfirst(string w);void newfollow(string w);void newselect(string w);void delfirst();private:string left,right,first,follow,select;int rlen;};#endif///////////////////////////////////////////////////////// //////////////////////edge.cpp#include<iostream>#include "edge.h"using namespace std;edge::edge(){cin>>left>>right;rlen=right.length();if(NODE.find(left)>NODE.length()) NODE+=left;}string edge::getlf(){return left;}string edge::getrg(){return right;}string edge::getfirst(){return first;}string edge::getfollow(){return follow;}string edge::getselect(){return select;}string edge::getro(){string str;str+=right[0];return str;}int edge::getrlen(){return right.length();}void edge::newfirst(string w){int i;for(i=0;i<w.length();i++)if(first.find(w[i])>first.length())first+=w[i];}void edge::newfollow(string w){int i;for(i=0;i<w.length();i++)if(follow.find(w[i])>follow.length()&&w[i]!='*') follow+=w[i];}void edge::newselect(string w){int i;for(i=0;i<w.length();i++)if(select.find(w[i])>select.length()&&w[i]!='*') select+=w[i];}void edge::delfirst(){int i=first.find('*');first.erase(i,1);}//LL1.cpp#include<iostream>#include<string>#include "edge.h"using namespace std;int SUM;string NODE,ENODE;//计算firstvoid first(edge ni,edge *n,int x){int i,j;for(j=0;j<SUM;j++){if(ni.getlf()==n[j].getlf()){if(NODE.find(n[j].getro())<NODE.length()){for(i=0;i<SUM;i++)if(n[i].getlf()==n[j].getro())first(n[i],n,x);}elsen[x].newfirst(n[j].getro());}}}//计算followvoid follow(edge ni,edge *n,int x){int i,j,k,s;string str;for(i=0;i<ni.getrlen();i++){s=NODE.find(ni.getrg()[i]);if(s<NODE.length()&&s>-1) //是非终结符if(i<ni.getrlen()-1) //不在最右for(j=0;j<SUM;j++)if(n[j].getlf().find(ni.getrg()[i])==0){if(NODE.find(ni.getrg()[i+1])<NODE.length()){for(k=0;k<SUM;k++)if(n[k].getlf().find(ni.getrg()[i+1])==0){n[j].newfollow(n[k].getfirst());if(n[k].getfirst().find("*")<n[k].getfirst().length())n[j].newfollow(ni.getfollow());}}else{str.erase();str+=ni.getrg()[i+1];n[j].newfollow(str);}}}}//计算selectvoid select(edge &ni,edge *n){int i,j;if(ENODE.find(ni.getro())<ENODE.length()){ni.newselect(ni.getro());if(ni.getro()=="*")ni.newselect(ni.getfollow());}elsefor(i=0;i<ni.getrlen();i++)for(j=0;j<SUM;j++)if(ni.getrg()[i]==n[j].getlf()[0]){ni.newselect(n[j].getfirst());if(n[j].getfirst().find('*')>n[j].getfirst().length())return;}}//输出集合void out(string p){int i;if(p.length()==0)return;cout<<"{";for(i=0;i<p.length()-1;i++){cout<<p[i]<<",";}cout<<p[i]<<"}";}//连续输出符号void outfu(int a,string c){for(i=0;i<a;i++)cout<<c;}//输出预测分析表void outgraph(edge *n,string (*yc)[50]){int i,j,k;bool flag;for(i=0;i<ENODE.length();i++){if(ENODE[i]!='*'){outfu(10," ");cout<<ENODE[i];}}outfu(10," ");cout<<"#"<<endl;int x;for(i=0;i<NODE.length();i++){outfu(4," ");cout<<NODE[i];outfu(5," ");for(k=0;k<ENODE.length();k++){flag=1;for(j=0;j<SUM;j++){if(NODE[i]==n[j].getlf()[0]){x=n[j].getselect().find(ENODE[k]);if(x<n[j].getselect().length()&&x>-1){cout<<"->"<<n[j].getrg();yc[i][k]=n[j].getrg();outfu(9-n[j].getrlen()," ");flag=0;}x=n[j].getselect().find('#');if(k==ENODE.length()-1&&x<n[j].getselect().length()&&x>-1)cout<<"->"<<n[j].getrg();yc[i][j]=n[j].getrg();}}}if(flag&&ENODE[k]!='*')outfu(11," ");}cout<<endl;}}//分析符号串int pipei(string &chuan,string &fenxi,string (*yc)[50],int &b) {char ch,a;int x,i,j,k;b++;cout<<endl<<" "<<b;if(b>9)outfu(8," ");elseoutfu(9," ");cout<<fenxi;outfu(26-chuan.length()-fenxi.length()," ");cout<<chuan;outfu(10," ");a=chuan[0];ch=fenxi[fenxi.length()-1];x=ENODE.find(ch);if(x<ENODE.length()&&x>-1){if(ch==a){fenxi.erase(fenxi.length()-1,1);chuan.erase(0,1);cout<<"'"<<a<<"'匹配";if(pipei(chuan,fenxi,yc,b))return 1;elsereturn 0;}elsereturn 0;}else{if(ch=='#'){if(ch==a){cout<<"分析成功"<<endl;return 1;}elsereturn 0;}elseif(ch=='*'){fenxi.erase(fenxi.length()-1,1);if(pipei(chuan,fenxi,yc,b))return 1;elsereturn 0;}else{i=NODE.find(ch);if(a=='#'){x=ENODE.find('*');if(x<ENODE.length()&&x>-1)j=ENODE.length()-1;elsej=ENODE.length();}elsej=ENODE.find(a);if(yc[i][j].length()){cout<<NODE[i]<<"->"<<yc[i][j];fenxi.erase(fenxi.length()-1,1);for(k=yc[i][j].length()-1;k>-1;k--)if(yc[i][j][k]!='*')fenxi+=yc[i][j][k];if(pipei(chuan,fenxi,yc,b))return 1;elsereturn 0;}elsereturn 0;}}}void main(){edge *n;string str,(*yc)[50];int i,j,k;bool flag=0;cout<<"请输入上下文无关文法的总规则数："<<endl;cin>>SUM;cout<<"请输入具体规则（格式：左部右部，*为空）："<<endl;n=new edge[SUM];for(i=0;i<SUM;i++)for(j=0;j<n[i].getrlen();j++){str=n[i].getrg();if(NODE.find(str[j])>NODE.length()&&ENODE.find(str[j])>ENODE.lengt h())ENODE+=str[j];}//计算first集合for(i=0;i<SUM;i++){first(n[i],n,i);/*cout<<"First("<<n[i].getlf()<<")=";out(n[i].getfirst());cout<<endl;*/}//outfu(10,"~*~");cout<<endl;for(i=0;i<SUM;i++)if(n[i].getfirst().find("*")<n[i].getfirst().length()){if(NODE.find(n[i].getro())<NODE.length()){for(k=1;k<n[i].getrlen();k++){if(NODE.find(n[i].getrg()[k])<NODE.length()){for(j=0;j<SUM;j++){if(n[i].getrg()[k]==n[j].getlf()[0]){n[i].newfirst(n[j].getfirst());break;}}if(n[j].getfirst().find("*")>n[j].getfirst().length()){n[i].delfirst();break;}}}}}/*for(i=0;i<SUM;i++){cout<<"First("<<n[i].getlf()<<")=";out(n[i].getfirst());cout<<endl;}outfu(10,"~*~");cout<<endl;*///计算follow集合for(k=0;k<SUM;k++){for(i=0;i<SUM;i++){if(n[i].getlf()==n[0].getlf())n[i].newfollow("#");follow(n[i],n,i);}for(i=0;i<SUM;i++){for(j=0;j<SUM;j++)if(n[j].getrg().find(n[i].getlf())==n[j].getrlen()-1)n[i].newfollow(n[j].getfollow());/*cout<<"Follow("<<n[i].getlf()<<")=";out(n[i].getfollow());cout<<endl;*/}}//outfu(10,"~*~");cout<<endl;//计算select集合for(i=0;i<SUM;i++){select(n[i],n);/*cout<<"Select("<<n[i].getlf()<<"->"<<n[i].getrg()<<")=";out(n[i].getselect());cout<<endl;*/}for(i=0;i<NODE.length();i++){str.erase();for(j=0;j<SUM;j++)if(n[j].getlf()[0]==NODE[i]){if(!str.length())str=n[j].getselect();else{for(k=0;k<n[j].getselect().length();k++)if(str.find(n[j].getselect()[k])<str.length()){flag=1;break;}}}}/*for(i=0;i<SUM;i++){cout<<"Select("<<n[i].getlf()<<"->"<<n[i].getrg()<<")=";out(n[i].getselect());cout<<endl;}*///输出cout<<endl<<"非终结符";outfu(SUM," ");cout<<"First";outfu(SUM," ");cout<<"Follow"<<endl;outfu(5+SUM,"-*-");cout<<endl;for(i=0;i<NODE.length();i++){for(j=0;j<SUM;j++)if(NODE[i]==n[j].getlf()[0]){outfu(3," ");cout<<NODE[i];outfu(SUM+4," ");out(n[j].getfirst());outfu(SUM+4-2*n[j].getfirst().length()," ");out(n[j].getfollow());cout<<endl;break;}}outfu(5+SUM,"-*-");cout<<endl<<"判定结论：";if(flag){cout<<"该文法不是LL(1)文法!"<<endl;return;}else{cout<<"该文法是LL(1)文法!"<<endl;}//输出预测分析表cout<<endl<<"预测分析表如下："<<endl;yc=new string[NODE.length()][50];outgraph(n,yc);/*for(i=0;i<NODE.length();i++){for(j=0;j<ENODE.length();j++)if(yc[i][j].length())cout<<yc[i][j]<<" ";else outfu(10," ");cout<<endl;}*/string chuan,fenxi,fchuan;cout<<endl<<"请输入符号串：";cin>>chuan;fchuan=chuan;fenxi="#";fenxi+=NODE[0];//cout<<"chuan="<<chuan<<endl<<"fenxi="<<fenxi<<endl;//分析符号串i=0;cout<<endl<<"预测分析过程如下："<<endl;cout<<"步骤";outfu(8," ");cout<<"分析栈";outfu(10," ");cout<<"剩余输入串";outfu(10," ");cout<<"动作";if(pipei(chuan,fenxi,yc,i))cout<<endl<<"输入串"<<fchuan<<"是该文法的句子！"<<endl;elsecout<<endl<<"输入串"<<fchuan<<"不是该文法的句子！"<<endl;}五、解析结果：测试数据一：S→a︳^︳(T)T→SFF→,SFF→ε实验截图输入（a，（a））#后测试结果为测试数据二：S →ABS→bCA →*A →bB →*B →aDC →ADC →bD →aSD →c实验结果截图六、实验总结分析通过本次上机实验，我加深了对预测分析LL（1）分析法的理解，同时体验到了编译原理中一些算法的巧妙。