一种为二义性文法构造SLR(I)分析器的方法

《一种为二义性文法构造SLR(I)分析器的方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据一种为二义性文法构造SLR(1)分析器的方法罗海丽(内蒙古科技大学信息工程学院，内蒙古包头014010)[摘要】文法具有二义性是实际中经常遇到的情况。本文以SLR(1)分析器为例介绍了一种为二义性文法构造语法分析器的方法。并通过实例分析了利用该方法进行语法分析的过程。[关键词】二义性文法；SLR(1)分析器；SLP．(1)分析表1．引言对于文法G，若L(G)中存在一个具有两棵或两棵以上语法树的句子，则称该文法具有二义性【n。目前绝大多数语法分析器要求所处理的文法是无二义的，否则在语法分析过程中对具有二义性的句子无法确定应选择哪棵语法树，使得

2、分析工作无法继续。二义性文法在实际应用中会经常出现，如何为二义性文法建立语法分析器是语法分析中要解决的一个重要问题。作者提出了二义性文法的SLRO)分析器的一种构造方法。文法GI为“不匹配else"文法：stmt--,ifexprthenstmtlifexprthenstmtelsestmtlother可以证明该文法具有二义性。本文介绍了构造该文法的SLR(I)分析器的方法。2．消除二义性闭if语句的一般规则是，每个else和前面最近的没有配对的then配对。可用这条规则避免二义性。其基本思想是：出现在then和else之间的语句必须是配对的，即不

3、能以一个未配对的then后面跟随任意的非else语句结束，于是else会被迫与这个未配对的then匹配，配对的语句是一个不包含不配对语句的if-then-else语句或任何非条件语句。按上述思想消除文法GI的二义性，将其改写为文法(32：stmt-*matched-stmtlunmatched-stmtmatched-stmt---,ifexprthenmatched-stmtelsematched-stmtlotheruumatched-stmt--*ifexprthenstmqifexprthenmatched-stmtelseunmatche

4、d．stmt用S表示strut，M表示matched-strut，U表示unmatched-strut，i表示ifexprthen，e表示else，a表示other，则文法G2可改写为文法G3：S_MIUM--÷iMeMlaU—+iSIiMeU可证明文法G3不具有二义性。3．构造SLR(I)分析器文法G3的SLR(1)分析器由SLR(1)分析表，SLR(1)分析程序和栈组成。3．1构造SLR(1)分析表(1)构造该文法的项目集规范族扩展文法，将文法G3改写为G4：0Si_+SlS—·M2S—·U3M-．iMeM4M—÷a5U—+iS6U—·iMeU

5、构造该文法的项目集规范族I_儡，I。，12．13，I．，15，k，17，I．，b，Im}，其中10={S’_+．S，S-÷．M，S-◆．U，M_+．iMeM，M_．a，U---,．iS,U一．iMeO}Il_{S’一S．}L尸{S—M．}13产{S—U．}、I产{M-+i．MeM，M_+．iMeM，M-+．a，U--,i．S，U--,．iMeU，S_+．M，S_．U，U_+．iS，U_÷．n订eU．U_+i．McU}I严{M-+a．}I严{U—iS．}l严{M—iM．eM，S_÷M．，U-+iM．eU}驴{M--,iMe．M，M_+．iMeM，M_

6、÷．a，U-+iMe．U，U-+．iS,U---,．iMeU)I尹{M---,iMeM．'Its{U—÷iMeU．}(2)计算非终结符的Follow集合Follow(S)={群}Follow(M)f{e，撑}Follow(U)={#}(3)构造SLR(1)分析表文法G3的SLR(1)分析表如表1。3．2构造SLR(1)分析程序【3】SLR(O分析算法如下：作者简介：罗海丽。女，辽宁大连人，硕士．讲师，研究方向：计算机软件技术。编译技术。一50一万方数据初态0入栈，输入串w放入缓冲区；令口指向w的第一个符号；repeatforeverbegin令S是

7、栈项状态，a是ip所指向的符号；ifaction[s，a】=岛thenbcg．m把a和状态j入栈；ip指向w中下～个符号endelseifaction[s，a]--rithenbegin若第i个产生式为A—p，则从栈顶弹出2·Ip个符号；令S’为现在栈顶状态，把A和goto[S’，A】入栈；endelseifaction【s，a]--'acc”thenreturnelseerror()end表l的SLR(1)分析表，上述的SLR分析算法和栈共同构成了文法G3的SLR(1)分析器。衰l文法G3的SLR(1)分析衰状ACTIaNGoTo态Iea撑SMU

8、O钆s，l23laCC2rl3r24s-％6735r．rI6如7&fI8sl＆9109r，10r‘3．3用SLR(1)分析