《第四章 语法分析——自上而下分析.ppt》由会员分享，可在线阅读，更多相关《第四章 语法分析——自上而下分析.ppt（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 语法分析语法分析自上而下分析自上而下分析 高级语言的语法结构适合用上下无关文法描述，高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础。因此，我们将上下文无关文法作为语法分析的基础。本章和下一章，我们将介绍编译程序构造中的一些本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法典型的语法分析方法4.1 语法分析器功能语法分析器功能 语法分析是编译过程的核心部分。它的任务是在语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。程
2、序的语法结构是否符合语法规则。下图表明了语法分析器在编译程序中的地位。下图表明了语法分析器在编译程序中的地位。第四章 语法分析-自上而下分析源程序编译前端中间代码代码优化中间代码代码生成器目标程序符 号 表代码生成器的位置代码生成器的位置第四章 语法分析-自上而下分析 按照语法分析树的建立方法，我们可以粗略地把语法分析方法分按照语法分析树的建立方法，我们可以粗略地把语法分析方法分为两类：一类是自上而下分析法，另一类为自下而上分析法。为两类：一类是自上而下分析法，另一类为自下而上分析法。4 4.2.2 自上而下分析面临的问题自上而下分析面临的问题 本节主要是通过例子使我们认识到，作自上而下分析所
3、遇到的主本节主要是通过例子使我们认识到，作自上而下分析所遇到的主要困难是语法的左递归性使分析陷入无限循环；回溯的不确定性，要求我要困难是语法的左递归性使分析陷入无限循环；回溯的不确定性，要求我们将已经完成工作推倒从来，为解决这些问题我们要消除左递归和消除回们将已经完成工作推倒从来，为解决这些问题我们要消除左递归和消除回溯。溯。4.3 LL(1)分析法分析法 4.3.1 左递归的消除左递归的消除 一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是 PP 1|P 2|P 1m|1|2|n 其中，每个其中，每个 都不等于都不等于，而每个，而每个 都不以都不以P开头，那末，消除开头，那
4、末，消除P的直接左递归性就是把这些规则改写成：的直接左递归性就是把这些规则改写成：P|1 P|2 P|n P P1P|2P|mP|第四章 语法分析-自上而下分析 直接左递归，和非直接左递归的消除方法均在必须掌握之列。这里我们直接左递归，和非直接左递归的消除方法均在必须掌握之列。这里我们切不可被形式描述消除左递归的算法吓倒，多做几个例题后再来理解是很有切不可被形式描述消除左递归的算法吓倒，多做几个例题后再来理解是很有好处的：好处的：例例4。3：考虑文法：考虑文法：SQc|c Q Rb|b R Sa|a 消除左递归。消除左递归。解：将终结符排序为解：将终结符排序为R、Q、S。对于对于R不存在直接左
5、递归。把不存在直接左递归。把R带入到带入到Q中有关的候选式：中有关的候选式：Q Sab|ab|b 现在现在Q同样不含直接左递归，把它带入同样不含直接左递归，把它带入S的有关候选式：的有关候选式：S Sabc|abc|bc|c 经消除经消除S的直接左递归后我们们得到整个文法的直接左递归后我们们得到整个文法 S abcS|bcS|cS S abcS|Q Sab|ab|b R Sa|a 由于关于由于关于Q,R的规则式多余的则可化简的规则式多余的则可化简第四章 语法分析-自上而下分析 得到：得到：S abcS|bcS|cS S abcS|4.3.2 消除回溯、提左因子消除回溯、提左因子 我们首先来看一
6、下在不得回溯的情况下对于文法有什么要求。前面已经说过，我们首先来看一下在不得回溯的情况下对于文法有什么要求。前面已经说过，欲实行自上而下的分析，文法不得含左递归。令欲实行自上而下的分析，文法不得含左递归。令G是一个不含左递归的文法，是一个不含左递归的文法，对对G 的所有的非终结符号的每个候选的所有的非终结符号的每个候选 定义它的终结首符集定义它的终结首符集FIRST()为：为：FIRST()=a|*a,a VT 特别是，特别是，若若*，则，则规定规定 FIRST()。换句话说换句话说FIRST(）是是 的所的所有可能推导的开头终结符或可能的有可能推导的开头终结符或可能的 。如果非终结符。如果非
7、终结符A 的所有候选首符集两的所有候选首符集两两不相交，即两不相交，即A的任何两个不同的候选的任何两个不同的候选 i和和 j FIRST(i)FIRST(j)=那么，当要求那么，当要求A匹配输入串时，匹配输入串时，A 就能根据它所面临的第一个输入符号就能根据它所面临的第一个输入符号a，准确地指派某个候选前去执行任务。这个候选就是那个终结首符集含准确地指派某个候选前去执行任务。这个候选就是那个终结首符集含a 的的。如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢？其办法是？其办法是提取公共左因子提取公共左因子。例如，假定
8、关于。例如，假定关于A 的规则是的规则是 A1|2|。|n|1|2|m （其中每个其中每个 不以不以 开头）开头）那末，可以把这些规则改写成：那末，可以把这些规则改写成：A A|1|2|m A|1|2|n 第四章 语法分析-自上而下分析 例有产生式 B bBcA|b 由于由于FIRST(bBcA)FIRST(b)=b 则需要提取公共左因子则需要提取公共左因子 将产生式改写成将产生式改写成：B bC C BcA|4.3.3 LL（1）分析条件分析条件 假定假定S是文法是文法G的开始符号，对于任何非终结符的开始符号，对于任何非终结符A我们定义：我们定义：FOLLOW(A)=a|S*Aa,a VT
9、特别是，若特别是，若S*A，则规定则规定#FOLLOW(A).也就是说，也就是说，FOLLOW(A)是所是所有举行中出现在紧接有举行中出现在紧接A之后的终结符活之后的终结符活#。判断某给定文法是否为判断某给定文法是否为LL(1)文法其条件为：文法其条件为：（1）文法不含左递归。文法不含左递归。（2）对于文法中每个非终结符）对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。即，的各个产生式的候选首符集两两不相交。即，若若 A 1|2|。|n 则：则：FIRST(i)FIRST(j)=（i j)(3)对文法中每一个终结符对文法中每一个终结符A，若它存在某个候选首符集包含若它存在某个候选首
10、符集包含，则，则 FIRST(A)FLLOW(A)=一个文法若满足以上条件，责称该文法一个文法若满足以上条件，责称该文法G为为LL(1)文法文法第四章 语法分析-自上而下分析 本节特别注意：如果空字本节特别注意：如果空字属于某个非终结符的候选首府集的属于某个非终结符的候选首府集的情况。情况。4.4 递归下降分析程序构造递归下降分析程序构造 当一个文法满足当一个文法满足LL(1)条件时，我们就可以构造一个不带回溯的条件时，我们就可以构造一个不带回溯的自上而下分析程序，这个分析程序由一组第归过程组成，每个过自上而下分析程序，这个分析程序由一组第归过程组成，每个过程对应文法的一个非终结符。这样一个分
11、析程序称为递归下降分程对应文法的一个非终结符。这样一个分析程序称为递归下降分析器。析器。在本节中我们对巴科斯范式进行了扩充：在本节中我们对巴科斯范式进行了扩充：（1）用花括号）用花括号 表示闭包运算表示闭包运算*(2）用）用 0n表示表示 可以任意重复可以任意重复0次至次至n 次，次，00=。（3）用方括号用方括号 表示表示 01，即表示，即表示 的出现可有可无。的出现可有可无。4.5 预测分析程序预测分析程序 使用高级语言的递归过程描述递归下降分析器，只有当具有实使用高级语言的递归过程描述递归下降分析器，只有当具有实现这种过程的编译系统时才有实际意义。实现现这种过程的编译系统时才有实际意义。
12、实现LL(1)分析的另一种分析的另一种有效方式是使用一张分析表和一个栈进行联合控制。我们现在介有效方式是使用一张分析表和一个栈进行联合控制。我们现在介绍的绍的预测分析程序预测分析程序就是属于这种类型的就是属于这种类型的LL(1)分析器。分析器。本节要本节要 掌握对给定文法构造出每个非终结符掌握对给定文法构造出每个非终结符的的FIRST和和FOLLOW集合集合。第四章 语法分析-自上而下分析 掌握掌握LL(1)预测分析表的构造，请参看预测分析表的构造，请参看4。5。1 预测分析程序的预测分析程序的工作过程（工作过程（P76）和和 4。5。2预测分析表的构造（预测分析表的构造（P78）。）。现在举
13、一些例子帮助同学们理解：现在举一些例子帮助同学们理解：例例4。7 对于文法对于文法 ETE E+TE|T FT T*FT|F(E)|i 我们构造每个非终结符的我们构造每个非终结符的FIRST和和FOLLOW集合集合 解：解：FIRST(E)=(,i FOLLOW(E)=),#FIRST(E)=+,FOLLOW(E)=),#FIRST(T)=(,i FOLLOW(T)=+,),#FIRST(T)=*,FOLLOW(T)=+,),#FIRST(F)=(,i FOLLOW(F)=*,+,),#在这里我们要注意在这里我们要注意FOLLOW(F)的求解过程其中的求解过程其中：FOLLOW(F)=FIRS
14、T(T)=*;因为因为T ,所以将所以将FOLLOE(T)加加到到FOLLOW(F)中中（由于（由于TFT),则：则：FOLLOW(F)=FOLLOW(T)=FIRST(E)=+第四章 语法分析-自上而下分析 构造分析表构造分析表M的算法是：的算法是：（1）对文法对文法G的每个产生式的每个产生式A执行第二步和第三步；执行第二步和第三步；（2）对于每个终结符）对于每个终结符a FIRST()，把把A加到加到MA,a中；中；（3）若若FIRST()，则对任何的则对任何的b FOLLOW(A)把把A加至加至Ma,b中；中；（4）把所有无定义的）把所有无定义的MA,a标上标上“出错标志出错标志”4.6
15、 LL(1)分析中的错误处理分析中的错误处理第四章 语法分析-自上而下分析例题与习题解答例题与习题解答例例1试构造与下列文法试构造与下列文法GS等价的无左递归文法。等价的无左递归文法。GS:SSa|Nb|c (1)N Sd|Ne|f (2)对于（对于（1）我们引入新非终结符）我们引入新非终结符S 则：则：S NbS|cS 1 S aS|2 将将 S代入代入（2）N Ne|NbSd|cSd|f 引入新非终结符引入新非终结符N N cSdN|fN 3 N eN|bSdN|4第四章 语法分析-自上而下分析例2：文法文法G的规则集为的规则集为;P begin d:X end X d:X|sY Y:sY
16、|做出该文法做出该文法LL(1)分析表。分析表。解：解：非终结符只有非终结符只有 P,X,Y 只有只有FIRST(Y)含有含有 则则需需 要求出要求出FOLLOW(Y)且且 FOLLOW(Y)=FOLLOE(X)=end则有则有LL(1)表：表：begin d :end s#P begind:X endX d:X sYY :sY 第四章 语法分析-自上而下分析 例例3：给出语言：给出语言L=1na0n1ma0m|n0,m=0 的的LL(1)文文法法GS并说明其理由。并说明其理由。解：观察句子解：观察句子,发现可分成两部分发现可分成两部分 1na0n 和和 1ma0m两部两部分中符号的个数分中符
17、号的个数n和和m没有制约关系。则可改造成下列没有制约关系。则可改造成下列文法：文法：S AB A 1A0|1a0 B 1B0|a 对于产生式对于产生式 A 1A0|1a0 两个候选式两个候选式 FIRST(1A0)FIRST(1a0)=1 所以上边文所以上边文法不是法不是LL(1)文法：需左提公因子，得到：文法：需左提公因子，得到：S AB A 1C C A0|a0 B 1B0|a 此文法满足此文法满足LL(1)文法的要求。文法的要求。第四章 语法分析-自上而下分析 例例4 设有文法：设有文法：GS:SaBc|bAB AaAb|b Bb|构造其构造其LL(1)分析表，并分析符号串分析表，并分析
18、符号串baabbb是否是是否是该文发的句子。该文发的句子。解：因为只有解：因为只有FIRST(B)含有含有 所以只考虑所以只考虑：FOLLOW(B)=FIRST(c)FOLLOW(S)=c,#该文法的该文法的LL(1)表表 a b c#S aBc bABA aAb bB b 符号串符号串baabbb是否为句子的分析过程是否为句子的分析过程步骤步骤 符号栈符号栈S 输入串输入串 规则规则1#S baabbb#SbAB2#BAb baabbb#第四章 语法分析-自上而下分析3#BA aabbb#AaAb4#BbAa aabbb#5#BbA abbb#AaBb6#BbbAa abbb#7#BbbA
19、bbb#Ab8#Bbbb bbb#9#Bbb bb#10#Bb b#11#B#A12#成功，成功，STOP 分析成功分析成功baabbb是该文法的一个句子。是该文法的一个句子。第四章 语法分析-自上而下分析第五章第五章语法分析语法分析自下而上自下而上分析（分析（1）所谓自下而上分析法就是从输入串开始，逐步进所谓自下而上分析法就是从输入串开始，逐步进行行“规约规约”，直至规约到文法的开始符号；或者说从，直至规约到文法的开始符号；或者说从语法树的末端开始，步步向上语法树的末端开始，步步向上“规约规约”，直到根结。，直到根结。5.1 自下而上分析基本问题自下而上分析基本问题 其基本问题包括下列问题：其基本问题包括下列问题：5.1.1归约归约 5.1.2 规范归约简述规范归约简述 在这一部分应掌握短语和直接短语两个重要在这一部分应掌握短语和直接短语两个重要 概念概念 5.1.3 符号栈的使用与语法树的表示符号栈的使用与语法树的表示第四章 语法分析-自上而下分析