编译原理-LR分析法.ppt

7 自底向上分析 (Bottom-up Parsing), LR分析器,7.1 LR分析器 自底向上分析 (Bottom-up Parsing),“L”: left-to-right scanning 自左向右扫描 “R”: rightmost derivation in reverse 最右推导的逆,5.3.4.1 LR分析方法概述 5.3.4.2 LR(0)分析器 5.3.4.3 SLR(1)分析器 5.3.4.4 LR(1)分析器 5.3.4.5 LALR(1)分析器,7.1.1 LR(0)分析器,例：考虑文法GS S aA A cA | d 识别accd是否该文法的句子。,Ac.A A.cA A.d s2,Sa.A A.cA A.d s1,S.aA s0,start,AcA. s4,SaA. s5,Ad. s3,A,d,d,A,c,a,c,Ac.A A.cA A.d s2,Sa.A A.cA A.d s1,S.aA s0,start,AcA. s4,SaA. s5,Ad. s3,A,d,d,A,c,a,c,s0 accd# shift s0as1 ccd# shift s0as1cs2 cd# shift s0as1cs2cs2 d# shift s0as1cs2cs2ds3 # reduce Ad s0as1cs2cs2As4 # reduce AcA s0as1cs2As4 # reduce AcA s0as1As5 # reduce SaA s0S # accept,GS: 1: S aA 2: A cA 3: A d accdL(GS ) ?,根据上述例子，可以总结如下： 一、概念 产生式右部符号被识别的多少, 在产生式右部加上.指示位置。 项目：在文法产生式右部某个位置标有. 的产生式，称为文法的一个LR(0)项目 。 为了叙述方便， 形如 A . 的项目称为归约项目； 形如 A . B 的项目称为待约项目(基本项目)； 形如 A . a 的项目称为移进项目。,定义(有效项目)：项目A1.2对活前缀 = 1 是有效的，如果存在规范推导 S *Aw 12w。 若项目 A1.B2 对活前缀 = 1 是有效的，且 B 是产生式，则项目 B . 对活前缀 = 1 也是有效的。,据假设，存在一个规范推导S *Aw 1 B 2w 设2w * xw, 则对任何B 有规范推导 rm S *Aw 1 B 2w 1 B xw 1 xw 所以 B . 对活前缀 1 也是有效的。, ：伽马 ：艾塔,定义 (有效项目集，项目集规范族)： 文法G的某个活前缀的所有有效项目组成的集合，称为活前缀的LR(0)有效项目集。 文法G的所有有效项目集组成的集合，称为G的LR(0)项目集规范族。,定义 (项目闭包)： 设I是文法G的一个LR(0)项目集合，I的项目闭包closure(I)定义如下： 1、I closure(I)。 2、若项目A . B closure(I)，且 B 是G的产生式，则项目B . closure(I)。 3、closure(I)仅包含上述两条规则确定的LR(0)项目。,定义 (转移函数)： 若I是文法G的一个LR(0)项目集，X是G中的文法符号。定义 go(I, X) = closure(J) 其中 J =A X . | A . X I 称函数go(I, X)为转移函数。 项目A X . 称为项目A . X后继。,二、识别句柄和活前缀的自动机,若文法G = ( VT, VN, S, P)，则识别G的句柄的自动机为DFA M = ( = VTVN， Q = G的LR(0)项目集规范族, q0 = closure( S.S )， F = 所有含归约项目的有效项目集组成的集合， = go(I,X) )。 若将所有状态均视为终态，则识别活前缀的自动机DFA M= ( = VTVN, Q = G的LR(0)项目集规范族, q0 = closure(S.S)， F = Q， = go (I,X) )。,定理： 对于拓广文法G的每一个活前缀 ，它的有效项目集恰好是从识别 G 活前缀的自动机的初态出发，经过 路径所到达的那个状态所代表的项目集合。,例：设拓广文法GS的产生式为： S S S aA | bB A cA | d B cB | d,Ac.A A.cA A.d I4,Sa.A A.cA A.d I2,Sb.B B.cB B.d I3,Bc.B B.cB B.d I5,S.S S.aA S.bB I0,start,SS. I1,AcA. I8,SaA. I6,Ad. I10,A,d,d,A,c,a,b,S,SbB. I7,BcB. I6,Bd. I11,B,d,d,B,c,c,c,识别文法 活前缀的DFA,LR(0)分析表,三、LR分析器的结构和工作过程,LR分析器的结构如图，它的工作过程由算法1描述。,输入,a1 . ai . an #,LR 驱动程序,分析表,输出,栈,sm Xm sm-1 Xm-1 . s0,图4.19 一个LR分析器的模型,action goto,算法1: LR分析算法,输入：一个输入串w和文法G的一张LR分析表M。 输出：若w L(G),输出w的一个自底向上的分析； 否则，输出一个出错表示。 方法：分别置放s0到栈中和w#到输入缓冲器中; 置ip指向w#的第一个符号； repeat forever begin 令s是栈顶状态且a是ip所指向的符号 if actions,a = shift s then begin 将a和s先后压入栈内； 使ip指向输入串中的下一个符号； end,算法1: LR分析算法,else if actions,a = reduce A then begin 从栈顶弹出2*|个符号； 令s是当前栈顶状态； 把A和gotos,A先后入栈； 输出产生式A end else if actions,a = accept then return else error( ) end,7.1.2 SLR(1)分析,若有效项目集中存在冲突动作: I = X . b, A . , B . ,设当前输入符号为a, 1. 若a = b, 则移进; 2. 若aFollow(A), 则用A 进行归约; 3. 若aFollow(B), 则用B 进行归约; 4. 其余情况报错.,SLR分析算法,算法2 (构造SLR分析表) 输入：一个拓广文法G 输出：对于G的分析表的action 子表和goto子表 方法： 1. 构造G的LR(0)项目集规范族。 2. 对于状态Ii的分析动作如下： (a) 若A . aB Ii且 go (Ii ,a)= Ij actioni,a = shift j (b) 若A . Ii, 对于所有a Follow(A) actioni,a = reduce A , A S (c) 若SS. Ii, actioni, #= accept 3. 若go(Ii, A) = Ij, AVN , 则 gotoi,A = j 4. 分析表其余位置为error,SLR(SLR(1)算法：如果文法G按上述算法构造出的分析表不存在冲突动作，则称G为SLR文法。类似地，不难定义LR(0)文法。,若将上述算法的2(b)步中的aFollow(A)改为aVT#，则由此修改后的算法所定义的文法，称为LR(0)文法。,问题. 如何定义LR(0)文法？,例： 设文法GE的产生式为,EE+T | T TT*F | F F (E) | id 并用SLR(1)方法分析id*id+idL(GE) ? G的拓广文法GE： (0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F id (3) TT*F,I0:E.E E.E+T E.T T.T*F T.F F.(E) F.id I1(I0 E): EE. EE.+T I2(I0 T) (I4 T): ET. TT.*F,I3(I0 F) (I4 F) (I6 F): TF. I4(I0 ( ) (I4 ( ) (I6 ( ) (I7 ( ): F(.E) E.E+T E.T T.T*F T.F F.(E) F.id,I5(I0 id) (I4 id) (I6 id) (I7 id): Fid. I6(I1 +) (I8 +) EE+.T T.T*F T.F F.(E) F.id,I7(I2 *) (I9 *): TT*.F F.(E) F.id I8(I4 E): F(E.) EE.+T I9(I6 T): EE+T. TT.*F I10(I7 F): TT*F. I11(I8 ): F(E).,G： (0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F id (3) TT*F,E E,E E+T,E T,T T*F,T F,F (E),F id,E,EE E E+T,T,E T T T*F,(,F ( E) E E+T E T T T*F T F F (E) F id,I0,I1,I2,I6,F,T F,I3,F id,id,I5,T,I2,F,I3,id,I5,(,E E+ T T T*F T F F (E) F id,+,*,T T* F F (E) F id,I7,F (E ) E E+T,E,I8,T,E E+ T T T*F,I9,F,I3,id,I5,(,F,T T* F ,I10,id,I4,(,I4,*,I7,),F (E) ,+,I6,I11,E E,E E+T,E T,T T*F,T F,F (E),F id,E,EE E E+T,T,E T T T*F,(,F ( E) E E+T E T T T*F T F F (E) F id,I0,I1,I2,I6,F,T F,I3,F id,id,I5,T,I2,F,I3,id,I5,(,E E+ T T T*F T F F (E) F id,+,*,T T* F F (E) F id,I7,F (E ) E E+T,E,I8,T,E E+ T T T*F,I9,F,I3,id,I5,(,F,T T* F ,I10,id,I4,(,I4,*,I7,),F (E) ,+,I6,I11,I0,I1,I6,I9,E,+,T,*,to I7,F,to I3,(,to I4,id,to I5,I2,I7,I10,T,*,F,(,to I4,id,to I5,I3,F,I4,I8,I11,(,E,),+,to I6,T,to I4,F,to I5,I5,id,id,(,图4.24 识别文法(4.22)的活前缀的 DFA,I1:EE I2: E T I9: E E+T E E+T T T *F T T *F I=X b , A , B 若bFOLLOW(A) FOLLOW(B)= 则，面对当前读入符号a，状态I的解决方法： 1. 若a=b,则移进。 2. 若ab, 且a FOLLOW(A),则用A 进行归约。 3. 若ab, 且a FOLLOW(B),则用B进行归约。 4. 此外，报错。 这种解决方法是比较简单的，因此称作SLR 分析，由此构造的分析表，称作SLR分析表。,对于表达式文法的例子，FOLLOW集如下：,I1: EE EE+T I2:ET T T *F I9:E E+T T T *F,G： (0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F id (3) TT*F,I1:FOLLOW(E)+= I2: FOLLOW(E)*= I9: FOLLOW(E)*= 可用SLR(1)方法实现,表4.11 文法(4.22)的SLR分析表,Follow(E)=#, +,),表：关于id*id+id的LR分析过程,7.1.3 LR(1)分析,例：设文法G的产生式为 (1) S L=R (2) S R,拓广文法G的LR(0)项目集规范族为: I0= S.S, S.L=R, S.R, L.*R, L.id, R.L I1= SS. I2= SL.=R, RL . I3= SR . I4= L*.R, R.L , L.*R, L.id I5= Lid . I6= SL=.R, R.L , L.*R, L.id I7= L*R. I8= RL. I9= SL=R.,(3) L *R (4) L id (5) R L,I1,I0,I3,I2,I6,I9,I8,I7,I5,I4,start,S,R,L,id,*,=,id,id,L,L,R,*,*,R,图: 识别文法GS活前缀的DFA,GS: (0) SS (1) S L=R (2) S R,(3) L *R (4) L id (5) R L,LR(1)分析表的构造,问题分析：当识别出句柄时，活前缀中与句柄相关的非终结符号A的后继符号集合，一般是非终结符号A的Follow集合的真子集。 例如在前例中，若活前缀L是句柄，则它的后继符号集合为#，而Follow(L) = =, # 。所以，只有在输入符号为#时, 用RL进行归约, 而输入符号为 =时, 移进。 可见用Follow集合来消除分析表的多重入口还是略嫌粗糙。,LR(1)项目: 由LR(0)项目和一个lookahead符号组成 A . , a ,LR(1)分析法的思想： 用活前缀中与句柄相关的非终结符号A的后继符号 (亦称为搜索符)集合，而不是Follow(A)，来避免分析表的多重入口。 重新定义项目， 使每个项目附带一个向前搜索符,定义 (LR(1)有效项目)： LR(1)项目A . , a (aVT#)对活前缀是有效的，如果存在规范推导 S * Aww 且aFirst(w#)。 定理： 若LR(1)项目A . B, a对活前缀是有效的，且 B 是一个产生式，则对任何bFirst(a)，项目B ., b也是活前缀的有效项目。,例. 构造文法GS的LR(1)分析表。 LR(1)项目集规范族,I0: S.S # S.L=R # S.R # L.*R =/# L.id =/# R.L # I1:(I0 S) SS. # I2:(I0 L) SL.=R # RL. # I3:(I0 R) SR. #,I4:(I0 *)(I4 *) L*.R =/# R.L =/# L.*R =/# L.id =/# I5:(I0 id)(I4 id) Lid. =/# I6:(I2 =) SL=.R # R.L # L.*R # L.id # I7:(I4 R) L*R. =/#,I8:(I4 L) RL. =/# I9:(I6 R) SL=R. # I10:(I6 L)(I11 L) RL. # I11:(I6 *)(I11 *) L*.R # R.L # L.*R # L.id # I12:(I6 id)(I11 id) Lid. # I13:(I11 R) L*R. #,GS: (0) SS (1) S L=R (2) S R,(3) L *R (4) L id (5) R L,action,goto,状态,= * id # S L R 0 s4 s5 1 2 3 1 acc 2 s6 r5 3 r2 4 s4 s5 8 7 5 r4 r4 6 s11 s12 10 9 7 r3 r3 8 r5 r5 9 r1 10 r5 11 s11 s12 10 13 12 r4 13 r3,例：构造文法 S C C C c C | d 的LR(1)和LALR分析表。,S.S,# S.CC,# C.cC,c/d C.d,c/d I0,SC.C,# C.cC,# C.d,# I2,SS.,# I1,SCC.,# I5,S,C,C,Cc.C,# C.cC,# C.d,# I6,CcC.,# I9,C,c,Cd.,# I7,d,c,Cc.C, c/d C.cC, c/d C.d, c/d I3,CcC.,c/d I8,C,c,Cd.,c/d I4,d,c,图： 对于文法的转移函数图,文法的LR(1)分析表,S.S S.CC C.cC C.d I0,SC.C C.cC C.d I2,SS. I1,SCC. I5,S,C,C,Cc.C C.cC C.d I3,CcC. I6,C,c,Cd. I4,d,c,c,d,文法的LR(1)分析表,文法的LALR(1)分析表,7.1.4 LALR分析表的构造,LR(k)方法分析能力很强，但是也耗费大量存储空间。在实际应用中，还须简化。观察图4.27可知: 1、从自动机状态等价的角度来看，图中彩色相同的状态是等价的。这些等价状态的特点是，它们的LR(0)有效项目集相同。由于判断是否等价只须比较状态的输出弧，因而不难看出，LR(0)有效项目集相同的状态必定等价。 2、对于初始状态I0，其中的有效项目均可从项目S.S, #推导出来；对于非初始状态I2, I3, I6，则其中“点在最左端”的项目均可由“点不在最左端”的项目推导出来。观察图也可以得到相同结果。因此在实际存储状态时，可以只存储“点不在最左端”的项目。,为了叙述方便，引入“同心项”和项目集的“核”的概念： 定义 (同心项)：如果两个LR(1)项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的心。 定义 (核)： 对于初始状态I0，有效项目S.S, #称为I0的核；而对于非初始状态，则其中 “点不在最左端”的有效项目称为它的核。 LALR分析法的基本思想：在LR(1)项目集规范族中，合并同心项以减少状态的数目；在存储LR(1)有效项目集时，仅存储其中的核。 注意，由于同心项的合并，使项目的搜索符与活前缀的对应关系不唯一，降低了分析器的识别能力，参见以下两例。,Cc.C, c/d/# C.cC, c/d/# C.d, c/d/# I36,I0,Cc+ | c+,CcC.,c/d/# I89,C,活前缀Cc+与搜索符#对应， 而活前缀c+与搜索符c和d对应。 当合并后的自动机识别出活前缀CcC时，若当前的输入符号是c或d，LR(1)分析器马上就能发现出错，而LALR分析器此时则不行，必须先归约，得到活前缀CC后才能发现出错。,例：在图中，I3和I6，I8和I9合并后得到如下部分状态图,问题: LALR分析器识别活前缀的能力是否比LR(1)的差？,答：一样。既然都是识别文法活前缀的自动机，它们就是等价的。,例：考虑文法G SS SaAd | bBd | aBe | bAe Ac Bc 构造G的LR(1)项目集规范族如下,I0: S.S # S.aAd # S.bBd # S.aBe # S.bAe # I1:(I0 S) SS. #,I2:(I0 a) Sa.Ad # Sa.Be # A.c d B.c e I3:(I0 b) Sb.Bd # Sb.Ae # A.c e B.c d,I4:(I2 A) SaA.d # I5:(I2 B) SaB.e # I6:(I2 c) Ac. d Bc. e I7:(I3 B) SbB.d # I8:(I3 A) SbA.e #,I9:(I3 c) Ac. e Bc. d I10:(I4 d) SaAd. # I11:(I4 e) SaBe. # I12:(I7 d) SbBd. # I13:(I8 e) SbAe. #,若将同心项I6和I9合并，则得到项目集 I69: Ac. d/e Bc. d/e 该项目集含“归约-归约”冲突。,因此，文法G是LR(1)文法，但不是LALR文法。,一、LALR(1)分析表的原理性构造方法,构造LR(1)项目集族, 如果它不存在冲突, 就把同心集合并在一起。若合并后不存在归约-归约冲突，则按这个集族构造文法LALR(1)分析表。,算法： LALR分析表的构造 输入：拓广文法G 输出：对于G的LALR(1)分析表 方法：1. 构造文法的LR(1)项目集族C=I0, I1, , In 2.合并C中的同心集，得到C=J0, J1, , Jm 3. 从C出发构造action表: (a) 若A . a,b Ji且 go (Ji ,a)= Jj 置actioni,a = s