编译原理自上而下语法分析.ppt
第四章 自上向下语法分析,语法分析的任务本章要点：自上而下语法分析的思想LL（1）方法递归下降分析预测分析,基本思想,主旨 对任何输入串，试图用一切可能，从文法的开始符号出发，自上而下地为输入串建立一棵语法树，或者为输入串寻找一个最左推导。本质上是一种试探过程,要解决的基本问题,例：GS：SxAy A*|*考虑输入串x*y 对于特定的非终结符号，使用哪个产生式来替换？,带回溯的自上而下语法分析存在的困难和缺点,文法的递归性虚假匹配错误的位置难以确定效率低，代价高,无回溯的自上向下分析技术,先决条件：无左递归 既没有直接左递归，也没有间接左递归。无回溯性对于任一非终结符号U的产生式右部x1|x2|xn，各xi的首终结符号两两不相交。,文法的左递归性,定义：文法的左递归性是指文法具有以下形式的直接左递归：U Ux|y 或间接左递归：U=+Ux,具有左递归性的文法举例,E E+T|TT T*F|FF(E)|i,消除文法的直接左递归,PP1|Pn|1|m改写为：P 1P|mP P 1P|nP|,例子,消除左递归前EE+T|TTT*F|FF(E)|i,消除左递归后ET E E+TE|TFT T*FT|F(E)|i,间接左递归举例,SQc|cQRb|bRSa|a 以上文法不含直接左递归，但S，Q，R都是左递归的，因为：S=Qc=Rbc=SabcQ=Rb=Sab=QabcR=Sa=Qca=Rbca,消除文法的左递归,前提：如果一个文法不含回路（形如P+P的推导），也不含以 为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以 为右部的产生式）。,消除文法的一切左递归的算法,1、把文法的所有非终结符按任一顺序排序2、FOR i=1 TO n DO(1)FOR j=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|k 其中Pj1|k是关于Pj的所有规则(2)消除关于规则的直接左递归3、化简由2所得的文法,例子,ABcdBCe|fCAb|c,消除回溯的基本思想,必须保证对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号，指派它的一个候选（右部）去执行任务，并且此候选的工作结果应是确定无疑的：即要么匹配成功，要么不可能获得匹配。,消除回溯对文法的要求,1、首先，文法不得含有左递归；2、设文法G不含左递归，对G的所有非终结符的每个候选 定义其终结首符集FIRST()为 FIRST()=a|=*a,aVT 特别是，若=*，则规定 FIRST()。如果非终结符A的所有候选首符集两两不相交，那么，当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选去执行任务。这个候选就是那个终结首符集含a的。,消除回溯方法：提取公共左因子,假设关于A的产生式是 A1|2|n|n+1 那么，可以将其改写为 A A|n+1 A 1|2|n 经过反复提取左因子，就能够把每个非终结符（包括新引进者）的多有候选首符集变成为两两不相交。代价：引入大量新的非终结符和空产生式。,GS：S Bx B x|考虑输入串xFOLLOW(U)=b|S=*xUby,bVT,x,y（VNVT)*；特别地，#FOLLOW(S)。,LL(1)分析条件,文法不含左递归设U是文法G的任一个非终结符，其产生式为 Ux1|x2|xn 如果 FIRST(xi)FIRST(xj)=(ij,i,j=1,2,n)当 FIRST(xi)时，有 FIRST(xi)FOLLOW(U)=则文法G为LL(1)文法。,LL(1)方法,基本思想：从S出发，生成句子的最左推导。选择合适产生式：从左到右扫描源程序，每次通过向前查看1个字符，选择合适的产生式。适用范围：仅对LL(1)文法适用。,FIRST()和FOLLOW(U),定义：1、FIRST()=a|=*a,aVT,（VNVT)*；特别地，如果=*，那么，我们规定 FIRST()。2、FOLLOW(U)=b|S=*xUby,bVT,x,y（VNVT)*；特别地，#FOLLOW(S)。直观地讲：FIRST(u)包含了u对应的字的所有可能的首终结符号。FOLLOW(U)表示了句型中可能紧跟再U后面的终结符号。,FIRST()构造算法,对于X(VNVT）,FIRST(X)的构造1：若XVT，则FIRST(X)=X2：若XVN，且有产生式Xa,a VT，则a FIRST(X)；如果X，那么 FIRST(X)。3：若有产生式X Y,Y VN,则FIRST(Y)FIRST(X);如果有产生式XY1Y2YK,其中Y1，Y2，Yi1 VN且Y1Y2Yi1=*,则FIRST(Yi)FIRST(X)；若Y1Y2YK=*，则 FIRST(X)。,FIRST()构造算法(续),设(VNVT）*,=X1X2Xn，FIRST()的构造1：若=，则FIRST()=2：若，则FIRST(X1)FIRST()。3：若X1X2。Xi1=*,则FIRST(Xi)FIRST()；若X1X2Xn=*,则 FIRST()。,FOLLOW(U)的构造算法,1、#FOLLOW(S)2、如果有产生式AxUy，那么FIRST(y)FOLLOW(U)。3、如果有产生式AxU或则 AxUy且y=*，那么FOLLOW(A)FOLLOW(U)。注意：步骤3需要重复执行，直到没有哪个非终结符号的FOLLOW集合增长为止。,FIRST的例子,文法GE:ETEE+TE|TFTT*FT|F(E)|iFIRST(F)=(，i FIRST(T)=FIRST(F)=(，i FIRST(E)=+，FIRST(T)=*,FOLLOW例子,文法GE:ETEE+TE|TFTT*FT|F(E)|iFOLLOW(E)=#,)FOLLOW(E)=FOLLOW(E)=#,)FOLLOW(T)=FIRST(E)FOLLOW(E)-=+,#,)FOLLOW(T)=FOLLOW(T)=+,#,)FOLLOW(F)=FIRST(T)FOLLOW(T)=+,#,),*,例子,求FIRST集与FOLLOW举例：文法GA:AB BXB BAB|XaX|bX XaX|bX|,递归下降分析程序（实现思想）,实现思想：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。,基本架构(1),变量：sym：当前符号函数：advance()：读输入串下一符号对于每个非终结符号U 1|2|n处理的方法如下：P(U)if sym FIRST(1)then P(1)/处理1的程序部分 else if sym FIRST(2)then P(2)/处理2的程序部分 else if sym FIRST(n)then P(n)else if sym FOLLOW(U)then return/处理空产生式情况 else error 对于无回溯的文法保证选择是唯一的。,基本架构(2),对于每个右部=x1x2xn的处理架构如下：P()P(x1);/处理x1的程序 P(x2);/处理x2的程序 P(xn);/处理xn的程序 说明：如果右部为空，则不处理。,基本架构(3),对于右部中的每个符号xi如果xi为终结符号：if(sym=a)sym=下一输入符号/对于终结符，直接将指针前调elseerror如果xi为非终结符号，直接调用相应的过程：P(xi),扩展的BNF表示法,花括号 x:表示符号串x出现0次或多次，即 x*xnm:m表示符号串x能出现的最大次数，n表示符号串x能出现的最小次数方括号 表示x01。圆括号（）利用圆括号可以提出非终结符的多个产生式右部的公共因子。,E E+T|E-T|T 可改成 E T+T|-T T T*F|T/F|F 可改成 T F*F|/F,用扩展的BNF表示法消除左递归,例子,|以上标识符产生式含有左递归，可以改写为：|,Z(U)|aUb,ET|E+T|E-T ET+T|-TTF|T*F|T/F TF*F|/F,有文法GZ：ZAcB|Bd A AaB|c B aA|a设计递归下降分析程序。,思考题,预测分析程序的结构,使用一个二维分析表和栈联合进行控制来实现语法分析。总控程序大同小异，而LL（1）分析表却千差万别。LL（1）分析表是进行LL（1）分析的核心。,输入符号串：,分析栈,LL（1）总控程序,分析表,输出流,预测分析表的结构,分析表实际上是一个从VN(VT#)到产生式的映射，通常以矩阵表示。其元素MU,a中可能存放一条非终结符U的产生式，说明当符号栈S的栈顶元素非终结符U遇到当前输入字符a时，所应选择的产生式；元素MU,a也可存放一个出错标志，说明符号栈S的栈顶元素非终结符U不应遇到当前输入符号a。,预测分析器的总控原理,在任何时候，总控程序都是按照栈顶符号X和当前输入符号a工作的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：1、若Xa，则宣布分析成功，停止分析过程；2、若Xa，则把X从栈顶逐出，让a指向下一输入符号；3、若X是一个非终结符，则查看分析表M。若M中存放着一条关于X的产生式，那么，首先把X逐出栈顶，然后，把产生式的右部符号按反序一一推进栈，同时做这个产生式相应的语义动作（目前不管）。若MX,a中存放着一条出错标志，则调用出错诊查程序Error。,例子,文法GE E TE E+TE|T FT T*FT|F(E)|i,例子,预测分析表的生成,从前面的论述我们看到，预测分析法的总控程序是固定的。对于某个文法，分析表是分析过程的核心。表中MU,a=UX1X2Xn表示对应于X1X2Xn字的首符号可以是a。就是说X1X2Xn=*a。我们可以通过这个方式来确定分析表中的值。,预测分析表的生成,一般来讲，对于一个符号串X1X2Xn的字的第一个终结符号就是X1对应的字的第一个终结符号。但是空产生式的存在使情况有一点复杂。对于U1U2Un，如果U1=*，那么符号串对应的字的首符号也可以是U2对应的字的首符号。计算一个符号串对应的字的首符号的算法也需要考虑到这些。,预测分析表的构造,基本思想：当我们需要将U选择某个产生式展开时，如果当前的输入为a，表示我们要将U展开为以a为首符号的字。如果有产生式Uu，且a FIRST(u)，那么表示这个产生式是个好的选择。,分析表构造算法,对于每个产生式U，执行一下步骤对于每个终结符号a FIRST()，MU,a=U.如果 FIRST()，对于每个终结符号b FOLLOW(U)，MU,b=U。将其它未定义的分析表元素置为ERROR。,分析表的例子,文法GE:ETE E+TE|TFTT*FT|F(E)|i,分析表的冲突,文法GS SiCtSS|aSeS|CbFIRST(iCtSS)=iFIRST(eS)=eFIRST(S)=i,aFIRST(C)=bFIRST(S)=e,FOLLOW(S)=FOLLOW(S)=#,e,LL(1)文法,LL(1)文法，其预测分析表中没有多重定义的元素，则该文法被称为LL(1)文法。LL(1)文法是无二义性的。,
