[理学]第4章 自上而下的语法分析.ppt

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