lr分析器实验报告分析

第1页共18页lr分析器实验报告分析一、实验目的与要求：（简述本次实验要求达到的目的，涉及到的相关知识点，实验的具体要求。）目的：掌握LR(1)分析法的基本原理掌握LR(1)分析表的构造方法掌握LR(1)驱动程序的构造方法要求：1.对LR(1)语法规则有明确的定义；2.编写的分析程序能够对实验结果进行正确的语法分析；3.对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成。二、实验内容（根据本次实验项目的具体任务和要求，完成相关内容，可包括：实验目的、算法原理、实验仪器、设备选型及连线图、算法描述或流程图、源代码、实验运行步骤、关键技术分析、测试数据与实验结果、其他）具体任务：构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从第2页共18页左向右扫描，和自底向上的语法分析方法。对下列文法，用LR（1）分析法对任意输入的符号串进行分析：（1）E-E+T（2）E-E—T（3）T-T*F（4）T-T/F（5）F-(E)（6）F-i输出的格式如下：(1)LR（1）分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串(3)输出过程如下：步骤状态栈符号栈剩余输入串动作10#i+i*i#移进(4)输入符号串为非法符号串(或者为合法符号串)第3页共18页备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。(2)在此位置输入符号串为用户自行输入的符号串。原理：LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现。同时利用数据结构中堆栈的性质，来分析一个具体的句型。步骤：分析一个LR（1）文法的产生式。正确无误的构造一个LR(1)的项目集。根据LR(1)的项目集构建LR(1)分析表。针对具体句型进行实例分析。关键技术分析：LR(1)文法中只有三个动作：移进，规约和接受，这三个动作也是通过查表得来的额，任何时候如果都是唯一确定这三个动作中的一个，我们就可以让LR(1)文法正确的运行。首先需要构建项目集，才能根据项目集的状态转换构建分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。分析栈，包括文法符号栈和相应第4页共18页的状态栈，它们均是先进后出栈。而分析器的动作就是由栈顶状态和当前输入符号所决定。流程图：代码：#includeiostream#includestack#includestringusingnamespacestd;第5页共18页stringaction[12][6]={S5,0,0,S4,0,0,//ACTION表0,S6,0,0,0,acc,0,r2,S7,0,r2,r2,0,r4,r4,0,r4,r4,S5,0,0,S4,0,0,0,r6,r6,0,r6,r6,S5,0,0,S4,0,0,S5,0,0,S4,0,0,0,S6,0,0,S11,0,0,r1,S7,0,r1,r1,0,r3,r3,0,r3,r3,0,r5,r5,0,r5,r5};intgotoarr[12][3]={1,2,3,//GOTO表0,0,0,0,0,0,0,0,0,8,2,3,第6页共18页0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0};charvt[6]={'i','+','*','(',')','#'};//存放终结符charvn[3]={'E','T','F'};//存放非终结符stringProduction[6]={E-E+T,E-T,T-T*F,T-F,F-(E),F-i};//产生式集合intcount=0;//记录当前进行处理的输入字符串字符位置intline=1;//记录处理的步骤数boolflag=false;intStatusNumber=1;//栈中状态数stringstacktd=#;//记录符号栈中内容intStatus[50]={0};//记录状态栈stackcharStack;//创建一个符号栈第7页共18页stackintstatus;//创建一个状态栈voidJudge(int&i,intj,chararr[],charch,strings){//判断输入串是否由文法终结符组成flag=false;for(intl=0;lj;l++){if(ch==arr[l]){flag=true;i=l;break;}}if(flag==false){cout\tErrorendl;count=s.size();}}第8页共18页voidOutputstatus(){//输出状态集for(inti=0;iStatusNumber;i++)coutStatus[i];}voidOutputstring(strings){//输出未处理的字符串for(inti=count;is.size();i++)couts.at(i);}voidOutput(strings){//输出步骤、状态集、符号集、输入串coutline\t;Outputstatus();cout\tstacktd\t;Outputstring(s);第9页共18页cout\t\t;line++;}voidShift(inti,strings){//移进函数SOutput(s);coutACTION[status.top(),s.at(count)]=Si,状态i入栈endl;status.push(i);//将状态i压进状态栈Status[StatusNumber]=i;//Status记录状态栈的内容Stack.push(s.at(count));//将当前面临的输入串符号压进符号栈stacktd=stacktd+s.at(count);//stacktd记录符号栈的内容count++;//当前面临的输入串字符往后移一位StatusNumber++;//状态数加一}voidGoto(stackintst1,stackcharst2,strings){//GoTo语句第10页共18页intj=-1;intch1=st1.top();charch2=st2.top();Judge(j,3,vn,ch2,s);//求得ch2在非终结符表中的位置if(gotoarr[ch1][j]==0){cout\tErrorendl;count=s.size();}else{status.push(gotoarr[ch1][j]);//新状态进栈Status[StatusNumber]=gotoarr[ch1][j];StatusNumber++;}}voidReduction(inti,strings){//归约函数ROutput(s);第11页共18页coutri:Production[i-1]归约，GoTo(;intN=Production[i-1].length()-3;for(intj=0;jN;j++){//消除要归约的状态及符号status.pop();Stack.pop();StatusNumber--;stacktd.erase(stacktd.length()-1);}coutstatus.top(),Production[i-1].at(0))=;Stack.push(Production[i-1].at(0));//符号进栈stacktd=stacktd+Stack.top();Goto(status,Stack,s);coutstatus.top()入栈endl;Status[StatusNumber]=status.top();}voidAnalyse(strings){//具体分析函数Stack.push('#');//初始化第12页共18页status.push(0);s=s+#;intt=-1;//记录ch在数组vt的位置while(counts.size()){inti=status.top();charch=s.at(count);Judge(t,6,vt,ch,s);if(flag==true){if(action[i][t]!=acc&&action[i][t]!=0){if(action[i][t].at(0)=='S'){action[i][t].erase(0,1);//删除action[i][t]的首字母SShift(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str())，将action[i][t]转换为整型第13页共18页action[i][t].insert(0,S);//将S添加回action[i][t]}elseif(action[i][t].at(0)=='r'){action[i][t].erase(0,1);//删除action[i][t]的首字母rReduction(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str())，将action[i][t]转换为整型action[i][t].insert(0,r);//将r添加回action[i][t]}}elseif(action[i][t]==0){cout\tErrorendl;break;}elseif(action[i][t]==acc)第14页共18页{Output(s);coutacc\t分析成功endl;break;}}elseif(flag==false)break;}}intmain(){strings;cout************************LR(1)分析*************************endl;cout本分析文法产生式为endl;for(intj=0;j6;j++)coutProduction[j]endl;cout************************LR(1)分析第15页共18页*************************endl;charT;do{cout输入字符串endl;cins;//输入要分析的字符串cout************************现进行如下分析*************************endl;cout步骤\t状态栈\t符号栈\t剩余输入串\t动作说明endl;Analyse(s);count=0;//记录当前进行处理的输入字符串字符位置line=1;//记录处理的步骤数stacktd=#;StatusNumber=1;while(!Stack.empty()){Stack.pop();}第16页共18页while(!status.empty()){status.pop();}cout是否继续分析,Y或y继续endl;cinT;}while(T=='y'||T=='Y');return0;}截图：第17页共18页三、实验分析与小结：（实验过程中的问题分析、产生的原因以及解决方法；实验结果分析；有待优化思路）经过这个实验的练习，通过对程序的分析，让我进一步了解LR（1）算法的思想以及它的进一步程序实现，让我对它的了解从简单的理论上升到程序实现的级别，有理论上升到实际，让我更清楚它的用途。在对实验的分析的时候，也遇到很多的问题，尽管上一个LL（1）分析法有些