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

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

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

3、描述：1.CLOSURE(I)的构造CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到：(1)I中的所有项目都属于CLOSURE(I)；(2)若项目Aa.B,a属于CLOSURE(I)，B是一个产生式，那么，对于FIRST中的每一个中介符b,如果.,b原来不在CLOSURE(I)中，则把它加进去；(3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。2.GO(I,X)的构造GO(I,X)=CLOSURE(J)其中J=任何形如AaX.,a的项目Aa.X.,a属于I3.FIRST集合的构造在这个程序中使用的是FIRST(a)，这基于每一个非终结符的

4、FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。方法如下：连续使用下面的规则，直到每个集合FIRST不再增大为止。（1） 若X属于VT，则FIRST(X)=X。（2）若X属于VN，且有产生式Xa，则把A加入到FIRST(X)中；若X也是一条产生式，则把也加入到FIRST中。4.LR(1)分析表的构造在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。4 设计内容4.1 主要变量说明：#define SIZE 20 /宏定义，定义sSIZ

5、E为12#define sSIZE 12 /宏定义，定义sSIZE为12#define aSIZE 6 /宏定义，定义aSIZE为6#define gSIZE 2 /宏定义，定义gSIZE为2#define geSIZE 6 /宏定义，定义geSIZE为6typedef struct Ge char head; /文法规则左部 char gen5; /文法规则右部 Generate;/生成符号串的基本数据结构体typedef struct A int staSIZE; /遇到终结符时下一个动作状态 int reaSIZE; /遇到非终结符时进行规约 Action;/动作表的基本数据结构体typ

6、edef struct G char headgSIZE; /状态转换时遇到的非终结符 int gtgSIZE; /标记下一个状态GOTO;/GOTO表的基本数据结构体int statusSIZE; /状态栈 int sta_Index; /状态栈栈顶标记 char symbolSIZE; /符号栈int sym_Index; /当前符号栈的标记char expressionSIZE; /输入的符号串int exp_Index; /输入符号串的标记int exp_top; /输入符号串的栈顶元素int step; /计算步骤int IsAccept = 0; /初始化接受状态标志置为0Gene

7、rate genegeSIZE +1;Action actsSIZE;GOTO gosSIZE;4.2 程序流程图：开始输入一个待判断的符号串进行分析分析成功NY进行归约分析输出分析结果结束4.3运行结果：运行后进入界面：上图是编译运行后进入的主界面，给出了给定文法、分析表，要求出入一个要进行分析的符号串。输入错误字符串beD：上图中含有非终结符，不符合要输入指定的几个非终结符的要求，所以提示错误。输入字符串aed：上图输入的符号串符合要求，可见结果为接受状态，为该文法的句子。输入字符串bcd:上图输入的符号串符合要求，但是进行分析时发现不能进行规约，结果错误，不是该文法的句子。5 程序关键代

8、码：void Initlize(void) /将终结符规约时所对应的要使用的 文法规则gene1.head = S; strcpy(gene1.gen,aAd); gene2.head = S; strcpy(gene2.gen,bAc); gene3.head = S; strcpy(gene3.gen,aec); gene4.head = S; strcpy(gene4.gen,bed); gene5.head = A; strcpy(gene5.gen,e);void Reduce(int sta, char symb,int col) /执行规约过程的函数 int i = 0; for

9、(i = 0; i strlen(geneactsta.recol.gen); i+) symbolsym_Index- = 0; symbol+sym_Index = geneactsta.recol.head; for(i = 0; i strlen(geneactsta.recol.gen) ; i+) statussta_Index - i = 0; sta_Index -= i; GOTOTable(statussta_Index, symbolsym_Index);void ActionTable(int sta, char symb,int col) /动作表 if(sta =

10、1 & col = 5) printf(ACCEPTn); IsAccept = 1; return; if(actsta.stcol != 0) printf(Actionn); status+sta_Index = actsta.stcol; symbol+sym_Index = symb; exp_top +; else if(actsta.recol != 0) printf(Reducen); Reduce(sta, symb, col); else printf(ERRORn); getchar(); exit(1); void GOTOTable(int sta, char sy

11、mb) /GOTO表 int i = 0; for(i = 0; i sSIZE; i+) if(gosta.headi = symb) status+sta_Index = gosta.gti; return; void Launch(void) /输出对符号串的状态分析表的函数 int s = statussta_Index; char exp = expressionexp_top; char sym = symbolsym_Index; while(IsAccept != 1) s = statussta_Index; exp = expressionexp_top; sym = sy

12、mbolsym_Index; printf( %dt ,step+); PrintStatus(); printf( %stt , 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 心得体会：此次课程设计中受益良多，从一开始的不知道从何入手，再到决定用的编程语言、设计程序流程、调试，最后到程序运行成功。较好的文法分析器是功能全面的能自动构造其项目集和转换函数并构造分析