搜索
基于LR(1)的语法分析程序1.设计目的：设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。2.设计要求：（1）根据LR(1)分析法编写一个语法分析程序，.输入已给定文法，直接输入根据己知文法构造的LR(1)分析表。（2）对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。3.设计过程：3.1LR(1)文法的含义：LR分析法的规约过程是规范推倒的逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR（0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。3.2设计思想：根据自身实际情况，给定了编译原理书中的一个LR(1)文法，求出其项目集合转换函数，从而得出此LR(1)文法的分析表，在程序中直接输出此分析表，并根据分析表中的内容可对输入的符号串进行分析，判断是接受还是出错，从而得出该输入的符号串是否为文法的一个句子。3.3算法描述：1.CLOSURE(I)的构造CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到：(1)I中的所有项目都属于CLOSURE(I)；(2)若项目[A→a.Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRSTβa中的每一个中介符b,如果[β→.ξ,b]原来不在CLOSURE(I)中，则把它加进去；(3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。2.GO(I,X)的构造GO(I,X)=CLOSURE(J)其中J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于I}3.FIRST集合的构造在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。方法如下：连续使用下面的规则，直到每个集合FIRST不再增大为止。（1）若X属于VT，则FIRST(X)={X}。（2）若X属于VN，且有产生式X→a…，则把A加入到FIRST(X)中；若X→ξ也是一条产生式，则把ξ也加入到FIRST中。4.LR(1)分析表的构造在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。4设计内容4.1主要变量说明：#defineSIZE20//宏定义，定义sSIZE为12#definesSIZE12//宏定义，定义sSIZE为12#defineaSIZE6//宏定义，定义aSIZE为6#definegSIZE2//宏定义，定义gSIZE为2#definegeSIZE6//宏定义，定义geSIZE为6typedefstructGe{charhead;//文法规则左部chargen[5];//文法规则右部}Generate;//生成符号串的基本数据结构体typedefstructA{intst[aSIZE];//遇到终结符时下一个动作状态intre[aSIZE];//遇到非终结符时进行规约}Action;//动作表的基本数据结构体typedefstructG{charhead[gSIZE];//状态转换时遇到的非终结符intgt[gSIZE];//标记下一个状态}GOTO;//GOTO表的基本数据结构体intstatus[SIZE];//状态栈intsta_Index;//状态栈栈顶标记charsymbol[SIZE];//符号栈intsym_Index;//当前符号栈的标记charexpression[SIZE];//输入的符号串intexp_Index;//输入符号串的标记intexp_top;//输入符号串的栈顶元素intstep;//计算步骤intIsAccept=0;//初始化接受状态标志置为0Generategene[geSIZE+1];Actionact[sSIZE];GOTOgo[sSIZE];4.2程序流程图：NY输入一个待判断的符号串进行分析进行归约分析分析成功结束开始输出分析结果4.3运行结果：运行后进入界面：上图是编译运行后进入的主界面，给出了给定文法、分析表，要求出入一个要进行分析的符号串。输入错误字符串beD：上图中含有非终结符，不符合要输入指定的几个非终结符的要求，所以提示错误。输入字符串aed：上图输入的符号串符合要求，可见结果为接受状态，为该文法的句子。输入字符串bcd:上图输入的符号串符合要求，但是进行分析时发现不能进行规约，结果错误，不是该文法的句子。5程序关键代码：voidInitlize(void)//将终结符规约时所对应的要使用的{文法规则gene[1].head='S';strcpy(gene[1].gen,aAd);gene[2].head='S';strcpy(gene[2].gen,bAc);gene[3].head='S';strcpy(gene[3].gen,aec);gene[4].head='S';strcpy(gene[4].gen,bed);gene[5].head='A';strcpy(gene[5].gen,e);voidReduce(intsta,charsymb,intcol)//执行规约过程的函数{inti=0;for(i=0;istrlen(gene[act[sta].re[col]].gen);i++){symbol[sym_Index--]='\0';}symbol[++sym_Index]=gene[act[sta].re[col]].head;for(i=0;istrlen(gene[act[sta].re[col]].gen);i++){status[sta_Index-i]='\0';}sta_Index-=i;GOTOTable(status[sta_Index],symbol[sym_Index]);}voidActionTable(intsta,charsymb,intcol)//动作表{if(sta==1&&col==5){printf(ACCEPT\n);IsAccept=1;return;}if(act[sta].st[col]!=0){printf(Action\n);status[++sta_Index]=act[sta].st[col];symbol[++sym_Index]=symb;exp_top++;}elseif(act[sta].re[col]!=0){printf(Reduce\n);Reduce(sta,symb,col);}else{printf(ERROR\n);getchar();exit(1);}}voidGOTOTable(intsta,charsymb)//GOTO表{inti=0;for(i=0;isSIZE;i++){if(go[sta].head[i]==symb){status[++sta_Index]=go[sta].gt[i];return;}}}voidLaunch(void)//输出对符号串的状态分析表的函数{ints=status[sta_Index];charexp=expression[exp_top];charsym=symbol[sym_Index];while(IsAccept!=1){s=status[sta_Index];exp=expression[exp_top];sym=symbol[sym_Index];printf(%d\t,step++);PrintStatus();printf(%s\t\t,symbol);PrintRestExp();switch(exp){case'a':ActionTable(s,exp,0);break;case'b':ActionTable(s,exp,1);break;case'c':ActionTable(s,exp,2);break;case'd':ActionTable(s,exp,3);break;case'e':ActionTable(s,exp,4);break;case'#':ActionTable(s,exp,5);break;}}}6心得体会：此次课程设计中受益良多，从一开始的不知道从何入手，再到决定用的编程语言、设计程序流程、调试，最后到程序运行成功。较好的文法分析器是功能全面的能自动构造其项目集和转换函数并构造分析表，然后进行分析的程序，但是实现LR（1）文法的自动分析程序对我来说很困难，最后决定直接输出分析表，而让程序实现对输入符号串的分析，在编程过程中也遇到了很多困难，如对某些终结符的动作或是规约函数的实现，最后通过请教同学和上网查找参考资料，都得到了解决。虽然我做的程序功能很简单，而且借鉴的地方不是很清楚具体细节，但是是我参与并动手了的成果，感觉很有收获。最后也感谢各位课设指导老师的悉心指导。