自上而下的语法分析.ppt

第4章 自上而下的语法分析,4.1 带回溯的自上而下分析法概述,从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。,4.1 带回溯的自上而下分析法概述,从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,4.1 带回溯的自上而下分析法概述,分析过程概述 例已知文法G： SxAy A*|* 和输入串=x*y。,4.1 带回溯的自上而下分析法概述,4.1 带回溯的自上而下分析法概述,4.1 带回溯的自上而下分析法概述,4.1 带回溯的自上而下分析法概述,4.1 带回溯的自上而下分析法概述,因S的第三个子结和指示器P所指的符号一致，故是一个句子。 显然上述分析过程本质上是一个试探过程，是反复使用不同产生式谋求匹配输入串的过程。,4.1 带回溯的自上而下分析法概述,问题和困难 对于左递归文法定义的语言，不能采用自上而下的语法分析法。 例已知左递归文法G：SSba和输入串=ab，其分析过程如下所示：,4.1 带回溯的自上而下分析法概述,4.1 带回溯的自上而下分析法概述,试图用非终结去推导匹配输入串，而推导所得到的子树第一个子结是该非终结符本身，这样就陷入了死循环。,4.1 带回溯的自上而下分析法概述,存在虚假匹配，回溯不可避免。 编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。,4.1 带回溯的自上而下分析法概述,当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。 带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。,4.2 直接左递归的消除,直接左递归消除方法 假定关于非终结符P的规则为 PP| 其中，不以P开头。可以把关于P的规则变换为如下形式： PP PP| 由于二者推导出的句型均为n（n0），故上述变换是等价的。,4.2 直接左递归的消除,例文法G EE+T|T TT*F|F F(E)|i|x|y 经消除直接左递归后变成 ETE E+TE| TFT T*FT| F(E)|i|x|y,4.3 不带回溯的自上而下分析法的基本原理,设文法G有产生式 A1|2|n 带回溯的自上而下的分析法 采用试探法，对于1、2直至n逐一试探。,4.3 不带回溯的自上而下分析法的基本原理,不带回溯的自上而下的分析法 在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。 引入候选式的first集定义 根据定义，求出每个候选式i的first集。,4.3 不带回溯的自上而下分析法的基本原理,根据当前输入符号，选择候选式进行推导。 进一步考虑（A） 引入非终结符follow集定义 修改分析算法,4.4 提取左因子,实例引入 例定义无符号整数的文法 NDN|D D0|1|2|3|4|5|6|7|8|9|0 就是这样一种情形，first(DN)first(D)=D。,4.4 提取左因子,解决方法 提取左因子，引进产生式，将文法改造为G。 NDN NN| D0|1|2|3|4|5|6|7|8|9|0 提取左因子一般规则,4.5 first集和follow集,4.5.1 first集的定义及构造算法 first集定义 是文法G的任一符号串（包括候选式），(VTVN)* first()=a a，aVT 若 ，则规定first()。,4.5 first集和follow集,文法符号first集构造算法 终结符的first集为终结符本身。 观察每个产生式，若有Xa，其中aVT，则afirst(X)；若X，则first(X)。 观察每个产生式，若有XY，其中YVN，则将first(Y)中的非元素（记为first(Y)/）加到first(X)中。,4.5 first集和follow集,考虑更一般情况，XY1Y2YiYn，其中Y1、Y2、Yi-1VN。 l 若first(Y1)中含有，则将first(Y2)/加到first(X)中，否则终止计算。 l若first(Y1)和first(Y2)中含有，则将first(Y3)/加到first(X)中，否则终止计算。 l若first(Y1)、first(Y2)、first(Yi-1)均含有，即Y1Y2Yi-1 ，则把first(Yi)/加到first(X)中，否则终止计算。 l若所有first(Yj) 均含有(1jn)，即Y1Y2Yn ，则first(X)。 反复使用规则，直至每个非终结符的first集不再增长为止。,4.5 first集和follow集,例，文法G如下所示, 求文法符号的first集。 ETE E+TE| TFT T*FT| F(E) | i | x | y,4.5 first集和follow集,解：非终结符的first集计算过程如下,4.5 first集和follow集,候选式first集构造算法 设A，=X1X2Xn，计算规则如下所示： 置first()=first(X1)/。 若first(X1)，则把first(X2)/加至first()中；若first(X1)且first(X2)，则把first(X3)/加至first()；依次类推。 若所有的first(Xi)均含有,其中1in，则first()。特别当=,则first()=。,4.5 first集和follow集,接上例，求文法G候选式的first集： ETEfirst(TE)=first(T) /=(,i,x,y E+TE|first(+TE)=+,first()= TFTfirst(FT)=first(F) /=(,i,x,y T*FT|first(*FT)=*,first()= F(E)|i|x|yfirst(E)=( 、first(i)=i、first(x)=x、first(y)=y,4.5 first集和follow集,任一文法符号串的first集构造算法 设AX1X2Xi-1XiXi+1Xn，求XiXi+1Xn的first集。 令= XiXi+1Xn，参照即可。,4.5 first集和follow集,4.5.2 follow集的定义及构造算法 follow集定义 设S是文法开始符号，对于文法的任何非终结符A follow(A)=aS Aa，aVT 特别是，若S A，规定#follow(A)。,4.5 first集和follow集,follow集构造算法 对于文法开始符号S，因为SS，故#follow(S)。 观察每个产生式，若AB，其中BVN，(VTVN)*、(VTVN)+，则把first()/加至follow(B)。 观察每个产生式，若AB或AB()，则把follow(A)加至follow(B)。反复使用第条规则，直至每个非终结符的follow集不再增长为止。,4.5 first集和follow集,例，文法G如下所示，求非终结符的follow集。 1. ET Efirst(E) /= + 2. E+TE 3. E 4. TFTfirst(T) /= * 5. T*FT 6. T 7. F(E)first( ) )=) 8. Fi 9. Fx 10. Fy,4.5 first集和follow集,解： 计算过程如下,4.6 递归下降分析法,递归下降分析法思想是：让每个非终结符对应一个过程（函数）。根据上述文法，构造递归下降分析程序，程序用类C语言描述。,4.7 预测分析法,预测分析法基本原理 产生式的一般形式为： A1|2|n| 设当前输入符号为a，根据下述原则 if (afirst(i) 用Ai推导（1in） else if (afollow(A) 用A推导 else 报错,4.7 预测分析法,构造分析表如下,4.7 预测分析法,以输入串“i + i#”为例，说明工作原理如下： ETEFTEiTEiEi+TEi+FTEi+iTEi+iEi+i i i i + + i i # #,4.7 预测分析法,分析表构造规则 构造所有候选式的first集，构造所有非终结符的follow集。 对于文法的每个产生式A执行和。 对于每个终结符afirst()，把A加至MAa。 若first()，则对于每个终结符bfollow(A)，把A加至MAb。 把所有未定义的MAc标上“出错标志”（cVT）。,4.7 预测分析法,预测分析控制程序实现 数据结构 M：二维数组，存放预测分析表。 stack：符号栈，初始时为“#S”（S为开始符号）。 X：表示栈顶符号 t.code：当前处理单词种别,4.7 预测分析法,算法描述 预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事，控制程序每次执行下述三种可能的动作之一（暂不考虑出错情况）。 l若X 和 t.code 均为 #，则分析成功，输入串为合法句子，终止分析过程。,4.7 预测分析法,l 若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等。让X出stack栈，并输入下一个单词二元式。 l若X是非终结符，则查预测分析表。若MXt.code存放着一条关于X的一个产生式，那么，让X出stack栈，然后把产生式右部符号串按反序一一推进stack栈。若右部符号串为空字，则意味着无任何文法符号进栈。,4.7 预测分析法,预测分析法讨论 预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。 在预测分析表中，若某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。 一个文法，若它的预测分析表不含多重定义，则称该文法是LL(1)文法、分析表为LL(1)分析表。,4.7 预测分析法,一个文法是LL(1)的，对于文法的每一个非终结符的任何两个不同候选式（A|），下述条件成立： l first()first()= l若，则first()follow(A)= 二义文法不是LL(1)文法,4.7 预测分析法,讨论If-then-else结构的文法 文法G，a表示普通语句，C表示布尔表达式 S fCtS | fCtSeS|a C I,