编译5语法—自下而上_zss_

1、编译原理编译原理(第三版第三版) 陈火旺等编著22022-6-10第五章第五章 语法分析语法分析自下而上分析自下而上分析n自上而下分析法自上而下分析法(Top-down)(Top-down)n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)32022-6-10n语法分析的方法：语法分析的方法：自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它基本思想：它从文法的开始符号出发从文法的开始符号出发，反复，反复使用各种产生式，寻找使用各种产生式，寻找 匹配匹配 的的推导推导。n递归下降分析法：对每一语法变量递归下降分析法：对每一语法变量( (非

2、终结非终结符符) )构造一个相应的子程序，每个子程序识构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。馈和联合作用实现对输入串的识别。n预测分析程序预测分析程序F优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。42022-6-10n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造直到文法的开始符号。即从树末端开始

3、，构造语法树。所谓语法树。所谓归约归约，是指根据文法的产生式规，是指根据文法的产生式规则，把产生式的右部替换成左部符号。则，把产生式的右部替换成左部符号。n算符优先分析法：按照算符的优先关系和结合算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。性质进行语法分析。适合分析表达式。nLRLR分析法：规范归约分析法：规范归约52022-6-1062022-6-10例：例： G(E)： E i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E Ei+ +* *EiiEEEE72022-6-105.1.1 5.1.1

4、归约归约n采用采用“移进归约移进归约”思想进行自下而上分析。思想进行自下而上分析。n基本思想：用一个寄存符号的后进先出栈，基本思想：用一个寄存符号的后进先出栈，把输入符号一个一个地移进到栈里，当栈顶把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这形成某个产生式的候选式时，即把栈顶的这一部分替换成一部分替换成( (归约归约为为) )该产生式的左部符该产生式的左部符号。号。82022-6-10n例：例：设文法设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d试对试对abbcdeabbcde进行进行“移进归约移进归约”分析。分析。a

5、 bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e92022-6-10步骤步骤: :1 12 23 34 45 56 67 78 89 91010动作动作: : 进进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 S102022-6-10bdbaceSABA 最终的最终的语

6、法分析树语法分析树自下而上分析过程：自下而上分析过程：边输入单词符号，边边输入单词符号，边归约。归约。 核心问题核心问题：如何如何识别可归约串识别可归约串112022-6-105.1.2 5.1.2 规范归约规范归约n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符号，假定号，假定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。 特别是，如果有特别是，如果有A A, ,则称则称 是句型是句型相对于规则相对于规则A A 的的直接短语直接短语。一个句型的。一个句型的最左直接短

7、语称为该句型的最左直接短语称为该句型的句柄句柄。三个重要三个重要概念概念122022-6-10考虑文法考虑文法G(E)： E T | E+T T F | T*F F (E) | i 以及句型以及句型 i1*i2+i3 ：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3n短语：短语： i1，i2，i3， i1*i2， i1*i2+i3n直接短语：直接短语： i1，i2，i3n句柄：句柄： i1132022-6-10n在一个句型对应的在一个句型对应的语法树中，以语法树中，以某非某非终结符终结符为根的两代为根的两代以上的子树的以上的子树的所有所有

8、末端结点从左到右末端结点从左到右排列就是相对于排列就是相对于该该非终结符非终结符的一个的一个短短语语，如果子树只有如果子树只有两代，则该短语就两代，则该短语就是是直接短语直接短语。EFFTTTi1+*EFi3i2142022-6-10n可用可用句柄句柄来对句子进行归约来对句子进行归约句型句型 归约规则归约规则abbcde (2) A baAbcde (3) A AbaAcde (4) B daAcBe (1) S aAcBe SbdbaceSABA152022-6-10bdbaceSABAdbaceSABAdaceSABaceSABS162022-6-10n定义定义：假定：假定 是文法是文法G

9、的一个句子，我们的一个句子，我们称序列称序列 n， n-1， ， 0 是是 的一个的一个规范归约规范归约，如果此序列满足：，如果此序列满足： 1 n= ； 2 0为文法的开始符号，即为文法的开始符号，即 0=S； 3 对任何对任何i，0 i n， i-1是从是从 i经把经把句句柄柄替换成为相应产生式左部符号而得到替换成为相应产生式左部符号而得到的。的。172022-6-10把上例倒过来写，则得到：把上例倒过来写，则得到：S S aAcBeaAcBe aAcde aAcde aAbcde aAbcde abbcde abbcde 显然这是一个最右推导。显然这是一个最右推导。规范归约规范归约是关于

10、是关于 的的一个一个最右推导最右推导的逆过程的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为由规范推导推出的句型称为规范句型规范句型。182022-6-105.1.3 符号栈的使用和分析树的表示符号栈的使用和分析树的表示n栈是语法分析的一种基本数据结构。栈是语法分析的一种基本数据结构。 首先将首先将 # # 作为栈底符号作为栈底符号n考虑文法考虑文法G(E)： E T | E+T T F | T*F F (E) | i输入串为输入串为i1*i2+i3 ，分析步骤为：，分析步骤为：192022-6-10步骤步骤 符号栈符号栈输入串输入串动作动作0 #i1*i2+i3#预备预备1

11、 #i1*i2+i3#进进2 #F*i2+i3#归，用归，用Fi3 #T*i2+i3#归，用归，用TF4 #T*i2+i3#进进nG(E)： E T | E+T T F | T*F F (E) | i202022-6-10步骤步骤 符号栈符号栈输入串输入串动作动作4 #T*i2+i3#进进5 #T*i2+i3#进进6 #T*F+i3#归，用归，用Fi7 #T+i3#归，用归，用TT*F8 #E+i3# 归，用归，用ET9 #E+i3# 进进nG(E)： E T | E+T T F | T*F F (E) | i212022-6-10步骤步骤 符号栈符号栈输入串输入串动作动作9 #E+ i3#进

12、进10#E+i3#进进11#E+F#归，用归，用Fi12#E+T#归，用归，用TF13#E#归，用归，用EE+T14#E#接受接受nG(E)： E T | E+T T F | T*F F (E) | i222022-6-105.2 5.2 算符优先分析算符优先分析n四则运算的优先规则：四则运算的优先规则： 先乘除后加减，同级从左到右先乘除后加减，同级从左到右n考虑二义文法考虑二义文法G(E)：G(E)： E i| E+E|E-E|E*E|E/E|(E)n它的句子有几种它的句子有几种不同的规范规约不同的规范规约。n归约即计算表达式的值。归约顺序不同，归约即计算表达式的值。归约顺序不同，则计算的顺

13、序也不同，结果也不一样。则计算的顺序也不同，结果也不一样。n如果规定算符的优先次序，并按这种规定如果规定算符的优先次序，并按这种规定进行归约，则归约过程是进行归约，则归约过程是唯一唯一的。的。232022-6-10例如：句子例如：句子i+i-ii+i-i* *(i+i)(i+i)Ei( () )i* *EiEE+ +EEE-ii+ +EEE242022-6-10Ei( () )i* *EiEE+ +EEE-ii+ +EEE返回例如：句子例如：句子i+i-ii+i-i* *(i+i)(i+i)252022-6-10句子句子i+i-i*(i+i)的归约过程是：的归约过程是：(1) i+i-i*(i

14、+i)(2) E+i-i*(i+i)(3) E+E-i*(i+i)(4) E-i*(i+i)(5) E-E*(i+i)(6) E-E*(E+i)(7) E-E*(E+E)(8) E-E*(E)(9) E-E*E(10) E-E(11) E262022-6-10n起决定作用的是相邻的两个起决定作用的是相邻的两个算符算符之间的之间的优优先关系先关系。n所谓所谓算符优先分析法算符优先分析法就是定义算符之间的就是定义算符之间的某种优先关系，借助于这种关系寻找某种优先关系，借助于这种关系寻找“可归可归约串约串”和进行归约和进行归约。272022-6-10n首先必须定义任何两个可能相继出现的终结首先必须定

15、义任何两个可能相继出现的终结符符a a与与b b的优先关系的优先关系 三种关系三种关系a a b a b a的优先级高于的优先级高于b bn注意：与数学上的注意：与数学上的 “ ”、“= =” 不同不同a a a aa a b b 并不意味着并不意味着 b b a a282022-6-105.2.1 算符优先文法及优先表构造算符优先文法及优先表构造n一个文法，如果它的任一产生式的右部都一个文法，如果它的任一产生式的右部都不含两个相继不含两个相继(并列并列)的非终结符，即不含的非终结符，即不含如下形式的产生式右部：如下形式的产生式右部：QR 则我们称该文法为则我们称该文法为算符文法算符文法。n约

16、定：约定：a、b代表任意终结符；代表任意终结符；P、Q、R代表任意非终结符；代表任意非终结符；代表由终结符和非终结符组成的任意序代表由终结符和非终结符组成的任意序列，包括空字。列，包括空字。292022-6-10n假定假定G是一个不含是一个不含 -产生式的算符文法。产生式的算符文法。对于任何一对终结符对于任何一对终结符a、b，我们说：，我们说：1. a b当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；n如果一个算符文法如果一个算符文法G中的任何终结符对中的任何终结符对(a，b)至多只满足下述三关系之一：至多只满足下述三关系之一：a b，a b 则称则称G是

17、一个是一个算符优先文法算符优先文法。2. a b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。302022-6-10n例例:考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | in由第由第(4)条规则，有条规则，有 ( )；n由规则由规则EET和和TT*F， 有有 *；n由由(2) TT*F 和和(3) FP F ，可得，可得* +；n由由(3)FP F 和和 F P F，可得，可得 。n由由(4)P(E)和和 EE+TT+TT*F+TF*F+TPF*F+TiF

18、*F+T 有有 ( +、( *、( 和和( i。312022-6-10 优先关系表优先关系表 + * i ( ) #+ * i ( ) # G结论结论: G是算符优先文法是算符优先文法 优先关系表优先关系表 + * i ( ) #+ * i ( ) # 322022-6-10n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足 a b的终结符对。的终结符对。2. a b当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。n确定满足关系

19、确定满足关系的所有终结符对：的所有终结符对：1. a b当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；332022-6-10n确定满足关系确定满足关系的所有终结符对：的所有终结符对：首先需要对首先需要对G的的每个非终结符每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：,|)(NTVQVaQaPaPaPFIRSTVT而或 a b 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。342022-6-10FIRSTVT Pa PaPQaaVQVTN( ) |,或而 ,|)(NTVQVaaQ

20、PaPaPLASTVT而或.,|=)(*TVaaaFIRST比较.,.|)(*TVaAaSaAFOLLOW比较352022-6-10q有了这两个集合之后，就可以通过检查每有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系个产生式的候选式确定满足关系 的所有终结符对。的所有终结符对。假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有 a b。362022-6-10n首先讨论构造集合首先讨论构造集合FIRSTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRST

21、VT(P)：1. 若有产生式若有产生式Pa或或PQa，则，则a FIRSTVT(P)；2. 若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则则a FIRSTVT(P)。FIRSTVT Pa PaPQaaVQVTN( ) |,或而 372022-6-10n数据结构：数据结构：布尔数组布尔数组 FP，a，使得，使得 FP，a为真的条件为真的条件是，当且仅当是，当且仅当a FIRSTVT(P)。开始时，按上。开始时，按上述的规则述的规则(1)对每个数组元素对每个数组元素FP，a赋初值。赋初值。栈栈STACK，把所有初值为真的数组元素，把所有初值为真的数组元素FP，a的符号对的符号对(P，

22、a)全都放在全都放在STACK之中。之中。382022-6-10n运算：运算：如果栈如果栈STACK不空，就将顶项弹出，记此不空，就将顶项弹出，记此项为项为(Q，a)。对于每个形如。对于每个形如PQ 的产生式，若的产生式，若FP，a为假，则变其值为真为假，则变其值为真且将且将(P，a)推进推进STACK栈。栈。上述过程必须一直重复，直至栈上述过程必须一直重复，直至栈STACK拆拆空为止。空为止。392022-6-10n如果把这个算法稍为形式化一点，我们如果把这个算法稍为形式化一点，我们可得如下所示的一个程序可得如下所示的一个程序(包括一个过程包括一个过程和主程序和主程序)：PROCEDURE

23、INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE； 把把(P，a)下推进下推进STACK栈栈 END；402022-6-10主程序：主程序：BEGIN FOR 每个非终结符每个非终结符P和终结符和终结符a DO FP，a:=FALSE； FOR 每个形如每个形如Pa或或PQa的产生式的产生式 DO INSERT(P，a)； WHILE STACK 非空非空 DOBEGIN 把把STACK的顶项，记为的顶项，记为(Q，a)，上托出去；，上托出去； FOR 每条形如每条形如PQ的产生式的产生式 DOINSERT(P，a)；END OF WHILE；END41

24、2022-6-10n这个算法的工作结果得到一个二维数组这个算法的工作结果得到一个二维数组F，从它可得任何非终结符从它可得任何非终结符P的的FIRSTVT。FIRSTVT(P)a | FP，a=TRUEn同理，可构造计算同理，可构造计算LASTVT的算法。的算法。422022-6-10n构造集合构造集合LASTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)：1. 若有产生式若有产生式P a或或P aQ，则，则a LASTVT(P)；2. 若若a LASTVT(Q)，且有产生式，且有产生式P Q ，则则a LASTVT(P)。

25、,|)(NTVQVaaQPaPaPLASTVT而或432022-6-10n使用每个非终结符使用每个非终结符P的的FIRSTVT(P)和和LASTVT(P)，就能够构造文法，就能够构造文法G的优先的优先表。表。 构造优先表的算法是：构造优先表的算法是：442022-6-10FOR 每条产生式每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和和Xi+1均为终结符均为终结符 THEN 置置Xi = Xi+1 IF i n-2且且 Xi 和和 Xi+2 都为终结符都为终结符但但 Xi+1 为非终结符为非终结符 THEN 置置Xi = Xi+2； IF Xi为终

26、结符而为终结符而Xi+1为非终结符为非终结符 THENFOR FIRSTVT(Xi+1)中的每个中的每个a DO 置置 Xi Xi+1 END构造优先表的算法是：构造优先表的算法是：452022-6-10n例例: 考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 计算文法计算文法G的的FIRSTVT和和LASTVT462022-6-10+ * ()iE TFP(,)(,*,)(,)(,*,)(iPFIRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT+ * ()iE TFP),)(),*

27、,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVT472022-6-105.2.2 算符优先分析算法算符优先分析算法n可归约串，句型，短语，直接短语，句柄，可归约串，句型，短语，直接短语，句柄，规范归约。规范归约。n一个文法一个文法G G的句型的的句型的素短语素短语是指这样一个短是指这样一个短语，它至少含有一个终结符，并且，除它语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。自身之外不再含任何更小的素短语。n最左素短语最左素短语是指处于句型最左边的那个素是指处于句型最左边的那个素短语。短语。482022-6-10n考虑下面的文法考虑下

28、面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | iEEF+*TiFTFTP+ETP句型：句型：T+F*P+i短语：短语：直接短语：直接短语：句柄：句柄：素短语：素短语：最左素短语：最左素短语：, T+F*P+iT, F, P, F*P, iT+F*PT, F, P, iTF*P, iF*P注意注意T+F*P不是，？不是，？492022-6-10n算符优先文法句型算符优先文法句型(括在两个之间括在两个之间)的一般的一般形式写成：形式写成： #N1a1N2a2NnanNn+1#其中，每个其中，每个ai都是终结符，都是终结符，N

29、i是可有可无的非是可有可无的非终结符。终结符。n定理定理：一个算符优先文法：一个算符优先文法G的任何句型的最的任何句型的最左素短语是满足如下条件的最左子串左素短语是满足如下条件的最左子串 NjajNiaiNi+1， aj-1 ai+1算符在同一层次上算符在同一层次上502022-6-10n算符优先分析算法算符优先分析算法n使用一个符号栈使用一个符号栈S，用它寄存终结符和非终结，用它寄存终结符和非终结符，符，k代表符号栈代表符号栈S的使用深度。的使用深度。 512022-6-10k:=1;Sk:=#;REPEAT 把下一个输入符号读进把下一个输入符号读进a中；中； IF Sk VT THEN j

30、:=k ELSE j:=k-1;WHILE Sj a DOBEGIN REPEAT Q:=Sj; IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把把Sj+1Sk归约为某个归约为某个N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sj = a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*调用出错诊察程序调用出错诊察程序*/ UNTIL a=#自左至右，终结符对终结符，非自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符对非终结符，而且对应的终结符相同。终结符相同。

31、 N X1 X2 Xk-j Sj+1 Sj+2 Sk522022-6-10n在算法的工作过程中，若出现在算法的工作过程中，若出现 j 减减1后的后的值小于等于值小于等于0时，则意味着输入串有错。时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号在正确的情况下，算法工作完毕时，符号栈栈S应呈现：应呈现：# N #。n由于非终结符对归约没有影响，因此，非由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈终结符根本可以不进符号栈S。532022-6-10n算符优先分析一般并不等价于规范归约。算符优先分析一般并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+

32、ETiFPiPiPn考虑下面的文法考虑下面的文法G(E)： (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i的句子的句子i+i*i+i542022-6-10n算符优先分析法特点：算符优先分析法特点：优点优点: : 简单，快速简单，快速缺点缺点: : 可能错误接受非法句子，能力有限可能错误接受非法句子，能力有限. .n算符优先分析法是一种广为应用、行之算符优先分析法是一种广为应用、行之有效的方法。有效的方法。用于分析各类表达式用于分析各类表达式ALGOL 60552022-6-105.2.3 5.2.3 优先函数优先函数n把每个终结符把每个终结符 与两个自然数与两