LR(1)分析法

计算机科学与技术系实验报告专业名称计算机科学与技术课程名称编译原理项目名称LR(1)分析法班级学号姓名同组人员无实验日期2016.11.4一、实验目的与要求：（简述本次实验要求达到的目的，涉及到的相关知识点，实验的具体要求。）目的：掌握LR(1)分析法的基本原理掌握LR(1)分析表的构造方法掌握LR(1)驱动程序的构造方法要求：1.对LR(1)语法规则有明确的定义；2.编写的分析程序能够对实验结果进行正确的语法分析；3.对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成。二、实验内容（根据本次实验项目的具体任务和要求，完成相关内容，可包括：实验目的、算法原理、实验仪器、设备选型及连线图、算法描述或流程图、源代码、实验运行步骤、关键技术分析、测试数据与实验结果、其他）具体任务：构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。对下列文法，用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)输入符号串为非法符号串(或者为合法符号串)备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。(2)在此位置输入符号串为用户自行输入的符号串。原理：LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现。同时利用数据结构中堆栈的性质，来分析一个具体的句型。步骤：分析一个LR（1）文法的产生式。正确无误的构造一个LR(1)的项目集。根据LR(1)的项目集构建LR(1)分析表。针对具体句型进行实例分析。关键技术分析：LR(1)文法中只有三个动作：移进，规约和接受，这三个动作也是通过查表得来的额，任何时候如果都是唯一确定这三个动作中的一个，我们就可以让LR(1)文法正确的运行。首先需要构建项目集，才能根据项目集的状态转换构建分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。而分析器的动作就是由栈顶状态和当前输入符号所决定。流程图：代码：#includeiostream#includestack#includestringusingnamespacestd;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,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;//创建一个符号栈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();}}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);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语句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);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('#');//初始化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]转换为整型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){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)分析*************************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();}while(!status.empty()){status.pop();}cout是否继续分析,Y或y继续endl;cinT;}while(T=='y'||T=='Y');return0;}截图：三、实验分析与小结：（实验过程中的问题分析、产生的原因以及解决方法；实验结果分析；有待优化思路）经过这个实验的练习，通过对程序的分析，让我进一步了解LR（1）算法的思想以及它的进一步程序实现，让我对它的了解从简单的理论上升到程序实现的级别，有理论上升到实际，让我更清楚它的用途。在对实验的分析的时候，也遇到很多的问题，尽管上一个LL（1）分析法有些启发，但是刚开始根本想不到用程序怎么实现这么繁杂的LR（1）文法，后来看了程序才知道，才转过来弯，通过对这个程序的分析与揣摩，让自己对这方