第五章语法自底向上方法

1、主要内容主要内容l自底向上分析的基本思想自底向上分析的基本思想l简单优先分析方法简单优先分析方法lLRLR类分析方法类分析方法基本思想基本思想 从待分析的符号串开始，自左向右进行从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文应产生式的左部非终极符，直到将输入串归约为文法的开始符。法的开始符。( (移入移入- -归约分析归约分析) )两种分析方法两种分析方法 简单优先和简单优先和LRLR类分

2、析方法类分析方法5.1 自底向上语法分析方法介绍自底向上语法分析方法介绍l例：例：S aAcBe 1 A b 2 A Ab 3 B d 4l输入流：输入流：abbcde。l规范推导过程为：规范推导过程为： 逆过程逆过程: :( (符号栈，输入流符号栈，输入流) )( -, abbcde)( -, abbcde)(a,bbcde)(a,bbcde)(a(ab b,bcde) ,bcde) (aA,bcde)(aA,bcde)(a(aAbAb,cde),cde)(aA,cde)(aA,cde)(aAc,de)(aAc,de)(aAc(aAcd d,e),e)(aAcB,e)(aAcB,e)( (a

3、AcBeaAcBe,-),-)(S,-)(S,-) S S aAcBeaAcBe11 aAc aAcd d44e e11 a aAbAb33cdcd44e e11 a ab b22b b33cdcd44e e11一种一种shift-reduce分析方法分析方法根据文法符号的优先关系确定句柄根据文法符号的优先关系确定句柄文法符号的优先关系的确定文法符号的优先关系的确定X X Y Y ：当且仅当存在一个产生式当且仅当存在一个产生式AXYAXYX X Y Y ：当且仅当存在一个产生式当且仅当存在一个产生式AXBAXB 并有并有B B+ +YY。X X Y Y ：当且仅当存在一个产生式当且仅当存在一个

4、产生式ABCABC 并有并有B B+ +XX，C C* *YY。 文法文法G G为为简单优先文法简单优先文法如果满足：如果满足： 对于任意两个语法符号对于任意两个语法符号X X和和Y Y，至多成立一种至多成立一种 优先关系；优先关系； 任意两个产生式都具有不同的右部。任意两个产生式都具有不同的右部。 FIRST(W) =S | W + S，S (VN VT) LAST(W) =S | W + S，S (VN VT) 若有若有USiSj: 则有则有Si Sj ;若有若有USiW:任任Sj FIRST(W),有有Si Sj若有若有UVW:任任Si LAST(V), Sj (FIRST(W) W)则

5、有则有Si Sj 输入流的开始和结束标志输入流的开始和结束标志 ，文法的开始符为，文法的开始符为Z，S FIRST(Z),有有# S，; 且且 ZS LAST(Z)，有有S #，; 且且Z 优先关系矩阵优先关系矩阵 一个文法的全部优先关系可以用矩阵一个文法的全部优先关系可以用矩阵来表示，称作优先关系矩阵。来表示，称作优先关系矩阵。l 例：例：l Z bMbl M a l M (Ll L Ma)#)a(bLMZ#)a(bLMZ)a L )bM ( a a ( bLMZFIRSTFIRST LASTLAST l定理定理：设设X1XiXi+1XjXn是一个句型，若有是一个句型，若有Xi Xi+1 X

6、i+2 Xj-1 Xj Xj+1则则Xi+1Xi+2Xj-1Xj一定是该句型的简单短语。一定是该句型的简单短语。l结论：结论： 用来确定句柄的头；用来确定句柄的头； 用来确定句柄用来确定句柄的内部；的内部； 用来确定句柄的结束。用来确定句柄的结束。l找第一个使找第一个使Sj Sj+1的的Sj。l从从Sj开始往前开始往前(左左)找第一个使找第一个使Si-1 Si的的Si。l用用SiSi+1Sj去查产生式的右部，并用相应去查产生式的右部，并用相应的左部符号代替句柄的左部符号代替句柄SiSi+1Sj (归约归约) 。l重复上述过程，直至输入符结束。如果归重复上述过程，直至输入符结束。如果归约出文法的

7、开始符号则成功。否则失败。约出文法的开始符号则成功。否则失败。符号栈符号栈 关系关系 输入流输入流 # b ( a a ) b # b ( a a ) b # b ( a a ) b # b ( a a ) b # b ( M a ) b # b ( M a ) b # b ( M a ) b # b ( L b # b M b # b M b # Z # 规范句型：规范句型：用最右推导导出的句型用最右推导导出的句型(也称右句也称右句型）。型）。 规范前缀：规范前缀：若存在规范句型若存在规范句型，且，且 是终极符是终极符串或空串，则称串或空串，则称 为规范前缀。为规范前缀。 规范活前缀：规范活

8、前缀：若规范前缀若规范前缀 不含句柄或含一个不含句柄或含一个句柄并且具有形式句柄并且具有形式 =( 是句柄是句柄)，则称规范，则称规范前缀前缀 为规范活前缀为规范活前缀(简称活前缀）。简称活前缀）。 归约规范活前缀：归约规范活前缀：若活前缀若活前缀 是含句柄的活前是含句柄的活前缀，即有缀，即有 =，且，且 是句柄，则称活前缀是句柄，则称活前缀 为归为归约规范活前缀（简称归约活前缀）。约规范活前缀（简称归约活前缀）。l活前缀的描述性定义：活前缀的描述性定义：形成可归前缀之形成可归前缀之前，包括可归前缀在内所有规范句型的前，包括可归前缀在内所有规范句型的前缀都称为活前缀。前缀都称为活前缀。l活前缀

9、活前缀 为一个或若干规范句型的前缀。为一个或若干规范句型的前缀。l在规范归约过程中的任何时刻已分析过在规范归约过程中的任何时刻已分析过的部分，即在分析栈（符号栈）中的符的部分，即在分析栈（符号栈）中的符号串均为规范句型的活前缀，表明输入号串均为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范串的已被分析过的部分是该文法某规范句型的一个正确部分。句型的一个正确部分。l线性正则式：线性正则式：不含不含*符号的正则表达式符号的正则表达式lLRSM：(Linear Regular States Machine)(1)从从LRSM可构造出恰好接受给定所有正可构造出恰好接受给定所有正 则式的确

10、定自动机则式的确定自动机DA；(2)从从LRSM的终止状态可判定接受的是哪的终止状态可判定接受的是哪 个正则式；个正则式；(3)从从LRSM的状态可判定一个正则式是不的状态可判定一个正则式是不 是另一正则式的前缀。是另一正则式的前缀。 l项目项目：假设：假设P是一个正则式，则我们称形是一个正则式，则我们称形如如P的表示为项目，其中的表示为项目，其中P是正则式编号。是正则式编号。其中黑点可出现于任何位置上。其中黑点可出现于任何位置上。 l项目集项目集：用：用IS表示表示lIS(X) ： SubItems(IS,X)= XP|X P IS,X SymbSet 简记为简记为IS(X) 假设有线性正则

11、项集假设有线性正则项集: :IS = IS = abd1,abd1, abc2,abc2, bc3,debc3,de 4,4, de de c5,c5, 则有则有 ：ISIS(a)(a) = a = a bd1, abd1, a bc2 bc2 ISIS(b)(b) = b= b c3 c3 ISIS(c)(c) = dec = dec 4 4 给定正则式集给定正则式集 1 1, , 2 2, n n ：构造初始项目集构造初始项目集ISIS0 0=1 11,.,1,.,n nnn，并给并给ISIS0 0标上标上NO(NO(表示未处理）。表示未处理）。从已构造的从已构造的LRSMLRSM部分图选

12、择被标为部分图选择被标为NONO的任一项目集的任一项目集ISISi i，并做下面动作：并做下面动作： 1 1 对每个符号对每个符号X X SymbSetSymbSet： 若若ISISi iX X非空，给非空，给ISISi iX X标上标上NONO，并在并在ISISi i和和ISISi iX X之间之间 画有向画有向X X边边: :ISISi i ISISi iX X。 2 2 给给ISISi i标上标上OKOK。 重复上述步骤二，直至在重复上述步骤二，直至在LRSMLRSM中没有被标记为中没有被标记为NONO的的 状态（项目集）节点为止。状态（项目集）节点为止。 abdcdbecdabc1ab

13、c1abd2abd2 ad3 ad3 bec4bec4bed5bed5S S0 0a abc1bc1a abd2bd2 a ad3 d3 S S1 1=S=S0 0a aababc1c1ababd2d2S S3 3b bec4ec4b bed5ed5S S2 2bebec4c4bebed5d5S S5 5abcabc11S S6 6abdabd22S S7 7adad33S S4 4becbec44S S8 8bedbed55S S9 9正则式到正则式到LRSMLRSM的转换例的转换例l展望符展望符：Lookup(S)Lookup(S)l有效前缀集有效前缀集 Prefix(S)Prefix(S

14、)l状态状态SiSi中的项目中的项目 PP表示表示 部分已被输部分已被输入，而且是入，而且是SiSi的前缀的后缀，的前缀的后缀， 表示待输表示待输入部分。入部分。l可构造接受给定正则式集合的可构造接受给定正则式集合的DADAl严格前缀：严格前缀：某状态中既含有定位点在尾处某状态中既含有定位点在尾处的项目又含有定位点不在尾处的项目，则的项目又含有定位点不在尾处的项目，则一个正则式是另一个正则式的严格前缀。一个正则式是另一个正则式的严格前缀。 开始符产生式的右部是归约活前缀。开始符产生式的右部是归约活前缀。 如果如果 A A 是归约活前缀，且是归约活前缀，且AA 是产生式，是产生式， 则则也是归约

15、活前缀。也是归约活前缀。 任何归约活前缀，都可按上述方式被派生。任何归约活前缀，都可按上述方式被派生。l 设文法开始符的产生式是：设文法开始符的产生式是： S S 1 1| | 2 2| n n RPSRPSG G= 1 1, n n | | A ARPSRPSG G,A,AP P + 识别规约活前缀的识别规约活前缀的LRSMLRSM的构造的构造b 例有文法例有文法GS: S aAc1 A Abb2 A b3 可归前缀集：可归前缀集： aAcaAc aAbb aAbb ab ab Y LR(0) LR(0)项目：项目：若若AA是产生式，是产生式， 则称则称AA为为LR(0)LR(0)项目项目(

16、 (简称项目），也简称项目），也 写作写作 pp形式。形式。Y 项目集的投影：项目集的投影：假设假设ISIS是是LR(0)LR(0)项目集，则项目集，则 称下面称下面ISIS(X)(X) 为为ISIS关于关于X X的投影集：的投影集： ISIS(X)(X) = A = A X X |A |AX XIS,IS, X X (V(VT T V VN N).).Y 项目集的闭包：项目集的闭包：假设假设ISIS是是LR(0)LR(0)项目集，则项目集，则 称下面称下面CLOSURE(IS)CLOSURE(IS)为为ISIS的闭包集：的闭包集： CLOSURE(IS)= IS CLOSURE(IS)= I

17、S A A | Y | YA ACLOSURE(IS)CLOSURE(IS) A A 是产生式是产生式 Z 归约活前缀的性质：若归约活前缀的性质：若 A A 是归约活前是归约活前 缀，缀，AA 是产生式，则是产生式，则也是归约活也是归约活 前缀。前缀。 Z 活前缀状态机性质：若有活前缀状态机性质：若有 Prefix(ISPrefix(ISi i ) )，且且AAISISi i ，则则 是归约活前缀。是归约活前缀。 v 若有若有 Prefix(ISPrefix(ISi i ) )，YYA AISISi i ，则则 根据性质根据性质2(2(活前缀状态机的性质），活前缀状态机的性质）， A A 是归

18、约活前缀。再根据派生原理，若是归约活前缀。再根据派生原理，若 AA 是是A A的产生式，则的产生式，则也是归约活前缀。也是归约活前缀。v 构造构造LRSMLRSM的思想：的思想： 如果在状态项目集如果在状态项目集ISISi i 中有项目中有项目AAB B ， 且且BB 是是B B的产生式，则在的产生式，则在ISISi i 中增加项目中增加项目 B B；对于对于ISISi i 这个过程继续到不可再扩这个过程继续到不可再扩 充为止。充为止。 u构造初始状态构造初始状态ISIS0 0：ISIS0 0=CLOSURE(Z=CLOSURE(Z S)S)，并给并给ISIS0 0标标上上NONO。u从已构造

19、的从已构造的LRSMLRSM部分图选择被标为部分图选择被标为NONO的任一状态的任一状态ISIS，并做并做 1 1 对每个符号对每个符号X X V VT T V VN N，做下面动作：做下面动作： 1) 1) 令令ISISj j = CLOSURE( IS= CLOSURE( IS(X)(X) )，若非空。若非空。 2) 2) 若在若在LRSMLRSM部分图中已有部分图中已有ISISk k与与ISISj j有相同项目有相同项目 集，则令集，则令m=km=k；否则构造否则构造ISISj j的状态点的状态点ISISj j， 并给并给ISISj j标上标上NONO，同时令同时令m=jm=j。 3)

20、3) 在在ISIS和和ISISm m之间画有向之间画有向X X边：边：IS IS ISISm m 。 2 2 给给ISIS标上标上OKOK。u重复上一步骤，直至没有被标记为重复上一步骤，直至没有被标记为NONO的状态节点为止。的状态节点为止。xk 例：构造例：构造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

21、T(E) TT(idETid)E+id(G GE E的的LRSMLRSM+2 SE $ $Z LRSM LRSM给出了所有的可归活前缀给出了所有的可归活前缀Z LRSM LRSM中的每个状态将对应一个饱和项目集：中的每个状态将对应一个饱和项目集： （1 1）其中一部分是由先驱状态分出来）其中一部分是由先驱状态分出来 ( (称为基本项目称为基本项目) )； （2 2）一部分则是由基本项目扩展出来的）一部分则是由基本项目扩展出来的 ( (称为扩展项目或派生项目称为扩展项目或派生项目) )。派生部。派生部 分项目的特点是其中的分项目的特点是其中的“ ”出现在出现在产产 生式右部的最左侧。生式右部的最

22、左侧。Y 形如形如A A PP的项目称为的项目称为归约型项目归约型项目Y 形如形如AA PP的项目称为的项目称为移入型项目移入型项目Y 移入归约冲突移入归约冲突Y 归约归约冲突归约归约冲突Y LRSMLRSM不能直接用于不能直接用于LRLR分析分析Y LRSMLRSM提供的信息：提供的信息： （1 1）合法性检查信息）合法性检查信息 AAa a （2 2）移入）移入/ /归约信息归约信息 AAa a ； AA （3 3）移入）移入/ /归约后的转向状态信息归约后的转向状态信息#X1X2 Xk XtSi0Si1Si2 Sik Sit aiai+1an #移入动作：设移入动作：设Sit的的ai输入

23、边所指向的状态为输入边所指向的状态为S*#X1X2 Xk XtSi0Si1Si2 Sik SitaiS*归约动作：设按归约动作：设按AXAXk+1k+1X Xk+2k+2XXt t进行归约，则首先归约为进行归约，则首先归约为A AS Sikik的的A A输出边所指向的状态设为输出边所指向的状态设为S S* *，则格局变为：则格局变为：#X1X2XkSi0Si1Si2SikAS*设当前格局是：设当前格局是：#X1X2XkSi0Si1Si2SikAOutputOutputStackStack# #a an na ai ia a1 1LRLR分析驱动器分析驱动器gotoactionInputInpu

24、tS St tX Xt t 1 LR(0)分析分析lActionAction矩阵：行代表状态，列代表输入矩阵：行代表状态，列代表输入符，而矩阵元素则表示相应的分析动作：符，而矩阵元素则表示相应的分析动作：Shift / Reduce / Accept / ErrorShift / Reduce / Accept / Error 。lGoToGoTo矩阵：行代表状态，而列则代表语矩阵：行代表状态，而列则代表语法符号（非终极符，终极符），而矩阵法符号（非终极符，终极符），而矩阵元素则表示移入或归约后的转向状态。元素则表示移入或归约后的转向状态。l定义定义 若若ISIS是一个是一个LR(0)LR(0

25、)项目集，项目集，X X是一个是一个文法符号，函数文法符号，函数GOGO（IS, XIS, X）定义为）定义为GOGO（IS, XIS, X）=CLOSURE=CLOSURE（ISIS(X)(X)），其中），其中ISIS(X)(X)为为LR(0)LR(0)项目集项目集ISIS的投影。的投影。 假设假设ISISk k为为LR(0)LR(0)项目集，则项目集，则 l若若A Aa aISISk k，且，且GO(ISGO(ISk k, a)= IS, a)= ISi i，a a V VT T，则，则action(ISaction(ISk k, a)=S, a)=Si i，表示把状态，表示把状态ISIS

26、i i和展望符和展望符a a入栈。入栈。l若若A AISISk k，则对任意，则对任意a a V VT T #，令，令action(ISaction(ISk k, , a)=Ra)=Rj j，其中产生式，其中产生式A A 的编号为的编号为j j，表示用编号为，表示用编号为j j的产生式进行归约。的产生式进行归约。l若若Z ZISISk k，且，且Z Z为拓广产生式的左部非终极符，则为拓广产生式的左部非终极符，则action(ISaction(ISk k, #)=Accept, #)=Accept。l若若GO(ISGO(ISk k, A)=IS, A)=ISi i，A A V VN N，则，则g

27、oto(ISgoto(ISk k, A)=i, A)=i。l其它情形，则其它情形，则Error(n)Error(n)，表示出错标志，也可不填。，表示出错标志，也可不填。文法如下：文法如下：S E $E E+T | TT id | (E)$ $+ +idid( () )# #E ET TS S0 0S S5 5S S6 61 19 9S S1 1S S2 2S S3 3S S2 2AccAccS S3 3S S5 5S S6 64 4S S4 4R2 R2R2R2R2R2S S5 5R4R4R4R4R4R4S S6 6S S5 5S S6 67 79 9S S7 7S S3 3S S8 8S S

28、8 8R5R5R5R5R5R4S S9 9R3R3R3R3R3R3GoToGoTo表表ActionAction表表首先置状态栈、符号栈和输入流的开始格局为：首先置状态栈、符号栈和输入流的开始格局为：（#S1,#,a1a2an#），则：），则：z若当前格局为（若当前格局为（#S1S2Sn,#X1X2Xn, aiai+1an#），且），且action(Sn, ai)=Sj，ai VT，则，则ai入符号栈，第入符号栈，第j个状态个状态Sj入状入状态栈。即移入后的格局变为：态栈。即移入后的格局变为：（#S1S2Sn Sj,#X1X2Xnai,ai+1an#）z若当前格局为（若当前格局为（#S1S2Sn

29、,#X1X2Xn, aiai+1an#），且），且action(ISn, a)=Rj，a VT #，则按照第，则按照第j个产生式进行归约，个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号入栈。符号栈和状态栈相应元素退栈，归约后的文法符号入栈。假设第假设第j个产生式为个产生式为A ，k=| | ( =Xn-k+1Xn)，则归约后，则归约后的格局变为：的格局变为：（#S1S2Sn-kS,#X1X2Xn-kA,aiai+1an#）其中其中S=goto(Sn-k, A)。z若状态栈的栈顶状态为若状态栈的栈顶状态为Si，输入流当前值为，输入流当前值为#，且，且action(Si, #)=A

30、ccept，则分析成功。，则分析成功。z若状态栈的栈顶状态为若状态栈的栈顶状态为Si，输入流当前值为，输入流当前值为a，且，且action(Si, a)=Error或空，则转向出错处理程序。或空，则转向出错处理程序。 状态栈状态栈 符号栈符号栈 输入串输入串 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 $# shift 2012 E$

31、 # accept id+id$ id+id$z 文法文法G G： Z aAc1 Z aAc1 A bB 2 | ba3A bB 2 | ba3 B dB 4 | e 5 B dB 4 | e 5 构造文法的构造文法的LR(0)LR(0)状态机，状态机，ActionAction表和表和 goto goto表，并给出符号串表，并给出符号串abdecabdec的的LR(0)LR(0) 分析过程。分析过程。+ SLR(1)SLR(1)分析方法分析方法ZLR(0)方法对文法的要求严格。方法对文法的要求严格。ZLR(0)方法容易出现冲突状态。方法容易出现冲突状态。一个文法例一个文法例: : lG GE

32、E: SE $ : SE $ 1 1lEE + T 2EE + T 2lET ET 3 3lTT TT P 4 P 4 l TP TP 5 5lPid Pid 6 6l P( E ) 7P( E ) 7 图图4.5.5.3 G E 的的LRSM0 + +E EP Pidid$ $+ +P Pidid( (T TT Tidid( ( ididE E( (P P ) ) 4 4 E T E T T T T T P P 7 7 P id P id 5 5 E E + E E + T T T T T T P P T T P P P P id id P P (E) (E) 3 3 T P T P 4 4

33、 S E S E $ $ E E E E + T + T 1 1 S S E $ E $ 11 E E E+T E+T 2 2 E E T T 3 3 T T T T P P 4 4 T T P P 5 5 P P id id 6 6 P P (E) (E) 7 7 0 0 T T T T P P P P id id P P (E) (E) 8 8 T T T T * * P P 9 9 E E+T E E+T T T T T P P 11 11 P (E P (E ) ) E E E E +T +T 12 12 P(E) P(E) 10 10P P( (T T P ( P ( E ) E )

34、 E E E+T E+T E E T T T T T T P P T T P P P P id id P P (E) (E) 6 6 7 7 8 8 S E $ S E $ 2 2如果某个状态有如下项目集：如果某个状态有如下项目集： A , B , D d ，则存在则存在着归约着归约-归约，移入归约，移入-归约冲突归约冲突 l若用若用A 归约，则当前输入符应在归约，则当前输入符应在A的的Follow集中集中 l若用若用B 归约，则当前输入符应在归约，则当前输入符应在B 的的Follow集集 l若移入，则当前输入符应为若移入，则当前输入符应为d。lLRSM0中存在着状态中存在着状态 A1 1 ，

35、An n ， B1 1 a1r1，Bm m amrm则集合：则集合： Follow(A1)、Follow(An)、a1,am 两两相交为空两两相交为空假设假设ISk为为LR(0)项目集，则项目集，则l若若AaISk，且，且GO(ISk, a)= ISi，a VT，则，则action(ISk, a)=Si，表示把状态，表示把状态ISi和展望符和展望符a入栈。入栈。l若若AISk，则对任意，则对任意a VT，a Follow(A)，令令action(ISk, a)=Rj，其中产生式，其中产生式A 的编号为的编号为j，表示用编号为表示用编号为j的产生式进行归约。的产生式进行归约。l若若ZISk，且，

36、且Z为拓广产生式的左部非终极为拓广产生式的左部非终极符，则符，则action(ISk, #)=Accept。l若若GO(ISk, A)=ISi，A VN，则，则goto(ISk, A)=i。l其它情形，则其它情形，则Error(n)，表示出错标志，也可不，表示出错标志，也可不填。填。 l对于一个文法，若按照上述算法构造的分析表对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为中没有冲突动作，则称该文法为SLR(1)文法。文法。l从定义可以看出从定义可以看出SLR(1)分析方法是用分析方法是用LR(0)项项目构成的目构成的LRSM0来识别活前缀，因此它们的来识别活前缀，因此它们

37、的状态数相同，但是，由于状态数相同，但是，由于LR(0)方法只看状态方法只看状态栈的内容而栈的内容而SLR(1)方法还要向前看展望符，因方法还要向前看展望符，因此此SLR(1)文法要比文法要比LR（0）文法广。）文法广。 图图4.5.5.3 G E 的的LRSM0 + +E EP Pidid$ $+ +P Pidid( (T TT Tidid( ( ididE E( (P P ) ) 4 4 E T E T T T T T P P 7 7 P id P id 5 5 E E + E E + T T T T T T P P T T P P P P id id P P (E) (E) 3 3 T

38、P T P 4 4 S E S E $ $ E E E E + T + T 1 1 S S E $ E $ 11 E E E+T E+T 2 2 E E T T 3 3 T T T T P P 4 4 T T P P 5 5 P P id id 6 6 P P (E) (E) 7 7 0 0 T T T T P P P P id id P P (E) (E) 8 8 T T T T * * P P 9 9 E E+T E E+T T T T T P P 11 11 P (E P (E ) ) E E E E +T +T 12 12 P(E) P(E) 10 10P P( (T T P ( P

39、( E ) E ) E E E+T E+T E E T T T T T T P P T T P P P P id id P P (E) (E) 6 6 7 7 8 8 S E $ S E $ 2 2lFollow(S)=#lFollow(E)=$,+,)lFollow(T)=$,+,),*lFollow(P) =$,+,),*# id()$ ETP0S5S6 1741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S6 12747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10State Action Lookahe

40、ad GoTol初始格局初始格局(#S0,#,a1a2an#)l若当前格局为若当前格局为 (#S0S1Sn,#X1X2Xn, aiai+1an#)，则，则若若action(Sn, ai)=Sk，则当前格局变为：，则当前格局变为：(#S0S1Sn Sk,#X1X2Xnai, ai+1an#)若若action(Sn, ai)=Rp，则当前格局变为：，则当前格局变为：(#S0Sn-kS,#X1X2Xn-kA,aiai+1an#)其中其中goto(Sn-k, A)=S若若action(Sn, ai)=Accept，则成功，则成功l其它情形，出错其它情形，出错分析栈分析栈 符号栈符号栈 输入串输入串 分

41、析动作分析动作 转向状态转向状态 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 T id +id$# R6 90,7,8,9 T P +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 E+P $# R5 110,1,3,11 E+T $# R2 10,1 E $# S20,1,2 E$ # AcceptZSLR(1)和和LR(0)具有相同

42、的状态机具有相同的状态机ZLR(0)只看分析栈的内容，不考虑当前输入符只看分析栈的内容，不考虑当前输入符 SLR(1)考虑输入符，用考虑输入符，用follow集来解决冲突，集来解决冲突，因此因此SLR(1)要比要比LR(0)分析能力强分析能力强 z 括号文法定义如下：括号文法定义如下： Z S$ Z S$ S (S) S | S (S) S | 构造该文法的构造该文法的SLR(1)SLR(1)分析表，并给出输分析表，并给出输入流入流( )( )( )( )$ $的的SLR(1)SLR(1)分析过程。分析过程。主要内容：主要内容：+ LR(1)LR(1)分析方法分析方法 Z E E (L,E)

43、E S L L,E L E S id S (S)Z EE(L,E)ESSidS (S)0E( L,E)S( S)L L,EL EE (L,E)E SS idS (S)1ES S(S )2(S状态状态2存在移入存在移入-归约冲突归约冲突ZLR(0)LR(0)方法不依赖输入流，直接判定归约，方法不依赖输入流，直接判定归约，容易出现冲突。容易出现冲突。ZSLR(1)SLR(1)方法简单的把非终极符的方法简单的把非终极符的followfollow集做集做为可归约的依据，并不精确。为可归约的依据，并不精确。Z一个非终极符在不同的位置上出现，它所允一个非终极符在不同的位置上出现，它所允许的后继符是不同的。

44、许的后继符是不同的。LR(1)LR(1)针对不同产生针对不同产生式上的非终极符，分别定义其后继符集（展式上的非终极符，分别定义其后继符集（展望符集望符集ReducelookupReducelookup），），减少了移入减少了移入/ /归约归约冲突。冲突。lLR(1)LR(1)项目：项目： AA, a , a 。LR(0)LR(0)项目及一个项目及一个V VT T #的展望符集合的展望符集合lIS:IS:LR(1)LR(1)项目集项目集lISIS(X)(X): : IS IS(X)(X) = A = A X X,a |A,a |AX X ,a,a IS IS lCLOSURE ( IS )CLO

45、SURE ( IS ) = IS = IS B B,b |A,b |AB B ,a,a CLOSURE(IS), CLOSURE(IS), B B 是产生式是产生式 , , b b First(First( a)a) lGOGO: :若若ISIS是一个是一个LR(1)LR(1)项目集，项目集，X X是一个文法符号是一个文法符号, ,则则GOGO（IS, XIS, X）=CLOSURE=CLOSURE（ISIS(X)(X)），），其中其中ISIS(X)(X)为为LR(1)LR(1)项目集项目集ISIS的投影的投影 l初始项目集：初始项目集：l ISS=CLOSURE( Z ISS=CLOSURE

46、( Z S, # )S, # )l若所有状态都处理完，则结束若所有状态都处理完，则结束l选一未处理完状态选一未处理完状态ISIS，对所有语法符号对所有语法符号l X X （V VT T V VN N #),#),求求ISISX X, ,令令l IS IS = CLOSURE(IS= CLOSURE(ISX X) )，若若ISIS不为空：不为空：l 若若ISIS为新状态，则增加为新状态，则增加IS ISIS IS, ,把把ISIS加加l 入入LRSMLRSM1 1中；否则为图中某个状态中；否则为图中某个状态ISISj j，则则在在ISISl 和和ISISj j之间增加一条转换边：之间增加一条转换

47、边：IS ISIS ISj jl转到步骤转到步骤2 2XXl 非非SLR(1)SLR(1)文法：文法： Z SZ S S L= R S L= R S R S R L aR L aR L b L b R L R L 0ZSSL=RSRLaRLbRL#= #= #1ZS #2SL =RRL #6SL= RR LLaRLb#7SL=R #3SR #4Lb =#10LaR #=5La RR LLaRLb# =# =# =# =11RL # =8La RR LLaRLb#9RL #12Lb #13LaR #SLabRb=RLRLabaaLRb假设假设ISk为为LR(1)项目集则：项目集则：l若若Z, #

48、 ISk，且，且Z为拓广产生式的左部非终为拓广产生式的左部非终极符，则极符，则action(ISk, #)=Accept。l若若A, a ISk，且产生式，且产生式A 的编号为的编号为j，则，则action(ISk, a)=Rj，表示用编号为，表示用编号为j的产生式进行的产生式进行归约。归约。l若若Aa , b ISk，且，且GO(ISk, a)=ISi，a VT，则则action(ISk, a)=Si，表示把状态，表示把状态ISi和展望符和展望符a入入栈。栈。l若若GO(ISk, A)= ISi，A VN，则，则goto(ISk, A)=i。l其它情形，则其它情形，则Error(n)，表示出

49、错标志，也可不，表示出错标志，也可不填。填。 l对于一个文法，若按照上述算法构造的对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为分析表中没有冲突动作，则称该文法为LR(1)文法。文法。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=balLR(1)的驱动程序与的驱动程序与SLR(1)的驱动程序是的驱动程序是相同的，可共用一个。相同的，可共用一个。状态栈状态栈 符号栈符号栈 输入串输入串 Action GoToAction GoTo0 aab=b# S5 0,5

50、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 # Az设文法设文法GS为：为：SAS | A aA | b 证明证明GS是是LR(1)文法；构造它的文法；构造它的LR(1)分析表；给出符号串分析表；给出符号串

51、abab#的的分析过程分析过程它具有它具有SLR(1)SLR(1)的状态数少的优点和的状态数少的优点和LR(1)LR(1)的适用范围广的优点。的适用范围广的优点。 LALR(1)LALR(1)方法的功能介于方法的功能介于SLR(1)SLR(1)和和LR(1)LR(1)之间。之间。LALR(1)LALR(1)状态机的状态个数和状态机的状态个数和LR(0)LR(0)状态状态机的状态个数相同，而其展望符则即不机的状态个数相同，而其展望符则即不采用采用SLR(1)SLR(1)的的FollowFollow集方法，也不采用集方法，也不采用LR(1)LR(1)的完全精确法。的完全精确法。 LR(1)LR(1

52、)状态机和状态机和LR(0)LR(0)状态机从它们所表状态机从它们所表示的自动机角度来看是等价的示的自动机角度来看是等价的 ；自动机可通过合并等价状态来减少状态自动机可通过合并等价状态来减少状态个数。个数。 在在LR(1)LR(1)状态机出现很多同心状态，而状态机出现很多同心状态，而LALR(1)LALR(1)状态机则不产生同心的状态，状态机则不产生同心的状态， 从而大大减少状态数，这就是从而大大减少状态数，这就是LALR(1)LALR(1)和和LR(1)LR(1)的主要差别。的主要差别。 LALR(1)LALR(1)状态机的定义方式：状态机的定义方式：用用LR(1)LR(1)状态机来定义；状态机来定义；用用L