编译4语法—自上而下_zss_

1、编译原理编译原理(第三版第三版) 陈火旺等编著22022-3-20第四章第四章 语法分析语法分析自上而下分析自上而下分析n本章主要介绍语法分析的处理本章主要介绍语法分析的处理n要进行语法分析，必须对语言的语法结构要进行语法分析，必须对语言的语法结构进行描述。进行描述。采用正规式和有限自动机可以描述和识别语言采用正规式和有限自动机可以描述和识别语言的单词符号；的单词符号；用上下文无关文法来描述语法规则。用上下文无关文法来描述语法规则。32022-3-20n上下文无关文法的定义：上下文无关文法的定义： 一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V

2、VN N，S S，P)P)，其中，其中V VT T：终结符集合：终结符集合( (非空非空) )V VN N：非终结符集合：非终结符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集合( (有限有限) )，每个产生式形式为，每个产生式形式为P P， P P V VN N， ( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。42022-3-204.1 语法分析器的功能语法分析器的功能n语法分析的任务是分析一个文法

3、的句子语法分析的任务是分析一个文法的句子结构。结构。n语法分析器的功能：按照文法的产生式语法分析器的功能：按照文法的产生式( (语言的语法规则语言的语法规则) )，识别输入符号串是，识别输入符号串是否为一个句子。否为一个句子。52022-3-20源程序源程序单词符号单词符号取下一单词取下一单词.语法分语法分析树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分62022-3-20n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)自上而下分析法自上而下分析法(Top-down)(Top-down)n基本

4、思想：它从文法的开始符号出发，反复基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找使用各种产生式，寻找 匹配匹配 的的推导推导。72022-3-204.2 自上而下分析面临的问题自上而下分析面临的问题n自上而下就是从文法的开始符号出发，向自上而下就是从文法的开始符号出发，向下下推导推导，推出句子。，推出句子。带带“回溯回溯”的的不带回溯的递归子程序不带回溯的递归子程序(递归下降递归下降)分析方法。分析方法。n自上而下分析的主旨：对任何输入串，试自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号图用一切可能的办法，从文法开始符号(根根结点结点)出发，自上而下地为输入

5、串建立一棵出发，自上而下地为输入串建立一棵语法树语法树。或者说，为输入串寻找一个最。或者说，为输入串寻找一个最左推导。左推导。82022-3-20n例例3.4.1 假定有文法假定有文法G(S): (1) SxAy (2) A*|* 分析分析输入串输入串x*y(记为记为 )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*92022-3-20n当某个非终结符有多个产生式候选时，可当某个非终结符有多个产生式候选时，可能带来如下问题能带来如下问题: :1. 1. 分析过程中，当一个非终结符用某一个候分析过程中，当一个非终

6、结符用某一个候选匹配成功时，这种匹配可能是暂时的选匹配成功时，这种匹配可能是暂时的。出。出错错时时，不得不，不得不“回溯回溯”。2. 2. 文法左递归问题文法左递归问题。一个文法是含有左递归一个文法是含有左递归的，如果存在非终结符的，如果存在非终结符 P:P:PP 含有左递归的文法将使自上而下的分含有左递归的文法将使自上而下的分析陷入无限循环。析陷入无限循环。102022-3-204.3 LL(1)分析法分析法n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯112022-3-204.3.1 左递归的消除左递归的消除n直接消除

7、见诸于产生式中的左递归：假直接消除见诸于产生式中的左递归：假定关于非终结符定关于非终结符P的规则为的规则为PP | 其中其中 不以不以P开头。开头。 我们可以把我们可以把P的规则等价地改写为如下的的规则等价地改写为如下的非直接左递归形式：非直接左递归形式：P P P P | 左递归变右递归122022-3-20n一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是PP 1 | P 2 | | P m | 1 | 2| n其中，每个其中，每个 都不等于都不等于 ，每个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直接左递归性就是把这些规的直接左递归性就是把这些规则改写成：

8、则改写成： P 1P | 2P | | nP P 1P | 2P | | mP | 左递归变右递归132022-3-20n例例4.2 文法文法G(E):EET | TTT*F | FF(E) | i消去直接左递归：消去直接左递归： ETE E +TE | TFT T *FT | F(E) | iPP 1 | P 2 | | P m | 1 | 2| nP 1P | 2P | | nP P 1P | 2P | | mP | 142022-3-20n例如文法例如文法G(S):SQc|cQRb|bRSa|a虽没有直接左递归，但虽没有直接左递归，但S、Q、R都是左递归都是左递归的的SQcRbcSabc

9、一个文法消除左递归的条件：一个文法消除左递归的条件：F不含以不含以 为右部的产生式为右部的产生式F不含回路不含回路:PP152022-3-20n消除左递归的算法消除左递归的算法:1. 把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的规则改写成的规则改写成 Pi 1 | 2 | k ; (其中其中Pj 1| 2| k是关于是关于Pj的所有规则的所有规则) 消除关于消除关于Pi规则的直接左递归性规则的直接左递归

10、性 END3. 化简由化简由2所得的文法。去除那些从开始符号出发永所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。远无法到达的非终结符的产生规则。162022-3-20n例例 考虑文法考虑文法G(S)SQc|cQRb|b (4.3)RSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。n对于对于R，不存在直接左递归。，不存在直接左递归。n把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的规则的规则变为变为 QSab | ab | b172022-3-20n现在的现在的Q不含直接左递归，把它代入到不含直接左递归，把它代入到S的有关候选后，的有关候选后，S变

11、成变成SSabc | abc | bc | cn消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an关于关于Q和和R的规则已是多余的，化简为：的规则已是多余的，化简为：SabcS | bcS | cS S abcS | (4.4)182022-3-204.3.2 消除回溯、提左因子消除回溯、提左因子n为了消除回溯就必须保证：为了消除回溯就必须保证： 对文法的任何非终结符，当要它去匹配输对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地入串时，能够根据它所面临的输入符号准确地指派它的一个候选去

12、执行任务，并且此候选的指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。工作结果应是确信无疑的。nA 1 | 2 | | nSa.IPA.192022-3-20如果非终结符如果非终结符A的所有候选首符集两两不相交，的所有候选首符集两两不相交，即即A的任何两个不同候选的任何两个不同候选 i和和 jFIRST( i)FIRST( j) 当要求当要求A A匹配输入串时，匹配输入串时，A A就能根据它所面临的就能根据它所面临的第一个输入符号第一个输入符号a a，准确地指派某一个候选前去，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含执行任务。这个候选就是那个终结首符集含a

13、 a的的 。如何把一个文法改造成任如何把一个文法改造成任何非终结符的所有候选首何非终结符的所有候选首符集两两不相交呢？符集两两不相交呢？n令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所的所有有非终结符的每个候选非终结符的每个候选 定义它的终结首定义它的终结首符集符集FIRST( )为：为：.,|=)(*TVaaaFIRST 特别是，若特别是，若 ，则规定，则规定FIRST( )。*202022-3-20n提取公共左因子提取公共左因子: 假定关于假定关于A的规则是的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个其中，每个 不以不以 开头开头) 那么

14、，可以把这些规则改写成那么，可以把这些规则改写成A A | 1 | 2 | | mA 1 | 2 | | nn经过反复提取左因子，就能够把每个非终经过反复提取左因子，就能够把每个非终结符结符(包括新引进者包括新引进者)的所有候选首符集变的所有候选首符集变成为两两不相交。成为两两不相交。212022-3-20例 有产生式 B bBcA|b 由于由于FIRST(bBcA) FIRST(b) =b 则需要提取公共左因子则需要提取公共左因子 将产生式改写成：将产生式改写成： B bC C BcA| 222022-3-20n假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何的任何非终结符非

15、终结符A，我们定义，我们定义.,.|)(*TVaAaSaAFOLLOWAS*特别是，若特别是，若 ，则规定，则规定 FOLLOW(A)4.3.3 LL(1)分析条件分析条件232022-3-20n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1. 文法不含左递归文法不含左递归;2. 对于文法中对于文法中每一个每一个非终结符非终结符A的各个产生式的的各个产生式的候选首符集两两不相交候选首符集两两不相交; 即，若即，若A 1| 2| n 则则 FIRST( i)FIRST( j) (i j)3. 对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候，若它存在某个

16、候选首符集包含选首符集包含 ，则，则FIRST(A)FOLLOW(A)= i=1,2,.,n如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)LL(1)文法文法。242022-3-20n对于一个满足上述条件的文法，可以对其输对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。入串进行有效的无回溯的自上而下分析。 假设要用非终结符假设要用非终结符A进行匹配，面临的输进行匹配，面临的输入符号为入符号为a，A的所有产生式为的所有产生式为A 1 | 2 | | n1. 若若a FIRST( i)，则指派，则指派 i执行匹配任务；执行匹配任务

17、；2. 若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则： (1) 若若 属于某个属于某个FIRST( i )且且 a FOLLOW(A)， 则让则让A与与 自动匹配。自动匹配。 (2) 否则，否则，a的出现是一种语法错误。的出现是一种语法错误。252022-3-20n构造不带回溯的自上而下分析器构造不带回溯的自上而下分析器n分析程序由一组递归过程组成，文法中每分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。析程序称为递归下降分析器。( (因为文法因为文法的定义通常是递归的的定义通常是递归的)

18、 )n几个全局过程和变量：几个全局过程和变量：ADVANCE，把输入串指示器，把输入串指示器IP指向下一个指向下一个输入符号，即读入一个单字符号输入符号，即读入一个单字符号SYM，IP当前所指的输入符号当前所指的输入符号ERROR，出错处理子程序，出错处理子程序4.4 递归下降分析程序构造递归下降分析程序构造262022-3-20n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in每个非终结符有对应的子程序的定义，每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终首先在分析过程中，当需要从某个非终结符出发进行展开结符出发进

19、行展开( (推导推导) )时，就调用这时，就调用这个非终结符对应的子程序。个非终结符对应的子程序。272022-3-20n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : PROCEDURE E；BEGIN T；E END；PROCEDURE E ； IF SYM=+ THEN BEGINADVANCE； T；E END282022-3-20PROCEDURE T；BEGIN F；T ENDPROCEDURE T ；IF SYM=* THENBEGIN ADVANCE； F；T END；n

20、例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : 292022-3-20n例例: :文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : PROCEDURE F； IF SYM=i THEN ADVANCE ELSE IF SYM=( THEN BEGIN ADVANCE; E； IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;302022-3-20主

21、程序主程序:PROGRAM PARSER;BEGIN ADVANCE; E; IF SYM # THEN ERROREND;312022-3-20n在元符号在元符号“”和和“|”的基础上，扩充的基础上，扩充几个元语言符号：几个元语言符号：1. 用花括号用花括号 表示闭包运算表示闭包运算 *。2. 用用 n0表示可任意重复表示可任意重复0次至次至n次，。次，。3. 用方括号用方括号 表示表示 10 ，即表示，即表示 的出现可的出现可有可无有可无(等价于等价于 | )。 引入上述元符号的文法亦称引入上述元符号的文法亦称扩充的巴科扩充的巴科斯范式斯范式。文法的另一种表示法和转换图文法的另一种表示法和

22、转换图322022-3-20n例如，通常的例如，通常的“实数实数”可定义为：可定义为： decimalsigninteger.digitexponent exponentEsigninteger integerdigitdigit sign + | -n用扩充的巴科斯范式来描述语法，直观易懂，用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。便于表示左递归消去和因子提取。332022-3-20n例例4.5 文法文法ET | E+TTF | T*FFi | (E)可表示成可表示成ET+TTF*FFi | (E) (4.6)342022-3-20n可以用语法图来表示语言的文法。

23、可以用语法图来表示语言的文法。T+ETF*TFi)FE(352022-3-20n可构造一组递归下降分析程序：可构造一组递归下降分析程序：PROCEDURE E；BEGIN T； WHILE SYM=+ DO BEGIN ADVANCE； T ENDEND；PROCEDURE T；BEGIN F； WHILE SYM=* DO BEGIN ADVANCE； F ENDEND；362022-3-204.5 预测分析程序预测分析程序一、预测分析程序工作原理一、预测分析程序工作原理n预测分析程序或预测分析程序或LL(1)分析法：分析法：总控程序总控程序分析表分析表 MA，a矩阵，矩阵，A VN ，a

24、VT 是终是终结符或结符或，分析栈分析栈 STACK 用于存放文法符号用于存放文法符号372022-3-20总控程序总控程序分析表分析表X#输入串输入串分析栈分析栈STACKa1a2.ai#预测分析程序的工作图预测分析程序的工作图# Sa1a2.ai#分析开始时：分析开始时：382022-3-20q总控程序根据现行栈顶符号总控程序根据现行栈顶符号X和当前输入和当前输入符号符号a，执行下列三种动作之一，执行下列三种动作之一:1. 若若Xa，则宣布分析成功，则宣布分析成功，停止分析。停止分析。2. 若若Xa ，则把，则把X从从STACK栈顶栈顶弹出，让弹出，让a指向下一个输入符号。指向下一个输入符

25、号。匹配成功392022-3-203. 若若X是一个非终结符，则查看分析表是一个非终结符，则查看分析表M 若若MX，a中存放着关于中存放着关于X的一个产的一个产生式，把生式，把X弹出栈顶，弹出栈顶，把产生式的把产生式的右部符号串按反序入栈右部符号串按反序入栈(若右部符号若右部符号为为 ，则什么也不做，则什么也不做)。在把产生式。在把产生式的右部符号推进栈的同时应做这个的右部符号推进栈的同时应做这个产生式相应的语义动作。产生式相应的语义动作。 若若MX，a中存放着中存放着“出错标志出错标志”，则调用出错诊察程序，则调用出错诊察程序ERROR。推导402022-3-20n例例4.6 对于文法对于文

26、法G(E)ETE E +TE | TFT T *FT | F(E) | i输入串为输入串为i1*i2+i3，利用分析表进行预测分析：，利用分析表进行预测分析：i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)412022-3-20步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式0#Ei1*i2+i3#1#E Ti1*i2+i3# ETE 2#E T Fi1*i2+i3# TFT 3#E T ii1*i2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF

27、(E)422022-3-20步骤步骤符号栈符号栈输入串输入串所用产生式所用产生式3#E T ii1*i2+i3# Fi4#E T *i2+i3#5#E T F* *i2+i3# T *FT 6#E T F i2+i3#7#E T i i2+i3# Fii+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)432022-3-20步骤步骤符号栈符号栈输入串输入串所用产生所用产生7#E T ii2+i3# Fi 8#E T +i3#9#E +i3# T 10#E T+ +i3# E +TE 11#E T i3#i+*()#EETE ETE

28、 E E +TE E E TTFT TFT T T T *FT T T FFiF (E)442022-3-20步骤步骤符号栈符号栈输入串输入串所用产生所用产生11#E Ti3#12#E T F i3# TFT 13#E T ii3# Fi14#E T #15#E # T 16# # E i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFiF (E)452022-3-20二、分析表二、分析表MA，a的构造的构造q构造构造FIRST( )和和FOLLOW(A)q构造分析表构造分析表MA，a462022-3-20构造构造FIRST( ),|=)(

29、*TVaaaFIRST n对每一文法符号对每一文法符号X VTVN构造构造FIRST(X) 连续使用下面的规则，直至每个集合连续使用下面的规则，直至每个集合FIRST不再增大为止：不再增大为止：1. 若若X VT，则，则FIRST(X)X。2. 若若X VN，且有产生式，且有产生式Xa，则把，则把a加入到加入到FIRST(X)中；若中；若X 也是一条产生式，则把也是一条产生式，则把 也加到也加到FIRST(X)中。中。472022-3-203. 若若XY是一个产生式且是一个产生式且Y VN，则把，则把FIRST(Y)中的所有非中的所有非 -元素都加到元素都加到FIRST(X)中；中；若若XY1

30、Y2Yk是一个产生式，是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何都是非终结符，而且，对于任何j，1 j i-1，FIRST(Yj)都含有都含有 (即即Y1Yi-1 )， 则把则把FIRST(Yi)中的所有非中的所有非 -元素都加到元素都加到FIRST(X)中；特别是，若所有的中；特别是，若所有的FIRST(Yj)均含有均含有 ，j1，2，k，则把，则把 加到加到FIRST(X)中。中。482022-3-20n对文法对文法G的任何符号串的任何符号串 =X1X2Xn构造构造集合集合FIRST( )。1. 置置FIRST( )FIRST(X1) - ；2. 若对任何若对任何1 j i-1，FIRST(Xj)，则把，则把FIRST(Xi) - 加至加至FIRST( )中；特别是，中；特别是，若所有的若所有的FIRST(Xj)均含有均含有 ，1 j n，则把，则把 也加至也加至FIRST( )中。显然，若中。显然，若 = 则则FIRST( ) = 。492022-3-20构造构造FOLLOW(A),|)(*TVaAaSaAFOLLOW502022-3-20n对于文法对于文法G的每个非终结符的每个非终结符X构造构造FOLLOW(X)的办法是，连续使用下面的的办法是，连续使用下面的规则，直至每个规则，直至每个FOLLOW不