第4章 自顶向下的语法分析.

1、第第4 4章自顶向下的语法分析章自顶向下的语法分析12 语法分析是在词法分析识别出的单语法分析是在词法分析识别出的单词符号串的基础上，词符号串的基础上，分析并判定句子的分析并判定句子的语法结构是否符合语法规则语法结构是否符合语法规则。 3 自顶向下分析法就是从文法的开始自顶向下分析法就是从文法的开始符号出发，不断建立直接推导，试图构符号出发，不断建立直接推导，试图构造一个造一个最左推导序列最左推导序列，最终由它推导出，最终由它推导出与输入符号串完全匹配（相同）的句子。与输入符号串完全匹配（相同）的句子。 从语法树的角度看，自顶向下分析从语法树的角度看，自顶向下分析法就是以开始符号为根节点，试图

2、向下法就是以开始符号为根节点，试图向下构造一棵语法树，其端末结符号串与输构造一棵语法树，其端末结符号串与输入符号串相同。入符号串相同。4.1 左递归左递归与回溯与回溯45 为了得到一个符号串的最左推导，为了得到一个符号串的最左推导，需要对每一步应使用的产生式进行判断，需要对每一步应使用的产生式进行判断，即反复使用有关产生式的各个候选式进即反复使用有关产生式的各个候选式进行行试探试探，以便找到应该使用的产生式。，以便找到应该使用的产生式。 分析中出现的问题分析中出现的问题1：左：左递归问题递归问题6 若若采用自顶向下的语法分析，应消除采用自顶向下的语法分析，应消除文法中存在的左递归。文法中存在的

3、左递归。 因为左递归的存在，有可能使推导不因为左递归的存在，有可能使推导不能结束，分析陷入循环状态。能结束，分析陷入循环状态。 例如：例如：A Aa | b7 从各种可能的选择中随机挑选一种，从各种可能的选择中随机挑选一种，并希望它是正确的。并希望它是正确的。 如果以后发现它是错误的，必须退如果以后发现它是错误的，必须退回去，再试另外的选择这种方式称为回去，再试另外的选择这种方式称为回回溯溯。 回溯代价极高，效率很低。回溯代价极高，效率很低。分析中出现的问题分析中出现的问题2：回溯问题：回溯问题8 从从文法的开始符号出发，如何根据当前文法的开始符号出发，如何根据当前的输入符号（单词符号）的输入

4、符号（单词符号）唯一唯一地确定选用哪地确定选用哪个产生式替换相应非终结符往下推导，或构个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。造一棵相应的语法树。 在在自上而下的分析方法中如何选择使自上而下的分析方法中如何选择使用哪个产生式进行推导？用哪个产生式进行推导？ 假定假定要被替换的最左非终结符号是要被替换的最左非终结符号是B，且有且有n条规则：条规则：BA1|A2|An，那么如何，那么如何确定用哪个右部去替代确定用哪个右部去替代B？4.2 FIRST和和FOLLOW集合的构造集合的构造9例例1:输入输入串串w=pccadd是否是合法的句子？是否是合法的句子？10 G：SpA|qB

5、AcAd|a BdB|b总结：本题中对于一个非终结符，存在若干总结：本题中对于一个非终结符，存在若干个候选式，即产生式形如：个候选式，即产生式形如：P1|2|n 每个候选式的第一个字符都是终结符，每个候选式的第一个字符都是终结符，且都不相同。这时可直接选用与当前输入符且都不相同。这时可直接选用与当前输入符号相同的那个候选式来替换号相同的那个候选式来替换P。 S=pA=pcAd=pccAdd=pccadd例例2：输入输入串串w=ccap是否是合法的句子？是否是合法的句子？11 G：SAp|Bp Aa|cA Bb|dBS=Ap=cAp=ccAp=ccap总结：本题不像上题选用产生式那样直观。总结：

6、本题不像上题选用产生式那样直观。 关于关于S产生式的候选式都以非终结符开产生式的候选式都以非终结符开始，但它们可推导出的首字符集合不相交，始，但它们可推导出的首字符集合不相交，因而可根据当前的输入符号属于哪个候选因而可根据当前的输入符号属于哪个候选式的首字符集合而决定选择相应的候选式式的首字符集合而决定选择相应的候选式进行推导。进行推导。FIRST集集12FIRST集就是一个文法符号串的开始符号集合集就是一个文法符号串的开始符号集合。 设设G=（VT，VN，S，P）是上下文无关文法，）是上下文无关文法，FIRST()=a|=*a,aVT,v* 若若=* ，则规定，则规定 FIRST()。 FI

7、RST()是是的所有可能推导的开的所有可能推导的开头终结符或可能的头终结符或可能的。计算计算FIRST集集131.若若X V ,则则FIRST(X)=X；2.若若X VN，且有产生式，且有产生式Xa，则把，则把a加入到加入到FIRST(X)中；若中；若X也是一条产生式也是一条产生式,则把则把 也加到也加到FIRST(X)中。中。3.若若XY是一个产生式且是一个产生式且Y VN，则把，则把FIRST(Y)中中的所有非的所有非 元元素都加到素都加到FIRST(X)中；若中；若X Y1Y2YK 是一个产生式是一个产生式,Y1,Y2,Y(i-1)都是非终结符都是非终结符,而且而且,对于任何对于任何j,

8、1j i-1, FIRST(Yj)都含有都含有 (即即Y1.Y(i-1) =* ),则把则把FIRST(Yj)中的所有非中的所有非 元素都元素都加到加到FIRST(X)中；特别是中；特别是,若所有的若所有的FIRST(Yj , j=1,2,K)均含有均含有 ,则把则把 加到加到FRIST(X)中。中。 例例3：输入：输入串串w=abd是否是合法的句子？是否是合法的句子？14 G：SaA|d AbAS| 总结：本题中对于一个非终结符，存在若干总结：本题中对于一个非终结符，存在若干个候选式，并且其中含有个候选式，并且其中含有，即形如：，即形如：P1|2| ，情况更为复杂。，情况更为复杂。 因此，当

9、某一非终结符的候选式含有因此，当某一非终结符的候选式含有时，它的非空候选式的首字符集两两不相交，时，它的非空候选式的首字符集两两不相交，并与在推导过程中紧跟该非终结符可能出现并与在推导过程中紧跟该非终结符可能出现的终结符集也不相交，即可唯一确定要选用的终结符集也不相交，即可唯一确定要选用的候选式。的候选式。S=aA=abAS=abS=abdFOLLOW集集15 FOLLOW集就是一个文法符号的后跟集就是一个文法符号的后跟终结符号的集合。终结符号的集合。设设G=（VT，VN，S，P）是上下文无关文法，）是上下文无关文法，AVN，S是开始符号。是开始符号。FOLLOW(A)=a|S=*Aa，a V

10、T若有若有S=*A，则规定，则规定# FOLLOW(A)。 FOLLOW(A)是所有出现在紧接是所有出现在紧接A之后的终结符或之后的终结符或“#”。计算计算FOLLOW集集161.对于文法的开始符号对于文法的开始符号S，置，置#于于FOLLOW(S) 中；中；2.若若A B是一个产生是一个产生式，式， 则把则把 FIRST() 加至加至FOLLOW(B)中；中；3.若若A B是一个产生是一个产生式，式， 或或A B是一个产生式，而是一个产生式，而 =* ， 则则把把FOLLOW（A）加至）加至FOLLOW（B）中中17产生式产生式FIRST集集FOLLOW集集SeT|RTTDR|RdR|Da|

11、bd表表4-4 文法文法GS的的FIRST集和集和FOLLOW集集e,d,a,b, #a,b, #d, a,b, #a,bd, #求各个非终结符的求各个非终结符的FIRST集和集和FOLLOW集。集。对上述三例的总结对上述三例的总结18 当文法中含有形如：当文法中含有形如：A，A 的产生的产生式时，其中式时，其中A VN，,V*，当，当,不同时不同时推导出空时（推导出空时（* ,= * )，则当，则当 对于对于非终结符非终结符A的替换可的替换可唯一唯一确定候选。确定候选。 FIRST() FIRST()= FIRST() FOLLOW(A)=4.3 LL(1)文法文法19一、一、LL(1)文法

12、的充分必要条件文法的充分必要条件20 对于对于文法文法G的每一个非终结符的每一个非终结符A的产生式的产生式 A，A 。如果。如果 SELECT(A) SELECT(A ) =则文法则文法G是一个是一个LL(1)文法。文法。 其中其中、不同时能不同时能=* 。 若若某文法是某文法是LL(1)文法，那么它能够唯文法，那么它能够唯一确定选用的产生式。一确定选用的产生式。 SELECT集集21 给定给定上下文无关文法的产生式上下文无关文法的产生式A， A VN，V*，则：，则：SELECT(A)= FIRST() * (FIRST()- ) FOLLOW(A) =* 22 一个文法一个文法G是是LL（

13、1）的，当且仅当对于）的，当且仅当对于G的每一个的每一个非终结符非终结符A的的任何两个不同产生任何两个不同产生式式A ，下面的条件成立：，下面的条件成立：FIRST（）FIRST()= ，也就是也就是 和和推推导不出以同一个终结符导不出以同一个终结符a为首的符号串；它们为首的符号串；它们不应该都能推出空字不应该都能推出空字 。.假若假若 =* ，那么，那么， FIRST（)FOLLOW（A） 。也就是，也就是， 若若 =* 。则则所能推出的串的首符号不应在所能推出的串的首符号不应在FOLLOW(A）中。）中。23 当选用确定的自顶向下分析方法时，首先当选用确定的自顶向下分析方法时，首先必须判别

14、所给文法是否是必须判别所给文法是否是LL(1)文法。文法。 步骤如下：步骤如下： 1. 求出能推出求出能推出的非终结符；的非终结符； 2. 计算计算FIRST集；集； 3. 计算计算FOLLOW集；集； 4. 计算计算SELECT集；集； 5. SELECT集相交是否为空。集相交是否为空。二、二、LL(1)文法的判别文法的判别24判断该文法是否为LL(1)文法。各个产生式的SELECT集如下：练习练习2526 由由LL(1)文法的定义可知，若文法中含有文法的定义可知，若文法中含有直接或间接直接或间接左递归左递归，或含有，或含有左公共因子左公共因子，则该，则该文法肯定不是文法肯定不是LL(1)文

15、法。文法。 因而，要设法消除文法中的左递归，提取因而，要设法消除文法中的左递归，提取左公共因子对文法进行等价变换。左公共因子对文法进行等价变换。三三、非非LL(1)到到LL(1)文法的等价变换文法的等价变换提取左公共因子提取左公共因子27 若若文法中含有形如：文法中含有形如：A1|2的的产生式，产生式，这导致了对相同左部的产生式其右部的这导致了对相同左部的产生式其右部的FIRST集相交，即对于非终结符集相交，即对于非终结符A的替换的替换不能唯一不能唯一确确定候选。定候选。等价变换等价变换一般形式一般形式28经过经过反复提取左因子，就能够把每个非终结反复提取左因子，就能够把每个非终结符（包括新引

16、进者）的多有候选首符集变成符（包括新引进者）的多有候选首符集变成为两两不相交。为两两不相交。代价：引入大量新的非终结符和相关产生式。代价：引入大量新的非终结符和相关产生式。等价变换等价变换消除左递归消除左递归29 左递归的两种形式：左递归的两种形式： 一个文法中含有左递归时，一个文法中含有左递归时，不能不能采用自顶采用自顶向下分析法。向下分析法。 直接直接左递归：产生式形如左递归：产生式形如AA + 间接左递归：间接左递归：A=A消除直接左递归消除直接左递归30 关于关于非终结符非终结符A的产生式为：的产生式为： 这种形式和原来的形式是等价的，即从这种形式和原来的形式是等价的，即从A推出的符号

17、串是相同的。推出的符号串是相同的。一般形式一般形式31消除消除直接左递归后改写为：直接左递归后改写为：消除直接左递归例子消除直接左递归例子3233 若文法中含有左递归，或含有左公共因子，若文法中含有左递归，或含有左公共因子，则该文法肯定不是则该文法肯定不是LL(1)文法。文法。 此时，可以设法消除文法中的左递归，提此时，可以设法消除文法中的左递归，提取左公共因子来对文法进行等价变换，这样就取左公共因子来对文法进行等价变换，这样就可能可能使其使其 变成变成LL(1)文法。文法。4.4 LL(1)分析法分析法3435要求要求:文法是文法是LL(1)文法文法 第一个第一个L 从左到右从左到右扫描输入

18、串；扫描输入串； 第二个第二个L 使用使用最最左左推导推导方法；方法； 1 只需查看一只需查看一个输入个输入符号便可决符号便可决 定选择哪个产生式进行推导。定选择哪个产生式进行推导。 实现技术实现技术: 1 .表驱动预测分析表驱动预测分析方法方法(LL(1)分析法分析法) 2 .递归子程序递归子程序法法一、一、LL(1)LL(1)分析器的逻辑结构分析器的逻辑结构36 LL(1)分析分析法由一张分析表、一个分析栈和一个控法由一张分析表、一个分析栈和一个控制程序组成。制程序组成。这个语法分这个语法分析过程完全析过程完全由预先根据由预先根据文法设计的文法设计的分析表分析表M以以及分析栈及分析栈S进进

19、行控制（控行控制（控制程序）。制程序）。对于不同的文法，会对于不同的文法，会有不同的分析表有不同的分析表M，但这种语法分析方法但这种语法分析方法的总控程序是一样的。的总控程序是一样的。分析栈分析栈S用于存放文法符号。分用于存放文法符号。分析开始时，栈底先放一个析开始时，栈底先放一个 # ，然后，放进文法的开始符号然后，放进文法的开始符号。随。随着分析的展开，放入相应符号。着分析的展开，放入相应符号。二、二、LL(1)分析表的结构及构造分析表的结构及构造方法方法37 分析表是一个二维数组分析表是一个二维数组MA，a，其中，其中A是非终结符，是非终结符，a是终结符或是终结符或#。 MA，a中若有产

20、生式，表明中若有产生式，表明A可用该产可用该产生式推导，以求与输入符号生式推导，以求与输入符号a匹配。匹配。 MA，a中若为空，表明中若为空，表明A不可能推导出不可能推导出与与a匹配的字符串。匹配的字符串。38 对文法对文法G的每个产生式的每个产生式A执行以下步骤：执行以下步骤： 1. 若若a SELECT(A),则则把把A 加至加至 A,a中；中； 2. 把所有无定义的把所有无定义的A,a标上标上“出错标志出错标志”。 为了使表简化，表中空白处为出错。为了使表简化，表中空白处为出错。算法实现算法实现39练习练习40构造构造GE文法文法的的LL(1)分析表。分析表。三、三、LL(1)分析器的工

21、作流程分析器的工作流程41总控程序总控程序42 总控程序在任何时候都是按分析总控程序在任何时候都是按分析栈栈顶符号栈栈顶符号X和当前的输入符号和当前的输入符号a行事行事的。对于任何的。对于任何(X，a)，总控程序每次，总控程序每次都执行下述三个动作之一：都执行下述三个动作之一： 1. 若若X=a= # ，则分析成功。，则分析成功。 2. 若若X=a # ，则把，则把X从栈顶弹出从栈顶弹出， 让让a指向下一个输入符号。指向下一个输入符号。 433. 若若X为一非终结符，则查分析表为一非终结符，则查分析表M。若若MX，a中为中为A产生式，将产生式，将A自栈自栈顶弹出，将产生式右部符号串按顶弹出，将

22、产生式右部符号串按逆序逆序逐逐一推入栈中；当产生式为一推入栈中；当产生式为A时，则只将时，则只将A弹出即可。若弹出即可。若MX，a中为空中为空,则调则调用出错处理程序。用出错处理程序。44算法实现算法实现当前字符匹当前字符匹配配成功。成功。要对栈顶要对栈顶的非终结的非终结符进行替符进行替换。换。45初始化注意一定要逆序入栈。栈顶为终结符，表示匹配成功。4.5 递归下降法递归下降法4647 对于对于LL(1)文法的分析可以采用两种方法：文法的分析可以采用两种方法： 一种是上一节介绍的一种是上一节介绍的LL(1)分析法，它利分析法，它利用用LL(1)分析表和语法分析栈来实现；分析表和语法分析栈来实现； 另一种是递归下降法，它利用一组可相另一种是递归下降法，它利用一组可相互递归调用的子程序来实现。互递归调用的子程序来实现。48 为每一个非终结符编制一个子程序，子为每一个非终结符编制一个