第5章 自下而上的语法分析(Tsu版电子教案).docx

《第5章 自下而上的语法分析(Tsu版电子教案).docx》由会员分享，可在线阅读，更多相关《第5章 自下而上的语法分析(Tsu版电子教案).docx（8页珍藏版）》请在三一办公上搜索。

1、第8页 共8页第5章 自下而上的语法分析（Tsu版电子教案）第5章 自下而上的语法分析从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。5.1 自下而上的语法分析概述概述实质上是一种移进归约法，设置一个栈，将输入串符号逐个移进栈内，一旦发现栈顶形成某个产生式的候选式时，立即将栈顶这一部分符号替换（归约）成该产生式的左部符号。例给定文法：SaAcBeAb | AbBd 和输入串abbcde，其移进归约过程如下所示：edBBbccccbAAAAAAAaaaaaaaaaS 移 移 归 移 归 移 移 归 移 归 因最终归约到根结点，输入串abbcde是

2、文法的一个句子。问题从第步到第步有二种选择，可将b归约成A，栈顶成aAA；也可将Ab归成A，栈顶成aA，显然后者是正确的，故需精确定义可归约串。句柄和规范归约短语直接短语（简单短语）句柄继续问题的讨论。句型aAbcde中存在三个短语，它们是Ab、d和aAbcde，其中Ab和d是直接短语，句柄是Ab。不能因为存在规则Ab，就断定b是这个句型的一个短语，b不是句柄，甚至连短语都不是。规范归约（最左归约）规范句型规范推导图解法5.2 LR分析法的基本原理前缀活前缀LR分析法的基本思想LR(0)项目（简称项目）在产生式右部的某个位置添加一个园点“.”。特例，A的项目为A.。例文法0. SE1. EaA

3、2. AcA3. Ad4. Ed这个文法的项目有S.ESE.E.aAEa.AEaA.A.cAAc.AAcA.A.dAd.E.dEd.构造识别活前缀的NFA将每个项目视为识别活前缀NFA的一个状态。规定状态S.S为NFA的唯一初态，状态SS.为NFA的唯一接受态（S为原文法开始符号，S为拓广文法开始符号）。因在每个状态都可识别出一个活前缀（初态可识别出活前缀），故NFA的每个状态都是终态，终态又称为活前缀识别态。如果状态i和状态j源自于同一产生式，而且状态i和状态j的园点位置相差一个文法符号，例状态i为i:XX1Xi-1 .XiXi+1Xn状态j为j:XX1Xi-1Xi .Xi+1Xn那么状态i

4、和j之间存在一条弧，标记为Xi，表示在状态i读入Xi进入状态j。若状态i园点之后的符号为非终结符（例i:X .A），那么从状态i画一条弧到所有k:A.状态。表示只有看到了从A推出的全部符号，状态i: X .A才可经A弧进入状态j: XA.。接上例，构造识别文法活前缀的NFA，如下所示： A.cAAc.A AAcA. c A.d dAd. E.aA aEa.A AEaA. S.E ESE. E.d dEd.其中称为初态（含有S.E的项目），状态、和称为句柄识别态（含有形如A.的项目），其中又称为接受态（含有SE.的项目）。构造识别活前缀的DFA 5:7: cAc.A AAcA.A.cA A.d

5、d6:Ad.2: cEa.A d4:A.cA AEaA.A.d0: aS.E 1:E.aAESE.E.dd3:Ed.其中0是初态，1为接受态，3、4、6和7是句柄识别态。项目分类LR(0)项目集规范族（简称项目集规范族）活前缀识别工作原理5.3项目集规范族的构造文法拓广项目集I 的闭包（CLOSURE(I)）状态转换函数（GO(I,X)）项目集规范族构造算法5.5 LR(0)分析表的构造预备工作引入产生式SS，将文法拓广成G。对G的产生式进行编号。构造文法G的状态转换函数GO(I,X)和项目集规范族C。构造法设项目集规范族C=I0、I1、In，将I0、I1、In视为分析表状态0、1、n。LR(

6、0)分析表存放在二维数组M中，第一维为状态，第二维为文法符号。若移进项目A.aIi且GO(Ii,a)= Ij，其中aVT，则置Mia=sj（s表示移进）。若归约项目A.Ii，对于任何aVT#，置Mia=rk（k是产生式A的编号，r表示归约）。若接受项目SS.Ii，则置Mi#=Acc（Acc表示接受）。若待约项目A.BIi且GO(Ii,B)= Ij，其中BVN，则置MiB=j。分析表中的空白表示出错。例已知文法GEaA|dAcA|d构造它的LR(0)分析表。解：预备工作1）引入产生式SE，将文法G拓广成G。2）产生式编号如下：0. SE1. EaA2. Ed3. AcA4. Ad3）构造上述文法

7、的状态转换函数GO(I,X)和项目集规范族（见5.3节）。构造分析表5.6 SLR(1)分析表的构造SLR(1)分析法的引出例简单算术表达式文法G：0. SE1. EE+T2. ET3. TT*F4. TF5. F(E)6. Fi它的项目集规范族如下图所示：项目集规范族共有12个状态（I0-I11），根据项目集规范族构造LR(0)分析表，如下：因M2*=s7r2、M9*=s7r1，分析表含多重定义，故上述分析表不是LR(0)分析表。SLR(1)分析法的基本思想假定I是项目集规范族的一个项目集I=X.b，A.，B.若follow(A)follow(B)=、follow(A)b=、follow(B

8、)b=，则SLR(1)分析法处理如下：若当前输入符号t.code和b相等，则移进输入符号。若当前输入符号t.codefollow(A)，则用产生式A进行归约。若当前输入符号t.codefollow(B)，则用产生式B进行归约。此外报错。构造法SLR(1)分析表的构造是在LR(0)分析表基础上进行的，只要对LR(0)分析表的构造方法稍加修改，就可获得SLR(1)分析表的构造方法，修改部分如下所述：预备工作计算非终结符的follow集。构造法若归约项目A.Ii，对于任何afollow(A)，置Mia=rk（k是产生式A的编号，r表示归约）。接上例，构造G的SLR(1)分析表。解：预备工作1）文法拓

9、广（同上）2）产生式编号（同上）3）构造状态转换函数GO(I,X)和项目集规范族（同上）4）计算非终结符的follow集folow(S)=#、folow(E)=#,+,)、folow(T)=#,+,),*、folow(F)=#,+,),*构造分析表5.7 LR语法分析器的控制程序数据结构LR分析表状态栈符号栈产生式右部符号串长度手工模拟控制程序计算算法描述分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示，控制程序的算法归纳如下：移进若MStopt.code=sj，说明句柄尚未形成，应执行移进操作。s表示移进，j为状态号，将j移入状态栈，将t.code移入符号栈，j

10、成为新的栈顶状态Stop。读下一个单词。归约若MStopt.code=rk，说明句柄已出现在栈顶，应该用编号为k的产生式A进行归约。假设，LEN()=r，MStop-rA=j。首先将栈顶r个元素出栈，然后将j和A分别移入状态栈和符号栈，j成为新的栈顶状态Stop。当前处理单词不变。接受MStopt.code=Acc，表示输入串是一个合法句子，程序终止运行。出错MStopt.code=空白，表示出错，最简单处理为程序终止运行。5.8 二义文法在LR分析法中的应用任何二义文法都不是LR文法，可通过现两种途径来解决文法的二义性问题。例简单算术表达式文法G：EE+E|E*E|(E)|i，它是一个二义文法，二义性源自于文法本身没有规定运算符的优先性和结合性。根据条件将文法修改成无二义性文法规定*优先+，同级运算服从左结合，修改文法为G1： EE+T|TTT*F|FF(E)|iG1是与G等价的非二义文法。 根据条件消除分析表的多重定义二义文法简单，分析表规模小，在程序设计语言中仍有应用。可根据二义文法构造分析表，然后根据条件消除分析表的多重定义。5.4 有效项目可根据课时和学生水平选讲。5.10 LR分析法在词法分析器自动构造中的应用可根据课时和学生水平选讲。