下载文档原格式
7.2 LR(0)分析表的构造4．构造LR(0)分析表——举例G[S′]：[0] S′→S [1] S→S(S)[2] S→εG[S]：[1] S→S(S)[2] S→εG[S]：[0] S′→SS′→.SS→.S(S)S→S.(S)S→.S(S) S→.7.3 SLR(1)分析表的构造1．LR(0)方法的不足LR(0)分析表的构造方法实际上隐含了这样一个要求：构造出的识别规范句型活前缀的有穷自动机中，每个状态均不能有冲突项目，这显然对文法的要求太高，也限制了该方法的应用。
7.3 SLR(1)分析表的构造1．LR(0)方法的不足例如，对文法G[S]：0S→E1 E→E+T2 E→T3 T→T*F4 T→F5 F→（E）6 F→i1I S→E.E→E.+TT→.T*F T→.FFT E #)(*+i G[S]：7.3 SLR(1)分析表的构造2．LR(0)方法的问题分析状态{ E→T.，T→T.*F}该状态含有移进-归约冲突，在分析表中表现为重定义。
7.3 SLR(1)分析表的构造2．LR(0)方法的问题①若U→x.ay ∈Ii ，且GO(Ii，a)=Ij，a∈VT，则ACTION[i，a]=“Sj”。
②若S′→S. ∈Ii，则置ACTION[i，＄]=“acc”。
③若U→x. ∈Ii ，则对任意终结符a和＄，均置ACTION[i，a]=“rj”或ACTION[i，＄]=“rj”。
④若GOTO(Ii ，U)=Ij，其中U∈VN，则置GOTO[i，U]=“j”。
⑤除上述方法得到的分析表元素外，其余元素均置“报错标志”。
7.3 SLR(1)分析表的构造3．解决问题的方法所以在状态{ E→T.，T→T.*F}中，只需要向前看下一输入符号是*，还是FOLLOW（E）中的符号，便可解决冲突了。
7.3 SLR(1)分析表的构造3．解决问题的方法假设一个状态Ii中含有冲突项目I i ={ U1→x.b1y1，U2→x.b2y2，…，Um→x.bmym，V1→x.，V 2→x.，…，Vn→x.}若{b1，b2，…，bm}和FOLLOW(V1)、FOLLOW(V2)、…、FOLLOW(Vn)两两互不相交，就可以采用向前看一个输入符号的方法来解决状态中的冲突。
§3.7 LR分析器(LR Parser)*本节提出一种有效的﹑自下而上的语法分析技术, LR(k) 分析技术, 它能适用于一大类上下文无关文法的分析.*其中:L表示从左到右扫描输入符号串,R表示构造最右推导的逆过程, k表示在作分析决定时要向前看k个输入符号. 在实际的编译器中,我们只考虑k=0或k=1的情形. 当(k)省略时,表示k=1.一.LR分析方法的优缺点优点:能够构造LR分析器来识别所有能用上下文无关文法写的程序设计语言的结构.LR分析方法是已知的最一般的无回溯移进―归约方法.它能够和其它移进―归约方法一样有效地实现.LR分析方法能分析的文法类是预测分析法能分析的文法类的真超集(proper superset).*LR分析方法向前看k个符号只需看右句型中某个产生式右边的k个符号,而预测分析方法向前看k个符号要看某个产生式右边的文法符号能推出的前k个符号. 因此,LR分析法比LL分析法简单,适用的文法类更广.LR分析器能及时察觉语法错误,在自左向右扫描输入时,尽可能快地发现错误.缺点:对典型的程序设计语言文法,手工构造LR 分析器工作量太大.*目前已有许多自动生成LR 分析器的生成器, 例如: Yacc.二. LR 分析算法1.结构: (见书 P248)栈中: s 0X 1s 1X 2s 2…X m s m其中: s i : 状态(state) , X i : 文法符号(grammar symbol)分析表: 动作函数action 和转移函数goto2. 动作: 根据当前栈顶状态s m 和当前输入符号a i , action[s m ,a i ]有四种可能动作:(1) 移进(shift)s, s 是一个状态(2) 按文法产生式A →β归约(reduce)(3) 接受(accept)(4) 出错3. 活前缀(viable prefix)文法G 的活前缀是它的右句型(right sentential form)的前缀, 它不超过该句型中最左句柄(handle)的右端.例: 文法 E →E+T | T , T →T *F | F , F →(E) | id , 存在最右推导: E rm ⇒T rm ⇒T *F rm ⇒T *id rm ⇒F *id rm⇒(E)*id (, (E, (E) 都是右句型(E)*id 的活前缀.4. 格局(configuration):栈中内容: s0X1s1X2s2…X m s m, 剩余输入串: a i a i+1…a n$组成当前格局: (s0X1s1X2s2…X m s m, a i a i+1…a n$)这个格局代表右句型: X1X2…X m a i a i+1…a n5. 分析器动作: 设当前格局是(s0X1s1X2s2…X m s m, a i a i+1…a n$)(1)如果action[s m,a i] =移进s, 分析器进入格局:(s0X1s1X2s2…X m s m a i s, a i+1a i+2…a n$)(2)如果action[s m,a i] =归约A→β, 分析器进入格局:(s0X1s1X2s2…X m-r s m-r As, a i a i+1…a n$)其中: s = goto[s m-r , A], r是β的长度.这里分析器首先从栈中弹出2r个符号,包括r个状态和r个文法符号,这些文法符号刚好匹配产生式的右部β,即β=X m-r+1X m-r+2…X m.(3)如果action[s m, a i] =接受, 分析完成.(4)如果action[s m,a i] =出错, 分析器发现错误,调用错误恢复例程.6. 例子: 文法(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→id分析表(parsing table) (见书P252)给出串id*id+id的移进―归约过程.(见书P253)*注意: 在实际的LR分析器中, 栈中不保存文法符号, 栈顶的状态代表栈中的内容.三.构造SLR分析表1.项目(item): 是右部的某个地方加点的G的产生式.例如: 产生式A→XYZ有项目: A→.XYZA→X.YZA→XY.ZA→XYZ.产生式A→ε只有一个项目 A→.*解释项目中加点的意义.2. 拓广文法(augmented grammar):在文法G中引入产生式: S’→ S, 得拓广文法G’, S’是G’的开始符号,S是G原来的开始符号.*引入这个新的产生式的目的是指出什么时候分析结束,宣布接受输入串.3. 闭包函数设I是项目集, 那么closure(I)是由下面两条规则从I构造的项目集(set of items):(1)初始, I的每个项目都加入closure(I);(2)如果A→α.Bβ在closure(I)中, 且B→γ是产生式, 那么, 如果B→.γ不在closure(I)中, 则把它加入.反复运用这条规则, 直到没有更多的项目可加入closure(I)为止.*A→α.Bβ的直观意义和B→.γ加入closure(I)的意义. 例: 文法: E’→EE→E+T | TT→T*F | FF→(E) | id设I = { E’→.E }, 那么closure(I)为{ E’→.E ,E→.E+T ,E→.T ,T→.T*F ,T→.F ,F→.(E) ,F→.id }4. 核心项目与非核心项目(kernel items and nonkernel items) (1)核心项目: 它包括初始项目S’→.S和所有点不在左端的项.(2)非核心项目: 它们的点在左端.*一个项目集可以只保留核心项目, 并通过求闭包求得该项目集.5. goto函数:设I是项目集, X是文法符号, 并设I中包含项目A→α.Xβ . 那么goto(I,X) = closure(I’), 其中I’是包含A→αX.β的项目集.例: I = { E’→E. , E→E.+T }goto(I, +)包含: E→E+.T T→.T*F T→. FF→.(E) F→. id6. 求拓广文法G’的LR(0)项目集规范族(canonical collection of sets of LR(0) items) 的算法Procedure item(G’);BEGINC := { closure({[S’→.S]})};REPEATFOR C的每个项目集I和每个文法符号X DOIF goto(I, X)非空且不在C中THEN把goto(I, X)加入C;UNTIL 本次循环没有项目集可以加入CEND例子: 文法: E’→E , E→E+T | T , T→T*F | F , F→(E) | idLR(0)项目集规范族(见书P244)该项目集规范族可构成一个DFA (见书P244)7. 构造SLR分析表算法输入: 拓广文法G’输出: G’的SLR分析表函数action和goto方法:(1)构造C = {I0, I1, …, I n }, 即G’的LR(0)项目集规范族.(2)状态i从I i构造, 它的分析动作如下确定:a)如果[A→α.aβ]在I i中, 并且goto(I i , a) = I j , 那么置action[i, a]为sj .b)如果[A→α.]在I i中, 那么对所有FOLLOW(A)中的a,置action[i, a]为rj, j是产生式A→α的编号.c)如果[S’→S.]在I i中, 那么置action[i, $]为接受acc.(3)对所有的非终结符A, 使用下面规则构造状态i的转移:如果goto(I i , A) = I j , 那么goto[i, A] = j .(4)不能由规则(2)和(3)定义的条目都置为出错.(5)分析器的初始状态是从包含[S’→.S]的项目集构造的状态.8. 例子: 从第6条的文法和LR(0)项目集规范族构造分析表(见书P252)9. 非SLR文法*若对某个文法G, 按上述方法构造的SLR分析表的每一个条目都没有多重定义, 那么该文法G称为SLR文法.*存在非SLR的上下文无关文法.例: 文法: S→L=R | RL→*R | idR→LLR(0)项目集规范族(见书P255).*项目集I2面临输入“=”时, 产生移进/归约冲突.*该文法虽然不是二义文法, 但也不是SLR文法.阅读: 教材 4.6 节作业:1.考虑下面文法E→E+T | TT→TF | FF→F* | a | b为此文法构造SLR分析表.。
