第五章第五章 自底向上的语法分析自底向上的语法分析l5.1 自底向上的语法分析方法概述自底向上的语法分析方法概述l5.2 LR(0)分析的有限自动机分析的有限自动机l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5 LR(1) 分析分析l5.6 LALR(1) 分析分析l5.7 LALR(1) 语法分析器的自动生成器语法分析器的自动生成器 (YACC)内容回顾l自底向上的分析过程自底向上的分析过程lLR分析机制分析机制lLR分析的关键问题分析的关键问题 自底向上语法分析的例子P:(1)Z ABb(2)(2) A a (3) A b(4) B b(5) B c(6) B bBa b c b输入输入符号栈符号栈动作动作abcbabcb移入移入a abcbbcb归约归约(2)(2)A Abcbbcb移入移入AbAbcbcb移入移入AbAbc cb b归约归约(5)(5)AbAbB Bb b归约归约(6)(6)ABABb b移入移入归约归约(1)(1)ABbABbZ Z成功成功自底向上分析过程是从所给自底向上分析过程是从所给输入串输入串出发，对其进行出发，对其进行最左归约最左归约的过程。的过程。LR 分析机制分析栈分析栈输入输入#aLR驱动程序驱动程序: - shift(移入移入) :移入型规范活前缀移入型规范活前缀 - reduce(归约归约):可归约规范活前缀可归约规范活前缀 LR分析表分析表规范规范活前活前缀缀LR分析的关键问题l如何判定规范活前缀如何判定规范活前缀?l如何判定移入型规范活前缀如何判定移入型规范活前缀?l如何判定归约规范活前缀以及用哪一如何判定归约规范活前缀以及用哪一个产生式归约个产生式归约?l如何判定分析结束如何判定分析结束?LR(k)自动机可以解决这些问题自动机可以解决这些问题!5.2 LR(0)分析的有限自动机分析的有限自动机l构造构造LR(0)自动机的依据自动机的依据 - 派生定理派生定理 l应用派生定理的例子应用派生定理的例子lLR(0)自动机自动机 LR(0) item (项项)LR(0) automatal构造构造LR(0)自动机的过程自动机的过程构造LR(0)自动机的依据 - 派生定理l派生定理派生定理: 给出了对任意一个给出了对任意一个CFG构造归约构造归约规范活前缀的方法规范活前缀的方法1* 1* 把把CFGCFG扩展为增广文法扩展为增广文法 , Z , Z S S; ;2 2 文法开始符文法开始符Z Z或或S S是归约规范活前缀是归约规范活前缀; ;3 3 如果如果 A A 是一个是一个归约规范活前缀归约规范活前缀, , 且有产生且有产生式式A A, ,那么那么, , 也是一个也是一个归约规范活前缀归约规范活前缀; ; ( ( , , 和和 是由终极符和非终极符构成的符号串是由终极符和非终极符构成的符号串, ,也可以是空串也可以是空串) )4 4 任何一个归约规范活前缀都是按照任何一个归约规范活前缀都是按照33方式方式派生出来的派生出来的; ;(证明略)派生定理应用例1l1 Sl2 S和和S aAc产生产生aAcl3 aAc和和A Abb产生产生aAbbl4 aAc和和A b产生产生abl5 aAbb和和A Abb产生产生aAbbl6 aAbb和和A b产生产生abl7最后最后,合起来得到合起来得到 S, aAc, aAbb, abVT = a, b, cVN = S, AS = SP: S aAc A Abb A b派生定理应用例2l1 Sl2 S和S aAc产生aAcl3 aAc和A ABb产生aABbl4 aAc和A a产生aal5 aABb和B bB产生aAbBl6 aABb和B b产生aAbl7 aAbB和B bB产生aAbbBl8 aAbB和B b产生aAbblVT = a, b, cVN = S, A, BS = SP: S aAc A ABb A a B bB B bLR(0)自动机lLR(0) 项目项目:带圆点的产生式带圆点的产生式,圆点只能出现圆点只能出现在产生式的右部符号串的任意位置在产生式的右部符号串的任意位置;产生式产生式SaAc，LR(0)项目：项目：lS aAclS a AclS a A clS a Ac 特别地，空产生式特别地，空产生式: S , 对应对应LR(0)项目项目S LR(0)自动机lLR(0)项目集合项目集合IS关于符合关于符合X的投影的投影IS 是一个是一个LR(0)项目的集合项目的集合;X 是一个符号是一个符号(终极符或非终极符终极符或非终极符);IS(X)表示项目集表示项目集IS关于符号关于符号X的投影的投影:IS(X) = S X | S X IS, X VT VNIS(x)只对只对IS中圆点后面是中圆点后面是X的项目起作用，所起的项目起作用，所起的作用就是将圆点从的作用就是将圆点从X的前面移到的前面移到X的后面的后面lIS = A A Bb, B a , B b B , Z cBlX = BlIS(B) = A AB b, B bB LR(0)自动机lLR(0)项目集合的闭包项目集合的闭包IS 是 LR(0)项目的集合;CLOSURE(IS)也是一个LR(0)项目集合, 按照下面的步骤计算:l1 初始, CLOSURE(IS) = ISl2 对于CLOSURE(IS)中没有处理的LR(0)项目,l 如果该项目的圆点后面是一个非终极符A, l 而且A的全部产生式是A1, , Anl 则增加如下LR(0)项目到CLOSURE(IS)l A 1, , A nl 3 重复2直到 CLOSURE(IS)收敛;LR(0)自动机VT = a, b, cVN = S, A, BS = SP: S aAc A ABb A Ba B bIS = S aAcCLOSURE(IS) = S aAcIS = S aAcCLOSURE(IS) = S aAc, A ABb, A Ba, B b LR(0)自动机lgoto函数IS 是 LR(0)项目集合;X 是一个符号(VT or VN终极符或非终极符);goto(IS, X) = CLOSURE(IS(x) LR(0)自动机lCFG G=VT, VN, S, P 的LR(0)自动机l(，SS，S0，TS， ) 是否需要是否需要 增广产生式增广产生式 Z S ？ = VT VN#S0 = CLOSURE(Z S) SSTS 构造构造 LR(0)自动机的过程中逐步生成的。自动机的过程中逐步生成的。构造LR(0)自动机的过程1增广产生式增广产生式 Z S2 = VT VN #3S0 = CLOSURE(Z S)4SS = S05对于对于SS中的每一个项目中的每一个项目IS, 和每个符号和每个符号X , 计算计算IS = goto(IS, X), 如果如果IS不为空不为空, 则则 建立建立 IS IS, 如果如果IS不为空且不为空且IS不属于不属于SS,则把则把IS加入加入SS;6重复重复5直到直到SS收敛收敛;7终止状态终止状态:包含形如包含形如A 项目的项目集合项目的项目集合;X构造LR(0)自动机的过程VT = a, b, cVN = S, A, BS = SP: S aAc A ABb A Ba B b Z SS aAc Z S Sa S a AcA ABb A BaB b A S aA c A A BbB b bB A B aa A Ba B b S aAc cB A AB bb A ABb b0*构造LR自动机的过程VT = a, b, cVN = S, A, BS = SP: S aAc A ABb A Ba B Z SS aAc Z S Sa S a AcA ABb A BaB A S aA c A A BbB B A B bb A Bb S aAc cB A AB b A ABb b0*l1 Sl2 S和S aAc产生aAcl3 aAc和A Abb产生aAbbl4 aAc和A b产生abl5 aAbb和A Abb产生aAbbl6 aAbb和A b产生abl7最后,合起来得到 S, aAc, aAbb, abVT = a, b, cVN = S, AS = SP: S aAc A Abb A bVT = a, b, cVN = S, AS = SP: S aAc A Abb A b Z S S aAcS Z S a S a Ac A Abb A bA S aA cA A A bbbbb A b c S aAc b A Ab b b b A Abb LR(0)自动机接受的语言恰好是归约规范活前缀的集合：S,aAc,aAbb,abVT = a, b, cVN = S, A, BS = SP: S aAc A ABb A a B bB B bl1 Sl2 S和S aAc产生aAcl3 aAc和A ABb产生aABbl4 aAc和A a产生aal5 aABb和B bB产生aAbBl6 aABb和B b产生aAbl7 aAbB和B bB产生aAbbBl8 aAbB和B b产生aAbblVT = a, b, cVN = S, A, BS = SP: S aAc A ABb A a B bB B b Z S S aAcS Z S a S a Ac A ABb A aA S aA cA A BbB bBB ba A a c S aAc bB b BB b B bBB bB B bB B A AB b b b A ABb bl结论结论:一个一个CFG的的LR(0)自动机接受的是该自动机接受的是该CFG的所有的所有LR0归约规范活前缀归约规范活前缀;第五章第五章 自底向上的语法分析自底向上的语法分析l5.1 自底向上的语法分析方法概述自底向上的语法分析方法概述l5.2 LR(0)分析的有限自动机分析的有限自动机l5.3 LR(0) 分析分析l5.4 SLR(1) 分析分析l5.5 LR(1) 分析分析l5.6 LALR(1) 分析分析l5.7 LALR(1) 语法分析器的自动生成器语法分析器的自动生成器 (YACC)LR(0)自动机内容回顾l派生定理派生定理lLR(0)项目项目lLR(0)项目集的闭包项目集的闭包lLR(0)项目集关于符号项目集关于符号X的投影的投影lLR(0)自动机的构造过程自动机的构造过程5.3 LR(0) 分析lLR(0) 自动机的相关概念自动机的相关概念lLR(0) 文法文法lLR(0) 语法分析方法语法分析方法LR(0) 分析表分析表LR(0) 分析的驱动程序分析的驱动程序lLR(0) 分析过程分析过程LR(0) 自动机的相关概念l移入项目移入项目: A a , a VTl归约项目归约项目: A ,l接受项目接受项目: Z S , (Z S是增广产生式是增广产生式)l移入状态移入状态:包含移入项目的状态包含移入项目的状态l归约状态归约状态:包含归约项目的状态包含归约项目的状态l冲突状态冲突状态(同一个状态中同一个状态中):包含不同的归约项目，则称该状态存在包含不同的归约项目，则称该状态存在归约归约-归约冲突归约冲突 ；既包含移入项目，又包含归约项目，则称该状态存在既包含移入项目，又包含归约项目，则称该状态存在移移入入-归约冲突归约冲突LR(0) 文法l给定一个上下文无关文法给定一个上下文无关文法 GlLR0 是是G的的LR(0)自动机自动机l如果如果LR0的任意一个状态都不存在冲突的任意一个状态都不存在冲突(归归约约-归约冲突、移入归约冲突、移入-归约冲突归约冲突), 则则G称为称为LR(0)文法文法;l可以推知：在可以推知：在LR(0)文法中，文法中，任意状态或者是移入状态任意状态或者是移入状态,或者是归约状态或者是归约状态如果是归约状态如果是归约状态,一定存在一个一定存在一个唯一唯一的归约项的归约项目目,该归约项目对应一个产生式该归约项目对应一个产生式p,因此因此, 该归约该归约状态称为状态称为p-归约状态归约状态LR(0) 分析方法StackInput#aLR驱动程序驱动程序: - shift(移入移入) : 移入型规范活前缀移入型规范活前缀 - reduce(归约归约): 归约规范活前缀归约规范活前缀 LR分析表分析表规范规范活前活前缀缀状态栈状态栈action表表goto表表LR(0)驱动程序驱动程序LR(0) 文法VT = a, b, cVN = S, A, BS = SP: (1) S aAc (2)A ABb (3)A Ba (4)B b Z SS aAc Z S Sa S a AcA ABb A BaB b A S aA c A A BbB b bB A B aa A Ba B b S aAc cB A AB bb A ABb b0123567894LR(0)分析的例子P: (0) Z S (1) S aAc (2)A ABb (3)A Ba (4)B ba b a c符号栈输入流分析动作 abac#移入abac#移入abac#归约 (4)aBac#移入aBac#归约(3)aAc#移入aAc#归约(1)S#归约(0)Z#接受LR(0)分析的例子状态状态栈栈符号符号栈栈输入输入流流分析动作分析动作0abac# 移入移入02abac#移入移入027abac#归约归约 (4)025aBac#移入移入0256aBac#归约归约(3)023aAc#移入移入0234aAc#归约归约(1)01S#归约归约(0)01Z#接受接受P: (0) Z S (1) S aAc (2)A ABb (3)A Ba (4)B ba b a cLR(0) 分析表laction表表lgoto表表LR(0) 分析表laction表 终极符终极符状状 态态 a1#S1Sn action(Si,a) = Sj, 如果Si到Sj有a输出边 action(Si,c) = Rp, 如果Si是p-归约状态,cVt # action(Si,#) = accept, 如果Si是接受状态 action(Si,a) = error, 其他情形LR(0) 分析表lgoto表 非终极符非终极符状状 态态 A1S1Sngoto (Si, A) = Sj, 如果Si到Sj有A输出边 goto (Si, A) = error,如果Si没有A输出边LR(0)分析表的例子VT = a, b, cVN = S, A, BS = SP: (1) S aAc (2)A ABb (3)A Ba (4)B b Z SS aAc Z S Sa S a AcA ABb A BaB b A S aA c A A BbB b bB A B aa A Ba B b S aAc cB A AB bb A ABb b0123567894action表 goto表abc#S A B0 S211accept2S7353S7S484 R1R1R1R15 S66 R3R3R3R37 R4R4R4R48S99 R2R2R2R2LR(0) 分析驱动程序l符号约定：符号约定：S0: 开始状态开始状态Stack:状态栈状态栈Stack(top):栈顶元素栈顶元素P:产生式产生式| P |:产生式产生式P右部符号个数右部符号个数;PA:产生式产生式P左部非终极符左部非终极符;Push(S):把状态把状态S压入压入stack;Pop(n):从从stack弹出弹出n个栈顶元素个栈顶元素;LR(0) 分析驱动程序l初始化初始化: push(S0); a = readOne();lL: Switch action(stack(top), a) Case error: error();Case accept: return true;Case Si: push(Si), a=readOne(); goto L;Case RP: pop(|P|); push(goto(stack(top), PA ); goto L;LR(0) 分析过程状态栈输入流分析动作0abac#S202bac#S7027ac#R4,Goto(3, B)=5025ac#S60256c#R3,Goto(3, A)=3023c#S40234#R1, Goto(0, S)=101#AcceptP: (0) Z S (1) S aAc (2)A ABb (3)A Ba (4)B ba b a c