编译原理自上而下语法分析.ppt

第四章 自上向下语法分析,语法分析的任务 本章要点： 自上而下语法分析的思想 LL（1）方法 递归下降分析 预测分析,基本思想,主旨 对任何输入串，试图用一切可能，从文法的开始符号出发，自上而下地为输入串建立一棵语法树，或者为输入串寻找一个最左推导。 本质上是一种试探过程,要解决的基本问题,例：GS：SxAy A* | * 考虑输入串x*y 对于特定的非终结符号，使用哪个产生式来替换？,带回溯的自上而下语法分析 存在的困难和缺点,文法的递归性 虚假匹配 错误的位置难以确定 效率低，代价高,无回溯的自上向下分析技术,先决条件： 无左递归 既没有直接左递归，也没有间接左递归。 无回溯性 对于任一非终结符号U的产生式右部x1|x2|xn，各xi的首终结符号两两不相交。,文法的左递归性,定义： 文法的左递归性是指文法具有以下形式的直接左递归： U Ux|y 或间接左递归： U=+Ux,具有左递归性的文法举例,E E+T|T T T*F|F F (E)|i,消除文法的直接左递归,PP1 | | Pn | 1 | | m 改写为： P 1P| | mP P 1P| | nP| ,例子,消除左递归前 EE+T|T TT*F|F F(E)|i,消除左递归后 ET E E +TE | TFT T *FT | F(E)|i,间接左递归举例,SQc|c QRb|b RSa|a 以上文法不含直接左递归，但S，Q，R都是左递归的，因为： S=Qc =Rbc =Sabc Q =Rb =Sab =Qabc R =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所得的文法,例子,ABcd BCe|f CAb|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 | 考虑输入串x FOLLOW(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)=X 2：若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: ETE E+TE| TFT T*FT| F(E)|i FIRST(F)= (，i FIRST(T)=FIRST(F)= (，i FIRST(E)= +， FIRST(T)=*, ,FOLLOW例子,文法GE: ETE E+TE| TFT T*FT| F(E)|i FOLLOW(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=下一输入符号 /对于终结符，直接将指针前调 else error 如果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|-T TF|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=