第7章lr分析法(lly)3剖析..ppt

第七章 LR(left-right)分析法,考查重点： LR(0)、SLR(1)、LR(1)，LALR(1)项目集规范族的构造，识别活前缀的DFA的构造，分析表的构造，及输入串的分析 LR(0)、SLR(1)、LR(1)、LALR(1)文法及其关系和区别,文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d,a,b,b,c,d,e,,,,步骤,符号栈,输入符号串,动作,,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,分析符号串abbcde是否G[S]的句子,对输入串abbcde#的移进-规约分析过程,在步骤3中，用A→b归约 在步骤5中，用A→Ab归约 问题：何时移进？何时归约？用哪个产生式归约（如何找当前句柄归约）？,3） #ab bcde# 归约(A→b),5） #aAb cde# 归约(A→Ab),4） #aA bcde# 移进,6） #aA cde# 移进,分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中的状态会发生变化 我们引入一个新的状态栈来表示符号栈中的符号目前状态 用LR分析表来表示不同状态下对于各输入符号应采取的动作,LR 分析器工作示意图,,,,步骤,符号栈,输入符号串,动作,,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(A→b) 024 r2 3,5） #aAb cde# 归约(A→Ab) 0236 r3 3,8） # aAcd e# 归约(B→d) 02358 r4 7,10） #aAcBe # 归约(S→aAcBe) 023579 r1 1,状态栈,,ACTION,GOTO,文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d,Si:移进，并将状态i进栈 ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈,S8,S9,问题： 对于一个文法，状态集是如何确定的？ LR分析表是如何得到的？,答案：需要构造识别可归前缀的有穷自动机,可归前缀与活前缀,文法G[S]： (1) S → aAcBe[1] (2) A → b[2] (3) A → Ab[3] (4) B → d[4],S aAcBe[1] aAcd[4]e[1] aAb[3]cd[4]e[1] ab[2]b[3]cd[4]e[1],每次归约句型的前部分依次为： ab[2] //? aAb[3] aAcd[4] aAcBe[1],规范句型的这种前部分符号串称为可归前缀 我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀,,a,ab  ,a,aA,aAb  ,a,aA,aAc,aAcd  ,a,aA,aAc,aAcB,aAcBe,活前缀,定义： S’ A 是文法G中的一个规范推导，如果符号串γ是的前缀，则称γ是G的一个活前缀。

在当前句型中，不包含句柄右边的前缀）,LR分析需要构造识别可归前缀的有穷自动机 把文法的终结符和非终结符都看成有穷自动机输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀（栈中形成句柄）时，认为达到了识别句柄的终态 注：在符号栈中，始终存放当前句型的活前缀,S8,S9,句子abbcde的可归前缀： ab[2] aAb[3] aAcd[4] aAcBe[1],文法G[S]： (1) S → aAcBe[1] (2) A → b[2] (3) A → Ab[3] (4) B → d[4],*,如何构造识别可归前缀的有限自动机,已经有了可归前缀如何构造有限自动机? 活前缀及其可归前缀的一般计算方法,,文法G[S]： S’ → S[0] S → aAcBe[1] A → b[2] A → Ab[3] B → d[4],句子abbcde的可归前缀（正规式）如下： S[0] ab[2] aAb[3] aAcd[4] aAcBe[1],构造识别其活前缀及可归前缀的有限自动机如下：,1,,0,,4,,3,,8,,7,,13,,12,,10,,18,,2,5,9,14,,6,,,17,15,16,,,11,,10,,,,,,,,,,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,*,1,,0,,4,,3,,8,,7,,13,,12,,10,,18,,2,5,9,14,,6,,,17,15,16,,,11,,10,,,,,,,,,,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,X,加上开始状态X,确定化,,,,,,X,1,,3,,2,4,6,8,5,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,7,,,*,,识别活前缀的确定的有限自动机,活前缀及其可归前缀的一般计算方法,定义：文法G，AVN, LC(A)={ | S’ A, V*, VT *} 规范推导中在非终结符A左边所有可能出现的符号串的集合(不包括句柄的活前缀? ) 推论：若文法G中有产生式B→A，则有 LC(A)  LC(B)·{},文法G’[S]： S’ → S[0] S → aAcBe[1] A → b[2] A → Ab[3] B → d[4],由前面定义与推论知： LC(S’) = {} LC(S) = LC(S’) *{} LC(A) = LC(S) *{a} LC(A) *{} LC(B) = LC(S) *{aAc},化简为： [S’] =  [S] = [S’] [A] = [S]a+[A] [B] = [S]aAc,求解方程组可得： [S’] =  [S] =  [A] = a+[A] [B] = aAc,[A] = a|[A],[A] = a*=a,这样我们求出了每个非终结符在规范推导中用该非终结符的右部替换该非终结符之前，它的左部可能出现的所有前缀，也就是在规范归约过程中用句柄归约成该非终结符之前不包括句柄的活前缀。

推论：若文法G中有产生式B→A，则有 LC(A)  LC(B)·{},不包括句柄的活前缀 + 句柄 = ？,可归前缀？,令 LR(0)C(A→) = LC(A)* {},文法G’的可归前缀有： LR(0)C(S’ → S) = [S’]*{S} = {S} LR(0)C(S → aAcBe) = [S]*{aAcBe} = {aAcBe} LR(0)C(A → b) = [A]*{b} = {ab} LR(0)C(A → Ab) = [A]*{Ab} = {aAb} LR(0)C(B → d) = [B]*{d} = {aAcd},总结：如何构造识别文法活前缀的有限自动机？,1、根据文法算出其可归前缀 2、根据可归前缀，构造识别文法活前缀的不确定有限自动机 3、确定化，从而构造出识别文法活前缀的确定的有限自动机,参见课本P124的例子,LR分析器的构造,1、构造识别文法活前缀的确定有限自动机 根据文法算出其可归前缀 根据可归前缀，构造识别文法活前缀的不确定有限自动机 确定化，从而构造出识别文法活前缀的确定的有限自动机 2、根据该自动机构造相应的分析表(ACTION表、GOTO表),输出,状态与符号栈,这种方法构造识别可归前缀的有限自动机从理论的角度讲是比较严格的，但实现起来却很复杂!! 是否存在一种比较实用的方法？,KISS准则！,项目（item）：在每个产生式的右部适当位置添加一个圆点构成项目 例如：产生式S → aAcBe对应有6个项目 [0] S → • aAcBe [1] S → a • AcBe [2] S → aA • cBe [3] S → aAc • Be [4] S → aAcB • e [5] S → aAcBe •,项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。

空产生式A→α 的项目只有一个： A→•,由文法的产生式直接构造识别活前缀和可归前缀的有限自动机,有限自动机NFA的每一个状态由一个项目构成,构造识别活前缀的NFA：,1、把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态 2、确定初态、句柄识别态、句子识别态 3、确定状态之间的转换关系 若项目i为 X → X1X2.Xi-1 • Xi.Xn 项目j为 X → X1X2.Xi-1 Xi • Xi+1.Xn 则从状态i到状态j连一条标记为Xi的箭弧 若i为X → • A，k为A → • ，则从状态i画标 记为  的箭弧到状态k,文法G‘： S’  E E  T + E E  T T  int * T T  int T  (E),文法的项目有： 1、 S’  • E 2、 S’  E • 3、 E  • T + E 4、 E  T • + E 5、 E  T + • E 6、 E  T + E • 7、 E  • T 8、 E  T • 9、T  • int * T 10、T  int • * T 11、T  int * • T 12、T  int * T •,13、 T  • int 14、 T  int • 15、 T  •(E) 16、 T  (• E) 17、 T  (E •) 18、 T  (E) • 注意： 初态 句柄识别态 句子识别态,注意：拓广文法引入的意义。

确保初态唯一）,NFA for Viable Prefixes of the Example,T ® . (E),T ® (.E),T ® (E.),T ® (E).,(,E,),S’ ® E.,E ® . T+E,E ® T.+E,E ® T+.E,E ® T+E.,S’ ® . E,E® . T,E® T.,T® int.,T® .int,T ® .int * T,T ® int * T.,T ® int *.T,T ® int.* T,e,e,e,e,E,e,T,e,e,e,E,+,e,int,int,*,T,e,e,e,e,e,T,e,NFA for Viable Prefixes in Detail (1),S’ ® . E,NFA for Viable Prefixes in Detail (2),S’ ® . E。