编译原理及实现技术：第五章 语法分析-自底向上分析方法

1、第五章 自底向上分析方法主要内容自底向上分析的基本思想简单优先分析方法LR类分析方法基本思想 从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析)两种分析方法 简单优先和LR类分析方法自底向上语法分析方法介绍例：S aAcBe 1 A b 2 A Ab 3 B d 4输入流：abbcde。规范推导过程为： 逆过程:(符号栈，输入流)( -, abbcde)(a,bbcde)(ab,bcde) (aA,bcde)(aAb,cde)(aA,cde)(aAc

2、,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-) S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1简单优先分析一种shift-reduce分析方法根据文法符号的优先关系确定句柄文法符号的优先关系的确定简单优先分析中的三种关系X Y ：当且仅当存在一个产生式AXYX Y ：当且仅当存在一个产生式AXB 并有B+Y。X Y ：当且仅当存在一个产生式ABC 并有B+X，C*Y。 文法G为简单优先文法如果满足： 对于任意两个语法符号X和Y，至多成立一种 优先关系； 任意两个产生式都具有不同的右部。 文法优先关系的确定 FIRST(W) =S | W + S

3、，S(VNVT) LAST(W) =S | W + S，S(VN VT) 若有USiSj: 则有Si Sj ;若有USiW:任SjFIRST(W),有Si Sj若有UVW:任SiLAST(V), Sj(FIRST(W) W)则有Si Sj 输入流的开始和结束标志 ，文法的开始符为Z，SFIRST(Z),有# S，; 且 ZSLAST(Z)，有S #，; 且Z 优先关系矩阵 一个文法的全部优先关系可以用矩阵来表示，称作优先关系矩阵。 例： Z bMb M a M (L L Ma)#)a(bLMZ#)a(bLMZ)a L )bM ( a a ( bLMZFIRST LAST定理：设X1XiXi+1

4、XjXn是一个句型，若有Xi Xi+1 Xi+2 Xj-1 Xj Xj+1则Xi+1Xi+2Xj-1Xj一定是该句型的简单短语。结论： 用来确定句柄的头； 用来确定句柄的内部； 用来确定句柄的结束。简单优先分析算法要点找第一个使SjSj+1的Sj从Sj开始往前(左)找第一个使Si-1Si的Si用SiSi+1Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1Sj (归约) 。重复上述过程，直至输入符结束。如果归约出文法的开始符号则成功。否则失败。简单优先分析实例符号栈 关系 输入流 # b ( a a ) b # b ( a a ) b # b ( a a ) b # b ( a a

5、) b # b ( M a ) b # b ( M a ) b # b ( M a ) b # b ( L b # b M b # b M b # Z # 规范句型：用最右推导导出的句型(也称右句型）。 规范前缀：若存在规范句型，且是终极符串或空串，则称为规范前缀。 规范活前缀：若规范前缀不含句柄或含一个句柄并且具有形式=(是句柄)，则称规范前缀为规范活前缀(简称活前缀）。 归约规范活前缀：若活前缀是含句柄的活前缀，即有=，且是句柄，则称活前缀为归约规范活前缀（简称归约活前缀）。LR类分析方法活前缀的描述性定义：形成可归前缀之前，包括可归前缀在内所有规范句型的前缀都称为活前缀。活前缀 为一个或

6、若干规范句型的前缀。在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。派生定理 开始符产生式的右部是归约活前缀。 如果A是归约活前缀，且A是产生式， 则也是归约活前缀。 任何归约活前缀，都可按上述方式被派生。 设文法开始符的产生式是： S 1|2|n RPSG=1,n|ARPSG,AP 识别规约活前缀的LRSM的构造 例有文法GS: S aAc 1 A Abb 2 A b 3 可归前缀集： aAc aAbb ab LR(0)项目：若A是产生式， 则称A为LR(0)项目(简称项目），也 写作

7、p形式。 项目集的投影：假设IS是LR(0)项目集，则 称下面IS(X) 为IS关于X的投影集： IS(X) = AX |AXIS, X(VTVN). 项目集的闭包：假设IS是LR(0)项目集，则 称下面CLOSURE(IS)为IS的闭包集： CLOSURE(IS)= IS A | YACLOSURE(IS) A是产生式 构造LR(0)活前缀状态机LRSM的算法要点 构造初始状态IS0：IS0=CLOSURE(ZS)，并给IS0标上NO。从已构造的LRSM部分图选择被标为NO的任一状态IS，并做 1 对每个符号XVTVN，做下面动作： 1) 令ISj = CLOSURE( IS(X)。 2)

8、若在LRSM部分图中已有ISk与ISj有相同项目 集，则令m=k；否则构造ISj的状态点ISj， 并给ISj标上NO，同时令m=j。 3) 在IS和ISm之间画有向X边：IS ISm 。 2 给IS标上OK。重复上一步骤，直至没有被标记为NO的状态结点为止。x 例：构造LR(0)状态机 S E $ E E + T E T T id T ( E )0 S E $ E E+T E T T id T ( E )1 SE $ EE +T 5 Tid 3 EE+ T T id T (E) 4 EE+T 9 ET 6 T( E) E E+T E T T id T ( E )7 T(E ) EE +T 8

9、T(E) TT(idETid)E+id(GE的LRSM+2 SE $ $ LRSM给出了所有的可归活前缀 LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“”出现在产 生式右部的最左侧。 形如A P的项目称为归约型项目 形如A P的项目称为移入型项目 移入归约冲突 归约归约冲突 LRSM不能直接用于LR分析 LRSM提供的信息： （1）合法性检查信息Aa （2）移入/归约信息 Aa A （3）移入/归约后的转向状态信息#X1X2XkXtSi0Si1S

10、i2SikSit aiai+1an #移入动作：设Sit的ai输入边所指向的状态为S*#X1X2XkXtSi0Si1Si2SikSitaiS*归约动作：设按AXk+1Xk+2Xt进行归约，则首先归约为ASik的A输出边所指向的状态设为S*，则格局变为：#X1X2XkSi0Si1Si2SikAS*设当前格局是：#X1X2XkSi0Si1Si2SikALR分析模型OutputStack#anaia1LR分析驱动器gotoactionInputStXt LR(0)分析LR分析表Action矩阵：行代表状态，列代表输入符，而矩阵元素则表示相应的分析动作：Shift / Reduce / Accept

11、/ Error GoTo矩阵：行代表状态，而列则代表语法符号（非终极符，终极符），而矩阵元素则表示移入或归约后的转向状态。定义 若IS是一个LR(0)项目集，X是一个文法符号，函数GO（IS, X）定义为GO（IS, X）=CLOSURE（IS(X)），其中IS(X)为LR(0)项目集IS的投影。 假设ISk为LR(0)项目集，则 若AaISk，且GO(ISk, a)= ISi，aVT，则action(ISk, a)=Si，表示把状态ISi和展望符a入栈。若AISk，则对任意aVT#，令action(ISk, a)=Rj，其中产生式A的编号为j，表示用编号为j的产生式进行归约。若ZISk，且Z

12、为拓广产生式的左部非终极符，则action(ISk, #)=Accept。若GO(ISk, A)=ISi，AVN，则goto(ISk, A)=i。其它情形，则Error(n)，表示出错标志，也可不填。LR(0)分析表的构造LR(0)分析例文法如下：S E $E E+T | TT id | (E)$+id()#ETS0S5S619S1S2S3S2AccS3S5S64S4R2 R2R2R2R2R2S5R4R4R4R4R4R4S6S5S679S7S3S8S8R5R5R5R5R5R4S9R3R3R3R3R3R3GoTo表Action表LR(0)驱动程序首先置状态栈、符号栈和输入流的开始格局为：（#S1

13、,#,a1a2an#），则：若当前格局为（#S1S2Sn,#X1X2Xn,aiai+1an#），且action(Sn, ai)=Sj，aiVT，则ai入符号栈，第j个状态Sj入状态栈。即移入后的格局变为：（#S1S2Sn Sj,#X1X2Xnai,ai+1an#）若当前格局为（#S1S2Sn,#X1X2Xn,aiai+1an#），且action(ISn, a)=Rj，aVT#，则按照第j个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号入栈。假设第j个产生式为A，k=| (=Xn-k+1Xn)，则归约后的格局变为：（#S1S2Sn-kS,#X1X2Xn-kA,aiai+1an#）其

14、中S=goto(Sn-k, A)。若状态栈的栈顶状态为Si，输入流当前值为#，且action(Si, #)=Accept，则分析成功。若状态栈的栈顶状态为Si，输入流当前值为a，且action(Si, a)=Error或空，则转向出错处理程序。 LR(0)分析实例状态栈 符号栈 输入串 Action Goto0 id+id$# shift 505 id +id$# reduce4 909 T +id$# reduce3 101 E +id$# shift 3013 E+ id$# shift 50135 E+id $# reduce4 40134 E+T $# reduce2 101 E $#

15、 shift 2012 E$ # accept id+id$ 文法G： Z aAc1 A bB 2 | ba3 B dB 4 | e 5 构造文法的LR(0)状态机，Action表和 goto表，并给出符号串abdec的LR(0) 分析过程。 SLR(1)分析方法LR(0)分析方法的不足LR(0)方法对文法的要求严格。LR(0)方法容易出现冲突状态。一个文法例: GE: SE $ 1EE + T 2ET 3TT P 4 TP 5Pid 6 P( E ) 7 图 GE 的LRSM0 +EPid$+Pid(TTid( idE(P ) 4 E T T T P 7 P id 5 E E + T T T

16、 P T P P id P (E) 3 T P 4 S E $ E E + T 1 S E $ 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7 0 T T P P id P (E) 8 T T * P 9 E E+T T T P 11 P (E ) E E +T 12 P(E) 10P(T P ( E ) E E+T E T T TP T P P id P (E) 6 7 8 S E $ 2如果某个状态有如下项目集： A , B , D d ，则存在着归约-归约，移入-归约冲突 若用A 归约，则当前输入符应在A的Follow集中 若用B 归约，则当前输入

17、符应在B 的Follow集 若移入，则当前输入符应为d。SLR(1)分析条件LRSM0中存在着状态 A1 1，An n， B11 a1r1，Bm mamrm则集合： Follow(A1)、Follow(An)、a1,am 两两相交为空SLR(1)分析表的构造假设ISk为LR(0)项目集，则若AaISk，且GO(ISk, a)= ISi，aVT，则action(ISk, a)=Si，表示把状态ISi和展望符a入栈。若AISk，则对任意aVT，aFollow(A)，令action(ISk, a)=Rj，其中产生式A的编号为j，表示用编号为j的产生式进行归约。若ZISk，且Z为拓广产生式的左部非终极

18、符，则action(ISk, #)=Accept。若GO(ISk, A)=ISi，AVN，则goto(ISk, A)=i。其它情形，则Error(n)，表示出错标志，也可不填。 SLR(1)文法定义对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为SLR(1)文法。从定义可以看出SLR(1)分析方法是用LR(0)项目构成的LRSM0来识别活前缀，因此它们的状态数相同，但是，由于LR(0)方法只看状态栈的内容而SLR(1)方法还要向前看展望符，因此SLR(1)文法要比LR（0）文法广。 图 GE 的LRSM0 +EPid$+Pid(TTid( idE(P ) 4 E T T T

19、 P 7 P id 5 E E + T T T P T P P id P (E) 3 T P 4 S E $ E E + T 1 S E $ 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7 0 T T P P id P (E) 8 T T * P 9 E E+T T T P 11 P (E ) E E +T 12 P(E) 10P(T P ( E ) E E+T E T T TP T P P id P (E) 6 7 8 S E $ 2Follow(S)=#Follow(E)=$,+,)Follow(T)=$,+,),*Follow(P) =$,+,),

20、*#id()$ ETP0S5S6 1741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S6 12747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10State Action Lookahead GoToSLR(1)驱动器初始格局(#S0,#,a1a2an#)若当前格局为 (#S0S1Sn,#X1X2Xn, aiai+1an#)，则若action(Sn, ai)=Sk，则当前格局变为：(#S0S1Sn Sk,#X1X2Xnai, ai+1an#)若action(Sn, ai)=Rp，则当前格局变为：(#S0Sn-

21、kS,#X1X2Xn-kA,aiai+1an#)其中goto(Sn-k, A)=S若action(Sn, ai)=Accept，则成功其它情形，出错。 分析栈 符号栈 输入串 分析动作 转向状态 0 id id+id$# S50,5 id id+id$# R6 40,4 P id+id$# R5 70,7 T id+id$# S80,7,8 T id+id$# S50,7,8,5 Tid +id$# R6 90,7,8,9 TP +id$# R4 70,7 T +id$# R3 10,1 E +id$# S30,1,3 E+ id$# S50,1,3,5 E+id $# R6 40,1,3,4

22、 E+P $# R5 110,1,3,11 E+T $# R2 10,1 E $# S20,1,2 E$ # AcceptSLR(1)与LR(0)SLR(1)和LR(0)具有相同的状态机LR(0)只看分析栈的内容，不考虑当前输入符 SLR(1)考虑输入符，用follow集来解决冲突，因此SLR(1)要比LR(0)分析能力强 括号文法定义如下： Z S$ S (S) S | 构造该文法的SLR(1)分析表，并给出输入流( )( )$的SLR(1)分析过程。主要内容： LR(1)分析方法 Z E E (L,E) E S L L,E L E S id S (S)Z EE(L,E)ESSidS (S)

23、0E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)1ESS(S)2(S状态2存在移入-归约冲突LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。SLR(1)方法简单的把非终极符的follow集做为可归约的依据，并不精确。一个非终极符在不同的位置上出现，它所允许的后继符是不同的。LR(1)针对不同产生式上的非终极符，分别定义其后继符集（展望符集Reducelookup），减少了移入/归约冲突。LR(1)项目：A, a 。LR(0)项目及一个VT#的展望符集合IS:LR(1)项目集IS(X): IS(X) = AX,a |AX,aIS CLOSURE ( IS ) = IS B

24、,b |AB,a CLOSURE(IS), B是产生式 , bFirst(a) GO:若IS是一个LR(1)项目集，X是一个文法符号,则GO（IS, X）=CLOSURE（IS(X)），其中IS(X)为LR(1)项目集IS的投影。 LRSM1的构造算法初始项目集： ISS=CLOSURE( Z S, # )若所有状态都处理完，则结束选一未处理完状态IS，对所有语法符号 X（VTVN #),求ISX,令 IS = CLOSURE(ISX)，若IS不为空： 若IS为新状态，则增加IS IS,把IS加 入LRSM1中；否则为图中某个状态ISj，则在IS 和ISj之间增加一条转换边：IS ISj转到步

25、骤2XX 非SLR(1)文法： Z S S L= R S R L aR L b R L 0ZSSL=RSRLaRLbRL#= #= #1ZS#2SL=RRL#6SL= RR LLaRLb#7SL=R #3SR#4Lb=#10LaR#=5LaRRLLaRLb# =# =# =# =11RL# =8LaRRLLaRLb#9RL#12Lb#13LaR#SLabRb=RLRLabaaLRbLR(1) 分析表的构造假设ISk为LR(1)项目集则：若Z, #ISk，且Z为拓广产生式的左部非终极符，则action(ISk, #)=Accept。若A, aISk，且产生式A的编号为j，则action(ISk,

26、 a)=Rj，表示用编号为j的产生式进行归约。若Aa, bISk，且GO(ISk, a)=ISi，aVT，则action(ISk, a)=Si，表示把状态ISi和展望符a入栈。若GO(ISk, A)= ISi，AVN，则goto(ISk, A)=i。其它情形，则Error(n)，表示出错标志，也可不填。 LR(1)文法的定义对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为LR(1)文法。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=baLR(1)驱动程序LR(1

27、)的驱动程序与SLR(1)的驱动程序是相同的，可共用一个。状态栈 符号栈 输入串 Action GoTo0 aab=b# S5 0,5 a ab=b# S50,5,5 aa b=b# S4 0,5,5,4 aab =b# R5 110,5,5,11 aaL =b# R6 100,5,5,10 aaR =b# R4 110,5,11 aL =b# R6 10 0,5,10 aR =b# R4 20,2 L =b# S60,2,6 L= b# S120,2,6,12 L=b # R5 9 0,2,6,9 L=L # R6 70,2,6,7 L=R # R2 10,1 S # A设文法GS为：SAS

28、 | A aA | b 证明GS是LR(1)文法；构造它的LR(1)分析表；给出符号串abab#的分析过程LALR(1)方法它具有SLR(1)的状态数少的优点和LR(1)的适用范围广的优点。 LALR(1)方法的功能介于SLR(1)和LR(1)之间。LALR(1)状态机的状态个数和LR(0)状态机的状态个数相同，而其展望符则即不采用SLR(1)的Follow集方法，也不采用LR(1)的完全精确法。 LALR(1)的思想来源LR(1)状态机和LR(0)状态机从它们所表示的自动机角度来看是等价的 ；自动机可通过合并等价状态来减少状态个数。 在LR(1)状态机出现很多同心状态，而LALR(1)状态机则不产生同心的状态， 从而大大减少状态数，这就是LALR(1)和LR(1)的主要差别。 LALR(1)状态机的定义方式：用LR(1)状态机来定义；用LR(0)状态机来定义。LALR(1)状态机的构造方法：先构造LR(1)状态机，后构造LALR(1)状态机按LR(1)状态机的方式构造，但发现同心状态 时不产生新状态，而是采用合并状态的方法。先构造LR(0)状态机，而后用传播方式求出每 个项目的展望符集。相关的术语