Parsing自底向上的分析.ppt

,Chapter 4.4 Bottom-Up Parsing自底向上的分析,4.4.1 OVERVIEW OF BOTTOM-UP PARSING 自底向上分析概述 4.4.2 FINITE AUTOMATA OF LR(0) ITEMS AND LR(0) PARSING LR(0)项的有穷自动机与LR(0) 分析 4.4.3 SLR(1) Parsing SLR(1)分析 4.4.4 General LR(1) and LALR(1) Parsing 一般的LR(1)和LALR(1)分析,4.4.1 OVERVIEW OF BOTTOM-UP PARSING 自底向上分析概述,Shift a terminal from the front of the input to the top of the stack. Reduce a string at the top of the stack to a nonterminal A, given the BNF choice A., A bottom-up parser has two possible actions (besides “accept“),1)已知G: S(S) S,请应用自底向上分析方法解() L(G)?, example,6 $S $ S S规约,1 $ () $ 移进,5 $(S)S $ S (S)S规约,3 $(S ) $ 移进,4 $(S) $ S规约,2 $( ) $ S规约,(2)分析过程,7 $S $ 接受,S=S S S =(S)S S(S)S =(S) S =( ) S,2)已知G: EE + n | n ,请应用自底向上分析方法解n+n L(G)?, example,6 $E $ EE规约,1 $ n+n$ 移进,5 $E+n $ EE+n规约,3 $E +n$ 移进,4 $E+ n$ 移进,2 $n +n$ En规约,(2)分析过程,7 $E $ 接受,E=E E E =E+n EE+n =n+n En,3)已知文法GS,请应用自底向上分析方法判断accd L(G)? S aA A cA | d, example,(2)有穷自动机,Ac.A A.cA A.d s2,Sa.A A.cA A.d s1,SS S.aA s0,start,AcA. s4,SaA. s5,Ad. s3,A,d,d,A,c,a,c,SS. s,S,6 $s0as1cs2cs2As4 $ reduce AcA,1 $s0 accd$ shift,5 $s0as1cs2cs2ds3 $ reduce Ad,3 $ s0as1cs2 cd$ shift,4 $ s0as1cs2cs2 d$ shift,2 $ s0as1 ccd$ shift,分析栈 输入 动作,(3)分析过程,7 $ s0as1cs2As4 $ reduce AcA,Ac.A A.cA A.d s2,Sa.A A.cA A.d s1,S.S S.aA s0,start,AcA. s4,SaA. s5,Ad. s3,A,d,d,A,c,a,c,(2)有穷自动机,SS S aA A cA | d,解： (1)拓广文法,8 $ s0as1As5 $ reduce SaA,9 $ s0S $ reduce SS,10 $ S $ accept,SS. s,S, 相关术语,S=S =(S)S =(S) = ( ) 推导中的终结符和非终结符的每个中间串称为右句型。,1) the right sentential form 右句型,当前栈和输入串之间发生了间隔，例E | +n, E+ | n, 在每种情况下，分析栈的符号序列被称为右句型的可行前缀。 E, E+, E+n都是右句型E+n的可行前缀。,2) 右句型的可行前缀 viable prefix（活前缀）,这个串，在右句子格式中发生的位置以及用来规约它的产生式被称为右句型的句柄。,3) The handle of the right sentential form 右句型的句柄,4.4.2 FINITE AUTOMATA OF LR(0) ITEMS AND LR(0) PARSING LR(0)项的有穷自动机与LR(0) 分析,4.4.2.1 LR(0) ITEMS LR(0)项,a production choice with a distinguished position in its right-hand side.,1) LR(0) ITEMS LR(0)项,if A is a production choice, and if and Y are any two strings of symbols (including the empty string s) such that = , then A is an LR(0) item.,Example,1)已知G，求其项目。 S S S (S)S|, example,2)已知G，求其项目。 EE EE + n | n, 相关术语,在文法产生式右部某个位置标有. 的产生式，称为文法的一个LR(0)项目 。,1) 项目,形如 A . 的项目称为初始项目； 形如 A . 的项目称为归约项目（完整项目）； 形如 A . B 的项目称为待约项目(基本项目) BN； 形如 A . a 的项目称为移进项目(基本项目) aT。, 相关术语,文法G的某个活前缀的所有有效项目组成的集合，称为活前缀的LR(0)有效项目集。 文法G的所有有效项目集组成的集合，称为G的LR(0)项目集规范族。,3)有效项目集，项目集规范族, 相关术语,设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)项目。,4)项目闭包,若I是文法G的一个LR(0)项目集，X是G中的文法符号。 go(I, X) = closure(J) 其中J =AX . | A . XI 称函数go(I, X)为转移函数。 项目A X . 称为项目A . X后继。,5)转移函数, 相关术语,若文法G = ( VT, VN, S, P)，则识别G的句柄的自动机为DFA M = ( = VTVN， Q = G的LR(0)项目集规范族, q0 = closure( S.S )， F = 所有含归约项目的有效项目集组成的集合， = go(I,X) )。,6) 识别G的句柄的自动机,若将所有状态均视为终态，则识别活前缀的自动机DFA M= ( = VTVN, Q = G的LR(0)项目集规范族, q0 = closure(S.S)， F = Q， = go (I,X) )。,7) 识别活前缀的自动机, 相关术语,对于拓广文法G的每一个活前缀 ，它的有效项目集恰好是从识别 G 活前缀的自动机的初态出发，经过 路径所到达的那个状态所代表的项目集合。,8)定理,4.4.2.2 Finite Automata of Items 项目的有穷自动机, LR(0)项的NFA的转换,AX,AX ,X,AX,X, X,1)已知G，求其DFA。 S S S (S)S|, example,S S S S S (S)S S (S)S S (S)S S (S)S S (S)S S ,解：,SS,S(S)S,S(S)S,S(S)S,S(S)S,),(,DFA,NFA,SS S(S)S S ,S(S)S S(S)S S ,S(S)S S(S)S S ,SS,S(S)S,S,(,),S,(,(,0,1,2,S(S)S,S,3,4,5, example,解：,2)已知G，求其DFA 。 EE EE + n | n,EE EE EE + n EE + n EE + n EE + n EE EE,DFA,例：已知拓广文法GS，求其LR(0)的分析表。 S S S aA | bB A cA | d B cB | d,核心项,所有的闭包项都是初始项,(1)识别文法活前缀的DFA,0 SS 1 SaA 2 SbB 3 AcA 4 Ad 5 BcB 6 Bd,输入,a1 . ai . an $,LR 驱动程序,分析表,输出,栈,sm Xm sm-1 Xm-1 . s0,action goto, LR分析器的结构和工作过程, The LR (0) parsing algorithm LR分析算法,Let s be the current state (at the top of the parsing stack).Then actions are defined as follows: 1. If state s contains any item of the form A X, where X is a terminal. Then the action is to shift the current input token on to the stack. If this token is X. and state s contains item A X, then the new state to be pushed on the stack is the state containing the item A X. If this token is not X for some item in state s of the form just described, an error is declared.,2. If state s contains any complete item (an item of the form A), then the action is to reduce by the rule A . A reduction by the rule S S, where s is the start state, is equivalent to acceptance, provided the input is empty, and error if the input is not empty. In all other cases, for new state is computed as follows. Remove the string and all of its corresponding states from the parsing stack (the string Y must be at the top of the stack, according to the way the DFA is constructed). Correspondingly, back up in the DFA to the state from which the construction of began (this must be the state uncovered by the removal of ). Again, by the construction of the DFA, this state must contain an item of the form B A. Push A onto the stack, and push (as the new state) the state containing the item B A. (Note that this corresponds to following the transition on A in the DFA, which is indeed reasonable, since we are pushing A onto the stack.),输入：一个输入串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, 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, example,例：已知文法GA，求其LR(0)的分析表，并判断(a)L(G)? A ( A ) | a,(3)LR(0)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程,4.4.3 SLR(1) Parsing SLR(1)分析,Let s be the current state (at the top of the parsing stack). Then. actions are defined as follows: 1. If state s contains any item of form A X,where X is a terminal, and X is the next token in the input string, then the action is to shift the current input token onto the stack, and the new state to be pushed on the stack is the state containing the item A X., The SLR(1) parsing algorithm,2 If state s contains the complete item A , and the next token in the inupt string is in Follow(A), then the action is to reduce by the rule A . A reduction by the rule S S, where s is the start state, is equivalent to acceptance; this will happen only if the next input token is $. In all other cases, the new state is computed as follows. Remove the siring Y and all of its corresponding states from the parsing stack. Correspondingly, back up in the DFA to the state from which the construction of began. By construction, this state must contain an item of the form B A. Push A onto the stack, and push the state containing the item B A. 3. If the next input token is such that neither of the above two cases applies, an error is declared .,A grammar is an SLR(l) grammar if the application of the above SLR( 1 ) parsing rules results in no ambiguity. In particular, a grammar is SLR( 1) if and only if, for any state s, the following two conditions are satisfied: 1. For any item A Xin s with X a terminal, there is no complete item B . in s with X in Follow(B). 2. For any two complete items A and B in s, Follow(A) Follow(B) is empty., Conditions,若有效项目集中存在冲突动作: I = X . b, A . , B . ,设当前输入符号为a, 1. 若a = b, 则移进; 2. 若aFollow(A), 则用A 进行归约; 3. 若aFollow(B), 则用B 进行归约; 4. 其余情况报错., SLR(1)分析, 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)文法？, example,解： (1)拓广文法 G的拓广文法GE： (0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F id (3) TT*F (2)识别文法的活前缀的 DFA (3)SLR(1)分析表 (4)分析过程,例：已知文法GE，并用SLR(1)方法分析id*id+idL(GE) ? EE+T | T TT*F | F F (E) | id,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,G：(0) E E (1) EE+T (2) ET (3) TT*F (4) TF (5) F (E) (6) F id,(2)识别文法的活前缀的 DFA,(2)识别文法的活前缀的 DFA,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,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)方法实现,(3)SLR分析表,Follow(E)=$, +,),(4) id*id+id的LR分析过程,分析栈,输入串,动作,(1) 0 (2) 0id5 (3) 0F3 (4) 0T2 (5) 0T2*7 (6) 0T2*7id5 (7) 0T2*7F10 (8) 0T2 (9) 0E1 (10) 0E1+6 (11) 0E1+6id5 (12) 0E1+6F3 (13) 0E1+6T9 (14) 0E1,id*id+id$ *id+id$ *id+id$ *id+id$ id+id$ +id$ +id$ +id$ +id$ id$ $ $ $ $,shift reduce by Fid reduce by TF shift shift reduce by Fid reduce by TT*F reduce by ET shift shift reduce by Fid reduce by TF reduce by EE+T accept, example,例：已知文法GE，求其SLR(1)的分析表，并判断n+nL(G)? EE + n | n,(3)SLR(1)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程, example,例：已知文法GS，求其SLR(1)的分析表，并判断( )( )L(G)? S (S)S|,(3)SLR(1)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程,4.4.4 General LR(1) and LALR(1) Parsing 一般的LR(1)和LALR(1)分析,(part 1).Given an LR(1) item AX,a, where X is any symbol (terminal or nonterminal ), there is a transition on X to the item A X,a (part 2). Given an LR(1) item AB,a, where B is a nonterminal, there are-transitions to items B,b for every production B and for every token b in First(a)., Definition of LR(1) transitions, example,例：已知文法GS，求其LR(1)的分析表，并判断 id:=idL(G)? S id | V := E V id E V | n,(3)LR(1)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程,解: (1) 拓广文法 S S S id S V := E V id E V E n (2) 识别文法活前缀的DFA,SV. :=E,$,SV:=.E,$ E.V ,$ E.n ,$ V .id,$,Sid. ,$ Vid. ,:=,S .S ,$ S .id ,$ S .V := E ,$ V .id ,:=,start,SS. ,$,EV. ,$,V,:=,id,V,S,SV:=E.,$,En. ,$,n,E,0,1,2,3,4,5,6,7,Vid. ,$,id,8,(3) LR(1)分析表,id := n $ S V E,0 1 2 3 4 5 6 7 8,Action goto,S2 1 3,ACC,R3 R1 S4 S8 S7 S6 6 5 R2 R4 R5 R3,SV. :=E,$,SV:=.E,$ E.V ,$ E.n ,$ V .id,$,Sid. ,$ Vid. ,:=,S .S ,$ S .id ,$ S .V := E ,$ V .id ,:=,start,SS. ,$,EV. ,$,V,:=,id,V,S,SV:=E.,$,En. ,$,n,E,0,1,2,3,4,5,6,7,Vid. ,$,id,8,0 S S 1 S id 2 S V := E 3 V id 4 E V 5 E n,(4) id:=id的LR分析过程,分析栈,输入串,动作,(1) 0 (2) 0id2 (3) 0V3 (4) 0V3:=4 (5) 0V3:=4id8 (6) 0V3:=4V6 (7) 0V3:=4E5 (8) 0S1,id:=id $ :=id $ :=id $ id $ $ $ $ $,shift reduce by V id shift shift reduce by V id reduce by E V reduce by S V := E accept,id := n $ S V E,0 1 2 3 4 5 6 7 8,Action goto,S2 1 3,ACC,R3 R1 S4 S8 S7 S6 6 5 R2 R4 R5 R3,0 S S 1 S id 2 S V := E 3 V id 4 E V 5 E n, example,例：已知文法GA，求其LR(1)的分析表，并判断(a)L(G)? A ( A ) | a,(3)LR(1)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程,解: (1) 拓广文法 A A A ( A ) | a (2) 识别文法活前缀的DFA,Aa. ,$,Aa. ,),A(.A) ,) A.(A) ,) A.a ,),A(.A),$ A.(A) ,) A.a ,),A.A ,$ A.(A),$ A.a ,$,start,AA. ,$,A(A .),),A(A .),$,A,a,a,A,(,(,a,A,A(A) .,$,A(A) .,),),),0,1,2,3,4,5,6,7,8,9,(3) LR(1)分析表,( ) a $ A,0 1 2 3 4 5 6 7 8 9,Action goto,S2 S3 1,ACC,S5 S6 4 R2 S7 S5 S6 8 R2 R1 S9 R1,(4) (a)的LR 分析过程,分析栈,输入串,动作,(1) 0 (2) 0(2 (3) 0(2(5 (4) 0(2(5a6 (5) 0(2(5A8 (6) 0(2(5A8)9 (7) 0(2A4 (8) 0(2A4)7 (9) 0A1,(a) $ (a) $ a) $ ) $ )$ )$ )$ $ $,shift shift shift reduce by Aa shift reduce by A(A) shift reduce by A(A) accept,0 AA 1 A(A) 2 Aa,( ) a $ A,0 1 2 3 4 5 6 7 8 9,Action goto,S2 S3 1,ACC,S5 S6 4 R2 S7 S5 S6 8 R2 R1 S9 R1, example,例：已知文法GS，求其LR(1)的分析表 S C C C c C | d,(3)LR(1)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程, FIRST PRINCIPLE OF LALR(1) PARSING The core of a state of the DFA of LR(l) items is a state of the DFA of LR(0)-items. SECOND PRINCIPLE OF LALR(1) PARSING Given two states s1 and s2 of the DFA of LR(l) items that have the same core, suppose there is a transition on the symbol X from s1 to a state t1. Then there is also a transition on X from state s2 to a state t2, and the states t1 and t2 have the same core., Definition of LALR(1) transitions,对于初始状态I0，有效项目S.S, $称为I0的核；而对于非初始状态，则其中 “点不在最左端”的有效项目称为它的核。, 相关术语,1)同心项,如果两个LR(1)项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的心。,2)核,在LR(1)项目集规范族中， LALR分析法合并同心项以减少状态的数目；在存储LR(1)有效项目集时，仅存储其中的核。,由于同心项的合并，使项目的搜索符与活前缀的对应关系不唯一，降低了分析器的识别能力。, example,例：已知文法GS，求其LR(1)的分析表 SS SaAd | bBd | aBe | bAe Ac Bc,(3)LR(1)分析表,(2)识别文法活前缀的DFA,解: (1)拓广文法,(4)分析过程,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. $,I69: Ac. d/e Bc. d/e,合并同心项,解:识别文法活前缀的DFA,若将同心项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 = shift j (b) 若A. ,a Ji,置actioni,a = r A , A S (c) 若SS., $ Ji,