编译原理-第五章

1、编译原理编译原理第五章第五章 语法分析语法分析(自下而上分析自下而上分析)王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW22022-3-24第五章第五章 语法分析语法分析(自下而上分析自下而上分析)从输入符号串开始从输入符号串开始，逐步进行，逐步进行“归约归约”，直到归约到直到归约到文法的开始符号文法的开始符号。即从语法树的末端开始即从语法树的末端开始，逐步向逐步向上上“归约归约”，直到根节点，直到根节点。 1.算符优先分析法：按照算符的优先关系和结合性算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。质进行语法分析。适合分析表达式。 2.LR分析法

2、：规范归约分析法：规范归约TJNU-COCIE-WJW32022-3-24第五章第五章 语法分析语法分析(自下而上分析自下而上分析)n5.1 自下而上语法分析基本问题自下而上语法分析基本问题n5.2 算符优先分析法算符优先分析法n5.3 LR分析法分析法n5.4 LR(0)项目集族和项目集族和LR(0)分析表的构造分析表的构造n5.5 SLR分析表的构造分析表的构造n5.6 规范规范LR分析表的构造分析表的构造TJNU-COCIE-WJW42022-3-245.1 自下而上语法分析基本问题自下而上语法分析基本问题1.基本思想基本思想用一个寄存符号的先进后出栈，把输入符号一个用一个寄存符号的先进

3、后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成选式时，即把栈顶的这一部分替换成(归约归约为为)该该产生式的左部符号。产生式的左部符号。2.归约归约是指根据文法的产生式规则，把产生式的右部替是指根据文法的产生式规则，把产生式的右部替换成左部符号。换成左部符号。一、移进归约一、移进归约TJNU-COCIE-WJW52022-3-24：设文法：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d试对试对abbcde进行进行“移进归约移进归约”分析。分析。a bbcdeba

4、 bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa eTJNU-COCIE-WJW62022-3-24步步骤骤: :1 12 23 34 45 56 67 78 89 91 10 0动动作作: : 进进a a进进b b 归归( (2 2) ) 进进b b 归归( (3 3) ) 进进c c进进d d 归归( (4 4) ) 进进e e 归归( (1 1) )e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS S：设文法：设文法G

5、(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d试对试对abbcde进行进行“移进归约移进归约”分析。分析。：1.何时进行归约？何时进行归约？2.“可归约串可归约串”的定义方法？的定义方法？(5步，为什么用步，为什么用(3)不用不用(2)TJNU-COCIE-WJW72022-3-24bdbaceSABA自下而上分析过程：边输入单词符号，边归约。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串核心问题：识别可归约串步步骤骤: :1 12 23 34 45 56 67 78 89 91 10 0动动作作: : 进进a a进进b b 归归( (2

6、2) ) 进进b b 归归( (3 3) ) 进进c c进进d d 归归( (4 4) ) 进进e e 归归( (1 1) )e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa aa aa aa aa aa aa aa aa aS STJNU-COCIE-WJW82022-3-241.短语短语定义定义:令令G是一个文法，是一个文法，S是文法的开始符号，假定是文法的开始符号，假定是文法是文法G的一个句型的一个句型其中其中, (V VN NV VT T)*，AV VN N ，如果有，如果有则则 称是句型称是句型相对于非终结符相对于非终结符A的的

7、短语短语。：因为句型是由开始符号推出来的，而短语是由非终因为句型是由开始符号推出来的，而短语是由非终结符号推出来的。所以，短语是句型的一部份或全结符号推出来的。所以，短语是句型的一部份或全部符号串。部符号串。AS*A且且二、二、规范归约规范归约TJNU-COCIE-WJW92022-3-242.直接短语直接短语特别是，如果有特别是，如果有A,则称则称 是句型是句型相对于规则相对于规则A 的的直接短语直接短语。3.句柄句柄一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句柄句柄。TJNU-COCIE-WJW102022-3-24：考虑文法：考虑文法G ： E T | E+T

8、T F | T*F F (E) | i求证求证i1*i2+i3是是G的一个句型，并找出该句型的全的一个句型，并找出该句型的全部短语、直接短语和句柄部短语、直接短语和句柄解：证明解：证明i1*i2+i3是是G的一个句型的一个句型E E+T T+T T*F+T F*F+T i1*F+T i1*i2+T i1*i2+F i1*i2+i3TJNU-COCIE-WJW112022-3-24找找i1*i2+i3的所有短语的所有短语(1)假设假设i1*i2+i3是一个短语是一个短语因为因为E E 且且 E i1*i2+i3所以所以i1*i2+i3是句型是句型i1*i2+i3关于关于E的一个短语的一个短语(2

9、)假设假设i1*i2是一个短语是一个短语因为因为E T+i3 且且 T i1*i2所以所以i1*i2是句型是句型i1*i2+i3关于关于T的一个短语的一个短语(3)假设假设i1是一个短语是一个短语因为因为E F*i2+i3 且且 F i1所以所以i1是句型是句型i1*i2+i3关于关于F的一个短语的一个短语AS*A且且* E T | E+T T F | T*F F (E) | iTJNU-COCIE-WJW122022-3-24找找i1*i2+i3的所有短语的所有短语(4)假设假设i2是一个短语是一个短语因为因为E i1*F+i3 且且 F i2所以所以i2是句型是句型i1*i2+i3关于关于

10、F的一个短语的一个短语(5)假设假设i3是一个短语是一个短语因为因为E i1*i2+F且且 F i3所以所以i3是句型是句型i1*i2+i3关于关于F的一个短语的一个短语(6)假设假设i2+i3是一个短语是一个短语因为因为E i1*E不成立，不成立， 且且 E i2+i3成立成立所以所以i2+i3不是句型不是句型i1*i2+i3的一个短语的一个短语AS*A且且* E T | E+T T F | T*F F (E) | iTJNU-COCIE-WJW132022-3-24：缺一不可缺一不可所以短语有：所以短语有：i1*i2+i3， i1*i2， i1，i2，i3找直接短语：找直接短语：根据定义，

11、如果有根据定义，如果有A,则称则称 是句型是句型相对于规则相对于规则A 的的直接短语直接短语因为有：因为有：F i所以所以i1、i2、i3是直接短语是直接短语找句柄：找句柄：根据定义，一个句型的最左直接短语称为该句型的根据定义，一个句型的最左直接短语称为该句型的句柄句柄。 i1是句型是句型i1*i2+i3的句柄的句柄AS*A和和TJNU-COCIE-WJW142022-3-244.规范归约规范归约定义：假定定义：假定 是文法是文法G的一个句子，我们称序列的一个句子，我们称序列 n， n-1， ， 0 是是 的一个的一个规范归约规范归约，如果此序列满足：，如果此序列满足： (1) n= (2)

12、0为文法的开始符号，即为文法的开始符号，即 0=S (3) 对任何对任何i，0 .b 表示表示a的优先性大于的优先性大于ba . . 不同于数学上的不同于数学上的 = a =.b 不一定对应着不一定对应着 b =. aa .b 不一定对应着不一定对应着 b . aa . a TJNU-COCIE-WJW292022-3-241.算符优先文法算符优先文法(1)算符文法算符文法一个文法，如果它的任一产生式的右部都不含两个一个文法，如果它的任一产生式的右部都不含两个相继相继(并列并列)的非终结符，即不含如下形式的产生式的非终结符，即不含如下形式的产生式右部：右部：QR 则我们称该文法为则我们称该文法

13、为算符文法算符文法，也称，也称OG文法文法 (Operater Grammar) 。约定：约定：a、b代表任意终结符；代表任意终结符；P、Q、R代表任意非终结符；代表任意非终结符；代表由终结符和非终结符组成的任意序列，代表由终结符和非终结符组成的任意序列，包括空字包括空字二、二、算符优先文法及优先表构造算符优先文法及优先表构造TJNU-COCIE-WJW302022-3-241. a =. b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；2. a .b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，的产生式，而而 R a或或R aQ。(2)定义终

14、结符之间的优先关系定义终结符之间的优先关系假定假定G是一个不含是一个不含 产生式的算符文法。对于任何产生式的算符文法。对于任何一对终结符一对终结符a、b，我们说：，我们说：TJNU-COCIE-WJW312022-3-24(3)如果一个算符文法如果一个算符文法G中的任何终结符对中的任何终结符对(a，b)至多至多只满足下述三关系之一：只满足下述三关系之一：a=.ba.ba.b 则称则称G是一个是一个算符优先文法算符优先文法(OPG文法文法)。TJNU-COCIE-WJW322022-3-24:考虑下面的文法考虑下面的文法G： EE+T | T TT*F | F FP F | P P(E) | i

15、试问：文法试问：文法G是一个是一个OPG文法吗？文法吗？解解: (1)G中没有形如中没有形如P QR 的产生式的产生式所以所以G是一个是一个OG文法文法TJNU-COCIE-WJW332022-3-24(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i(2)找出找出G中任意两个非终结符号的优先关系中任意两个非终结符号的优先关系因为因为P(E) aQb由由(1)和和(2)EE + TTT * F a R Q b由由(2)和和(3)TT * F FP F a R Q b1.a =. b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；

16、的产生式；2. a .b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，的产生式，而而 R a或或R aQ。所以所以 ( =. ) 所以所以 + . * 所以所以 * . TJNU-COCIE-WJW342022-3-24(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i由由(1)和和(3)EE + TTFP F a R Q b所以所以 + . + 1.a =. b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；2. a .b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，的产生式，而而 R a或或R

17、aQ。TJNU-COCIE-WJW352022-3-24(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i由由(2)TT * FT T * FR b a Q所以所以 * . * 由由(3)FP FFP F a R Q b所以所以 . 1.a =. b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；2. a .b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，的产生式，而而 R a或或R aQ。TJNU-COCIE-WJW362022-3-24(1)EE+T | T(2)TT*F | F(3)FP F | P(4

18、)P(E) | i由由(4)P( E )a R且且EE+TT+TT*F+TF*F+TP F*F+T(E) F*F+T Qb Qb Qb b i F*F+T b所以所以( . + , * , , ( , i 1.a =. b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；2. a .b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，的产生式，而而 R a或或R aQ。TJNU-COCIE-WJW372022-3-24(1)EE+T | T(2)TT*F | F(3)FP F | P(4)P(E) | i由由(4)P( E ) Rb且且EE+TE+T*

19、FE+T*P F E+T*P P E+T*P (E) aQ aQ aQ a E+T*P i a所以所以 + , * , , ) , i . ) 以下略以下略在该文法中任意两个终结符号之间在在该文法中任意两个终结符号之间在.中只有一种关系成中只有一种关系成立，所以，立，所以，G是一个是一个OPG文法。文法。1.a =. b 当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；2. a .b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，的产生式，而而 R a或或R aQ。TJNU-COCIE-WJW382022-3-242.构造算符优先关系表构造算符优先关

20、系表(1)通过检查产生式的每一个候选式可以找出满足通过检查产生式的每一个候选式可以找出满足a=.b （即（即Pab或或PaQb的产生式）的产生式）(2)为了满足为了满足.，需对，需对G中每个非终结符中每个非终结符P构造两构造两个集合个集合FIRSTVT(P)和和LASTVT(P)：FIRSTVT Pa PaPQaaVQVTN( ) |,或而,|)(NTVQVaaQPaPaPLASTVT而或TJNU-COCIE-WJW392022-3-24(3)构造集合构造集合FIRSTVT(P)的算法的算法按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRSTVT(P)： 若有产生

21、式若有产生式Pa或或PQa，则则a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则则a FIRSTVT(P)。TJNU-COCIE-WJW402022-3-24(4)同理构造构造集合同理构造构造集合LASTVT(P)的算法的算法按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)： 若有产生式若有产生式P a或或P aQ ，则则a LASTVT(P)； 若若a LASTVT(Q)，且有产生式，且有产生式P Q ，则则a LASTVT(P)。TJNU-COCIE-WJW412022-3-24 (5)有了这两个集合之后，就

22、可以通过检查每个产生有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系式的候选式确定满足关系.的所有终结符对。的所有终结符对。(1)(1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为aPaP 那么，对任何那么，对任何b b FIRSTVT(P)FIRSTVT(P)，有，有a a . b b。FIRSTVT Pa PaPQaaVQVTN( ) |,或而,|)(NTVQVaaQPaPaPLASTVT而或TJNU-COCIE-WJW422022-3-24:考虑下面的文法考虑下面的文法G： EE+T | T TT*F | F FP F | P P(E) | i构造该文法构造该

23、文法G的每个非终结符的的每个非终结符的FIRSTVT和和LASTVT集合集合解解: (1)构造构造FIRSTVT集合集合FIRSTVT(P)= FIRSTVT(F)= FIRSTVT(T)= FIRSTVT(E)= 若有产生式若有产生式Pa或或PQa，则则a FIRSTVT(P)； 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则，则a FIRSTVT(P)。( , i ,( , i*, ,( , i+,*, ,( , iTJNU-COCIE-WJW432022-3-24:考虑下面的文法考虑下面的文法G： EE+T | T TT*F | F FP F | P P(E) | i构造该

24、文法构造该文法G的每个非终结符的的每个非终结符的FIRSTVT和和LASTVT集合集合解解: (1)构造构造LASTVT集合集合LASTVT(P)= LASTVT(F)= LASTVT(T)= LASTVT(E)= ), i ,) , i*, ,), i+,*, ,) , i 若有产生式若有产生式P a或或P aQ ，则则a LASTVT(P)； 若若a LASTVT(P)，且有产生式，且有产生式P Q ，则，则a LASTVT(P)。TJNU-COCIE-WJW442022-3-24:G:EE+T | TTT*F | FF(E) | i求出该文法每个终结符号的优先关系，并构造优先分析表求出该

25、文法每个终结符号的优先关系，并构造优先分析表(1)EE+T，且，且*, (, i FIRSTVT(T) aP所以所以+ . +FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i (1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-WJW452022-3-24:G:EE+T | TTT*F | FF(E) | I(3

26、)TT*F，且，且 (, i FIRSTVT(F) aP所以所以* . *FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i (1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-WJW462022-3-24:G:EE+T | TTT*F | FF(E) | i(5)F(E) ，且，且+,*, (, i FIRSTV

27、T(E) aP所以所以( . )(7)F(E) ，所以所以( =. )(0)通过检查产生式的每一个候选式可以找通过检查产生式的每一个候选式可以找出满足出满足a=.b （即（即Pab或或PaQb的产生式）的产生式）FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i (1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-

28、WJW472022-3-24+* i()#+.*. .i.EE.(.EE.#.E=.构造分析表如下：构造分析表如下：其中，其中，E=ERRORTJNU-COCIE-WJW482022-3-24：对于对于#号，相当于在文法开始符号号，相当于在文法开始符号S前加一个前加一个额外的开始符号，比如为额外的开始符号，比如为Z然后，把然后，把Z #S#添加到原文法中，再进行分析。添加到原文法中，再进行分析。TJNU-COCIE-WJW492022-3-24:G:EE+T | TTT*F | FF(E) | I(1)因为因为Z#E#所以所以# =. #(2)因为因为FIRSTVT(E)=+, *, , (,

29、 i Z #E# aP所以所以# . #Z #E#EE+T | TTT*F | FF(E) | i(1)假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有a . b。TJNU-COCIE-WJW502022-3-24# . #+* i()#+.*. .i.EE.(.EE.#.E=.TJNU-COCIE-WJW512022-3-241.问题的提出问题的提出自下而上分析自下而上分析移进移进-归约法：句柄为可归纳串归约法：句柄为可归纳串算符优先分析法：最左素短语为可归纳串算符优先分析法：最左素短语为可归纳串2.素短语素短语指一个句型

30、的短语，它至少包括有一个终结符指一个句型的短语，它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语号且除去它本身之外不再含任何更小的素短语3.最左素短语最左素短语处在句型最左端那个素短语成为最左素短语处在句型最左端那个素短语成为最左素短语三、算符优先分析算法的设计三、算符优先分析算法的设计TJNU-COCIE-WJW522022-3-24:考虑下面的文法考虑下面的文法G： EE+T | T TT*F | F F(E) | i求句型求句型E+T*F+i的素短语和最左素短语的素短语和最左素短语解解: 构造一个推导构造一个推导EE+TE+T+TE+T+TE+T*F+FE+T*F+i素短语

31、：素短语：T*F，i最左素短语：最左素短语：T*F短语：短语：E+T*F+iE+T*FT*FiTJNU-COCIE-WJW532022-3-244.算符优先分析算法和设计算符优先分析算法和设计(1)句型的一般表示形式：句型的一般表示形式： #N1a1N2a2NnanNn+1#其中，每个其中，每个ai都是终结符，都是终结符，Ni是可有可无的非终结符是可有可无的非终结符(2)定理：定理：一个算符优先文法一个算符优先文法G的任何句型的最左素短语是满足的任何句型的最左素短语是满足如下条件的最左子串如下条件的最左子串 NjajNiaiNi+1， aj-1 . ai+1：出现在左端或右端的非终结符一定属于

32、这个素短语出现在左端或右端的非终结符一定属于这个素短语TJNU-COCIE-WJW542022-3-24:EE+T | TTT*F | FF(E) | i句型句型关系关系 最左素短语最左素短语归约符号归约符号#i#.i#i+#.+i F#F+#F+i#. + . i #F+i*#. + . *i F#F+F*#F+F*i#. + . * . i #F+F*i#. + . * . #i F#F+F*F#. + . #F*F T#F+T# #.# F+T E#E#对句子对句子 i + i * i 进行分析进行分析TJNU-COCIE-WJW552022-3-24算符优先分析一般不等于规范归约算符优

33、先分析一般不等于规范归约:文法文法G：EE+T | T TT*F | F FP F | P P(E) | i解解:#.+.#P+i#.+.#P+P#.#E#右边是规范归约右边是规范归约对句型对句型 “#i+i#” 进行分析进行分析TJNU-COCIE-WJW562022-3-241.优先函数的定义优先函数的定义把每个终结符把每个终结符 与两个自然数与两个自然数f( )与与g( )相对应，使得相对应，使得若若 1 . 2，则，则f( 1) . 2，则，则f( 1) g( 2)f称为入栈优先函数，称为入栈优先函数，g称为比较优先函数。称为比较优先函数。(1)优点优点:便于比较，节省空间；便于比较，

34、节省空间；(2)缺点缺点:原来不存在优先关系的两个终结符，由于自原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的然数相对应，变成可以比较的。要进行一些特殊的判断。判断。四、优先函数四、优先函数TJNU-COCIE-WJW572022-3-24：文法：文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的优先函数如下表的优先函数如下表：(1)对应一个优先关系表的优先函数对应一个优先关系表的优先函数f和和g并不唯并不唯一，只要存在一对，就存在无穷多对一，只要存在一对，就存在无穷多对+* ()i#F24

35、40660G 1355050TJNU-COCIE-WJW582022-3-24注意注意：(2) 许多优先关系表不存在优先函数许多优先关系表不存在优先函数：不存在对应的优先函数不存在对应的优先函数f f和和g g假定存在假定存在f f和和g g，则有，则有 f(a)=g(a)f(a)=g(a)，f(a)g(b)f(a)g(b)， f(b)=g(a)f(b)=g(a)，f(b)=g(b)f(b)=g(b)导致如下矛盾导致如下矛盾: : f(a) g(b) = f(b) = g(a) = f(a) f(a) g(b) = f(b) = g(a) = f(a)aba=.b=.=.TJNU-COCIE-

36、WJW592022-3-242.优先函数的构造方法优先函数的构造方法如果优先函数存在，则可以通过以下三个步骤从优如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数先表构造优先函数:(1)对于每个终结符对于每个终结符a，令其对应两个符号，令其对应两个符号fa和和ga，画一张以所有符号画一张以所有符号fa和和ga为结点的方向图。为结点的方向图。如果如果a.=.b，则从，则从fa画一条弧至画一条弧至gb如果如果a.=.b，则从，则从gb画一条弧至画一条弧至fa 。(2)对每个结点都赋予一个数，此数等于从该结点对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点出发所能到达的结点(包括

37、出发点自身包括出发点自身)。赋给赋给fa的数作为的数作为f(a)赋给赋给ga的数作为的数作为g(a)。(3)检查所构造出来的函数检查所构造出来的函数f和和g是否与原来的关系是否与原来的关系矛盾。若没有矛盾，则矛盾。若没有矛盾，则f和和g就是要求的优先函数，就是要求的优先函数，若有矛盾，则不存在优先函数。若有矛盾，则不存在优先函数。TJNU-COCIE-WJW602022-3-24gifif*g*g+f+f#g#:取前面文法取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) F (E) | i的终结符的终结符+，*，i，#i+*#fg74662151TJNU-COCI

38、E-WJW612022-3-243.构造方法证明构造方法证明现在必须证明：现在必须证明：若若a=.b，则，则f(a)g(b)；若若a.b，则，则f(a).b，则，则f(a) g(b)。第一个关系可从函数的构造直接获得。因为，若第一个关系可从函数的构造直接获得。因为，若a=.b，则既有从，则既有从fa到到gb的弧，又有从的弧，又有从gb到到fa的弧。的弧。所以，所以，fa和和gb所能到达的结是全同的。所能到达的结是全同的。至于至于a.b的情形，只须证明其一。的情形，只须证明其一。如果如果a.b，则有从，则有从fa到到gb的弧。也就是的弧。也就是gb能到达能到达的任何结的任何结fa也能到达。因此，

39、也能到达。因此，f(a) g(b)。所需。所需证明的是，在这种情况下，证明的是，在这种情况下，f(a)=g(b)不应成立。不应成立。TJNU-COCIE-WJW622022-3-24我们将指出，如果我们将指出，如果f(a)=g(b)，则根本不存在优先函，则根本不存在优先函数。假若数。假若f(a)=g(b)，那么必有如下的回路：，那么必有如下的回路：fa1fafamgb1gbgbm因此有因此有a.b, aa.b, a1 1.=.b, a.=.b.=.b1 1, , , a, am m.=.b.=.bm m, a.=.b, a g(b) f(a1) g(b1) f(am) g(bm) f(a)从而

40、导致从而导致f(a) f(a)，产生矛盾。因此，不存在优先函，产生矛盾。因此，不存在优先函数数f和和g。TJNU-COCIE-WJW632022-3-245.3 LR分析法分析法L指从左到右扫描输入指从左到右扫描输入R指构造最右推导的逆指构造最右推导的逆k指的是在决定分析动作时向前看的符号个数指的是在决定分析动作时向前看的符号个数一、一、LR(k)分析法分析法TJNU-COCIE-WJW642022-3-241.分析能力强大分析能力强大nLR分析器能够构造识别所有上下文无关文法写分析器能够构造识别所有上下文无关文法写的程序设计语言的结构的程序设计语言的结构nLR分析方法是已知的最一般的无回溯移

41、进分析方法是已知的最一般的无回溯移进-归约归约方法，它能够和其他移进方法，它能够和其他移进-归约方法一样有效地归约方法一样有效地实现实现nLR方法能分析的文法类是预测分析法能分析的方法能分析的文法类是预测分析法能分析的文法类的真超集文法类的真超集nLR分析器能及时察觉语法错误分析器能及时察觉语法错误TJNU-COCIE-WJW652022-3-242.LR分析器的组成分析器的组成总控程序总控程序一张分析表一张分析表LRLR分析分析总控程序总控程序分析表分析表输入输入输出输出TJNU-COCIE-WJW662022-3-243. LR分析表的种类分析表的种类LR(0)分析表分析表功能较弱，但是它

42、是建立功能较弱，但是它是建立LR分析的基础分析的基础SLR(简单简单LR)分析表分析表功能一般，但容易实现，使用价值比较高功能一般，但容易实现，使用价值比较高规范规范LR分析表分析表功能强，应用范围比较广，但实现代价高功能强，应用范围比较广，但实现代价高LALR(向前向前LR)分析表分析表功能介于功能介于SLR与规范与规范LR之间。之间。TJNU-COCIE-WJW672022-3-244.LR分析法的基本思想分析法的基本思想使用的最右推导的逆过程，就是使用的最右推导的逆过程，就是规范归约规范归约在规范归约中，记住已移进和归约出的整个符号串在规范归约中，记住已移进和归约出的整个符号串(记住历史

43、记住历史)根据产生式，推测未来可能碰到的输入符号根据产生式，推测未来可能碰到的输入符号(展望未来展望未来)根据当前正在要进栈的输入符号根据当前正在要进栈的输入符号(面对现实面对现实)最终是为了寻找最终是为了寻找句柄句柄(可归约串可归约串)TJNU-COCIE-WJW682022-3-24LRLR分析分析程程 序序状态状态符号符号分析栈分析栈action gotoaction goto LR LR分析表分析表a a1 1a a2 2a ai ia an n# #输入串输入串 输出输出二、二、 LR分析器的结构分析器的结构TJNU-COCIE-WJW692022-3-241.LR分析器栈的结构分析

44、器栈的结构(1)把历史和展望材料抽象成某些状态。分析栈用把历史和展望材料抽象成某些状态。分析栈用来存放这些状态。栈顶的状态都代表了整个历史来存放这些状态。栈顶的状态都代表了整个历史和已经推测出的展望。和已经推测出的展望。(2)为了有助于明确规约手续，将已规约出的文法为了有助于明确规约手续，将已规约出的文法符号串也同时放到栈里。符号串也同时放到栈里。状态状态符号符号分析栈分析栈TJNU-COCIE-WJW702022-3-242.LR分析表的结构分析表的结构动作表：动作表：ACTIONs，a：当状态当状态s面临输入符号面临输入符号a时，应采取什么动作时，应采取什么动作状态转换表：状态转换表：GO

45、TOs，X：状态状态s面对文法符号面对文法符号X时，下一状态是什么时，下一状态是什么TJNU-COCIE-WJW712022-3-24(1)动作表动作表ACTIONs，a：当状态：当状态s面临输入符号面临输入符号a时，应采时，应采取什么动作取什么动作每一项每一项ACTIONs，a所规定的四种动作所规定的四种动作:. 移进移进. 归约归约. 接受接受. 报错报错TJNU-COCIE-WJW722022-3-24. 移进移进 把把(s，a)的下一状态的下一状态s=GOTOs,a 和输入符号和输入符号a推进栈，下一输入符号变推进栈，下一输入符号变成现行输入符号成现行输入符号.状态状态符号符号分析栈分

46、析栈asTJNU-COCIE-WJW732022-3-24. 归约归约 指用某产生式指用某产生式A进行归约进行归约. 假若假若 的长度为的长度为r， 归约动作归约动作是是A， 去除栈顶去除栈顶r个项，使状个项，使状态态sm-r变成栈顶状态，然后把变成栈顶状态，然后把(sm-r, A)的下一状态的下一状态s=GOTOsm-r, A和文法符和文法符号号A推进栈推进栈.状态状态符号符号分析栈分析栈 r个个AsTJNU-COCIE-WJW742022-3-24. 接受接受 宣布分析成功，停止分析器工作。宣布分析成功，停止分析器工作。. 报错报错 发现源程序含有错误，调用出错处理程序发现源程序含有错误，

47、调用出错处理程序TJNU-COCIE-WJW752022-3-24可以看成是一个三元式的变化过程可以看成是一个三元式的变化过程(状态序列，已规约串，输入串状态序列，已规约串，输入串)n分析开始时分析开始时:状态序列状态序列 已归约串已归约串 输入串输入串 (s0， #， a1a2 an #)n以后每步的结果可以表示为以后每步的结果可以表示为: (s0 s1 sm ，# X1 Xm ，aiai+1 an #)分析器下一步的动作由分析器下一步的动作由ACTIONsm ，ai所规定的。所规定的。三、三、 LR分析器的工作过程分析器的工作过程TJNU-COCIE-WJW762022-3-24 (s0

48、s1 sm ，# X1 Xm ，aiai+1 an #).若若ACTION(sm , ai)为移进，且为移进，且s=GOTOsm , ai ，则三元式格局变为则三元式格局变为: (s0 s1 sms ，# X1 Xm ai ， ai+1 an #).若若ACTION(sm , ai)为按为按A归约，三元式变为归约，三元式变为: (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #)此处此处, s=GOTO(sm-r, A), r为为 的长度的长度, = Xm-r+1 Xm.若若ACTION(sm , ai)为为接受接受，则三元式不再变，则三元式不再变化，变化过程终止，宣布

49、分析成功化，变化过程终止，宣布分析成功.若若ACTION(sm , ai)为为报错报错，则三元式变化过，则三元式变化过程终止，报告错误程终止，报告错误.TJNU-COCIE-WJW772022-3-24文法文法G(E)： (1) EET(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi分析分析i*i+i四、四、LR分析器示例分析器示例TJNU-COCIE-WJW782022-3-24ACTIONGOTO状态状态i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r

50、1r110r3r3r3r311r5r5r5r5其其LRLR分析表为（书分析表为（书P101P101）: :TJNU-COCIE-WJW792022-3-24假定输入串为假定输入串为i*i+i， LR分析器的工作过程分析器的工作过程:步骤步骤状态状态符号符号输入串输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#TJNU-COCIE-WJW802022-3-24步骤步骤状态状态符号符号输入串输入串(9)01#E+i#(10)016#E+i#(1

51、1)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15) 接受接受TJNU-COCIE-WJW812022-3-24(1)定义：对于一个文法，如果能够构造一张分析表，定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就使得它的每个入口均是唯一确定的，则这个文法就称为称为LR文法文法：不是所有上下文无关文法都是：不是所有上下文无关文法都是LR文法，但多文法，但多数程序设计语言都可用数程序设计语言都可用LR文法描述文法描述(2)定义：一个文法，如果能用一个每步顶多向前检定义：一个文法，如果能用一个每步顶多向前检查查k个

52、输入符号的个输入符号的LR分析器进行分析，则这个文法分析器进行分析，则这个文法就称为就称为LR(k)文法文法：对于多数程序设计语言，：对于多数程序设计语言，k=0或或1，足够了。，足够了。五、五、LR文法文法TJNU-COCIE-WJW822022-3-24(3)非非LR结构结构LR文法不是二义的，二义文法肯定不会是文法不是二义的，二义文法肯定不会是LR的。的。 S iCtS | iCtSeS 栈栈 输入输入 iCtS e#iCtS是否为句柄？是规约还是继续移进？是否为句柄？是规约还是继续移进？TJNU-COCIE-WJW832022-3-245.4 LR(0)项目集族和项目集族和LR(0)分

53、析表的构造分析表的构造1.字的前缀字的前缀是指字的任意首部是指字的任意首部.如如:字字abc的前缀有的前缀有 ，a，ab，abc2.活前缀活前缀是指规范句型的一个前缀，这种前缀不含句柄之是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型后的任何符号。即，对于规范句型， 为句柄，为句柄，如果如果=u1u2ur，则符号串，则符号串u1u2ui(1 i r)是是的的活前缀活前缀。( 必为终结符串必为终结符串)一、规范句型活前缀的概念一、规范句型活前缀的概念TJNU-COCIE-WJW842022-3-24：1.在在LR分析工作过程中的任何时候，栈里的文法分析工作过程中的任何时候

54、，栈里的文法符号符号X1 X2 Xm应该构成活前缀，把输入串的剩应该构成活前缀，把输入串的剩余部分配上之后，即应成为规范句型余部分配上之后，即应成为规范句型(如果整个如果整个输入串确实是一个句子输入串确实是一个句子)。因此，只要输入串的。因此，只要输入串的已扫描部分保持可归约为一个活前缀，则意味着已扫描部分保持可归约为一个活前缀，则意味着扫描过的部分没有错。扫描过的部分没有错。2.LR分析器的工作实质上就是一个逐步产生或识分析器的工作实质上就是一个逐步产生或识别所给文法规范句型活前缀的过程。别所给文法规范句型活前缀的过程。3.对于一个文法对于一个文法G, 可以构造一个可以构造一个DFA,它能识

55、别它能识别G的所有活前缀的所有活前缀.然后我们可以将该然后我们可以将该DFA转变成转变成LR分析表分析表TJNU-COCIE-WJW852022-3-241.LR(0)项目的提出项目的提出(1)活前缀与句柄的关系活前缀与句柄的关系A.活前缀中已含有句柄的全部活前缀中已含有句柄的全部(句柄在最右边句柄在最右边)B.活前缀中只含句柄的一部分符号活前缀中只含句柄的一部分符号C.活前缀中全然不含句柄的任何符号活前缀中全然不含句柄的任何符号分析一下：分析一下：从从A看出看出A的右部的右部 已出现在栈顶，用产生式已出现在栈顶，用产生式A进进行归约行归约.从从B看出看出A1 2，已经看到，已经看到 1，期待

56、看到，期待看到 2从从C看出看出A，产生式的右部，产生式的右部一点都没看到一点都没看到二、构造识别文法二、构造识别文法G的所有活前缀的的所有活前缀的NFATJNU-COCIE-WJW862022-3-24(2)LR(0)项目概念项目概念文法文法G的每个产生式的右部添加一个圆点称为的每个产生式的右部添加一个圆点称为G的的LR(0)项目项目:AXYZ有四个项目：有四个项目：A.XYZ AX.YZ AXY.Z AXYZ. TJNU-COCIE-WJW872022-3-242.构造识别文法所有活前缀的构造识别文法所有活前缀的NFA方法方法文法文法G(SG(S ) ) S S EE EaA|bB EaA

57、|bB AcA|d AcA|d BcB|d BcB|d 构造识别该文法所有活前缀的构造识别该文法所有活前缀的NFATJNU-COCIE-WJW882022-3-24(1)求出该文法的求出该文法的LR(0)LR(0)项目项目S S EEEaA|bBEaA|bBAcA|dAcA|dBcB|dBcB|d1.S1.S E E2.S2.S EE3.E3.EaA aA 4.Ea4.EaA A5.EaA5.EaA6.A6.AcAcA7.Ac7.AcA A8.AcA8.AcA9.A9.Ad 10.Add 10.Ad11.E11.EbBbB 12.Eb12.EbB B 13.EbB13.EbB14.B14.Bc

58、BcB 15.Bc15.BcB B 16.BcB16.BcB17.B17.Bd d18.Bd18.BdTJNU-COCIE-WJW892022-3-24(2)构造识别文法的构造识别文法的NFA为为M = (S, , f, S0, Z)其中其中S=s|s是文法是文法G的的18个个LR(0)项目项目=S,E, A, B, a, b, c, dS0= S S E EZ:规定每个状态都是识别活前缀的终态规定每个状态都是识别活前缀的终态(18个个)TJNU-COCIE-WJW902022-3-24f: 若状态若状态i为为XX1 Xi-1Xi Xn ， 状态状态j为为XX1 Xi-1Xi Xi+1 Xn

59、，则从状态则从状态i画一条标志为画一条标志为Xi的有向边到状态的有向边到状态j； 若状态若状态i为为X .A ，A为非终结符，为非终结符， 则从状态则从状态i画一条画一条 边到所有状态边到所有状态j：A. 。 ： 状态状态i：S S E E 状态状态j j：EEaAaAijXiijTJNU-COCIE-WJW912022-3-24678910453121112131415161817 a AEbBBcAcd识别活前缀的识别活前缀的NFANFA15. S E2. S E16. EaA 17. EaA5. EaA18. AcA19. AcA8. AcA20. Ad 10. Ad21. EbB22.

60、 EbB13. EbB23. BcB24. BcB 16. BcB25. Bd18. BddTJNU-COCIE-WJW922022-3-24用子集法，把项目集变为状态用子集法，把项目集变为状态IIaIbIcISIAIB1,3,114,6,9三、三、把识别文法所有活前缀的把识别文法所有活前缀的NFA确定化确定化TJNU-COCIE-WJW932022-3-24识别活前缀的识别活前缀的DFADFA0: S E EaA EbB 4: AcA AcA Ad 2: EaA AcA Ad1: S E3: EbB BcB Bd5: BcB BcB Bd 11: Bd9: BcB7: EbB10: Ad6: