LR(0)文法分析.docx

《LR(0)文法分析.docx》由会员分享，可在线阅读，更多相关《LR(0)文法分析.docx（16页珍藏版）》请在优知文库上搜索。

1、试验名称：1.R(O)文法分析一、试验目的：输入：随意的压缩了的上下文无关文法。输出：相应的1.R(0)分析表。二、试验原理：对于1.R文法，我们可以自动构造相应的1.R分析表。为了构造1.R分析表，我们须要定义一个重要概念一一文法的标准句型“活前缀”。这种句柄之后不含任何符号的前缀称为活前缀。在1.R分析工作过程中的任何时候，栈里的文法符号(自栈底而上)XiX:Xm应当构成活前缓，把输入串的剩余同部配上之后即应成为标准句型(假如整个输入串的确构成一个句子)。因此，只要输入串的已扫描局部保持可归约成一个活前缀，那就意味着所扫描过的局部没有错误。对丁-一个文法G我们可以构造一个有限自动机，它能识

2、别G的全部活前缀，然后把这个自动机转变成1.R分析表，依据该1.R分析表进展1.R分析，就能保证在分析的过程中，假如分析的句子是正确的，栈里的文法符号(自栈底而上)始终构成活前缀。假假设一个文法G的拓广文法G的活前缀识别自动机中的每个状态(工程集)不存在下述状况：(I)既含移进工程又含归约工程；(2)含有多个归约工程，那么称G是一个1.R(0)文法。该自动机的状态集合即为该文法的1.R(0)工程集标准族。构造识别文法活前缀DFA有3种方法：(1)依据形式定义求出活前缀的正那么表达式，然后由此正那么表达式构造NFA再确定为DFA；(2)求出文法的全部工程,按肯定规那么构造识别活前缀的NFA再确定

3、化为DFA：运用闭包函数(C1.OSURE)和转向函数(Go(I,X)构造文法G的1.R(O)的工程集标准族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。符号出的前缀是指该符号串的随意首部,包括空申”例如，对符号串abc.其前缀有，a，ab,aba假如输入率没有错误的话，一个标准句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成个标准句型。活前皴与句柄的关系如下：(I)活前缀已含有句柄的全部符号，说明产生式AB的右部S已出现在栈顶。(2)活前缀只含句柄的局部符号，说明A-BiB2的右部子串已出现在栈顶，期盼

4、从输入申中看到B2推出的符号。13)活前缀不含有句柄的任何符号，此时期望ATB的右部所推出的符号串在文法G的每个产生式的右部(候选式)的任何位置上添加一个侧点，所构成的每个产生式称为1.R(0)工程。如产生大Axyz有如下工程：A.xyz,At,A,ATXyZ.为刻划分析过程中的文法的每一个产生式的右部符号已有多大一局部被识别(出现在栈顶)，可以用这种标有网点的产生式来踊定。A-.刻划产生式Af的右部已出现在栈顶。(2) AfB1.B2刻划A-IBz的右部子申I己出现在栈顶，期盼从输入出中看到B2推出的符号。(3) A-.B刻划没有句柄的任何符号在栈顶，此时期望A-B的右部所推出的符号串。(4

5、)对FAfC的1.R(O)工程只有A-.设文法G=(V,Vn,S,P)是一个上下文无关文法，假设存在一个标准推导SgaAWmaPIP2w(其中A-2wP),那么称工程A-02对活前缀=al是有晟的，即1.R(O)有效工程。从直观意义上讲，一个1.R(O)工程指明白在分析过程中的某一步我们看到产生式的多大局部被识别,1.R(O)工程中的圆点可看成是分析栈栈顶与输入串的分界限，圆点左边为已进入分析栈的同部，右边是当前输入或接若扫描的符号串.不同的1.R(O)工程，反映了分析栈顶的不同状况，我们依据1.R(O)工程的作用不同，将其分为四类：(1)归约工程：表现形苴：A-*a.这类1.R(O)工程表示

6、句柄a恰好包含在栈中，即当前栈顶的同部内容构成了所期望的句柄，应按A-a进展归约。(2)承受工程：表现形式：Sfa.其中S是文法惟一的开场符号。这类1.R(O)工程实际是特别的归约工程，表示分析栈中内容恰好为a,用Sfa进展归约,那么整个分析胜利。移进工程:表现形式：A-*a.?(beVr)这类1.R(O)工程表示分析栈中是不完全包含句柄的活前皴，为构成恰好有句柄的活前级，需将b移进分析栈。(4)待约工程：表现形式：-.B(BWVN)这类1.R(O)工程表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，应把当前输入字符串中的相应内容先归约到B,在给出1.R(O)工程的定义和分类之

7、后，我们从这些1.R(O)工程动身，来构造能识别文法全部前缀的有限自动机.其步骤是：首先构造能识别文法全部活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。由文法G的1.R工程构造识别文法G的全部活前缀的非确定有限自动机的方法：(1)规定含有文法开场符号的产生式(设S*A)的第一个1.R(O)工程(即S-A)为NFA的惟一初态。(2)令全部1.R(0)工程分别对应NFA的个状态II1.R(O)工程为归约工程的对应状态为终态.(3)假设状态i和状态j出自同一文法G的产生式且两个状态1.R(O)工程的圆点只相差一个位置，即：假设i为X-XiXz-XmX-Xn,j为X

8、-XiX2-XiXni-Xn,那么从状态i引一条标记为Xi的弧到状态j(4)假设状态i为待约工程(设X-。AB),那么从状态i引E弧到全部A-r的状态。为了使“承受”状态易于识别，我们通常将文法G进展拓广。假定文法G是一个以S为开场符号的文法，我们构造一个G,它包含整个G,但它引进了一个不出现在G中的非终结符S,并加进一个新产生式SS,以S-SG为开场符号。那么，我们称G是G的拓广文法。这样,便会有一个仅含工程S-S的状态，这就是惟的“承受-态。假如I是文法G的一个工程集，定义和构造I的闭包C1.OSURE(I)如下：(1) I的工程都在C1.OSURE中。(2) 假设A-B属于C1.OSUR

9、E(I),那么每一形如B-”的工程也属于C1.OSURE(I)o(3) S(2)直到C1.OSURE不再扩大.定义转换函数如卜丁GO(I.X)=C1.OSURE(J)其中：I为包含某一工程集的状态，X为一文法符号，J=AfaXBAfa.XPG。圆点不在产生式右部最左边的工程称为核，惟一的例外是S-.s,因此用GOTO(1.X)状态转换函数得到的J为转向后状态闭包工程集的核。运用闭包函数(C1.OSURE)和转换函数(GO(I,X构造文法G的1.R(O)的工程集标准族，步骤如下：1)置工程S-S为初态集的核,然后对核求闭包C1.OSURE(S/-.S)得到初态的闭包工程桀.(2)对初态集或其他所

10、构造的工程集应用转换函数GO(I,X)=C1.oSURE(J)求出新状态J的闭包工程集。(3)重复(2)直到不出现新的工程集为止。计克1.R(0)工程集标准族C=Io,11,.In的算法伪代码如下：Procedureitemsets(G,);BeginC:=(C1.OSURE(Sz.S)RepeatForC中每一工程集I和每一文法符号XDoifGO(I,X)非空且不属于CThen把GO(IrX)放入C中UntilC不再增大End;一个工程集可能包含多种工程，假设移进和灯约工程同时存在，那么称移进-归约冲突，假设归约和归约工程同时存在，那么称归约-归约冲突。下面看一个详细的例子：我们希望能依据识

11、别文法的活前缀的DFA建立1.R分析器，因此，须要探讨这个DFA的每个工程集(状态)中的工程的不同作用。我们说工程AfB1.B2对活前缀Pi是有效的，其条件是存在标准推导Snganaifig一般而言，问一工程可能对几个活前缀都是有效的(当一个工程出现在几个不同的集合中时便是这种情形)假设归约工程AfB1.对活前缀是有效的，那么它告知我们应把符号串回归约为A,即把活前缀变成Ao假设移进工程A-B1.B2对活前缀灯是有效的，那么它告知我们，句柄尚未形成，因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在假设干工程对它都是有效的。而且它们告知我们应做的事情各不一样，相互冲突.这种

12、冲突通过向前多看几个输入符号，或许能够获得解决。对于每个活前缀，我们可以构造它的仃效工程集。事实上，个活前缀y的有效工程集正是从上述的DFA的初态动身，经读出Y后而到达的那个工程集(状态)。换言之，在任何时候，分析栈中的活前级XX2Xm的有效工程集正是栈顶状态Sm所代表的那个集合。这是1.R分析理论的一条根本定理。事实上，栈顶的工程集(状态)表达了栈里的切有用信息一一历史。前面我们已经对1.R(0)文法进展了定义,下面我们来看一下1.R(0)分析表是如何构造的。Xrr1.R(0)文法，我们可以干脆从它的工程集标准族C和活前缀识别自动机的状态转换函数Go构造出1.R分析表。下面是构造1.R(0)

13、分析表的算法。假定C=UoJi,.,In),令每个工程集h的下标k为分析器的一个状态,因此,G，的1.R(O)分析表含有状态0,1,11o令那个含有工程S，一.S的Ik的卜标k为初态。AeTK)N了表和GOTOr表可按如下方法构造：(I)假设工程A-aB属于Ik且GO(h.a)=lj.a为终结符，那么置ACTIoNkaI为“把状态j和符号a移进栈，简记为“旷；(2)假设工程A-.属于Ik,那么，对任何终结符a,置AcnoNk,a为“用产生式A-进展规约，简记为“丁：其中，假定Aia为文法G的第j个产生式：13)假设工程S，-S.属于Ik,那么置AcnoNk#为“承受，荷记为*acc*：(4)假

14、设Go(Ik,A)=Ij,A为非终结符，那么置GoTOk,A|=j；(5)分析表中凡不能用上述1至4填入信息的空白格均当上“出错标记”。按上述兑法构造的含有AenON和GOTO两局部的分析表，假如每个入口不含多重定义，那么称它为文法G的张1.R(O)分析表。具仃1.R(O)表的文法G称为一个1.R(0)文法，1.R(O)文法是无二义的。例如，文法G(E)的拓广文法如下：(O)S-EEfaA(2)E-bBA-CA(4)A-*d(5)BfCB三、试验内容及其代码如下所示：#include#include#includc#includcusingnamespacestd:WcfincOKI#dcfi

15、ncERROR0defineN50#lefineY20intvmum.vnnum.pronumW依次是终结符个数，非终结符个数，产生.式个数charvtN:终结符集CharVnN;/非终结符集CharOkHNMN=2，用于存储文法CharoIdZNN=2W用于存储增广文法intACTIONNN=0H动作表intGOTONN=();状态转换表typcdcfstructSqE(intt：状态编号charcl;SqE;堆栈元素typedefstructitemimf;工程前部，表示产生式编号ini1;工程后部，表示停顿点在产生式的位置iicmH定义工程IypedefstructlinkHf:连接前部，表示所用符号的编号，非终结符编号=在VnU中的下标+100in”：连接后部，即状态编号)1ink:定义状态之