自上而下的语法分析.ppt

1,第4章 自上而下的语法分析,4.1 带回溯的自上而下分析法概述 4.2 直接左递归的消除 4.3 不带回溯的自上而下分析法的基本原理 4.4 提取左因子 4.5 first集和follow集 4.6 递归下降分析法 4.7 预测分析法,从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。,2,4.1 带回溯的自上而下分析法概述,从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。 分析过程概述 例已知文法G： SxAy A*|* 和输入串=x*y。 初始时，指示器P指向的第一个符号x。 从S推导，因最左子结和输入串第1个符号相匹配，故P指向下一符号*。 因第二个子结是非终结符A，从A采用第一个候选进行推导。从A推导出的左子结和指示器P所指的符号一致，故P指向下一个符号y。 因A的第二个子结*和指示器P所指的符号不一致，这意味着A的第一个候选不适用于构造的语法树，应该回溯。将A的子树注销，P恢复进入A时的值。 用A的第二个候选进行推导，因子树A的子结和指示器P所指的符号*一致，则P指向下一个符号y。 因S的第三个子结和指示器P所指的符号一致，故是一个句子。,3,显然上述分析过程本质上是一个试探过程，是反复使用不同产生式谋求匹配输入串的过程。,问题和困难 对于左递归文法定义的语言，不能采用自上而下的语法分析法。 存在虚假匹配，回溯不可避免。 编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。 当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。 带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。 总上所述，必须消除分析过程中的回溯，只有不带回溯的分析方法才是实际可使用的。,4,4.2 直接左递归的消除,程序设计语言文法的左递归性通常是由左递归规则直接引起的，由规则推导所产生的间接左递归的情况较少见。 实例引入 例：已知左递归文法G：SSa|b，构造文法G的等价文法G，G不含左递归。 解：文法G如下所示 SbS SaS| SSaSaaban 或 Sb L(G)= bann0 SbSbaSban 或 SbSb L(G)= bann0 L(G)= L(G) 文法G和G等价，而文法G不含左递归。,5,直接左递归消除方法 假定关于非终结符P的规则为 PP| 其中，不以P开头。可以把关于P的规则变换为如下形式： PP PP| 由于二者推导出的句型均为n(n0)，故上述变换是等价的。 例文法G： EE+T|T TT*F|F F(E)|i|x|y 经消除直接左递归后变成 ETE E+TE| TFT T*FT| F(E)|i|x|y,6,直接左递归消除一般规则及等价性证明 设非终结符P的产生式如下 PP1|P2|Pm|1|2|n 其中，i（1in）不以P开头。可将P的规则改成如下等价形式，即可消除左递归。 P1P|2P|nP P1P|2 P|m P | 证： PP1| P2| Pm|1|2|n 等价于 PP（1|2|m）|（1|2|n） 令=1|2|m、=1|2|n，则上式为： PP|。 消除直接左递归后变成 PP PP|,7,证： PP1| P2| Pm|1|2|n 等价于 PP（1|2|m）|（1|2|n） 令=1|2|m、=1|2|n，则上式为： PP|。 消除直接左递归后变成 PP PP| 用1|2|m替代，用1|2|n替代，则有 P（1|2|n）P P（1|2|m）P | 等价于 P1P|2P|nP P1P|2 P|m P |,8,4.3 不带回溯的自上而下分析法的基本原理,设文法G有产生式：A1|2|n 带回溯的自上而下的分析法 采用试探法，对于1、2直至n逐一试探。 不带回溯的自上而下的分析法 在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。 对于文法某一句型，只要该文法不是二义文法，从非终结符A出发的最左推导只有一个候选是正确的。 如果该候选式获得匹配，那么这个匹配决不会是虚假的。若该候选式无法完成匹配任务，则任何其它候选式也肯定无法完成。,9,算法思想如下： 引入候选式的first集定义 first()=aa，aVT。 first()直观意义是：从候选式出发，推导出的所有符号串的第一个终结符，都属于这个集合。 根据定义，求出每个候选式i的first集，设： first(1)=a1、b1、 first(2)=a2、b2、 first(n)=an、bn、 根据当前输入符号，选择候选式进行推导。 if (t.codefirst(i) 用Ai推导（1in） else 报错 由于推导的唯一性，要求first(i)first(j)=，其中1i,jn、ij。,10,进一步考虑（A） 设文法G有产生式A1|2|n|，因A无需任何字符匹配（相当于在句型推导中丢弃A），故当t.codefirst(i)不能简单地处理为出错，需进一步分析，A匹配于空字可能是一个正确的选择。 引入非终结符follow集定义 follow(A)=a|SAa，aVT follow(A)的直观意义是：在所有句型中紧跟在非终结符A之后的终结符。 若当前处理符号属于follow(A)，则用A进行推导（相当于在句型推导中丢弃A），当前处理符号参加下一次匹配。 修改分析算法 if (t.codefirst(i) 用Ai推导（1in） else if (t.codefollow(A) 用A推导 else 报错 由于推导的唯一性，要求first(i)first(j)=，first(i)follow(A) = ，其中1i,jn、ij。,11,4.4 提取左因子,实例引入 例定义无符号整数的文法 NDN|D D0|1|2|3|4|5|6|7|8|9 因first(DN)first(D)=0,1,2,3,4,5,6,7,8,9，故文法含有左因子。 解决方法 提取左因子，引进产生式，将文法改造为G。 ND N NN| D0|1|2|3|4|5|6|7|8|9|0 提取左因子一般规则 考虑一般情况，设非终结符P的规则为 P1|2|n，(VTVN)+，i(VTVN)* 引进非终结符P，可以把这些规则改写成 PP P1|2|n,12,先讨论文法符号，然后再讨论候选式、任意文法符号串的first集的构造。 first集定义 是文法G的任一符号串（包括候选式），(VTVN)* first()=aa，aVT 若，则规定first()。 first()直观意义是：从推导出的所有符号串的第一个终结符。或者，从可推导至空字。 文法符号first集构造算法 终结符的first集为终结符本身。 观察每个产生式，若有Xa，其中aVT，则afirst(X)；若X，则first(X)。 观察每个产生式，若有XY，其中YVN，则将first(Y)中的非元素（记为first(Y)/）加到first(X)中。,4.5.1 first集的定义及构造算法,13,证： 设终结符afirst(Y)，根据定义有Ya。 XY XYa 即Xa，根据定义有afirst(X)。 考虑更一般情况,XY1Y2YiYn,其中Y1、Y2、Yi-1VN。 若first(Y1)中含有，则将first(Y2)/加到first(X)中，否则终止计算。 若first(Y1)和first(Y2)中含有，则将first(Y3)/加到first(X)中，否则终止计算。 若first(Y1)、first(Y2)、first(Yi-1)均含有，即Y1Y2Yi-1，则把first(Yi)/加到first(X)中，否则终止计算。 若所有first(Yj) 均含有(1jn)，即Y1Y2Yn，则first(X)。 反复使用规则，直至每个非终结符的first集不再增长为止。规则实质上是一个传递规则。,14,例，文法G如下所示, 求文法符号的first集。 ETE E+TE| TFT T*FT| F(E) | i | x | y 解：文法符号first集的计算规则如下,15,在“规则”列处填入的是计算公式，需多次重复计算，直至每个非终结符的first集不再增长为止。计算过程如下,说明： 由于终结符的first集计算较为简单，在计算过程中不再列出。 在计算E的 first集时（ETE），因first(T)不含，故没有必要考虑E的first集，同理T的first集计算（TFT）。 计算也可从下至上进行。,16,候选式first集构造算法 设A，=X1X2Xn，计算规则如下所示： 置first()=first(X1)/。 若first(X1)，则把first(X2)/加至first()中；若first(X1)且first(X2)，则把first(X3)/加至first()；依次类推。 若所有的first(Xi)均含有,其中1in，则first()。特别当=,则first()=。 接上例，求文法G候选式的first集： ETE first(TE)=first(T) /=(,i,x,y E+TE| first(+TE)=+,first()= TFT first(FT)=first(F) /=(,i,x,y T*FT| first(*FT)=*,first()= F(E)|i first(E)=( 、first(i)=i Fx|y first(x)=x、first(y)=y,任一文法符号串的first集构造算法 设AX1X2Xi-1XiXi+1Xn，求XiXi+1Xn的first集。 令= XiXi+1Xn，参照即可。,17,4.5.2 follow集的定义及构造算法,follow集定义 设S是文法开始符号，对于文法的任何非终结符A follow(A)=aSAa，aVT 特别是，若SA，规定#follow(A)。 （注：由于算法的需要，人为地在源程序尾部添加了#，特别规定因此而来） follow(A)直观意义是：在所有句型中紧跟在非终结符A之后的终结符或#。 follow集构造算法 对于文法开始符号S，因为SS，故#follow(S)。 观察每个产生式，若AB，其中、(VTVN)+， BVN，则把first()/加至follow(B)。 观察每个产生式，若AB或AB()，则把follow(A)加至follow(B)。,18,证：设afollow(A)，根据定义有SAa。 AB SAaB a 因a在句型中紧跟在B之后，故afollow(B)。,反复使用第条规则，直至每个非终结符的follow集不再增长为止。第条规则实质上是一条传递规则。 例，文法G如下所示，求非终结符的follow集。 ET E first(E) /= + E+TE E TFT first(T) /= * T*FT T F(E) first( ) )=) Fi Fx Fy,19,解：根据上述规则，非终结符follow集的计算规则如下,根据ETE，follow(E)应加至follow(E)；因E，所以follow(E)还应加至follow(T)。同理E+TE、TFT、T*FT。 follow集的计算也可从下至上进行。,“规则”列处填入的是计算公式，需多次重复计算，直至每个非终结符的follow集不再增长为止。计算过程如下,20,4.6 递归下降分析法,递归下降分析法思想是：让每个非终结符对应一个过程（函数）。根据上述文法，构造递归下降分析程序，程序用类C语言描述。,void E( )/ ETE T;E; ,void E( )/ E+TE| if (t.code=+)cinft.codet.val;T;E; ,void T( )/ TFT F;T; ,void T( )/ T*FT| if (t.code=*)cinft.codet.val;F;T ,void F( )/ F(E) | i | x | y if (t.code=() cinft.codet.val; E;if (t.code=) cinft.codet.val; else if (t.code=i| t.code=x| t.code=y) cinft.codet.val; ,struct code_valchar code;char val20; t; ifstream cinf(“lex_r.txt“,ios:in);,21,为了便于理解，源程序“(a+b)*c”用单词种别“(i+i)*i#”表示，手工计算如下： step 调用过程(函数) t.cod 文件Lex_r 0) E ( i+i)*i# 1) TE ( i+i)*i# 2) FTE ( i+i)*i# 3) ESTE i +i)*i# S代表语句if (t.code=)cinft.codet.val; 4) TESTE i +i)*i# 5) FTESTE i +i)*i# 6) TESTE (T匹配于) + i)*i# 7) ESTE + i)*i# 8) TESTE i )*i# 9) FTESTE i )*i# 10) TESTE(T匹配于) ) *i# 11) ESTE (E匹配于) ) *i# 12) STE ) *i# 13) TE * i# 14) FTE i # 15) TE (T匹配于) # 16) E(E匹配于) # 17) (回到主程序结束处即E之后) # ,22,4.7 预测分析法,递归下降分析法是利用高级语言的递归过程（函数）来实现的，只有当高级语言的编译系统允许过程（函数）递归调用，递归下降分析法才有意义。现考虑一个不使用递归的更一般的实用方法，这种分析法是由分析表和控制程序构成。,预测分析法基本原理 产生式的一般形式为： A1|2|n| 设当前输入符号为a，根据下述原则 if (afirst(i) 用Ai推导（1in） else if (afollow(A) 用A推导 else 报错,23,构造分析表如下,分析表构造规则 构造所有候选式的first集，构造所有非终结符的follow集。 对于文法的每个产生式A执行和。 对于每个终结符afirst()，把A加至MAa。 若first()，则对于每个终结符bfollow(A)，把A加至MAb。 把所有未定义的MAc标上“出错标志”（cVT）。,24,预测分析控制程序实现 数据结构 M: 二维数组，存放预测分析表。 stack: 符号栈，初始时为“#S“（S为开始符号）。 X: 表示栈顶符号 t.code:当前处理单词种别 算法描述（暂不考虑出错情况） 预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事（ XPop(stack) ），控制程序每次执行下述三种可能的动作之一。 若X 和 t.code 均为 #，则分析成功，输入串为合法句子，终止分析过程。 若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等，则读入下一个单词二元式。 若X是非终结符，则查预测分析表。若MXt.code存放着一条关于X的一个产生式，那么把产生式右部符号串按反序压入stack栈。若右部符号串为空字，则意味着无任何文法符号进栈。,25,假设由单词种别构成的源程序为“i+i#”，手工计算如下： step stack X t.code 文件Lex_r.txt 0) #E i +i# 1) # E i +i# #ET i +i# 2) #E T i +i# #ETF i +i# 3) #ET F i +i# #ETi i +i# 4) #ET i i +i# #ET + i# 5) #E T + i# #E + i# 6) # E + i# #ET+ + i# 7) #ET + + i# #ET i #,26,step stack X t.code 文件Lex_r.txt 7) #ET + + i# #ET i # 8) #E T i # #ETF i # 9) #ET F i # #ETi i # 10) #ET i i # #ET # 11) #E T # #E # 12) # E # # # 13) # # Acc,预测分析法不仅避免了过程（函数）的递归调用，并且使得自上而下的语法分析器的自动构造成为可能。,27,1. procedure LL1 2. 初始化符号栈 3 push(符号栈, #):push(符号栈, S) 4. t.codecode:t.valval /从文件读第一个单词的二元式 5. donefalse 6. repeat 7. Xpop(状态栈) 8. if X=# then 9. if X= t.code then 10. output ”Acc”:donetrue 11. end if /否则出错 12. else if XVT then 13. if X= t.code then 14. t.code code:t.valval /从文件读下一个单词的二元式 15. end if /否则出错 16. else if XVN then 17. if MXt.code=“X“ then /= X1X2Xn 18. for i| downto 1 19. push(状态栈,Xi) 20. end for 21. end if 22. end if /否则出错 23. until done 24. end procedure,28,预测分析法讨论 预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。 在预测分析表中，若某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。 一个文法，若它的预测分析表不含多重定义，则称该文法是LL(1