第七单元 LR分析法.pptVIP

第七章 LR分析法 7.1 LR分析概述 7.2 LR(0)分析 7.3 SLR(1)分析 7.4 LR(1)分析 7.5 LALR(1)分析 7.6 二义性文法在LR分析中的应用 第七章 LR分析法 7.1 LR分析概述 LR(K)分析:根据当前分析栈中的符号串和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还归约和用哪个产生式归约,因而也就能唯一地确定句柄。 LR分析器 第七章 LR分析法 LR分析器的工作过程: 第七章 LR分析法 LR分析过程中的四种动作: GOTO[Si,X]=Sj: ACTION[Si,a]: (1)移进 (2)归约 (3)接受acc (4)报错 7.2 LR(0) 分析 S aAcBe A b|Ab B d 输入串：abbcde# 最右推导：S aAcBe aAcde aAbcde abbcde 第七章 LR分析法 7.2.1 可归前缀和子前缀 S aAcBe[1] A b[2] A Ab[3] B d[4] 输入串abbcde#的最右推导: S aAcBe[1] aAcd[4]e[1] aAb[3]cd[4]e[1] ab[2]b[3]cd[4]e[1] 第七章 LR分析法 活前缀: ,a ,ab ,a ,aA ,aAb ,a ,aA ,aAc ,aAcd ,a ,aA ,aAc ,aAcB ,aAcBe 定义7.1 若S’ ? ?A ? ? ???是文法G中的一个规范推导。 如果符号串?是??的前缀，则称?是G的一个活前缀。 7.2.2 识别活前缀的有限自动机 拓广文法为: S’ →S[0] S → aAcBe[1] A → b[2] A → Ab[3] B → d[4] 构造识别其活前缀及可归前缀的有限自动机: 识别活前缀的NFA: 第七章 LR分析法 7.2.3 活前缀及其可归前缀的一般计算方法 定义 7.2 设G=(VN,VT,P,S)是一个上下文无关文法, 对于 A ?VN有 LC(A)={?|S ?A?,? ?V*,??V*T } 推论:若文法G中有产生式 B ?A? 则有 LC(A) ? LC(B) · {?} 因此,对于示例文法有: LC(S’)={?} [S’]= ? LC(S)=LC(S’) · {?} [S]=[S’]= ? LC(A)=LC(S’) · {a} ∪LC(A) ·{?} [A]=[S]a+[A]=a ?*=a LC(B)=LC(S) · {aAc} [B]=[S]aAc=aAc 第七章 LR分析法 活前缀LR(0)CONTEXT(A ? ), 即:LR(0)C(A ?)=LC(A) · {? } 因此,对示例文法有: LR(0)C(S’ S)=S LR(0)C(S aAcBe)=aAcBe LR(0)C(A b)=ab LR(0)C(A Ab)=aAb LR(0)C(B d)=aAcd 例:设文法G’为 (0)S’ →E (1)E →aA (2)E →bB (3)A →cA (4)A →d (5)B →cB (6)B →d 第七章 LR分析法 第七章 LR分析法 第七章 LR分析法 第七章 LR分析法 第七章 LR分析法 b)若项目A→?·属于Ik,则对任何终结符 a和 ‘#’号置ACTION[k,a]和ACTION[k,#]为“rj”,j为在文法G’中某产生式A→?的序号, rj动作的含义是把当前文法符号栈顶的符号串?归约为A,并栈指针向下移动| ? |的长度,非终结符A变为当前面临的符号. c)若GO(Ik,A)=Ij,则置GOTO[k,A]为“j”,其中A为非终结符,表示当前状态为“k”时,遇文法符号A时状态应转向j,因此A移入文法符号栈,j移入状态栈. d)若项目S’ → S · 属于Ik,则置ACTION[k,#]为“acc”,表示接受 e)凡不能用上述方法填入的分析表的元素,均应填上“报错标志”. 示例: 0.S’ → E 1.E → aA 2.E → bB 3.A → c