自顶向下的语法分析

1、1第五章第五章自顶向下语法分析方法自顶向下语法分析方法2语法分析语法分析n语法分析（语法分析（Ch3:Ch3:句子分析）是编译程序的核心句子分析）是编译程序的核心部分。其作用是识别由词法分析给出的单词符部分。其作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）。号序列是否是给定文法的正确句子（程序）。语法分析方法语法分析方法自顶向下分析自顶向下分析自底向上分析自底向上分析3自顶向下自顶向下分析分析面向目标面向目标的分析方法的分析方法确定确定的自顶向下分析的自顶向下分析方法需对文法有一定的限方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构制，但由于实现方法简单、

2、直观，便于手工构造或自动生成语法分析器，是最常用的方法之造或自动生成语法分析器，是最常用的方法之一。一。不不确定确定的自顶向下的自顶向下分析分析方法是带回溯的分析方方法是带回溯的分析方法，实际是一种穷举的试探方法，效率低，代法，实际是一种穷举的试探方法，效率低，代价高，使用较少。价高，使用较少。自顶向下的语法分析自顶向下的语法分析4自顶向下的语法分析自顶向下的语法分析5.1 5.1 确定的自顶向下分析思想确定的自顶向下分析思想5.2 5.2 不确定的自顶向下分析不确定的自顶向下分析5.3 5.3 非非LL(1)LL(1)文法的等价变换文法的等价变换5.4 5.4 LL(1)LL(1)文法的判别

3、文法的判别5.5 5.5 确定的自顶向下分析方法确定的自顶向下分析方法5n确定的自定向下分析方法，是从文法的开确定的自定向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符始符号出发，考虑如何根据当前的输入符号（单词符号）号（单词符号）惟一惟一的确定选用哪个产生的确定选用哪个产生式替换相应非终结符向下推导，或如何构式替换相应非终结符向下推导，或如何构造一棵相应的语法树。造一棵相应的语法树。n什么样的文法什么样的文法能够进行确定的自顶向下语能够进行确定的自顶向下语法分析？法分析？5.1 5.1 确定的自顶向下分析思想确定的自顶向下分析思想6n文法文法G1SG1S：S S p pA|A|

4、q qB BA A c cA Ad d| |a aB B d dB |B |c cn识别输入串识别输入串 w w= = pccadd#pccadd# 是否是是否是G1SG1S的句子的句子例例1 1n自顶向下的推导自顶向下的推导过程为：过程为：S pA pcAd pccAdd pccadd#7n文法特点：文法特点：n每个产生式右部都由终结符号开始每个产生式右部都由终结符号开始n如果两个产生式有相同的左部，那么它们的右部由不同如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始的终结符开始n文法在推导过程中完全可以根据当前的输入文法在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往

5、下推导，符号决定选择哪个产生式往下推导，分析过分析过程唯一确定程唯一确定。S S p pA |A |q qB BA A c cA Ad d| |a aB B d dB |B |c c8n文法文法G2SG2S：S AS Ap p |B|Bq q A A c cA |A |a aB B d dB |B |b bn识别输入串识别输入串w w= = ccap#ccap#是否是是否是G2SG2S的句子的句子 例例2推导过程：推导过程： S# Ap# cAp# ccAp# ccap#9S AS Ap p |B|Bq qA A c cA |A |a aB B d dB |B |b bn文法特点：文法特点：n

6、产生式的右部不全是由终结符开始产生式的右部不全是由终结符开始n如果两个产生式有相同的左部，它们的右部由不同的如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始终结符或非终结符开始n文法中无空产生式文法中无空产生式n对于产生式中相同左部含有非终结符开始的产对于产生式中相同左部含有非终结符开始的产生式时，可通过考察生式时，可通过考察产生式向下推导时能够推产生式向下推导时能够推导出的第一个终结符导出的第一个终结符唯一确定该用哪个产生式唯一确定该用哪个产生式进行替换。进行替换。具有相同左部的具有相同左部的产生式向下推导产生式向下推导时能够推导出不同的终结符时能够推导出不同的终结符10F

7、IRSTFIRST集的定义集的定义n设设G=(VG=(VT T，V VN N，P P，S)S)是上下文无关文是上下文无关文nFIRST(FIRST( )=a|)=a| = a = a ，a aV VT T， ， V V* * n若若 =则规定则规定FRIST(FRIST( ) ) 称称FRIST(FRIST( ) )为为 的的开始符号集开始符号集或或首符号集首符号集。n在文法在文法G2G2中：中：S-Ap A-cA|aS-Ap A-cA|a FRIST( FRIST(Ap)=aAp)=a，ccS-Bq B-dB|bS-Bq B-dB|b FRIST(Bq) FRIST(Bq)=b=b，d d

8、使得面向非终结符使得面向非终结符S S为某一输入符号为某一输入符号x x寻求匹配时寻求匹配时, ,可可由由x x与与两集合的归属关系确定选用哪个产生式进行推导两集合的归属关系确定选用哪个产生式进行推导。（。（文法文法1 1同同）*交集交集为空为空无空产无空产生式生式11例例3（含空产生式的文法）（含空产生式的文法）n文法文法GSGS：S aA |dS aA |d A A b bAS |AS |n识别输入串识别输入串 w= w= abd#abd# 是否是是否是GSGS的句子的句子n当某一非终结符的产生式中含有空产生式时，它的当某一非终结符的产生式中含有空产生式时，它的非空产非空产生式右部的首符号

9、集两两不相交生式右部的首符号集两两不相交，并与在推导过程紧跟该并与在推导过程紧跟该非终结符右边可能出现的终结符集也不相交非终结符右边可能出现的终结符集也不相交，则仍可构造，则仍可构造确定的自顶向下分析。确定的自顶向下分析。A-bAS|b|A-bAS|d|n推导过程：推导过程：S aA abAS abS abd12FOLLOWFOLLOW集的定义集的定义n设设G=(VG=(VT T，V VN N，P P，S)S)是上下文无关文法，是上下文无关文法，A AVVN N，S S是是开始符号开始符号nFOLLOW(A)= a S = A ,aVT，aFRIST( )， V*， V+ n若若S = A ，

10、且且 =，则，则#FOLLOW(A)n也可定义为：也可定义为：nFOLLOW(A)=aFOLLOW(A)=a S = S = AaAa，且，且aVaVT T n若有若有S S = A A，则规定则规定#F#FOLLOW(A)OLLOW(A) （用（用“# #”作为输入串的结束符，或称输入串括号）作为输入串的结束符，或称输入串括号）*13结论结论n当文法中含有形如当文法中含有形如 AA A A （AVAVN N， ， V V* *） 的产生式时，的产生式时，若若 和和 不能同时推导出空，假定不能同时推导出空，假定 = =, , =则当则当 FIRST( )(FIRST( )FOLLOW(A)=

11、时，若当前非终结符为时，若当前非终结符为A,A,面临某一输入符号面临某一输入符号x x，可，可由由x x的归属决定的归属决定选择选择A A的哪个候选式对非终结符的哪个候选式对非终结符A A进进行替换。行替换。*14SelectSelect集集（PredictPredict集）集）n给定上下文无关文法的产生式给定上下文无关文法的产生式AA ，AVAVN N， V V* *，若，若 =，则，则 SELECT(A SELECT(A )= FIRST()= FIRST( ) )n如果如果 =，则，则 SELECT(ASELECT(A )=(FIRST()=(FIRST( )-)FOLLOW(A)-)F

12、OLLOW(A)*一个上下文无关文法能进行确定的自顶向下语法分一个上下文无关文法能进行确定的自顶向下语法分析的充分必要条件是：析的充分必要条件是：对每个非终结符对每个非终结符A A的两个不同的两个不同产生式，产生式，AA ，AA ，满足，满足 SELECT(ASELECT(A )SELECT(A)SELECT(A )= )= 其中其中 、 不同时能不同时能=,=,这样的文法称为这样的文法称为LL(1)LL(1)文法文法。LL(1)LL(1)文法文法*16LL(1)LL(1)文法文法n能够使用自顶向下分析技术的文法是能够使用自顶向下分析技术的文法是LL(1)LL(1)文法。文法。nLL(1)LL

13、(1)的含义的含义n第第1 1个个L: L: 自顶向下分析时从左向右扫描输入串自顶向下分析时从左向右扫描输入串n第第2 2个个L: L: 分析过程中将用最左推导分析过程中将用最左推导n1:1:只需向右看一个符号便可决定如何推导即选择哪个只需向右看一个符号便可决定如何推导即选择哪个产生式（进行）推导产生式（进行）推导n类似也可以有类似也可以有LL(k)LL(k)文法，也就是需向前查看文法，也就是需向前查看k k个个符号才可确定选用哪个产生式。符号才可确定选用哪个产生式。17例文法例文法GSGS：SaA|d SaA|d AbAS| AbAS|nSELECT(SaA)=a SELECT(Sd)=dn

14、SELECT(AbAS)=b SELECT(A)=a, d, #nSELECT(SaA)SELECT(Sd)=ad= SELECT(AbAS)SELECT(A)=ba,d,#= 文法为文法为LL(1)文法文法，可对输入串进行确定的自顶向下分析。，可对输入串进行确定的自顶向下分析。18例文法例文法GSGS：SaAS|bSaAS|b AbA| AbA|nSELECT(SaAS)=a SELECT(Sb)=bnSELECT(AbA)=b SELECT(A)=a，bnSELECT(SaAS)SELECT(Sb)=ab= SELECT(AbA)SELECT(A)=ba, b 该文法不是该文法不是LL(1

15、)文法文法.不能对输入串（如不能对输入串（如w=ab）进行确定的自顶向下的语法分析。）进行确定的自顶向下的语法分析。 S=aAS=abAS=abS=? =aS=ab195.2 5.2 不确定的自顶向下分析不确定的自顶向下分析n当文法不满足当文法不满足LL(1)LL(1)文文法的条件时，不能进法的条件时，不能进行确定的自顶向下分析，分析过程中会出现行确定的自顶向下分析，分析过程中会出现回溯现象，即只能进行不确定的自顶向下分回溯现象，即只能进行不确定的自顶向下分析。析。n三种情况下会引起分析过程中的回溯：三种情况下会引起分析过程中的回溯：20第一种情况第一种情况n关于同一非终结符的不同产生式右部关

16、于同一非终结符的不同产生式右部FIRSTFIRST集交集不为空集交集不为空而引起回溯：而引起回溯：n如：文法如：文法S-xAyS-xAy A-ab|a A-ab|a输入串输入串w=xayw=xay，分析过程可能为：，分析过程可能为：n关于同一非终结符的不同产生式右部以相同的符关于同一非终结符的不同产生式右部以相同的符号串号串 开始（开始（A-A-| |），称为具有），称为具有左公因子左公因子。左公因子的存在必定会使左公因子的存在必定会使FIRSTFIRST集交集不为空集交集不为空。Sx A ya bSx A ya21第二种情况第二种情况n关于同一非终结符的不同产生式右部存在能关于同一非终结符的

17、不同产生式右部存在能=的产生式，且该非终结符的的产生式，且该非终结符的FOLLOWFOLLOW集与集与其它产生式右部其它产生式右部FIRSTFIRST集的交集不为空集的交集不为空。n如文法如文法GSGS：SaAS|bSaAS|b AbA| AbA| First(bA) First(bA)与与Follow(A)Follow(A)的交集不为空。对输的交集不为空。对输入串入串W=abW=ab的分析存在回溯（前面已经证明）。的分析存在回溯（前面已经证明）。*22第三种情况第三种情况n文法中含有左递归文法中含有左递归。n文法文法G G，存在，存在UVUVn n，如果有，如果有U-UU-U, , 则则G

18、G为左递归文法为左递归文法（直接左递归直接左递归）n类似的：类似的：U-VU-V V-U V-U（间接左递归间接左递归）n如：如：S-Sa S-bS-Sa S-b 输入串输入串W=baaW=baa的分析：的分析：S=bS=b = =SaSa=ba=ba = =SaSaa=baa a=baa （回溯）（回溯）n不难证实，若文法中含有间接左递归，也会引起回不难证实，若文法中含有间接左递归，也会引起回溯。溯。23不确定的自顶向下分析不确定的自顶向下分析n分析过程是一种试探过程，分析过程需进行分析过程是一种试探过程，分析过程需进行回溯，也称这种方法是回溯，也称这种方法是带回溯的自顶向下分带回溯的自顶向

19、下分析方法析方法。n语法分析的同时往往进行语义分析，回溯代语法分析的同时往往进行语义分析，回溯代价高，在实际的编译程序设计中很少使用。价高，在实际的编译程序设计中很少使用。245.3 5.3 非非LL(1)LL(1)文法的改造文法的改造n若文法中含有左公因子或左递归，则文法肯定不是若文法中含有左公因子或左递归，则文法肯定不是LL(1)LL(1)文法，不能进行确定的自顶向下语法分析。文法，不能进行确定的自顶向下语法分析。n通过提取左公共因子、消除左递归对文法进行等价通过提取左公共因子、消除左递归对文法进行等价变换，在变换，在某些特殊情况某些特殊情况下可使非下可使非LL(1)LL(1)文法变为文法

20、变为LL(1)LL(1)文法。文法。n提取左公因子，消除左递归之后文法只是满足提取左公因子，消除左递归之后文法只是满足LL(1)LL(1)文法文法的必要条件，而不是充分条件，所以不一定是的必要条件，而不是充分条件，所以不一定是LL(1)LL(1)文法。文法。25提取左公因子提取左公因子n若文法中含有形如若文法中含有形如|的的产生式，则称文法中含有左产生式，则称文法中含有左公因子。公因子。这将导致关于同一非终结符的不同产生式右部的这将导致关于同一非终结符的不同产生式右部的FIRSTFIRST集交集不为空，不满足集交集不为空，不满足LL(1)LL(1)文法的充要条件。文法的充要条件。n如如ifif

21、语句的文法语句的文法S if E then S S if E then S |if E then S else S |if E then S else S |other |other 存在左公因子存在左公因子 if E then Sif E then S 影响影响: :遇到遇到 if if 时难以判断用哪一个产生式进行匹配（推导）时难以判断用哪一个产生式进行匹配（推导）26提取左公因子提取左公因子n可将文法中的可将文法中的A A|变换为：变换为：nB B B B| （B B为新引入的非终结符）为新引入的非终结符）n若若和和 中仍含有左公共因子，可再次提取，直至引入新非中仍含有左公共因子，可再次

22、提取，直至引入新非终结符的有关产生式再无左公共因子为止。终结符的有关产生式再无左公共因子为止。n如如if if 语句文法语句文法 S if E then S S if E then S |if E then S else S |if E then S else S |other |othern改写为：改写为： S if E then SSS if E then SS|other |other S|else S S|else S27提取左公因子提取左公因子n更一般的，可将形如更一般的，可将形如 AA1 1|2 2| |n n | |1 1|2 2| | | | m m 的规则改写为的规则改写为

23、AAAA|1 1|2 2| | | | m mAA1 1|2 2| |n n28n例例1 1：文法：文法G1G1的产生式为的产生式为(1) SaSb(1) SaSb (2) SaS (2) SaS (3) S (3) S (1)(2) (1)(2)提取左公共因子后得提取左公共因子后得 SaS(b|SaS(b| ) ) S S 进一步变为进一步变为G1G1： SaSASaSA S S A Abb A A （非（非LL(1)LL(1)文法）文法） 29n例例2 2：文法：文法G2G2的产生式为的产生式为(1)Aad(1)Aad (2)ABc(2)ABc (3)BaA (3)BaA (4)BbB (

24、4)BbBn将将(3)(4)(3)(4)代入代入(2)(2)得到：得到： (1)Aad(1)Aad (2)AaAc (2)AaAc (3)AbBc (3)AbBc (4)BaA (4)BaA (5)BbB (5)BbB左公共因子可能是隐式的左公共因子可能是隐式的30n提取提取(1)(2)(1)(2)的左公共因子的左公共因子 Aa(d|Ac)Aa(d|Ac) AbBc AbBc BaA BaA BbB BbBn引入新终结符引入新终结符A A (1) AaA (1) AaA (2) AbBc (2) AbBc (3) A (3) Add (4) A (4) AAcAc (5) BaA (5) Ba

25、A (6) BbB (6) BbB （LL(1)LL(1)文法）文法）J注意：注意：J有些文法不能在有限步骤内提取左公因子。有些文法不能在有限步骤内提取左公因子。(P86(P86例例5.9)5.9)J提取左公因子后提取左公因子后若不含空产生式和左递归则文法是若不含空产生式和左递归则文法是LL(1)LL(1)文法文法，否则需进一步判定。否则需进一步判定。 (1)Aad (1)Aad (2)AaAc (2)AaAc (3)AbBc (3)AbBc (4)BaA (4)BaA (5)BbB (5)BbB31消除直接左递归消除直接左递归n直接左递归直接左递归n若文法中含有形如若文法中含有形如AA|AA

26、|的产生式，的产生式，则称文法中含有直接左递归则称文法中含有直接左递归（生成的串的形式（生成的串的形式为为 . . . . . . ）n直接左递归的消除：直接左递归的消除：n将将AA|AA|替换为替换为 AAAA A AAAn文法文法S-Sa|bS-Sa|b改写后对输入串改写后对输入串baaa#baaa#是否可是否可进行确定分析？进行确定分析？32表达式文法消除左递归表达式文法消除左递归nGE:GE:nEE+TEE+TT TnTTTT* *F FF FnFiFi(E) (E) n消除左递归后为：消除左递归后为：nE T EE T EnE E + T E + T E| | nT F TT F T

27、nT T* * F T F TnF ( E )F ( E )i i将AA|替换为 AA AA33n一般而言，假定关于一般而言，假定关于P P的全部产生式是的全部产生式是PPP P 1 1 | P| P 2 2 | | | P | P m m | | 1 1 | | 2 2| | | n n 则消除则消除P P的直接左递归之后为：的直接左递归之后为： PP 1 1P P | | 2 2P P | | | | n nP P P P 1 1P P | | 2 2P P | | | | m mP P | | 左递归变左递归变右递归右递归消除直接左递归消除直接左递归34消除间接左递归消除间接左递归n间接

28、左递归间接左递归nS Aa | b (1)(2)nA Sd | (3)(4)n先变换成直接左递归先变换成直接左递归(1)(2)(1)(2)代入代入(3)(3)nS Aa | bnA Aad | bd | n再消除左递归再消除左递归nS Aa | bnA bd A | A nA adA | 35消除一切左递归消除一切左递归n1. 1. 把文法把文法G G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成A A1 1， A A2 2，A An n；n2. 2. FOR i:=1 TO n DOFOR i:=1 TO n DO BEGIN BEGIN FOR j:=1 TO i-1 D

29、O FOR j:=1 TO i-1 DO BEGIN BEGIN 把形如把形如A Ai iAAj j 的规则改写成的规则改写成 A Ai i 1 1 | | 2 2 | | | k k ; ; ( (其中其中A Aj j 1 1| | 2 2| | | k k是关于是关于A Aj j的所有规则的所有规则) ) END END 消除关于消除关于A Ai i规则的直接左递归性规则的直接左递归性 ENDENDn3. 3. 化简由化简由2 2所得的文法。去除无用产生式。所得的文法。去除无用产生式。M注意该算法要求文法中不含形如注意该算法要求文法中不含形如A-AA-A的产生式和空产生式。的产生式和空产生

30、式。36消除一切左递归消除一切左递归n例如文法例如文法G(S):G(S):SQc|cSQc|cQRb|bQRb|b RSa|a RSa|a 虽没有直接左递归，但虽没有直接左递归，但S S、Q Q、R R都是左递归的都是左递归的S SQcQcRbcRbcSabcSabc37n文法文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R R、Q Q、S Sn对于对于R R，不存在直接左递归，把，不存在直接左递归，把R R代入到代入到Q Q的有的有关候选关候选后，把后，把Q Q的规则变为的规则变为 QSab | ab | bn现在的现在的Q Q不含直接左递归，把它不

31、含直接左递归，把它代入到代入到S S的有关的有关候选候选后，后，S S变成变成SSabc | abc | bc | c消除一切左递归消除一切左递归38nS变成：变成：SSabc | abc | bc | cn消除消除S的直接左递归后：的直接左递归后：SabcS | bcS | cS S abcS | QSab |ab | bRSa|an关于关于Q和和R的规则已是多余的，化简为：的规则已是多余的，化简为：SabcS | bcS | cS S abcS | 消除一切左递归消除一切左递归39n注意，由于注意，由于对非终结符排序的不同，最后所得对非终结符排序的不同，最后所得的文法在形式上可能不一样的文

32、法在形式上可能不一样。但不难证明，它。但不难证明，它们都是等价的。们都是等价的。n例如，若对前面文法的非终结符排序选为例如，若对前面文法的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：，那么，最后所得的无左递归文法是：SQc | cQRb | bRbcaR | caR |a R R bca R | 消除一切左递归消除一切左递归40非非LL(1)LL(1)文法的改造文法的改造n提取左公因子，消除左递归提取左公因子，消除左递归之后文法只之后文法只是满足是满足LL(1)LL(1)文法的文法的必要条件必要条件，而不是充，而不是充分条件，所以分条件，所以不一定是不一定是LL(1)LL(1)

33、文法文法。n根据定义进行判别根据定义进行判别415.4 LL(1)5.4 LL(1)文法的判别文法的判别n根据定义进行判别根据定义进行判别n对每个非终结符对每个非终结符A A的两个不同产生式，的两个不同产生式，AA ，AA ，满足，满足SELECT(ASELECT(A )SELECT(A)SELECT(A )= )= ，其中，其中 、 不同时能不同时能=，这样的文法称为，这样的文法称为LL(1)LL(1)文法文法。n为求为求SELECT(ASELECT(A ) )，需求出，需求出FIRST(FIRST( ),),若若 =，则还需求出则还需求出FOLLOW(A),FOLLOW(A),因此判别步骤

34、为：因此判别步骤为：n1)1)求出能推出求出能推出 的非终结符的非终结符n2)2)计算非终结符的计算非终结符的FIRSTFIRST集集n3)3)计算非终结符的计算非终结符的FOLLOWFOLLOW集集 （若所有非终结符均不能推出空，此步可省）（若所有非终结符均不能推出空，此步可省）n4)4)计算计算SELECTSELECT集合，根据定义判定。集合，根据定义判定。*42以改造后的表达式文法为例以改造后的表达式文法为例nGEnE T EnE + T E|nT F TnT* F TnF ( E )i431)求出能推出求出能推出 的非终结符的非终结符nP79-80(略略)：逐次扫描的过程：逐次扫描的过

35、程n一般情况：一般情况：n若有形如若有形如A- 的空产生式，则的空产生式，则A能推出空能推出空n若每个产生式右部都含有终结符，则肯定不能推出空若每个产生式右部都含有终结符，则肯定不能推出空n当关于某一非终结符的一个产生式右部全是非终结符且每一个当关于某一非终结符的一个产生式右部全是非终结符且每一个都能推出空时，该非终结符能推出空都能推出空时，该非终结符能推出空n如：文法如：文法GE nE T E nE + T E| nT F TnT* F T nF ( E )i 能推出空能推出空能推出空能推出空不能推出空不能推出空不能推出空不能推出空不能推出空不能推出空442)计算计算FIRST集集n求一个文

36、法符号的求一个文法符号的FIRSTFIRST集集(1)(1)若若X X V V ，则，则FIRST(X)=XFIRST(X)=X(2)(2)若若X X V VN N，且有产生式，且有产生式X Xa a，a a V V ，则，则a a FIRST(X)FIRST(X)(3)(3)若若X X V VN N，X X，则，则 FIRST(X)FIRST(X)(4)(4)若若X X，Y Y1 1，Y Y2 2，Y Yn n都都 V VN N，而有，而有XYXY1 1Y Y2 2Y Yn n，当，当Y Y1 1，Y Y2 2，Y Yi-1i-1都都= 时时( (1 1i in)n)，则，则First(YF

37、irst(Y1 1) ) ，First(YFirst(Y2 2) ) ，First(YFirst(Yi-1i-1) ) ，First(YFirst(Yi i) )都包含都包含在在First(XFirst(X) )中中(5)(5)当当(4)(4)所有所有Y Yi i= 时时(i=1(i=1，2 2，n)n)，则，则First(XFirst(X) )包含包含 First(YFirst(Y1 1) )First(YFirst(Y2 2) )First(YFirst(Yn n) ) 反复使用反复使用(2)(2)(5)(5)直到每个符号的直到每个符号的FIRSTFIRST集不再扩大为止集不再扩大为止*4

38、5表达式文法表达式文法nFIRST(E)=FIRST(T)= FIRST(E)=FIRST(T)= nFIRST(EFIRST(E )= )= nFIRST(T)=FIRST(F)= FIRST(T)=FIRST(F)= nFIRST(TFIRST(T )= )= nFIRST(F)=FIRST(F)=E T E 否否E + T E| 是是T F T 否否T* F T 是是F ( E )i 否否(, i(, i(1)(1)若若X X V V ，则，则FIRST(X)=XFIRST(X)=X(2)(2)若若X X V VN N，且有产生式，且有产生式X Xa a，a a V V ，则，则a a

39、FIRST(X)FIRST(X)(3)(3)若若X X V VN N，X X，则，则 FIRST(X)FIRST(X)(4)(4)若若X X，Y Y1 1，Y Y2 2，Y Yn n都都 V VN N，而有，而有XYXY1 1Y Y2 2Y Yn n，当，当Y Y1 1，Y Y2 2，Y Yi-1i-1都都= 时时( (1 1i in)n)，则，则First(YFirst(Y1 1) ) ，First(YFirst(Y2 2) ) ，First(YFirst(Yi-1i-1) ) ，First(YFirst(Yi i) )都包含在都包含在First(XFirst(X) )中中(5)(5)当当(

40、4)(4)所有所有Y Yi i= 时时(i=1(i=1，2 2，n)n)，则，则First(XFirst(X)=)=First(YFirst(Y1 1) )First(YFirst(Y2 2) )First(YFirst(Yn n) ) (, i *, +, 46n求出每个文法符号的求出每个文法符号的FIRSTFIRST集后可以求出集后可以求出一个符号一个符号串的串的FIRSTFIRST集集n若符号串若符号串 V V* *， =X=X1 1X X2 2X Xn n，当，当X1X1不能不能= ，则置，则置First(First( )= )= First(X1First(X1) )n若对任何若对任

41、何j(j(1 1j ji-1i-1，2 2i in n) )， FIRST(XFIRST(Xj j) )， FIRST(XFIRST(Xi i) )，则，则n当所有当所有FIRST(XFIRST(Xj j) )( (1 1j jn n) )，都含有，都含有 时，则时，则n如如nFIRST(TEFIRST(TE)=FIRST(T)=)=FIRST(T)=(, i nFIRST(FIRST(* *FTFT)=)=* * )First(X)-)(First(X)First(i11jij) )(First(X)First(1jnjn文法文法Gs: nS-MH|anH-LSo|nK-dML|nL-eHf

42、nM-K|bLMn根据定义求解根据定义求解nFirst(S)=First(M) First(H) a=a, b, d, e, nFirst(H)=First(L) =e, nFirst(K)=d =d, nFirst(L)= enFirst(M)=First(K) b=b, d, 例：求文法例：求文法Gs每个非终结符的每个非终结符的First集集47是是是是是是否否是是483)计算计算FOLLOW集集(1)对于文法的开始符号对于文法的开始符号S，置，置#于于FOLLOW(S)中中(2)若若B是一个产生式，则把是一个产生式，则把FIRST()的非空元的非空元素素加至加至FOLLOW(B)中中;

43、如果如果= (即即 FIRST()），则把），则把FOLLOW(A)加至加至FOLLOW(B)中。中。(3)反复使用反复使用(2)直至每个非终结符的直至每个非终结符的FOLLOW集不再集不再增大为止。增大为止。*49nFOLLOW(E)= ) ，# nFOLLOW(E)=FOLLOW(E) = ) ，#nFOLLOW(T)= (FIRST(E)-) FOLLOW(E) FOLLOW(E)= +， ) ， #nFOLLOW(T)=FOLLOW(T)= +， ) ， #nFOLLOW(F)= (FIRST(T)-) FOLLOW(T) FOLLOW(T)= +，*，)， #表达式文法表达式文法nF

44、IRST(E)= (, i nFIRST(E)=+, nFIRST(T)= (, i nFIRST(T)=*, nFIRST(F)=(, i E T E 否否E + T E| 是是T F T 否否T* F T 是是F ( E )i 否否(1)(1)对于文法的开始符号对于文法的开始符号S S，置，置# #于于FOLLOW(S)FOLLOW(S)中中(2)(2)若若B B是一个产生式，是一个产生式，则把则把FIRST()FIRST()的非空元素的非空元素加加至至FOLLOW(B)FOLLOW(B)中，中，如果如果= ( (即即 FIRST()FIRST()），则把），则把FOLLOWFOLLOW（

45、A A）加至）加至FOLLOWFOLLOW（B B）中。）中。n文法文法Gs: nS-MH|anH-LSo|nK-dML|nL-eHfnM-K|bLMn根据定义求解根据定义求解nFollow(S)=o, #nFollow(H)=Follow (S) f=f, o, #nFollow(K)=Follow(M)=e, o, #nFollwo(L)= (First(So)-) Follow(K) (First(M)-) Follow(M)= a, b, d, e, o, # nFollow(M)= (First(H)-) Follow(S) (First(L)-)= e, o, #例：求文法例：求文

46、法Gs每个非终结符的每个非终结符的Follow集集是是是是是是否否是是First(S)=a, b, d, e, First(H)=e, First(K)=d, First(L)= eFirst(M)=b, d, 51nE+TE| SELECT(E+TE)=FIRST(+TE)=+SELECT(E )=FOLLOW(E)=) ,nT*FT| SELECT(T*FT)=FIRST(*FT)=*SELECT(T )=FOLLOW(T)=+，)，nF(E)|iSELECT(F(E)=FIRST(E)=(SELECT(Fi)=FIRST(i)=i关于同一非终结符的不同产生式的关于同一非终结符的不同产生式

47、的SELECT集合交集为空集合交集为空结论结论：GE是是LL（1）文法）文法4)计算计算SELECT集集nFIRST(E)= (, i nFIRST(E)=+, nFIRST(T)= (, i nFIRST(T)=*, nFIRST(F)=(, i nFOLLOW(E)= ),# nFOLLOW(E)=),#nFOLLOW(T)=+, ),# nFOLLOW(T)=+,),#nFOLLOW(F)=+,*,),# n给定上下文无关文法的产生式给定上下文无关文法的产生式A ，AVN， V*，若，若 = * ，则则SELECT(A )= FIRST( )。n如果如果 = * ，则，则 SELECT(

48、A )=(FIRST( )-)FOLLOW(A)求文法求文法Gs的的Select集并判定是否为集并判定是否为LL(1)文法文法n文法文法Gs: nS-MH|anH-LSo|nK-dML|nL-eHfnM-K|bLM52First(S)=a, b, d, e, First(H)=e, First(K)=d, First(L)= eFirst(M)=b, d, Follow(S)=o, #Follow(H)=f, o, #Follow(K)=e, o, #First(L)=a, b, d, e, o, # Follow(M)= e, o, #是是是是是是否否是是?YES！53n关系图法求关系图法求

49、FIRST集、集、FOLLOW集（略）集（略）54例文法例文法: SAB|bC Ab| BaD| CAD|b DaS|c 判断其是否为判断其是否为LL(1)文法文法n求求FIRST集集FIRST(S)= (FIRST(A)-)FIRST(B)-)b= a,b,FIRST(A)= b, FIRST(B)= a, FIRST(C)= a,b,cFIRST(D)= a,c此时是否能够得此时是否能够得到结论？到结论？55文法文法 SAB|bC Ab| BaD| CAD|b DaS|cn求求FOLLOW集集FOLLOW(S)=#FOLLOW(D) = (First(B)-)(First(D)-)FOLL

50、OW(S) = a, c FOLLOW(S) = FOLLOW(B)=FOLLOW(S) = FOLLOW(C)=FOLLOW(S) = FOLLOW(D)=FOLLOW(B)FOLLOW(C) = FIRST(B)= a, FIRST(D)= a,c#a, c, #FOLLOW(A)= 56n求求SELECT集合集合SAB|bCSELECT(SAB)=(FIRST(AB)-)FOLLOW(S)=a, b, #SELECT(SbC)=FIRST(bC)=b 交集不为空交集不为空Ab|SELECT(Ab)=FIRST(b)=bSELECT(A)= )=(FIRST()-)FOLLOW(A)=a,

51、 c, #文法文法 SAB|bC Ab| BaD| CAD|b DaS|c57BaD| SELECT(BaD)=FIRST(aD)=aSELECT(B )=)=(FIRST()-)FOLLOW(B)=#CAD|bSELECT(CAD)=FIRST(AD)=a, b, cSELECT(Cb)=FIRST(b)=b 交集不为空交集不为空DaS|cSELECT(DaS)=FIRST(aS)=aSELECT(Dc)=FIRST(c)=c判定：判定：结论：结论：GSGS不是不是LL(1)LL(1)文法文法文法文法 SAB|bC Ab| BaD| CAD|b DaS|c58典型例题及解答典型例题及解答n给

52、定一文法，进行改写后判定是否为给定一文法，进行改写后判定是否为LL(1)nP97 例例2nP98 例例3n通常将非终结符的通常将非终结符的FIRST集集FOLLOW集表集表示在一张表中（例如示在一张表中（例如P96表表5.5）n作业：作业：P101.7，选做其一，选做其一595.5 5.5 确定的自顶向下分析方法确定的自顶向下分析方法n递归子程序法（预测分析）递归子程序法（预测分析）n分析高效（线性时间）、容易实现（方便手工编码）、错误定位和诊断信息准确、被很多开源和商业的编译器所采用nGCC 4.0， LLVM，n表驱动的预测分析方法表驱动的预测分析方法n分析高效（线性时间）、错误定位和诊断

53、信息准确、有很多开源或商业的生成工具nANTLR， n前提：前提：文法为文法为LL(1)文法文法60递归子程序法递归子程序法n实现思想实现思想n对每个非终符按其产生式结构产生相应语法对每个非终符按其产生式结构产生相应语法分析子程序；分析子程序；终结符产生匹配命令，而非终终结符产生匹配命令，而非终结符则产生调用命令。结符则产生调用命令。因为文法递归相应子因为文法递归相应子程序也递归，所以称这种方法为递归子程序程序也递归，所以称这种方法为递归子程序法（递归下降分析方法）。法（递归下降分析方法）。61n当产生式形如当产生式形如: A-1|2| : A-1|2| |n|n则按下面的方法编写子程序则按下

54、面的方法编写子程序A A：（：（PascalPascal风格）风格） nprocedure A( )procedure A( )begin if begin if tokenSelect(A-1)tokenSelect(A-1) then then (1)(1) else else if if tokenSelect(A-2)tokenSelect(A-2) then then (2)(2) else else if if tokenSelect(A-n)tokenSelect(A-n) then (n)then (n) else else err( ) err( ) endendn其中对其中

55、对i=X1X2i=X1X2XnXn， (i) = (i) = (X1);(X1);(X2);(X2);(Xn);(Xn);n如果如果XVXVN N，(X)= X(); (X)= X(); n如果如果XVXVT T，(X)= Match(X) (X)= Match(X) （若匹配，则（若匹配，则MatchMatch中应包含向前读一输入符号的动作，也有的书中写为：中应包含向前读一输入符号的动作，也有的书中写为：advance()advance()或或nextsym()nextsym()）n如果如果X= ,() = skip(X= ,() = skip(空语句空语句) )递归子程序法递归子程序法62

56、递归子程序法递归子程序法n例：例：1）假设有文法）假设有文法nZ a B anB b B | cnSelect(ZaBa)=a, Select(BbB)=b, SelectBc=c则相应的递归子程序可如下：则相应的递归子程序可如下：63procedure Z( ) procedure Z( ) /Z a B a/Z a B abegin begin if token=a then Match(a) if token=a then Match(a)；/ReadToken/ReadToken B B（）；（）； Match(a)Match(a)； else err( )else err( )；en

57、d;end;procedure B ( ) procedure B ( ) / B b B | c/ B b B | cbeginbegin if token = b then Match(b); if token = b then Match(b);/ReadToken/ReadToken B B（）（）; ;else if token = c then Match(c);else if token = c then Match(c); else err( )else err( )end;end;语法分析主程序：语法分析主程序：Begin Begin ReadToken; Z() ReadT

58、oken; Z()； IF tokenIF token # # THEN THEN err()err() End EndZ a B aB b B | cn对输入串对输入串abbbbbbbbbbbbca#的递的递归下降分析归下降分析match(a);B();match(a);abbbbbbbbbbbbca64n例：例：2）文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : PROCEDURE E( )BEGIN T()；E ()ENDPROCEDURE E ( )BEGIN IF token=+ THE

59、N BEGIN ADVANCE()； T()；E () END /否则认为与否则认为与 匹配匹配END65PROCEDURE T()BEGIN F()；T ()ENDn例：例：2）文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归下降子程序为对应的递归下降子程序为: : PROCEDURE T ()BEGIN IF token=* THEN BEGIN ADVANCE()； F()；T () END/否则认为与否则认为与 匹配匹配END66n例：例：2）文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) |

60、 in对应的递归对应的递归下降子程序为下降子程序为: : PROCEDURE F()BEGIN IF token=i THEN ADVANCE() ELSE IF token=( THEN BEGIN ADVANCE(); E()； IF token=) THEN ADVANCE() ELSE ERR() END ELSE ERR()END67n例：例：2）文法文法G(E):G(E):ETE E +TE | TFT T *FT | F(E) | in对应的递归对应的递归下降子程序为下降子程序为: : 主程序主程序: :PROGRAM PARSER()BEGIN ADVANCE(); E();