第四章_3 LR分析法课件

《第四章_3 LR分析法课件》由会员分享，可在线阅读，更多相关《第四章_3 LR分析法课件（42页珍藏版）》请在金锄头文库上搜索。

1、4.5 LR分析法,1 概述 LR分析法是一种自下向上的规范归约的语法分析方法。,L,R,从左到右扫描输入串,最右推导的逆过程,规范归约,4.5 LR分析法,2 特点,优点：,缺点：,文法限制少,构造LR分析器工作量大，实现困难。 使用YACC自动生成LALR(1)分析器。,4.5 LR分析法,3 四种LR类型,LR(0),SLR(1),LR(1),LALR(1),基础,理论过度,理论过度,实用,4.5 LR分析法,4 四种LR文法之间的关系 LR(0) SLR(1) LR(1) LALR(1),SLR(1),LR(1),LALR(1),LR(0),4.5.1 LR分析器的工作原理和过程,1

2、LR分析器结构,LR分析表,总控程序,a1,am,$,ai,输出,Sm,Xm,S1,X1,S0,$,. . .,. . .,分析栈,4.5.1 LR分析器的工作原理和过程,1 LR分析器结构 总控程序 总控程序与文法与输入符号串无关。 分析栈 两部分指针同步。,Sm,Xm,S1,X1,S0,$,. . .,. . .,分析栈,状态栈,文法符号栈,4.5.1 LR分析器的工作原理和过程,2 LR分析表 LR分析表是LR分析器的核心部分。 它由两部分组成： 分析动作表(ACTION) 状态转换表(GOTO),LR分析表实例,状态,ACTION,GOTO,a,(,),*,$,S,A,B,0,1,2,

3、3,4,S3,S2,1,2,3,acc,r2,r2,r2,r2,r2,S3,S4,S3,4,移进,归约,接受,报错,状态转换,4.5.1 LR分析器的工作原理和过程,3 LR分析器的工作过程 例 4.14 文法G为： 0. S S 1. S A 2. S B 3. A aAb 4. A c 5. B aBb 6. B d,该文法的LR分析表,根据文法GS的LR(0)分析表，对输入串aacbb$进行语法分析。,4.5.2 LR(0)分析法,0 LR分析表的构造步骤 (1)根据文法构造识别文法所有规范句型活前缀的DFA (2)将DFA转换成一张LR分析表,4.5.2 LR(0)分析法,1 文法规范

4、句型的活前缀 字符串的前缀 指字符串的任意首部。 例：字符串abc的前缀有: , a, ab, abc 规范句型的活前缀 不包含句柄右边的符号。 例：某文法规范句型aaAbb$,它的句柄是aAb， 则 前缀： , a, aa, aaA, aaAb, aaAbb, aaAbb$. 活前缀： , a, aa, aaA, aaAb.,4.5.2 LR(0)分析法,1 文法规范句型的活前缀 LR分析器的分析栈中，栈内的文法符号应是某个规范句型的活前缀。 LR分析需要构造识别活前缀的DFA。 把文法的终结符和非终结符都作为输入符号，输入符号进栈的同时，状态也进行转换。,4.5.2 LR(0)分析法,2

5、LR(0)项目 活前缀与句柄的三种关系： (1)全部包含 A ,即句柄 形成，进行归约。 (2)部分包含 A ,句柄部分 形成，移进或待约。 (3)零包含 A , 未形成，移进或待约。,A ,A ,A ,4.5.2 LR(0)分析法,2 LR(0)项目 右部标有圆点的产生式称为LR(0)项目。 特别的，对于A 的LR(0)项目 A ,4.5.2 LR(0)分析法,3 LR(0)项目分类 归约项目 A 移进项目 A a 待约项目 A B 接受项目 S S ,4.5.2 LR(0)分析法,4 构造识别活前缀的DFA方法 DFA主要有两部分：状态、状态转换函数。,状态：LR(0)项目集 LR(0)项

6、目的集合称为项目集。,利用闭包函数、GO函数构造DFA的组成部分。,闭包函数(CLOSURE) 设I是项目集，则 CLOSURE(I)含有： I中所有项目。 若I中有A B ,则B r 也属于CLOSURE(I)。 重复上一步，直到CLOSURE(I)不再增大。 GO函数 GO(I,X)=CLOSRUE(J). JA X |A X I,例文法4.14 0. S S 1. S A 2. S B 3. A aAb 4. A c 5. B aBb 6. B d,令I=S S,CLOSURE(I)= S S S A S B A aAb A c B aBb B d ,构造识别文法规范句型活前 缀的DFA

7、。,4.5.2 LR(0)分析法,4 构造识别活前缀的DFA方法 (0) 拓广文法，引入S，使S S,并对规则编号; (1)求CLOSURE(S S),得到初态项目集; (2)对已构造的项目集，应用GO函数，求后继状态; (3)重复(2)直到不出现新的项目集为止。 构成识别一个文法活前缀的DFA的状态全体，称为这个文法的LR(0)项目集规范族。,构造4.14文法的LR(0)项目集规范族。,LR(0)文法:不存在移进归约并存，或归约归约并存。,I1:S S,例 4.14文法GS: S (S) S a (1)构造识别文法规范句型活前缀的DFA; (2)判断该文法是否LR(0)文法，若是，构造LR(

8、0)分析表;若不是，说明理由。,拓广文法，并给出每条规则编号： 0. S S 1. S (S) 2. S a,4.5.2 LR(0)分析法,5 LR(0)分析表的构造(ACTION,GOTO) (1)A a ,且GO(I,a)=J,置ACTION(I,a)=Sj (2)A B ,且GO(I,B)=J,置GOTOI,B=J (3)A ,对所有终结符a,置ACTION(I,a)=rj (4)S S ，置ACTIONI,$=acc. (5)其他空白格均置“出错标志”。 构造出的LR分析表不含多重定义，则该表为LR(0)分析表。 能构造LR(0)分析表的文法为LR(0)文法。,例 4.14文法GS:

9、S (S) S a (1)构造识别文法规范句型活前缀的DFA; (2)判断该文法是否LR(0)文法，若是，构造LR(0)分析表;若不是，说明理由。,拓广文法，并给出每条规则编号： 0. S S 1. S (S) 2. S a,4.5.2 LR(0)分析法,结论： LR(0)分析器不需要向前查看输入符号就能归约。 若G是LR(0)文法，也是SLR(1)文法、LR(1)文法、LALR(1)文法。,4.5.3 SLR(1)分析法,1 LR(0)项目集中的冲突情况 LR(0)文法要求很难满足。 (P85) 例4.16中的文法 分析引起冲突的原因： LR(0)分析法中对归约项目的处理方法， 当一个项目集

10、中同时含有移进和归约项目,或 有多个归约项目时，必定会产生多重定义。,例4.16中的冲突项目。,I1:EE EE+T,I0:,I2:ET TT*F,I9:EE+T TT*F,4.5.3 SLR(1)分析法,2 SLR(1)文法 对于移进归约冲突，或归约归约冲突，需向前查看一个输入符号， 对归约项目用产生式左部非终结符的FOLLOW集解决。 SLR(1)即简单的LR(1)方法，对于一个文法中有冲突的LR(0)项目集，若都能用SLR(1)方法解决时，称这个文法是SLR(1)文法。,4.5.3 SLR(1)分析法,3 SLR(1)方法 假设一个LR(0)项目集I中有m个移进项目和n个归约项目时： I

11、=A11a11, A22a22, , Ammamm B1 r1, B2 r2,Bn rn 其中，a1, a2, am和FOLLOW(B1),FOLLOW(B2),FOLLOW(Bn)两两相交都为时，可用SLR(1)方法解决： 对于当前输入符号a： (1)a a1, a2, am时，移进; (2) aFOLLOW(Bi)时，用Bi ri归约。,A11a11 A22a22 Ammamm B1r1 B2r2 Bnrn,栈顶串,输入串首字符,分析例4.16中的冲突项目集I1,I2,I9 。,I1: E E E E +T,I2: E T T T *F,I9: E E+T T T *F,FOLLOW(E)

12、=$,FOLLOW(E)=+,),$,FOLLOW(E)=+,),$,4.5.3 SLR(1)分析法,4 SLR(1)分析表 与LR(0)分析表构造基本相同，仅对归约项目修改： 若I中有归约项目A ，对a FOLLOW(A)，置ACTION(I,a)=rj。 结论： 若文法的SLR(1)分析表不含多重定义元素，则称该文法为SLR(1)文法。,构造例 4.15 的SLR(1)分析表。,4.5.4 LR(1)分析法,1 产生原因 SLR(1)对归约项目的处理，会产生无效归约： 即，FOLLOW集中的某些终结符不属于规范句型 解决方法：重新定义LR(1)项目，加入展望符(搜索符)。,4.5.4 LR

13、(1)分析法,2 LR(1)项目定义 二元组A ,a 其中,A 是一个LR(0)项目; a是终结符,称为搜索符,作用于归约项目. 当 ，搜索符a无意义; 当 = ，当输入符号为a时才归约。,4.5.4 LR(1)分析法,3 构造LR(1)项目集族 (0)引入I=s s,$为初始项目; (1)项目集I的闭包函数CLOSURE I的任何项目都属于CLOSURE(I); A B ,a属于CLOSURE(I),若有 B r, b FIRST( a)，则B r,b也属于CLOSURE(I); 重复上步直到项目集不再增大为止。 (2)转换函数GO 与LR(0)转换函数构造方法相同，搜索符在转换函数中不变。

14、,例4.18构造文法G的LR(1)项目集族。,G: 0. S S 1. S LR 2. S R 3. L *R 4. L i 5. R L,令I=S S,$，构造它的LR(1)项目集族。,4.5.4 LR(1)分析法,4 LR(1)分析表的构造方法 与LR(0)分析表构造方法基本相同，仅对归约项目修改： 若归约项目A ,a属于Ik，对搜索符a，置ACTIONk,a=rj.,例4.19 构造G的LR(1)项目集的DFA 和LR(1)分析表。,G: 0. S S 1. S (S) 2. S a,令S S,$为初态集的项目，构造DFA。,4.5.4 LR(1)分析法,5 结论 如果一个文法的LR(1

15、)分析表无多重定义入口; 或任何一个LR(1)项目集中无动作冲突， 称该文法为LR(1)文法。 LR(1)分析法会引起状态数剧增，在应用中受到限制，为些引入LALR(1)方法。,4.5.5 LALR(1)分析法,1 特点 LALR(1)分析法介于LR(1)和SLR(1)之间， 采用与LR(1)相同的搜索符方法， 状态数与SLR(1)相同。 2 基本思想 将LR(1)项目集族中所有同心的项目集合并为一： 同心集合并，心不变，搜索符合并; 转换函数合并。,例4.20 0. S S 1. S (S) 2. S a 利用LR(1) 分析法,构造 其项目集DFA：,I0:S S, $ S (S), $ S a, $,I2:S( S), $ S (S), ) S a, ),I1:SS , $,I3:Sa , $,I4:S(S ), $,I6:Sa , ),I5:S ( S), ) S (S), ) S a, ),I7: S(S) , $,I9: S(S) ,),I8:S(S ) , ),S,a,(,),S,(,a,S,(,a,),合并同心集后的项目集，不含归