《自下而上的lr(k)分析方法》由会员分享，可在线阅读，更多相关《自下而上的lr(k)分析方法（37页珍藏版）》请在金锄头文库上搜索。
1、第七章 自下而上的LR(k)分析 方法LR(K)的含义 L:自左向右扫描输入串;R:采用最右推导的逆过 程分析句子,K:在分析的过程中至多查看K个符 号 给定文法G，S是其开始符号。考虑该文法中一 个终结符串w的一个规范推导Sw1w2 w 假定uAvuxv是上述推导中的一个推导步。 Ax是用于该推导步的产生式；u和 v(VNVT)。 对上述这样的一步推导，仅通过扫描ux和（至 多）查看v中开始的k个符号就能唯一确定选用 产生式Ax去进行推导,我们就称G为LR(k)文法 。 LR(k)分析器是按从左至右方式扫描输入串 ，并按自下而上方式进行规范归约的分析程 序。 一个LR(k)分析器主要由两部分
2、组成：一个 总控程序和一个分析表。一般说来，所有LR 分析器的总控程序基本上是大同小异的，只 是分析表各不相同。 本章主要介绍LR(0) 分析表的构造算法及相 关知识。 7.1 LR分析器的工作原理和过程1. LR 分析法概述 LR分析是一种规范归约。规范归约的关键是分 析过程中如何确定分析栈的栈顶的符号串是否 形成句柄。 LR分析确定句柄的基本思想是在规范归约分析 过程中,根据分析栈中记录的已移进和归约出的 整个符号串(即历史)和根据使用的规则推测未 来可能遇到的输入符号(即展望),以及现实读到 的输入符号这三个方面的信息来确定分析栈的 栈顶符号串是否形成句柄.2. LR(k)分析器的逻辑结
3、构LR分析器是一个确定的下推自动机 LR(k)分析方法的主要思想： 1.严格地进行最左归约（识别句柄并归约 它）。 2.将识别句柄的过程划分为由若干状态控 制，每个状态控制识别出句柄的一个符号 。 3.分析栈：存放已识别的文法符号和状态 ,描述的是分析过程中的历史和展望信息; 4.由一个总控程序来控制整个识别过程。LR分析器的工作过程总控程序在分析的每一步，都是按照栈顶状态q和当前输入符号a，查阅LR分析表，并执行其中ACTIONq，a和GOTO部分规定的操作。 LR分析器的分析表由分析动作表（ACTION表 ）和 状态转换表(goto函数表)两部分组成 ，它们都是用二维数组表示的。 ACTI
4、ON表指明了分析程序采取的动作 移进(Si)：句柄尚未形成，需要继续把符号 移进栈以形成句柄 归约( rj)：句柄已经形成，用对应的产生 式进行归约。 接收(acc)：表示整个分析工作完毕，输入 串合法。 报错(空白)：出错处理。ACTION Si,am 动作表a1a2aiamS1S2S mAction sm,aisn S1,S2Sn为分析器的 各个状态; a1,a2am为文法的全 部符号 ACTIONSi,a:规 定了当前状态为 Si,面临输入符号a 时应执行的动作( 移进、归约、接 受、报错）GOTOSm,xi状态转换表 X1,X2Xn为文法字汇 表中的全部文法符号 GOTOSi,X规定了
5、 当前状态为Si,栈 顶为文法符号X时 ,转移到的下一个 状态.x1x2 xixnS1S2S mGoto sm,xisnLR分析器的工作过程 LR分析器的一个构形由两部分构成:栈中符号串 和尚待扫描的输入串(S0X1S1X2S2XmSm,aiai+1an$) 分析器的工作过程就是从一种构形到另一种构 形的转换过程. (S0，a1a2an$)为初始构形 (S0AZ,$),其中A是文法开始号,ACTIONZ,$= 接收 分析器的下一次移动是由栈顶状态Sm和当前输 入符号ai去查看ACTION表并执行ACTIONSm,ai 规定的动作并根据GOTOSm,ai表去确定栈顶状 态(1)若ACTIONSm
6、,ai=移进S,则分析器执行一个移 进动作,进入构形(S0X1S1X2S2XmSmaiS,ai+1an$),此时ai进栈,栈 顶状态S=GOTOSm,ai(2)若ACTIONSm,ai=归约A,则分析器执行一 个归约动作(按产生式A进行归约),进入构 形(S0X1S1X2S2Xm-rSm-rAS,aiai+1an$),其中 S=GOTOSm-r,A,r是产生式A的长度,栈顶符 号串Xm-r+1Xm和A的右部匹配,即为当前句型 的句柄。 （3）若ACTIONSm,ai= 接收， 分析成功 （4）若ACTIONSm,ai=ERROR，输入串有语法错误 ，分析器停止工作，进行错误处理。状 态态ACT
7、IONGOTOabcde$ABD0S211acc2S433S6S54r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1例:GA1 AaBcDe2 Bb3 BBb4 Dd输入串abbcde$的分析过程步 骤状态栈符号栈输入串动作00$abbcde$s2102$a bbcde$s42024$ab bcde$r2 goto2,B=33023$aB bcde$s640236$aBb cde$r3 goto2,B=35023$aB cde$s5输入串abbcde$的分析过程步 骤状态栈符号栈输入串动作60235$aBc de$s87023
8、58$aBcd e$r4 goto5,D=7802357$aBcD e$s99023579 $aBcDe $r1 goto0,A=11001$A $ acc 分析成功构形移动分析栈尚待扫描的输入串10 abbcde$ 20a2 bbcde$ 30a2b4 bcde$ 40a2B3 bcde$ 50a2B3b6 cde$ 60a2B3 cde$ 70a2B3c5 de$ 80a2B3c5d8 e$ 90a2B3c5D7 e$ 100a2B3c5D7e9 $ 110A1 $7.2 LR(0)分析表的构造LR分析法的基本原理 例如，对文法GA：AaBcDe BbBBb Dd 分析符号串abbcde。
9、句柄的识别是一个符号一个符号得到的，若将从左到右每识别得到句柄的一个符号就对应着一个状态，则可将n个符号的句柄的识别分成n+1个状态。 用LR(0)项目来表示一个句柄的所有识别状 态。 文法G的LR(0)项目定义为：文法G的每个产 生式右部的某个位置添加一个“”。7.2 LR(0)分析表的构造 规范句型的活前缀 一个符号串的前缀是指该串的任意 首部，包括。 活前缀（Viable Prefix）是指规范 句型的一个前缀，它不包含该句型的 句柄右边的任何符号。在得到一个规范句型的完整句柄之前所识别的符号串称为规范句型的活前缀。7.2 LR(0)分析表的构造 GS：AaBcDe Bb BBb Ddd
10、bBeDcBaAb abbcde对应的语法树规范句型句柄活前缀abbcdeb,a,abaBbcdeBb,a,aB, aBbaBcded,a,aB, aBc,aBcdaBcDeaBcDe,a,aB, aBc,aBcD, aBcDe7.2 LR(0)分析表的构造活前缀与句柄的关系(1)AAB 句柄的符号还没有开始识别, 希望 看到从输入串中与AB对应的符号串。 (2)AAB 已识别句柄的一部分,希望看到能 规约为B的符号串 (3)AAB 当前句柄已经形成，可以进行规约 。7.2 LR(0)分析表的构造文法G的拓广文法 给定文法G，S是其开始符号，G的拓广文法是G ，其开始符号为S，区别在于后者仅增
11、加一个 产生式SS。例如，对文法 GA：1.AaBcDe 2.Bb3.BBb 4.Dd拓广后文法 为 GS:0.S A1.AaBcDe 2.Bb3.BBb 4.Dd 该文法的LR(0)项 目: 0.S .A 1.S A. 2.A.aBcDe 3.A a.BcDe 4.A aB.cDe 5.A aBc.De 6.A aBcD.e 7.A aBcDe. 8.B.b 9. Bb. 10.B.Bb 11.BB.b 12. BBb. 13. D.d 14.Dd.7.2 LR(0)分析表的构造 LR(0)项目集SS 初始项目 SS 接收项目 Ux.归约项目； Ux.Vy(VVN)待约项目。Ux.ay(x，
12、y为符号串，aVT)移进项目；Uxa.y(x，y为符号串，aVT)是Ux.ay的后继项目S .A A.aBcDe 等价项目 A a.BcDe B.Bb B.b 等价项目7.2 LR(0)分析表的构造 文法共有个LR(0) 项目，表示在对这个文 法的句子进行分析的时候可能出现的种状 态，但是其中一些状态是等价的。 等价项目识别的活前缀是相同的，可以由他们 组成的项目集作为将要构造的的一个状 态。7.2 LR(0)分析表的构造CLOSURE(I)函数求与I相关的所有LR(0)项目的等 价项目 I中的每一项目都属于它 若AB属于CLOSURE(I)且B是文法中的一个 产生式，则关于产生式B的任何形如
13、B的项目也 属于它 重复上述步骤，直到它不再增大为止 利用闭包算法可以把（）项目分为几个等价 类 令 I= S .A 则CLOSURE(I)= = S .A,A.aBcDe它 是DFA的初态，用I0来表示，它识别的活 前缀是，那么在I0状态下，移进或归约 为某一个文法符号之后可能转移的下一 个状态是什么？ 一般说来，对于状态中的任意项目A.，是任意文法符号（终结符 或非终结符），在移进或归约出之后， 应该转到其后继项目A.（可能有多 个）所在的状态状态转换函数goto(I, X)函数goto(I, X)=CLOSURE (所有形如 AX的项目 AXI) 先找出形如 AXI的项目 然后将其变成A
14、X 再求CLOSURE (AX) 例如： I0 S .A，A.aBcDe I0的后继项目所在的状态为： GO(I0,A)=CLOSURE(S A.)= S A.=I1 GO(I0,a)= CLOSURE(Aa.BcDe)=Aa.BcDe, B.Bb,B.b=I2 GO(I2,B)= CLOSURE(AaB.cDe,BB.b)=AaB.cDe, BB.b =I3 GO(I2,b)= CLOSURE(Bb.)=Bb. =I4 GO(I3,c)= CLOSURE(AaBc.De)= AaBc.De. D.d=I5 GO(I3,b)= CLOSURE(BBb.)=BBb.=I6 GO(I5,D)= CLOSURE(AaBcD.e)=AaBcD.e= I7 GO(I5,d)= CLOSURE(Dd.)= Dd.= I8 GO(I7,e)= CLOSURE(AaBcDe.)= AaBcDe.=I9 因此从初始项目出发S .A出发，利用 CLOSURE和GO函数，可以构造出不识别文 法G的所有活前缀的DFA构造的方法： (1)求CLOSURE
