编译原理——第五章-3.ppt

1、1,编译方法,中国人民大学信息学院 陈文萍,2,第五章 语法分析自下而上分析,5.1 自下而上分析基本问题 5.2算符优先分析 5.3 LR 分析法 5.4 语法分析器的自动产生工具 YACC,3,5.1 自下而上分析基本问题,自下而上语法分析 试图将一个字符串反向归约至开始符号 比自上而下语法分析更有效率，对语法的限制更少 移进归约过程 移进：将一个终结符推进栈 归约：当栈顶形成某个产生式的候选式时，把这些符号从栈中弹出，把产生式的左部符号压入栈,4,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,b,b,c,d,e,A,3） #ab bcde# 归约(

2、Ab),A,5） #aAb cde# 归约(AAb),B,8） # aAcd e# 归约(Bd),S,10） #aAcBe # 归约(SaAcBe),分析符号串abbcde是否GS的句子,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,对输入串abbcde#的移进-规约分析过程,a,5,规范归约,短语、直接短语、句柄的定义： 文法GS，S A，且A 则称是句型相对于非终结符A的短语。 若有A ，则称 是

3、句型 相对于该规则A 的直接短语。 一个句型的最左直接短语称为该句型的句柄。 规范归约: 设是文法G的一个句子，称序列n ,n-1, 0 是的一个规范规约，如果此序列满足： n 0 为文法的开始符，即0 S 对任何i,0i=b,24,文法GE： (0) E#E# (1) EE+T (2) ET (3) TT*F (4) TF (5) FPF|P (6) P(E) (7) Pi,FIRSTVT(E)=# FIRSTVT(E)=+,*,(,i FIRSTVT(T)=*,(,i FIRSTVT(F)=,(,i FIRSTVT(P)=(,i LASTVT(E)=# LASTVT(E)=+,*,),i

4、LASTVT(T)=*,),i LASTVT(F)=,),i LASTVT(P)=),i,1)=关系 由产生式(0)和(6),得 #=#，（=） 2）关系 找形如：AaB的产生式 #E：则#FIRSTVT(E) +T: 则+FIRSTVT(T) *F: 则*FIRSTVT(F) F:则 # E+ ,则 LASTVT(E)+ T* ,则 LASTVT(T)* P ,则 LASTVT(P) E) ,则 LASTVT(E),25,算符优先分析算法,归约过程中，只考虑终结符之间的优先关系来确定可归约串，而与非终结符无关 不存在单个非终结符组成的可归约串，用算符优先分析法的归约过程与规范归约是不同的 为

5、解决在算符优先分析过程中如何寻找可归约串，引进最左素短语的概念,26,算符优先分析算法,算符文法的任一句型有如下形式： #N1a1N2a2.NnanNn+1#, 对于算符优先文法，如果aNb(或ab)出现在句型r中 若ab，则在r中必有含有a而不含b的短语存在 若a=b，则在r中含有a的短语必含有b，反之亦然 句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含更小的素短语。处于句型最左边的素短语为最左素短语 定理：一个算符优先文法G的任何句型的最左素短语是满足下列条件的最左子串NjajNiaiNi+1 aj-1 ai+1,27,算符优先分析算法,文法GE： (1) EE+T (2

6、) ET (3) TT*F (4) TF (5) FPF|P (6) P(E) (7) Pi,句型#T+T*F+i# 其短语有： T+T*F+i T+T*F T T*F i,最左素短语为：T*F,28,算符优先分析算法,K:=1; Sk:=#; Repeat a：下一个输入符号； IF Sk VT THEN j:=k ELSE j:=k-1; WHILE Sja DO BEGIN REPEAT Q:=Sj; IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把sj+1sk 归约为某个N; k:=k+1; Sk:=N; END OF WHILE; IF

7、 Sj a OR Sj=a THEN BEGIN k:=k+1; Sk:=a END ELSE ERROR /*调用出错诊察程序*/ UNTIL a=#,29,算符优先文法的错误处理,错误种类 栈顶的终结符与下一个输入符之间没有优先关系 栈顶出现了素短语,但没有一个产生式的右部为此素短语 错误处理 改变,插入,删除符号 给出错误信息,30,LR分析法,能力强 大部分上下文无关文法都能用LR分析 识别效率高，准确发现输入串错误 难点 手工编写LR分析器工作量大 现实 有LR分析器的生成器，如YACC,31,LR分析法,LR含义 L： 从左到右扫描输入串 ， R：构造最右推导 LR分析特征 栈顶状

8、态为S, 当前输入符号是a时做什么-? 四种技术 LR(0) SLR 规范LR LALR,32,LR分析器,LR分析器模型,33,LR分析器,核心：分析表 动作（ACTION）表: ACTIONS,a告诉分析器状态为S, 当前输入符号是a时做什麽 状态转换（GOTO）表: GOTOS,A规定状态S面对文法符号为A时，下一状态是什么 工作过程：栈的状态序列，已归约串和输入串所构成的三元式的变化过程。 初始状态：（s0, #, a1a2an# ） 分析过程：（ s0 s1 sm, # X0 X1 Xm, aiai+1an# ）,34,LR分析算法,分析器动作：由栈顶状态sm和当前输入符号ai决定，

9、即执行 ACTION sm, ai 的动作。 三元式的变化 1. 若ACTIONsm, ai为移进，且s= GOTOsm, ai： （ s0 s1 sms, # X1 Xmai, ai+1an# ） 2.若ACTIONsm, ai为按产生式A归约, 的长度为r，且s= GOTOsm-r, A： （ s0 s1 sm-rs, # X1 Xm-rA, aiai+1an# ） 3.若ACTIONsm, ai为接受，则终止分析，宣布成功。 4.若ACTIONsm, ai为报错，则终止分析，报告错误。,35,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,Si:移进

10、，并将状态i进栈 ri:用第i个产生式归约，同时状态栈与文法符号栈退出相应个符号，根据GOTO表将相应状态入栈,LR分析算法,36,步骤,符号栈,输入符号串,动作,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# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(

11、AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,37,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,*,8,38,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a b

12、bcde# 移进 02 S4,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,39,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,40,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #

13、a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,41,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0

14、236 r3 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,*,8,42,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,状态栈,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B

15、,e,d,8,43,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,状态栈,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,44,步骤,符号栈,输入符号串,动作,1） # abbc

16、de# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,45,步骤,符号栈,输入符号串,动作,1） # abbcde#

17、移进 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,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,*,8,46,步骤,符号栈,输入

18、符号串,动作,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,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,G

19、OTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,*,8,47,步骤,符号栈,输入符号串,动作,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# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） #

20、 aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,*,8,48,LR文法,LR文法: 分析表的每个入口唯一确定 多数程序设计语言都可以用LR文法描述 LR(k)文法: 每步顶多向前检查k个输入符号 考虑 k=1 的情况,49,LR(0),几个定义： 前缀: 字的任意首部 例如: abc的前缀有 , a, ab, abc 活前缀：规范句型的一个前缀，且不含句柄之后的任何符号。 已扫描部分可归约为一个活前缀，则扫描过的部

21、分没出错 活前缀与句柄之间的关系 活前缀不含有句柄的任何符号 期望从剩余输入串中能够看到由某产生式A的右部所推导出的符号串； 活前缀只含有句柄的部分符号 某产生式A12的右部子串1已经出现在栈顶，期待从剩余的输入串中能够看到2推导出的符号串； 活前缀已经含有句柄的全部符号 某一产生式A的右部符号串已经出现在栈顶，用该产生式进行归约。,50,LR(0),LR(0)项目：文法G的每一个产生式的右部符号添加一个圆点 表示已有多大一部分被识别（出现在栈顶）的情况，圆点指示位置。 例：Ab，项目为：A.b， A.b， Ab. 可看作保持有关分析栈及移进归约分析过程中信息的有穷自动机的状态 根据圆点所在的

22、位置和圆点后是终结符还是非终结符或为空把项目分为以下几种： 移进项目，形如 A a a是终结符, , V* 以下同 待约项目，形如 A B 归约项目，形如 A 接受项目，形如 S S A的LR(0)项目只有A 是归约项目,51,活前缀与LR项目,定义：有效项目 项目A12对活前缀=1是有效的，如果存在一个规范推倒导：,推论：若项目AB对活前缀=是有效的，并且B是一个产生式，则项目B对活前缀=也是有效的。,52,LR项目集,文法G的某个活前缀的所有有效项目组成的集合称为的有效项目集； 文法G的所有有效项目集组成的集合称为G的LR(0)项目集规范族。,53,LR(0)项目的NFA,NFA的初态：对

23、文法G拓广为G，G包含整个G，此外加进一个新产生式SS。S和S分别为G和G的开始符号。S为LR(0)项目NFA的初态。 例：文法 S S, S ( S ) S | 存在着以下的8个项目： S.S SS. S. ( S ) S S( .S ) S S( S. )S S( S ) .S S( S )S. S.,54,LR(0)项目的NFA,状态之间的转换关系确定方法为如下： 若i项目(状态i)为：XX1X2Xi-1XiXn j项目(状态i)为：XX1X2Xi-1XiXi+1Xn i项目和j项目出于同一个产生式，那么从状态i到状态j连一条标记为Xi的箭弧。 如果状态i为 XA,则画标记为的箭弧到状态

24、A，即A的所有产生式圆点在最左边的状态,55,LR(0)项目的NFA,S.S SS. S. ( S ) S S( .S ) S S( S. )S S( S ) .S S( S )S. S.,56,LR(0)项目的DFA,LR(0)项目的NFA用子集法确定化为DFA,57,构造LR(0)项目集规范族,构造LR（0）项目的闭包CLOSURE（I） 算法： function CLOSURE (I); /* I 是项目集*/ J:= I; repeat for J 中的每个项目A .B 和产生式 B ，若B . 不在J中 do 将 B . 加到J中 until 再没有项目加到J中 return J ;

25、 定义：GO (I,x) = CLOSURE(J) 其中， I:项目集，x: 文法符号， J=任何形如A x. 的项目|A .x I,58,构造LR(0)项目集规范族,通过CLOSURE和GO构造文法G的LR(0)项目集规范族。构造算法：（ C=I0, I1, . In ） Procedure itemsets(G); Begin C := CLOSURE (S .S) Repeat For C 中每一项目集I和每一文法符号x Do if GO(I,x) 非空且不属于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End;,59,LR(0) 分析表的构造,算法：假定C=I

26、0, I1,，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G 的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION和GOTO可按如下方法构造： 1.若项目A.a属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”; 2.若项目A.属于Ik, 那么，对任何终结符a, 置ACTIONk, a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式； 3.若项目SS.属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”; 4.若GO (Ik, A)

27、= Ij, A为非终结符，则置GOTO(k, A)=j; 5.分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,60,LR(0)文法,按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为一个LR（0）文法。 LR(0)文法是无二义的。,61,思考,如果项目A12对活前缀=1是有效的，当1在分析栈的栈顶时 如果2，表示句柄没有完全入栈，分析器应该移进 如果2， 1是句柄，应该用产生式A1归约 一个活前缀的有效项目集就是从上述DFA的初态出发，沿着标记为的路径到达的那个项目集（状态） 这是L

28、R分析理论的一条基本定理 当活前缀在栈顶时，其有效项目集（即栈顶状态）概括了所有可以从栈中收集到的有用信息 冲突通过向前看几个输入符号或许能够解决,62,LR（0）分析,例 GS为: S a A c B e A b A Ab B d 1)构造识别活前缀的DFA 2)构造它的LR(0)分析表 3)分别给出对输入符号串abbcde和Abbbce的LR(0)分析步骤,63,GS拓广为: S S S a A c B e A b A Ab B d,I0 : S S S a A c B e,I1 : S S ,I2 : S a A c B e A b A Ab,I3 : S a A c B e A A b

29、,I4 : A b ,I5 : S a A c B e B d,I7 : S a A c B e,I8 : B d ,I9 : S a A c B e ,I6 : A A b ,S,a,A,b,b,c,B,e,d,GL= ab+ cde,64,例 GS的LR(0)分析表,65,Step states. Syms. The rest of input action goto 1 0 # abbcde# s2 2 02 #a bbcde# s4 3 024 #ab bcde# r2 3 4 023 #aA bcde# s6 5 0236 #aAb cde# r3 3 6 023 #aA cde#

30、s5 7 0235 #aAc de# s8 8 02358 #aAcd e# r4 7 9 02357 #aAcB e# s9 10 023579 #aAcBe # r1 1 11 01 #S # acc,对输入串abbcde#的分析过程,66,Step states. Syms. The rest of input action goto 1 0 # abbce# s2 2 02 #a bbce# s4 3 024 #ab bce# r2 3 4 023 #aA bce# s6 5 0236 #aAb ce# r3 3 6 023 #aA ce# s5 7 0235 #aAc e# 出错 说明abbce#不是 文法 GS的句子,对输入串abbce#的分析过程,67,SLR分析法,为什么SLR？ LR(0)文