1、编译原理与技术编译原理与技术第第4章章 自顶向下的语法分析自顶向下的语法分析 编译原理与技术编译原理与技术2主要内容主要内容u自顶向下语法分析概述自顶向下语法分析概述 uLL(1)文法文法u递归下降分析技术递归下降分析技术 u预测分析技术预测分析技术uLL(1)分析中的错误处理分析中的错误处理 编译原理与技术编译原理与技术34.1 自顶向下语法分析的一般方法自顶向下语法分析的一般方法u基本思想：基本思想：对任何输入串，试图用一切可能的办法，从对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下，从左到右地文法开始符号出发，自上而下，从左到右地为输入串建立分析树。或者说，为输入串寻为
2、输入串建立分析树。或者说，为输入串寻找最左推导。找最左推导。u特点：特点：本质上是一种试探过程，反复使用不同的产本质上是一种试探过程，反复使用不同的产生式谋求匹配输入串。生式谋求匹配输入串。编译原理与技术编译原理与技术4例例4.1：设文法设文法GS：ScAd，Aab|a，输入串为，输入串为cad，自，自顶向下进行语法分析，并构造相应语法树。顶向下进行语法分析，并构造相应语法树。4.1 自顶向下语法分析的一般方法自顶向下语法分析的一般方法先按文法的开始符号产生根结点S，选择S惟一的产生式构造语法树，如图4.1(a)所示。把S的子结点从左到右与输入串中的字符相比较，第一个子结点c匹配输入串第一个符
3、号。第二个子结点是非终结符A，要选择A的产生式进一步构造。而A有两个候选式，先选择Aab构造语法树，如图4.1(b)所示。(a)(b)(c)图4.1 输入串cad的语法分析树编译原理与技术编译原理与技术5 此时A的最左子结点a匹配输入串第二个符号。而A的第二个子结点b和输入串第三个符号不一致，说明A的这个产生式不能用来产生该输入串。这就需要回到子结点A，选用另一个产生式Aa来构造语法树，如图4.1(c)所示。这种回头选用其他产生式的过程称为回溯。回溯时，要把由前面产生式Aab得到的子树删除，并重新读入在子结点A处的当时符号a。用新的产生式构造语法树后，A的子结点为a，与当前符号一致，读入最后一
4、个输入符号d。此时结点A完成匹配，它的右边是结点d，与当前符号一致。这样就完成了输入串的匹配，说明输入串cad是该文法的一个句子。上面的分析同时也给出了输入串cad的最左推导过程：S cAd cad。4.1 自顶向下语法分析的一般方法自顶向下语法分析的一般方法(a)(b)(c)编译原理与技术编译原理与技术6u这种一般方法存在一些问题：这种一般方法存在一些问题：(1)左递归问题左递归问题 自顶向下分析采取最左推导，文法中含有左递归会使自顶向下分析采取最左推导，文法中含有左递归会使自上而下的分析过程陷入无限循环。因此，必须消除文自上而下的分析过程陷入无限循环。因此，必须消除文法的左递归。法的左递归
5、。(2)回溯问题回溯问题 反复寻找可正确匹配的产生式时可能需要不断回溯，反复寻找可正确匹配的产生式时可能需要不断回溯，虚假匹配现象需要使用更复杂的回溯技术。这样将会产虚假匹配现象需要使用更复杂的回溯技术。这样将会产生许多额外工作，因此应设法消除回溯。生许多额外工作，因此应设法消除回溯。4.1 自顶向下语法分析的一般方法自顶向下语法分析的一般方法编译原理与技术编译原理与技术7(3)出错处理出错处理 分析不成功时，要确定出错的具体位置比较困难。分析不成功时，要确定出错的具体位置比较困难。(4)效率问题效率问题 这种带回溯的自顶向下方法实际上是一种穷尽一切可这种带回溯的自顶向下方法实际上是一种穷尽一
6、切可能的试探法，因此效率很低，代价较高，从而该方法只能的试探法，因此效率很低，代价较高，从而该方法只有理论意义，在实际应用中价值不大。有理论意义，在实际应用中价值不大。4.1 自顶向下语法分析的一般方法自顶向下语法分析的一般方法编译原理与技术编译原理与技术84.2 LL(1)文法文法要实现无回溯的自顶向下语法分析，对相应文法要实现无回溯的自顶向下语法分析，对相应文法必须要有一定的限制。首先，文法应该不含左递必须要有一定的限制。首先，文法应该不含左递归，若文法中含有左递归，则需使用文法的等价归，若文法中含有左递归，则需使用文法的等价变换消除左递归。其次，还要消除回溯。变换消除左递归。其次，还要消
7、除回溯。通过提取左因子消除某些文法的回溯，为什么？通过提取左因子消除某些文法的回溯，为什么？没有左递归和左因子的文法是否一定可以进行确没有左递归和左因子的文法是否一定可以进行确定的自顶向下分析？定的自顶向下分析？编译原理与技术编译原理与技术9u首符集首符集FIRST4.2 LL(1)文法文法例例4.2：文法文法G1S:SpA|qB AcAd|a BdB|bw1=pccadd自顶向下的推导过程：S pA pcAd pccAdd pccadd语法树：ddSpASpAcA dSpAcA dcA dSpAcAcAa编译原理与技术编译原理与技术104.2 LL(1)文法文法文法文法G1S:SpA|qB
8、AcAd|a BdB|b这个文法的特点：这个文法的特点：每个产生式的右部都由终结每个产生式的右部都由终结符号开始。符号开始。如果两个产生式有相同的左如果两个产生式有相同的左部，那么它们的右部由不同部，那么它们的右部由不同的终结符开始。的终结符开始。对于这样的文法，分析输入串时，可以跟据输入串的当前符号确定选取产生式。比如w1=pccadd，第一个符号是p，而从开始符号S出发，只有选择产生式SpA推导，才能出现符号p。同样，要出现第二个符号c，必须选择产生式AcAd。这样，虽然具有相同左部的产生式不只一个，但文法的特点决定了每一步推导只能选择惟一的产生式，从而可以避免回溯。编译原理与技术编译原理
9、与技术114.2 LL(1)文法文法 例例4.3：文法文法G2S:SAa|Bb Aa|cA Bb|dBw2=ccaa自顶向下的推导过程：S Aa cAa ccAa ccaa语法树：SAaSAacASAacAcASAacAcAa编译原理与技术编译原理与技术124.2 LL(1)文法文法文法文法G2S:SAa|Bb Aa|cA Bb|dB这个文法的特点：这个文法的特点：每个产生式的右部不全是由每个产生式的右部不全是由终结符号开始。终结符号开始。如果两个产生式有相同的左如果两个产生式有相同的左部，那么它们的右部由不同部，那么它们的右部由不同的终结符或非终结符开始。的终结符或非终结符开始。文法中无空产
10、生式。文法中无空产生式。对于这样的文法，分析输入串时，也可以跟据输入串的当前符号确定地选取产生式。比如推导w2=ccaa时，首先考虑开始符号S，它可以推出以A或B开头的符号串。而由以A和B为左部的产生式可知，A只能推出以a,c开头的符号串，B只能推出以b,d开头的符号串。因此，要得到w2的第一个符号c，只有选择产生式SAa，AcA。同样，要出现第二个符号c，仍需选择产生式AcA，没有别的选择。这样，文法的特点决定了每一步推导只能选择确定的产生式，从而可以避免回溯。编译原理与技术编译原理与技术13由上面两个例子可知，一个文法在推导过程中是否会产由上面两个例子可知，一个文法在推导过程中是否会产生回
11、溯，与文法中具有相同左部的每个产生式右部所能生回溯，与文法中具有相同左部的每个产生式右部所能推出的开头符号有关系。推出的开头符号有关系。定义定义4.1:设设G=(VN,VT,P,S)是上下文无关文法，对于是上下文无关文法，对于V*，V=VNVT，定义首符集，定义首符集FIRST()为为 FIRST()=a|,aVT,V*即即 FIRST()=a|a,aVT,V*特别地，若特别地，若 ，则规定，则规定FIRST()，即，即FIRST()是是能推导出的所有在开头位置的终结符或空符。能推导出的所有在开头位置的终结符或空符。4.2 LL(1)文法文法编译原理与技术编译原理与技术144.2 LL(1)文
12、法文法 由此我们可以看出，如果文法中不含空符产生式，并由此我们可以看出，如果文法中不含空符产生式，并且每个非终结符的所有候选式右部的首符集两两不相交，且每个非终结符的所有候选式右部的首符集两两不相交，则推导中就不会产生回溯。而提取左因子正是为了达到则推导中就不会产生回溯。而提取左因子正是为了达到这个目的，即反复提取左因子后，就能够把每个非终结这个目的，即反复提取左因子后，就能够把每个非终结符（包括新引进的非终结符）的所有候选首符集变成两符（包括新引进的非终结符）的所有候选首符集变成两两不相交。因此，提取左因子可以使得不含空符产生式两不相交。因此，提取左因子可以使得不含空符产生式的文法消除回溯。
13、的文法消除回溯。编译原理与技术编译原理与技术154.2 LL(1)文法文法u后继符集后继符集FOLLOW例例4.4：文法文法G3S:SAa|Bb Aa|cA|Bb|dB输入串w3=cca自顶向下的推导过程为：S Aa cAa ccAa cca G3与例4.3中文法G2惟一不同之处在于，G3中非终结符A的候选式中含有空符产生式。分析时，对于输入串w3的前两个符号cc，可以确定使用产生式AcA，而要得到第三个符号a，按照a所在的首符集我们应该选择产生式Aa，但是显然这种选择是错误的，因为这样得到的是符号串ccaa而不是cca。实际上，这时正确的选择是产生式A，也就是让A自动匹配到空符，就可以得到与
14、输入串匹配的符号串cca。编译原理与技术编译原理与技术164.2 LL(1)文法文法 这说明只要求文法每个非终结符的所有候选首符集两两不相交是不够的，还需要进一步讨论。观察上面例子可以看出，之所以会出现上述问题，是因为文法中含有空符产生式A，并且推导过程中A后面跟的终结符a恰好也是A的一个右部首符集中的符号。也就是说，a既能紧跟在A的后面出现，也能由A推出。这样，如果遇到当前非终结符是A而输入串中相应符号为a时，就不容易确定该用产生式A将A自动匹配空符得到紧跟其后的a，还是用产生式Aa推出a。文文法法G3S:SAa|Bb Aa|cA|Bb|dB编译原理与技术编译原理与技术17因此，一个文法能否
15、进行确定的自顶向下语法分析，不因此，一个文法能否进行确定的自顶向下语法分析，不仅仅与文法中具有相同左部的产生式右部的仅仅与文法中具有相同左部的产生式右部的FIRST集有集有关系，若有产生式右部可能推出关系，若有产生式右部可能推出，则还与其左部非终，则还与其左部非终结符的后继符号集合有关。结符的后继符号集合有关。定义定义4.2:设设G=(VN,VT,P,S)是上下文无关文法，对于是上下文无关文法，对于PVN，定义后继符集，定义后继符集FOLLOW(P)为为 FOLLOW(P)=a|S P 且且aFRIST(),VT*,V+即即 FOLLOW(P)=a|S Pa,aVT。特别地，若特别地，若S P
16、，则规定，则规定$FOLLOW(P)。即。即FOLLOW(P)是推导过程中所有可能紧跟在是推导过程中所有可能紧跟在P之后的终结之后的终结符或边界符号符或边界符号$（$用来界定输入串，表示为：用来界定输入串，表示为：$输入串输入串$）。4.2 LL(1)文法文法编译原理与技术编译原理与技术18 可以看出，开始符号S后面不会跟任何符号，但是有S S，因此FOLLOW(S)=$。非终结符A后面可能不跟任何符号，即S A，也可能跟开始符号S，而S推导的符号串只能以a,d开头，即FIRST(S)=a,d，因此FOLLOW(A)=a,d,$。4.2 LL(1)文法文法 例例4.5：文法文法G4S:SaA|
17、d AbAS|输入串w4=abd的推导过程为：S aA abAS abS abd编译原理与技术编译原理与技术19u一般地，文法中含有形如一般地，文法中含有形如P|，PVN，,V*的产的产生式时，若生式时，若,不能同时推导出空符，不妨设不能同时推导出空符，不妨设 ,，则当则当 FIRST()(FIRST()FOLLOW(P)=时，对于非终结符时，对于非终结符P可以确定地选取产生式。可以确定地选取产生式。4.2 LL(1)文法文法 比如例4.4中，产生式Aa|cA|，FOLLOW(A)=a,$，FIRST()=FIRST(a|cA)=a,c，FIRST()=FIRST()=，FIRST()(FIR
18、ST()FOLLOW(A)=a,ca,$=a 。因此不能确定选取产生式。而例4.5中，产生式AbAS|，FOLLOW(A)=a,d,$，FIRST()=FIRST(bAS)=b，FIRST()=FIRST()=，FIRST()(FIRST()FOLLOW(A)=ba,d,$=。因此可以确定选取产生式。编译原理与技术编译原理与技术20u选择集选择集SELECT 定义定义4.3:给定不含左递归的上下文无关文法的产生式给定不含左递归的上下文无关文法的产生式P,PVN,V*，定义选择集，定义选择集SELECT(P)为为 若若 ，则，则SELECT(P)=FIRST()若若 ，则，则SELECT(P)=
19、(FIRST()-)FOLLOW(P)也就是说，当文法中含有形如也就是说，当文法中含有形如P|（PVN，,V*,不同时能推出不同时能推出）的产生式时，能够使用确定）的产生式时，能够使用确定的自顶向下分析必须使文法满足的自顶向下分析必须使文法满足 SELECT(P)SELECT(P)=4.2 LL(1)文法文法编译原理与技术编译原理与技术21 比如，例4.5中 SELECT(SaA)=FIRST(aA)=a，SELECT(Sd)=FIRST(d)=d SELECT(AbAS)=FIRST(bAS)=b，SELECT(A)=(FIRST()-)FOLLOW(A)=a,d,$SELECT(SaA)S
20、ELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,$=因此，文法G4可以进行确定的自顶向下语法分析。4.2 LL(1)文法文法例例4.5：文文法法G4S:SaA|d AbAS|编译原理与技术编译原理与技术22uLL(1)文法文法 定义定义4.4:文法文法G是是LL(1)文法，当且仅当每个非终结符文法，当且仅当每个非终结符P的任何两个候选式的任何两个候选式P|（,V*）满足：）满足：不存在终结符不存在终结符a，使得，使得和和推出的符号串都能以推出的符号串都能以a开开头。即头。即FIRST()FIRST()=若若 ,，则，则所能推出的符号串的开头符号不在所能推出的符号
21、串的开头符号不在FOLLOW(P)中。即中。即FIRST()FOLLOW(P)=4.2 LL(1)文法文法编译原理与技术编译原理与技术234.2 LL(1)文法文法 由由SELECT集可以得到集可以得到LL(1)文法的另一个等价定义：文法的另一个等价定义：定义定义4.5:一个上下文无关文法是一个上下文无关文法是LL(1)文法，当其仅当对文法，当其仅当对于每个非终结符于每个非终结符P的任何两个候选式的任何两个候选式P|满足满足SELECT(P)SELECT(P)=其中其中PVN，,V*，且，且,不同时推出不同时推出。例例4.6：下面文法是否是下面文法是否是LL(1)文法？文法？（1）G1S:Sa
22、A|d AbAS|（2）G2S:SaAS|b AbA|编译原理与技术编译原理与技术244.2 LL(1)文法文法 解：用定义4.4判断（1）对于S aA|d，FIRST(aA)FIRST(d)=ad=；对于A bAS|，FIRST(bAS)FIRST()=b=；FIRST(bAS)=b，FOLLOW(A)=a,d,$，FIRST(bAS)FOLLOW(A)=ba,d,$=；因此文法G1满足条件,，由定义4.4知该文法是LL(1)文法。（2）对于S aA|b，FIRST(aA)FIRST(b)=ab=，对于A bAS|，FIRST(bAS)FIRST()=b=，FIRST(bAS)=b，FOLL
23、OW(A)=a,b,$FIRST(bAS)FOLLOW(A)=ba,b,$=b。因此文法G2满足条件，但不满足条件，从而不是LL(1)文法。编译原理与技术编译原理与技术254.2 LL(1)文法文法 用定义4.5判断（1）SELECT(SaA)=FIRST(aA)=a SELECT(Sd)=FIRST(d)=d SELECT(AbAS)=FIRST(bAS)=b SELECT(A)=(FIRST()-)FOLLOW(A)=a,d,$所以 SELECT(SaA)SELECT(Sd)=ad=SELECT(AbAS)SELECT(A)=ba,d,$=由定义4.5知文法G1是LL(1)文法。（2）SE
24、LECT(SaAS)=FIRST(aAS)=a SELECT(Sb)=FIRST(b)=b SELECT(AbA)=FIRST(bA)=b SELECT(A)=(FIRST()-)FOLLOW(A)=a,b,$所以 SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b,$由定义4.5知文法G2不是LL(1)文法。编译原理与技术编译原理与技术264.2 LL(1)文法文法uLL(1)文法的特点文法的特点l没有左因子没有左因子l不是二义的不是二义的l不含左递归不含左递归 一个文法中若含有左递归和左因子，则它一定不是一个文法中若含有左递归和左因子，则
25、它一定不是LL(1)LL(1)文法，也就不可能用确定的自顶向下分析法。然而，某些文法，也就不可能用确定的自顶向下分析法。然而，某些含有左递归和左因子的文法可以通过等价变换，消除左递含有左递归和左因子的文法可以通过等价变换，消除左递归和左因子后可能变为归和左因子后可能变为LL(1)LL(1)文法，不过仍需要用文法，不过仍需要用LL(1)LL(1)文文法的定义加以判别。也就是说，文法中不含左递归和左因法的定义加以判别。也就是说，文法中不含左递归和左因子只是子只是LL(1)LL(1)文法的必要条件。文法的必要条件。编译原理与技术编译原理与技术274.3 递归下降分析技术递归下降分析技术u基本思想基本
26、思想为文法中每个非终结符编写一个递归过程，为文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，串，当某非终结符的产生式有多个候选式时，按按LL(1)形式唯一确定选择哪个候选式进行推形式唯一确定选择哪个候选式进行推导，若遇到某候选式为导，若遇到某候选式为，认为其自动匹配。，认为其自动匹配。把这些把这些递归过程组合起来就构成了文法的递递归过程组合起来就构成了文法的递归下降分析程序。归下降分析程序。编译原理与技术编译原理与技术284.3 递归下降分析技术递归下降分析技术u递归下降分析器的设计递归下降
27、分析器的设计 设设LL(1)文法文法G=(VN，VT，P，S)，VN=X1，X2，Xn。对。对G的每个非终结符号的每个非终结符号Xi，可以，可以按照下面方法设计子程序按照下面方法设计子程序Pi()：（1）对于形如）对于形如Xi 1|2|m 的产生式，在相应子程的产生式，在相应子程序序Pi()中，应该能够判断当前输入符号中，应该能够判断当前输入符号a属于哪个候选式属于哪个候选式j 的的FIRST集，并转入该候选式相应代码段，继续识别。集，并转入该候选式相应代码段，继续识别。对候选式的选择可用对候选式的选择可用if语句或语句或case语句实现。语句实现。编译原理与技术编译原理与技术294.3 递归
28、下降分析技术递归下降分析技术 （2）对于形如）对于形如XiY1Y2Yk（YjVNVT）的产生式，）的产生式，相应子程相应子程Pi()是一个依次识别其右部各符号是一个依次识别其右部各符号Yj（j=1,2,k）的过程：如果）的过程：如果YjVT，则判断当前输入符，则判断当前输入符号是否与号是否与Yj匹配；若匹配；若YjVN则应有调用相应于则应有调用相应于Yj的子程的子程序的代码。序的代码。（3）对于形如）对于形如Xi的产生式，在相应的子程序的产生式，在相应的子程序Pi()中，中，应该能够判断当前输入符号应该能够判断当前输入符号a是否属于集合是否属于集合FOLLOW(Xi)，从而决定是从，从而决定是
29、从Pi()返回还是报错。返回还是报错。（4）在各个子程序）在各个子程序Pi()中，均应含有进行语法检查的代中，均应含有进行语法检查的代码。码。编译原理与技术编译原理与技术304.3 递归下降分析技术递归下降分析技术 例例4.8：下面文法产生下面文法产生Pascal类型的子集，我们用类型的子集，我们用dotdot表表示示“.”，以强调这个字符序列作为一个词法单元。，以强调这个字符序列作为一个词法单元。type simple|id|array simple of type simple integer|char|num dotdot num 显然该文法是显然该文法是LL(1)文法，为其构造递归下降
30、分析器。文法，为其构造递归下降分析器。编译原理与技术编译原理与技术314.3 递归下降分析技术递归下降分析技术 使用类Pascal语言为非终结符type设计子程序如下：proccdure type;begin case lookahead of in integer,char,num:simple():begin match();match(id)end array:begin match(array);match();simple();match();match(of);type()end other error()end caseend;编译原理与技术编译原理与技术324.3 递归下降分析
31、技术递归下降分析技术 在这段代码中，使用变量lookahead来存放向前查看的单词符号，根据该单词符号的不同而选择不同的动作。具体来说，如果lookaheadFIRST(simple)=integer,char,num，则转入simple子程序；如果当前单词符号为，则调用匹配函数match，检查是否匹配，若匹配则读入下一个单词符号，存放到变量lookahead中，然后继续调用匹配函数match，检查当前符号是否与match函数的参数id匹配，若匹配则意味着可以选取产生式type id；如果当前单词为array，则依次执行以下操作：匹配array，匹配 ，调用simple子程序，匹配 ，匹配of
32、，递归调用type子程序；如果lookahead中的单词符号不是上述符号，则调用出错处理函数error。编译原理与技术编译原理与技术334.3 递归下降分析技术递归下降分析技术 我们用nexttoken作为读取下一个单词符号的函数，则match函数的设计如下：procedure match(t:token);begin if lookahead=t then lookahead:=nexttoken()else error()end if end;编译原理与技术编译原理与技术344.3 递归下降分析技术递归下降分析技术 类似地，给出非终结符simple的子程序如下：procedure simp
33、le;begin case lookahead of integer:match(integer)char:match(char)num:begin match(num);match(dotdot);match(num)end other error()end caseend;编译原理与技术编译原理与技术354.3 递归下降分析技术递归下降分析技术 这样，我们得到了两个非终结符的子程序，递归下降分析的主程序设计就比较简单了。首先需要读入一个单词符号，然后调用开始符号的子程序，让其自动递归下降进行子过程调用。当所有调用结束，最终回到主程序时，判断是否到达输入串末尾，如果到达，则分析成功，否则出错
34、。我们用函数gettoken读入输入串第一个单词符号，则主程序伪代码如下：begin lookahead=gettoken();type();if lookahead=$exit;else error()end if end编译原理与技术编译原理与技术364.3 递归下降分析技术递归下降分析技术 将上面的各程序组合起来，就得到了该类型定义文法的递归下降分析器。现在使用该分析器分析输入串array integer of char，首先读入第一个单词array，然后调用开始符号type的子程序，依次进行下面操作：匹配array，读取下一符号 ；匹配 ，读取下一单词integer；调用simple的
35、子程序，匹配integer，读取下一符号 。返回type过程，继续进行下面操作：匹配 ，读取下一单词of；匹配of，读取下一单词char；递归调用type过程，因为char在integer,char,num中，所以调用simple过程，匹配char，读取下一符号，即输入串的结束符$。返回最近的type过程，结束操作，返回外层type过程，结束操作，返回主程序。此时变量lookahead中存放的是结束符$，因此该分析过程结束。说明该输入串符合Pascal类型定义。编译原理与技术编译原理与技术374.3 递归下降分析技术递归下降分析技术例例4.9：为下列表达式文法为下列表达式文法GE编写递归下降识
36、别编写递归下降识别程序。程序。E E+T|T T T*F|F F(E)|i解：步骤1：消除左递归：E TE E+TE|T FT T*FT|F(E)|i 步骤2：编写递归下降识别子程序，这里使用C语言形式。见下页图。编译原理与技术编译原理与技术38 编译原理与技术编译原理与技术394.3 递归下降分析技术递归下降分析技术 步骤3：编写递归下降识别主程序main()lookahead=getsymbol();E();if lookahead=$exit;else error();编译原理与技术编译原理与技术404.3 递归下降分析技术递归下降分析技术 使用该识别程序识别输入串：i*i+i，首先读入
37、符号i，然后调用子程序E，在E中调用子程序T，在T中调用子程序F，匹配i，读入下一符号*，子程序F调用完毕，回到T。在T中继续调用子程序T，匹配*，读入下一符号i。在T中继续调用子程序F，匹配i，读入下一符号+，回到子程序T。在T中递归调用子程序T，不执行任何操作返回T，进而返回T，进而返回E。在E中继续调用子程序E，匹配+，读入下一符号i，调用子程序T。在T中调用子程序F，匹配i，读入下一符号，为输入串结束符$，返回E。在E中递归调用E，不执行任何操作返回E，进而返回E。至此子程序E调用完毕，回到主程序，检查到达输入串末尾，从而识别成功。编译原理与技术编译原理与技术414.3 递归下降分析技
38、术递归下降分析技术 用花括号用花括号表示闭包运算表示闭包运算*。用用n0表示表示可任意重复可任意重复0到到n次，次，特别地，特别地，n0=0=。用方括号用方括号表示表示10，即表示即表示可以出现也可以不出现，等价于可以出现也可以不出现，等价于|。u扩充的巴科斯范式扩充的巴科斯范式EBNF 例例4.10：例例4.9的表达式文法用扩充的巴科斯范式表示为：的表达式文法用扩充的巴科斯范式表示为：E T+T T F*F F(E)|i与每个非终结符相对应的递归子程序的伪代码如下：与每个非终结符相对应的递归子程序的伪代码如下：编译原理与技术编译原理与技术42 编译原理与技术编译原理与技术434.3 递归下降
39、分析技术递归下降分析技术 使用该识别程序识别输入串：i*i+i。首先读入符号i，然后调用子程序E，在E中调用T，在T中调用F，匹配i，读入下一符号*，返回T。在T中匹配*，读入下一符号i；调用F，匹配i，读入下一符号+，返回T，返回E。在E中匹配+，读入下一符号i，调用T。在T中调用F，匹配i，读入下一符号，为输入串结束符$，返回T，返回E，返回主程序。检查到达输入串末尾，从而识别成功。显然，使用EBNF编写的递归子程序数量较少，分析过程也比较简单。但是需要注意的是，将BNF转化为EBNF通常不是一件很容易的事情。编译原理与技术编译原理与技术444.3 递归下降分析技术递归下降分析技术u递归下
40、降分析的特点递归下降分析的特点 优点优点 l实现思想简单明了，程序结构和语法规则有直接实现思想简单明了，程序结构和语法规则有直接的对应关系。的对应关系。l由于每个过程表示一个非终结符号的处理，添加由于每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。语义加工工作比较方便。l递归下降分析需要书写程序的语言支持递归调用，递归下降分析需要书写程序的语言支持递归调用，如果递归调用机制是高效的，那么分析程序也是如果递归调用机制是高效的，那么分析程序也是高效的。高效的。编译原理与技术编译原理与技术454.3 递归下降分析技术递归下降分析技术缺点缺点l递归下降分析对文法要求比较高，必须满足递归下降
41、分析对文法要求比较高，必须满足LL(1)文法。文法。当然在某些语言中个别产生式的推导当不满足当然在某些语言中个别产生式的推导当不满足LL(1)而满足而满足LL(2)时，也可以采用多向前扫描一时，也可以采用多向前扫描一个符号的办法。个符号的办法。l由于递归调用多，所以速度慢，占用空间多。由于递归调用多，所以速度慢，占用空间多。尽管如此，递归下降分析方法仍是许多程序语言尽管如此，递归下降分析方法仍是许多程序语言（例如（例如PASCAL，C等编译系统）常常采用的语法分析等编译系统）常常采用的语法分析方法。方法。编译原理与技术编译原理与技术464.4 预测分析技术预测分析技术 u预测分析程序的工作过程
42、预测分析程序的工作过程 一个预测分析器由预测分析程序一个预测分析器由预测分析程序(总控程序总控程序)、先进后出栈先进后出栈(STACK)、预测分析表三个部分组、预测分析表三个部分组成，其中只有预测分析表与文法有关，它是一成，其中只有预测分析表与文法有关，它是一个二维矩阵，存放非终结符个二维矩阵，存放非终结符X面临输入符号面临输入符号a时时应选择的产生式，一般用应选择的产生式，一般用MX,a表示，是预测表示，是预测分析程序分析时的主要依据。分析程序分析时的主要依据。编译原理与技术编译原理与技术474.4 预测分析技术预测分析技术 图4.2 预测分析器模型编译原理与技术编译原理与技术484.4 预
43、测分析技术预测分析技术预测分析程序开始时，将预测分析程序开始时，将$置入置入STACK栈，将开始符栈，将开始符号号S置入置入STACK栈，将第一个输入符号读入栈，将第一个输入符号读入a，将栈，将栈顶符号读入顶符号读入X。总控程序执行下面四种动作之一。总控程序执行下面四种动作之一。（1）推导推导 若若XVN，并且，并且MX,a中存有产生式中存有产生式X X1X2Xk，则，则X 出栈，出栈，X1,X2,Xk反序置入反序置入STACK栈栈（X 时直接将时直接将X出栈即可）；出栈即可）；（2）匹配）匹配 若若X=a$，则，则X出栈，把下一输入符号读入出栈，把下一输入符号读入a。（3）接受）接受 若若X
44、=a=$，则分析成功，停止分析过程。，则分析成功，停止分析过程。（4）出错）出错 若若XVT，但，但Xa，或者若，或者若XVN，但，但MX,a 中中存放出错标记存放出错标记error，则报告出错。，则报告出错。编译原理与技术编译原理与技术494.4 预测分析技术预测分析技术 预测分析程序工作示意图 编译原理与技术编译原理与技术504.4 预测分析技术预测分析技术算法4.1 非递归的预测分析输入：输入串w和文法GS的分析表M输出：如果wL(G),输出w的最左推导，否则报告错误。$S进栈,S在栈顶,w$在输入缓冲区,ip指向w$的第一个符号;/准备工作flag:=true /flag作为控制标记w
45、hile flag do 令X等于栈顶符号,a等于ip指向的符号;if XVN then do if MX,a=X Y1Y2 Yk then do 从栈中弹出X;把Yk,Yk1,Y1依次压入栈,Y1在栈顶;输出产生式X Y1Y2 Yk else error()/报告错误 else if X=a then do if X=$then flag:=false /结束循环 else 把X从栈顶弹出,ip指向下一符号 else error()end while;编译原理与技术编译原理与技术514.4 预测分析技术预测分析技术u预测分析表的构造预测分析表的构造 构造构造FIRST集集 首先求出文法中每个
46、文法符号的首符集，即为首先求出文法中每个文法符号的首符集，即为XVTVN构造构造FIRST(X)。方法如下：。方法如下：l若若XVT，则，则FIRST(X)=X；l若若XVN，且有产生式，且有产生式X a，则，则FIRST(X)=FIRST(X)a。特别地，若有产生式特别地，若有产生式X，则，则FIRST(X)=FIRST(X)；编译原理与技术编译原理与技术524.4 预测分析技术预测分析技术l若若XVN，且有产生式，且有产生式X Y1Y2Yk，(i=1,2,k)，则，则 若若 1ik，使得使得FIRST(Yj)，(j=1,2,i-1)，即，即Y1Y2Yi-1，则，则FIRST(X)=FIRS
47、T(X)(FIRST(Yj)-)；若若 1ik，都有都有FIRST(Yj)，则，则FIRST(X)=FIRST(X)l反复利用以上规则，直到反复利用以上规则，直到FIRST(X)不再增大为止。不再增大为止。然后求符号串然后求符号串 的首符集的首符集FIRST()，算法如下：，算法如下：编译原理与技术编译原理与技术534.4 预测分析技术预测分析技术算法4.2 求符号串的首符集FIRST()输入：文法G,符号串=X1X2Xn及FIRST(Xi),其中Xi(VNVT),1i n输出：首符集FIRST()FIRST()=,k=0for i=1 to n do if FIRST(Xi)then 置FI
48、RST()=FIRST()(FIRST(Xi)-)且 k=k+1 else 置FIRST()=FIRST()FIRST(Xi)结束循环end for；if k=n then 置FIRST()=FIRST()编译原理与技术编译原理与技术544.4 预测分析技术预测分析技术例例4.11：文法文法GS:S AB|bC A b|B aD|CAD|b D aS|c 各非终结符的首符集为：FIRST(D)=a,c FIRST(B)=a,FIRST(A)=b,FIRST(C)=(FIRST(A)-)FIRST(D)b=a,b,c FIRST(S)=(FIRST(A)-)(FIRST(B)-)b =a,b,符
49、号串AB的首符集为：FIRST(AB)=(FIRST(A)-)(FIRST(B)-)=a,b,考虑产生式SAB|bC，因为 FIRST(AB)FIRST(bC)=a,b,b，由定义4.6可知，该文法不是LL(1)文法。编译原理与技术编译原理与技术554.4 预测分析技术预测分析技术构造构造FOLLOW集集l若若P是文法开始符号，则是文法开始符号，则FOLLOW(P)=$；l若有产生式若有产生式PQ，则，则FOLLOW(Q)=FOLLOW(Q)(FIRST()-)l若有产生式若有产生式PQ，或者有产生式，或者有产生式PQ而而，即，即FIRST()，则，则FOLLOW(Q)=FOLLOW(Q)FO
50、LLOW(P)l反复使用上面规则，直到每个反复使用上面规则，直到每个FOLLOW集不再增大为止。集不再增大为止。编译原理与技术编译原理与技术564.4 预测分析技术预测分析技术算法4.3 求非终结符后继集FOLLOW输入：文法GS及FIRST(X),所有X(VNVT)输出：所有非终结符的后继集FOLLOWFOLLOW(S)=$FOLLOW(P)=,所有PVN,PSfor 每一个产生式 do if 该产生式形如PQ then 置 FOLLOW(Q)=FOLLOW(Q)(FIRST()-)if then 置FOLLOW(Q)=FOLLOW(Q)FOLLOW(P)if 该产生式形如PQ then 置
