基于LR的语法分析程序报告.doc

《基于LR的语法分析程序报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于LR(1)的语法分析程序1.设计目的：设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。2.设计要求：（1）根据LR(1)分析法编写一个语法分析程序，.输入已给定文法，直接输入根据己知文法构造的LR(1)分析表。（2）对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。3.设计过程：3.1LR(1)文法的含义：LR分析法的规约过程是规范推倒的

2、逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR（0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。3.2设计思想：根据自身实际情况，给定了编译原理书中的一个LR(1)文法，求出其项目集合转换函数，从而得出此

3、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]原来不在CLO

4、SURE(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，则FIRS

5、T(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#defineaSIZE

6、6//宏定义，定义aSIZE为6#definegSIZE2//宏定义，定义gSIZE为2#definegeSIZE6//宏定义，定义geSIZE为6typedefstructGe{charhead;//文法规则左部chargen[5];//文法规则右部}Generate;//生成符号串的基本数据结构体typedefstructA{intst[aSIZE];//遇到终结符时下一个动作状态intre[aSIZE];//遇到非终结符时进行规约}Action;//动作表的基本数据结构体typedefstruc

7、tG{charhead[gSIZE];//状态转换时遇到的非终结符intgt[gSIZE];//标记下一个状态}GOTO;//GOTO表的基本数据结构体intstatus[SIZE];//状态栈intsta_Index;//状态栈栈顶标记charsymbol[SIZE];//符号栈intsym_Index;//当前符号栈的标记charexpression[SIZE];//输入的符号串intexp_Index;//输入符号串的标记intexp_top;//输入符号串的栈顶元素intstep;//计算步骤

8、intIsAccept=0;//初始化接受状态标志置为0Generategene[geSIZE+1];Actionact[sSIZE];GOTOgo[sSIZE];4.2程序流程图：开始输入一个待判断的符号串进行分析分析成功NY进行归约分析输出分析结果结束4.3运行结果：运行后进入界面：上图是编译运行后进入的主界面，给出了给定文法、分析表，要求出入一个要进行分析的符号串。输入错误字符串beD：上图中含有非终结符，不符合要输入指定的几个非终结符的要求，所以