编译原理编译原理编译原理编译原理 第四章第四章 自上向下语法分析自上向下语法分析vv语法分析的任务语法分析的任务vv本章要点：本章要点：自上而下语法分析的思想自上而下语法分析的思想LL（1）方法方法递归下降分析递归下降分析预测分析预测分析 编译原理编译原理编译原理编译原理 基本思想基本思想vv主旨主旨 对任何输入串，试图用一切可能，从文法的对任何输入串，试图用一切可能，从文法的开始符号出发，自上而下地为输入串建立一开始符号出发，自上而下地为输入串建立一棵语法树，或者为输入串寻找一个最左推导。棵语法树，或者为输入串寻找一个最左推导。vv本质上是一种试探过程本质上是一种试探过程 编译原理编译原理编译原理编译原理 要解决的基本问题要解决的基本问题 例：例：GS：SxAy A* | * 考虑输入串考虑输入串x*y 对于特定的非终结符号，使用哪个产生式来对于特定的非终结符号，使用哪个产生式来替换？替换？ 编译原理编译原理编译原理编译原理 带带回溯的自上而下语法分析回溯的自上而下语法分析存在的困难和缺点存在的困难和缺点vv文法的递归性文法的递归性vv虚假匹配虚假匹配vv错误的位置难以确定错误的位置难以确定vv效率低，代价高效率低，代价高 编译原理编译原理编译原理编译原理 无回溯的自上向下分析技术无回溯的自上向下分析技术vv先决条件：先决条件： 无左递归无左递归 既没有直接左递归，也没有间接左递归。既没有直接左递归，也没有间接左递归。既没有直接左递归，也没有间接左递归。既没有直接左递归，也没有间接左递归。 无回溯性无回溯性对于任一非终结符号对于任一非终结符号对于任一非终结符号对于任一非终结符号U U的产生式右部的产生式右部的产生式右部的产生式右部x x1 1|x|x2 2|x xn n，各，各，各，各x xi i的首终结符号两两不相交。的首终结符号两两不相交。的首终结符号两两不相交。的首终结符号两两不相交。 编译原理编译原理编译原理编译原理 文法的左递归性文法的左递归性vv定义：定义： 文法的左递归性是指文法具有以下形式的直文法的左递归性是指文法具有以下形式的直接左递归：接左递归： U Ux|y 或间接左递归：或间接左递归： U=+Ux 编译原理编译原理编译原理编译原理 具有左递归性的文法举例具有左递归性的文法举例vvE E+T|TvvT T*F|FvvF (E)|i 编译原理编译原理编译原理编译原理 消除文法的直接左递归消除文法的直接左递归 PP1 | | Pn | 1 | | m改写为：改写为： P 1P| | mP P 1P| | nP| 编译原理编译原理编译原理编译原理 例子例子消除左递归前消除左递归前EE+T|TTT*F|FF(E)|i消除左递归后消除左递归后l lET E l lE +TE | l lTFT l lT *FT | l lF(E)|i 编译原理编译原理编译原理编译原理 间接左递归举例间接左递归举例SQc|cQRb|bRSa|a 以上文法不含直接左递归，但以上文法不含直接左递归，但S，Q，R都是左递归的，因为：都是左递归的，因为：S=QcQc =RbcRbc =SabcSabcQ Q =RbRb =SabSab =QabcQabcR =SaSa =QcaQca =RbcaRbca 编译原理编译原理编译原理编译原理 消除文法的左递归消除文法的左递归前提：如果一个文法不含回路（形如前提：如果一个文法不含回路（形如P + P的推导），也不含的推导），也不含以以 为为右部的产生式，右部的产生式，那么可以通过执行消除文法左递归的算那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法消除文法的一切左递归（改写后的文法可能含有以法可能含有以 为右部的产生式）。为右部的产生式）。 编译原理编译原理编译原理编译原理 消除文法的一切左递归的算法消除文法的一切左递归的算法1 1、把文法的所有非终结符按任一顺序排序、把文法的所有非终结符按任一顺序排序、把文法的所有非终结符按任一顺序排序、把文法的所有非终结符按任一顺序排序2 2、FOR i=1 TO n DOFOR i=1 TO n DO (1) FOR j=1 TO i-1 DO (1) FOR j=1 TO i-1 DO 把形如把形如把形如把形如P Pi iPPj j 的规则改写成的规则改写成的规则改写成的规则改写成 P Pi i1 1| | | | k k 其中其中其中其中P Pj j1 1| | |k k是是是是关于关于关于关于P Pj j的所有规则的所有规则的所有规则的所有规则 (2)(2)消除关于规则的直接左递归消除关于规则的直接左递归消除关于规则的直接左递归消除关于规则的直接左递归3 3、化简由、化简由、化简由、化简由2 2所得的文法所得的文法所得的文法所得的文法 编译原理编译原理编译原理编译原理 例子例子vvABcdvvBCe|fvvCAb|c 编译原理编译原理编译原理编译原理 消除回溯的基本思想消除回溯的基本思想 必须保证对文法的任何非终结符，当要它去必须保证对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符匹配输入串时，能够根据它所面临的输入符号，指派它的一个候选（右部）去执行任务，号，指派它的一个候选（右部）去执行任务，并且此候选的工作结果应是确定无疑的：即并且此候选的工作结果应是确定无疑的：即要么匹配成功，要么不可能获得匹配。要么匹配成功，要么不可能获得匹配。 编译原理编译原理编译原理编译原理 消除回溯对文法的要求消除回溯对文法的要求1 1、首先，文法不得含有左递归；、首先，文法不得含有左递归；、首先，文法不得含有左递归；、首先，文法不得含有左递归；2 2、设文法设文法设文法设文法GG不含左递归，对不含左递归，对不含左递归，对不含左递归，对GG的的的的所有非终结符的每个所有非终结符的每个所有非终结符的每个所有非终结符的每个候选候选候选候选 定义其终结首符集定义其终结首符集定义其终结首符集定义其终结首符集FIRST() FIRST() 为为为为 FIRST()=a| =FIRST()=a| = *a,a*a,aV VT T 特别是，若特别是，若特别是，若特别是，若 = = *，则规定则规定则规定则规定 FIRST() FIRST() 。如果如果如果如果非终结符非终结符非终结符非终结符A A的所有候选首符集两两不相交，那么，的所有候选首符集两两不相交，那么，的所有候选首符集两两不相交，那么，的所有候选首符集两两不相交，那么，当要求当要求当要求当要求A A匹配输入串时，匹配输入串时，匹配输入串时，匹配输入串时，A A就能根据它所面临的第一就能根据它所面临的第一就能根据它所面临的第一就能根据它所面临的第一个输入符号个输入符号个输入符号个输入符号a a，准确地指派某一个候选去执行任务。准确地指派某一个候选去执行任务。准确地指派某一个候选去执行任务。准确地指派某一个候选去执行任务。这个候选就是那个终结首符集含这个候选就是那个终结首符集含这个候选就是那个终结首符集含这个候选就是那个终结首符集含a a的的的的 。 编译原理编译原理编译原理编译原理 消除回溯方法：提取公共左因子消除回溯方法：提取公共左因子vv假设关于假设关于假设关于假设关于A A的产生式是的产生式是的产生式是的产生式是 AA1 1| | 2 2| | | | n n| | n+1n+1 那么，可以将其改写为那么，可以将其改写为那么，可以将其改写为那么，可以将其改写为 A A | A A | n+1n+1 A A 1 1| | 2 2| | | | n n vv经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符（包括新引进者）的多有候选首符集变成为两两（包括新引进者）的多有候选首符集变成为两两（包括新引进者）的多有候选首符集变成为两两（包括新引进者）的多有候选首符集变成为两两不相交。不相交。不相交。不相交。vv代价：引入大量新的非终结符和空产生式。代价：引入大量新的非终结符和空产生式。代价：引入大量新的非终结符和空产生式。代价：引入大量新的非终结符和空产生式。 编译原理编译原理编译原理编译原理 vvGS：S Bx B x | 考虑输入串考虑输入串xvvFOLLOW(U)=b|S = *xUby, bVT , x,y （VNVT)* ；特别地，；特别地，# FOLLOW(S)。 编译原理编译原理编译原理编译原理 LL(1)分析条件分析条件vv文法不含左递归文法不含左递归vv设设U是文法是文法G的任一个非终结符，其产生式的任一个非终结符，其产生式为为 Ux1 1|x2 2|xn n 如果如果 FIRST(xi i)FIRST(xj j) = (ij, i,j=1,2,n) (ij, i,j=1,2,n) vv当当 FIRST(xi i) 时，有时，有 FIRST(xi i) FOLLOW(U) = 则文法则文法G为为LL(1)文法。文法。 编译原理编译原理编译原理编译原理 LL(1)方法方法vv基本思想：从基本思想：从S出发，生成句子的最左推导。出发，生成句子的最左推导。vv选择合适产生式：从左到右扫描源程序，每选择合适产生式：从左到右扫描源程序，每次通过向前查看次通过向前查看1个字符，选择合适的产生式。个字符，选择合适的产生式。vv适用范围：仅适用范围：仅对对LL(1)文法适用。文法适用。 编译原理编译原理编译原理编译原理 FIRST()和和FOLLOW(U)vv定义：定义：定义：定义： 1 1、FIRST()=a| =FIRST()=a| = *a,a*a,aV VT T , , （V VN NV VT T)* )* ；特别地，特别地，特别地，特别地，如果如果如果如果 =* =* ，那么，我们规定那么，我们规定那么，我们规定那么，我们规定 FIRST()FIRST()。 2 2、FOLLOW(U)=b|S =FOLLOW(U)=b|S = * *xUbyxUby, b, bV VT T , x,y , x,y （V VN NV VT T)* )* ；特别地，特别地，特别地，特别地，# # FOLLOW(S)FOLLOW(S)。vv直观地讲：直观地讲：直观地讲：直观地讲：FIRST(u)FIRST(u)包含了包含了包含了包含了u u对应的字的所有可能的首终结符号。对应的字的所有可能的首终结符号。对应的字的所有可能的首终结符号。对应的字的所有可能的首终结符号。FOLLOW(U)FOLLOW(U)表示了句型中可能紧跟表示了句型中可能紧跟表示了句型中可能紧跟表示了句型中可能紧跟再再再再U U后面的终结符号。后面的终结符号。后面的终结符号。后面的终结符号。 编译原理编译原理编译原理编译原理 FIRST() 构造算法构造算法vv对于对于对于对于X X(V(VN NV VT T）,FIRST(X) ,FIRST(X) 的构造的构造的构造的构造1 1：若：若：若：若X X V VT T，则，则，则，则FIRST(X)=XFIRST(X)=X2 2：若若若若X X V VN N，且有产生且有产生且有产生且有产生式式式式Xa, a Xa, a V VT T ，则，则，则，则a a FIRST(X)FIRST(X)；如果如果如果如果X X ，那么那么那么那么 FIRST(X)FIRST(X)。3 3：若若若若有产生式有产生式有产生式有产生式X Y,Y X Y,Y V VN N , ,则则则则FIRST(Y) FIRST(Y) FIRST(X);FIRST(X); 如果有产生式如果有产生式如果有产生式如果有产生式XXY Y1 1Y Y2 2YYK K, ,其中其中其中其中Y Y1 1，Y Y2 2，Y Yi i1 1 V VN N且且且且Y Y1 1Y Y2 2YYi i1 1 = * * , , 则则则则FIRST(YFIRST(Yi i) ) FIRST(X)FIRST(X)；若若若若Y Y1 1Y Y2 2YYK K = * * ，则则则则 FIRST(X)FIRST(X)。 编译原理编译原理编译原理编译原理 FIRST() 构造算法构造算法(续续)vv设设 (VNVT）*, = X1X2Xn ，FIRST() 的构造的构造1 1：若若若若 = = ，则，则，则，则FIRST(FIRST( )=)= 2 2：若若若若 ，则，则，则，则FIRST(FIRST(X X1 1) ) FIRST(FIRST( ) )。3 3：若若若若X X1 1X X2 2。X Xi i1 1 = * * , , 则则则则FIRST(XFIRST(Xi i) ) FIRST(FIRST( ) )；若若若若X X1 1X X2 2X Xn n = * * , , 则则则则 FIRST(FIRST( ) )。 编译原理编译原理编译原理编译原理 FOLLOW(U)的构造算法的构造算法 1、# FOLLOW(S) 2、如果有产生式如果有产生式AxUy，那么那么FIRST(y) FOLLOW(U)。 3、如果有产生式如果有产生式AxU或则或则 AxUy且且y = * ，那么那么FOLLOW(A) FOLLOW(U) 。vv注意：步骤注意：步骤3需要重复执行，直到没有哪个需要重复执行，直到没有哪个非终结符号非终结符号的的FOLLOW集合增长为止。集合增长为止。 编译原理编译原理编译原理编译原理 FIRST的例子的例子vv文法文法文法文法GE:GE:ETEETEE+TE| E+TE| TFTTFTT*FT| T*FT| F(E)|iF(E)|ivvFIRST(F)= (FIRST(F)= (，i i vvFIRST(T)=FIRST(F)= (FIRST(T)=FIRST(F)= (，i i vvFIRST(E)= +FIRST(E)= +， FIRST(T)=*, FIRST(T)=*, 编译原理编译原理编译原理编译原理 FOLLOW例子例子vv文法文法文法文法GE:GE:ETEETEE+TE| E+TE| TFTTFTT*FT| T*FT| F(E)|iF(E)|ivvFOLLOW(E)=#,)FOLLOW(E)=#,)vvFOLLOW(E)=FOLLOW(E)=#,)FOLLOW(E)=FOLLOW(E)=#,)vvFOLLOW(T)=FIRST(E)FOLLOW(T)=FIRST(E) FOLLOW(E)-FOLLOW(E)- =+,#,)=+,#,)vvFOLLOW(T)=FOLLOW(T)= FOLLOW(T)=FOLLOW(T)= =+,#,)=+,#,)vvFOLLOW(F)=FIRST(T) FOLLOW(F)=FIRST(T) FOLLOW(T)= FOLLOW(T)= +,#,),*+,#,),* 编译原理编译原理编译原理编译原理 例子例子 求求FIRST集与集与FOLLOW举例：举例： 文法文法GA: AB BXB BAB| XaX|bX XaX|bX| 编译原理编译原理编译原理编译原理 递归下降分析程序（实现思想）递归下降分析程序（实现思想）vv实现思想：实现思想：识别程序由一组子程序组成。每个子程序对应于识别程序由一组子程序组成。每个子程序对应于识别程序由一组子程序组成。每个子程序对应于识别程序由一组子程序组成。每个子程序对应于一个非终结符号。一个非终结符号。一个非终结符号。一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描每一个子程序的功能是：选择正确的右部，扫描每一个子程序的功能是：选择正确的右部，扫描每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该完相应的字。在右部中有非终结符号时，调用该完相应的字。在右部中有非终结符号时，调用该完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。非终结符号对应的子程序来完成。非终结符号对应的子程序来完成。非终结符号对应的子程序来完成。 编译原理编译原理编译原理编译原理 基本架构基本架构(1)vv变量：变量：变量：变量： symsym：当前符号：当前符号：当前符号：当前符号vv函数：函数：函数：函数：advance( )advance( )：读输入串下一符号：读输入串下一符号：读输入串下一符号：读输入串下一符号vv对于每个非终结符号对于每个非终结符号对于每个非终结符号对于每个非终结符号U U 1 1| | 2 2| | n n处理的方法如下：处理的方法如下：处理的方法如下：处理的方法如下：P(U) P(U) if sym if sym FIRST(FIRST(1 1 )then P( )then P(1 1) )/ /处理处理处理处理11的程序部分的程序部分的程序部分的程序部分 else if sym else if sym FIRST(FIRST(2 2 )then P( )then P(2 2) ) / /处理处理处理处理22的程序部分的程序部分的程序部分的程序部分 else if sym else if sym FIRST(FIRST(n n )then P( )then P(n n) ) else if sym else if sym FOLLOW(U)thenFOLLOW(U)then return return / /处理空产生式情况处理空产生式情况处理空产生式情况处理空产生式情况 else error else error vv对于无回溯的文法保证选择是唯一的。对于无回溯的文法保证选择是唯一的。对于无回溯的文法保证选择是唯一的。对于无回溯的文法保证选择是唯一的。 编译原理编译原理编译原理编译原理 基本架构基本架构(2)vv对于每个右部对于每个右部对于每个右部对于每个右部 =x =x1 1x x2 2x xn n的处理架构如下：的处理架构如下：的处理架构如下：的处理架构如下：P(P() ) P(x P(x1 1 ); ); / /处理处理处理处理x x1 1的程序的程序的程序的程序 P(xP(x2 2 ); ); / /处理处理处理处理x x2 2的程序的程序的程序的程序 P(xP(xn n ); ); / /处理处理处理处理x xn n的程序的程序的程序的程序 vv说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。 编译原理编译原理编译原理编译原理 基本架构基本架构(3)vv对于右部中的每个符号对于右部中的每个符号对于右部中的每个符号对于右部中的每个符号x xi ivv如果如果如果如果x xi i为终结符号：为终结符号：为终结符号：为终结符号：if(symif(sym= a)= a)sym=sym=下一输入符号下一输入符号下一输入符号下一输入符号 / /对于终结符，直接将指针前调对于终结符，直接将指针前调对于终结符，直接将指针前调对于终结符，直接将指针前调elseelseerrorerrorvv如果如果如果如果x xi i为非终结符号，直接调用相应的过程：为非终结符号，直接调用相应的过程：为非终结符号，直接调用相应的过程：为非终结符号，直接调用相应的过程： P (xP (xi i) ) 编译原理编译原理编译原理编译原理 扩展扩展的的BNF表示法表示法vv花括号花括号花括号花括号 x: x:表示符号串表示符号串表示符号串表示符号串x x出现出现出现出现0 0次或多次，即次或多次，即次或多次，即次或多次，即 x*x* x xn nmm: m: m表示符号串表示符号串表示符号串表示符号串x x能出现的最大次数，能出现的最大次数，能出现的最大次数，能出现的最大次数，n n表示符表示符表示符表示符号串号串号串号串x x能出现的最小次数能出现的最小次数能出现的最小次数能出现的最小次数vv方括号方括号方括号方括号 表示表示表示表示xx0 01 1 。vv圆括号（）圆括号（）圆括号（）圆括号（） 利用圆括号可以提出非终结符的多个产生式右部的利用圆括号可以提出非终结符的多个产生式右部的利用圆括号可以提出非终结符的多个产生式右部的利用圆括号可以提出非终结符的多个产生式右部的公共因子。公共因子。公共因子。公共因子。 编译原理编译原理编译原理编译原理 vvE E+T|E-T|T 可改成可改成 E T+T| -T vvT T*F|T/F|F 可改成可改成 T F*F| /F用扩展的用扩展的BNF表示法消除左递归表示法消除左递归 编译原理编译原理编译原理编译原理 例子例子| 以上标识符产生式含有左递归，可以改写为：以上标识符产生式含有左递归，可以改写为：| 编译原理编译原理编译原理编译原理 Z(U)|aUb过程过程Zadvance( )U出口出口语法错误：语法错误：输入串少输入串少)sym =aYNNNNYY语法错误：语法错误：输入串少输入串少(、a语法错误：语法错误：输入串少输入串少bsym =(sym =)sym =badvance( )advance( )UY 编译原理编译原理编译原理编译原理 ET|E+T|E-T ET+T|-TET|E+T|E-T ET+T|-TTF|T*F|T/F TF*F| /FTF|T*F|T/F TF*F| /FETYN出口出口advance( )sym =+sym =-NYTFYN出口出口advance( )sym =*sym =/NY 编译原理编译原理编译原理编译原理 有文法有文法有文法有文法GZGZ： ZAcB|BdZAcB|Bd A A AaB|cAaB|c B B aA|aaA|a设计递归下降分析程序。设计递归下降分析程序。设计递归下降分析程序。设计递归下降分析程序。思考题思考题 编译原理编译原理编译原理编译原理 预测分析程序的结构预测分析程序的结构 使用一个二维分析表和栈联合进行控制来实现语法分析。使用一个二维分析表和栈联合进行控制来实现语法分析。使用一个二维分析表和栈联合进行控制来实现语法分析。使用一个二维分析表和栈联合进行控制来实现语法分析。 总控程序大同小异，而总控程序大同小异，而总控程序大同小异，而总控程序大同小异，而LLLL（1 1）分析表却千差万别。分析表却千差万别。分析表却千差万别。分析表却千差万别。 LLLL（1 1）分析表是进行分析表是进行分析表是进行分析表是进行LLLL（1 1）分析的核心。分析的核心。分析的核心。分析的核心。输入符号串：输入符号串： 分析栈分析栈a1a2an# XZS#LL（1）总控程序总控程序分析表分析表输出流输出流 编译原理编译原理编译原理编译原理 预测分析表的结构预测分析表的结构 分析表实际上是一个从分析表实际上是一个从VN (VT #)到到产生式的映射，通常以矩阵表示。产生式的映射，通常以矩阵表示。其元其元素素MU,a中可能存放一条非终结符中可能存放一条非终结符U的产的产生式，说明当符号栈生式，说明当符号栈S的栈顶元素非终结的栈顶元素非终结符符U遇到当前输入字符遇到当前输入字符a时，所应选择的时，所应选择的产生式；元素产生式；元素MU,a也可存放一个出错也可存放一个出错标志，说明符号标志，说明符号栈栈S的栈顶元素非终结符的栈顶元素非终结符U不应遇到当前输入符号不应遇到当前输入符号a。 编译原理编译原理编译原理编译原理 预测分析器的总控原理预测分析器的总控原理vv在在在在任何时候，总控程序都是按照栈顶符号任何时候，总控程序都是按照栈顶符号任何时候，总控程序都是按照栈顶符号任何时候，总控程序都是按照栈顶符号X X和当前输入符号和当前输入符号和当前输入符号和当前输入符号a a工作的。对于任何（工作的。对于任何（工作的。对于任何（工作的。对于任何（X X，a a），），），），总控程序每次都执行下述三种总控程序每次都执行下述三种总控程序每次都执行下述三种总控程序每次都执行下述三种可能的动作之一：可能的动作之一：可能的动作之一：可能的动作之一：vv1 1、若、若、若、若X Xa a ，则宣布分析成功，停止分析过程；则宣布分析成功，停止分析过程；则宣布分析成功，停止分析过程；则宣布分析成功，停止分析过程；vv2 2、若、若、若、若X Xaa ，则把，则把，则把，则把X X从栈顶逐出，从栈顶逐出，从栈顶逐出，从栈顶逐出，让让让让a a指向下一输入符指向下一输入符指向下一输入符指向下一输入符号；号；号；号；vv3 3、若若若若X X是是是是一个非终结符，则查看分析表一个非终结符，则查看分析表一个非终结符，则查看分析表一个非终结符，则查看分析表MM。若。若。若。若MM中存放着一中存放着一中存放着一中存放着一条关于条关于条关于条关于X X的产生式，那么，首先把的产生式，那么，首先把的产生式，那么，首先把的产生式，那么，首先把X X逐出栈顶，然后，把产生逐出栈顶，然后，把产生逐出栈顶，然后，把产生逐出栈顶，然后，把产生式的右部符号按式的右部符号按式的右部符号按式的右部符号按反序反序反序反序一一推进栈，同时做这个产生式相应的一一推进栈，同时做这个产生式相应的一一推进栈，同时做这个产生式相应的一一推进栈，同时做这个产生式相应的语义动作（目前不管）。若语义动作（目前不管）。若语义动作（目前不管）。若语义动作（目前不管）。若MX,aMX,a中存放着一条出错标志，中存放着一条出错标志，中存放着一条出错标志，中存放着一条出错标志，则调用出错诊查程序则调用出错诊查程序则调用出错诊查程序则调用出错诊查程序ErrorError。 编译原理编译原理编译原理编译原理 例子例子vv文法文法GE E TE E +TE | T FT T *FT | F (E)|i 编译原理编译原理编译原理编译原理 例子例子i+*)#(ETETEE+TETFTFTT*FTFi(E)i+i*i#i+i*i#+i*i#i*i#+i*i#i+i*i#+i*i#i+i*i#i*i#i*i#E#ET#ETF#ET+#ET#ET#ETi#E#ETi#ETF 编译原理编译原理编译原理编译原理 预测分析表的生成预测分析表的生成vv从前面的论述我们看到，预测分析法的从前面的论述我们看到，预测分析法的总控程序是固定的。对于某个文法，分总控程序是固定的。对于某个文法，分析表是分析过程的核心。析表是分析过程的核心。vv表中表中MU,a=UX1X2Xn表示对应表示对应于于X1X2Xn字的首符号可以字的首符号可以是是a。就是说就是说X1X2Xn=*a。我们可以通过这个方我们可以通过这个方式来确定分析表中的值。式来确定分析表中的值。 编译原理编译原理编译原理编译原理 预测分析表的生成预测分析表的生成vv一般来讲，对于一个符号串一般来讲，对于一个符号串X1X2Xn的字的的字的第一个终结符号就是第一个终结符号就是X1对应的字的第一个终对应的字的第一个终结符号。但是空产生式的存在使情况有一点结符号。但是空产生式的存在使情况有一点复杂。复杂。vv对于对于U1U2Un，如果如果U1=* ，那么符号串对那么符号串对应的字的首符号也可以是应的字的首符号也可以是U2对应的字的首符对应的字的首符号。计算一个符号串对应的字的首符号的算号。计算一个符号串对应的字的首符号的算法也需要考虑到这些法也需要考虑到这些。 编译原理编译原理编译原理编译原理 预测分析表的构造预测分析表的构造vv基本思想：基本思想： 当我们需要当我们需要将将U选择某个产生式展开时，如果选择某个产生式展开时，如果当前的输入为当前的输入为a，表示我们要表示我们要将将U展开展开为以为以a为首符号的字。如果有产生式为首符号的字。如果有产生式Uu，且，且a FIRST(u)，那么表示这个那么表示这个产生式产生式是个好的是个好的选择。选择。 编译原理编译原理编译原理编译原理 分析表构造算法分析表构造算法vv对于每个产生对于每个产生式式U ，执行一下步骤执行一下步骤对于每个终结符号对于每个终结符号对于每个终结符号对于每个终结符号a a FIRST()FIRST()，MU,a=U.MU,a=U.如果如果如果如果 FIRST( )FIRST( )，对于每个终结符号对于每个终结符号对于每个终结符号对于每个终结符号b b FOLLOW(U)FOLLOW(U)，MU,b=U MU,b=U 。vv将其它未定义的分析表元素置为将其它未定义的分析表元素置为ERROR。 编译原理编译原理编译原理编译原理 分析表的例子分析表的例子vv文法文法文法文法GE:GE:ETEETE E+TE| E+TE| TFT TFTT*FT| T*FT| F(E)|i F(E)|ii+*)#(ETETEETETFTFTTFTFi(E) 编译原理编译原理编译原理编译原理 分析表的冲突分析表的冲突vv文法文法GS SiCtSS|a SeS| CbvvFIRST(iCtSS)=iFIRST(eS)=evvFIRST(S)=i,aFIRST(C)=bvvFIRST(S)=e, vvFOLLOW(S)=FOLLOW(S)=#,eabeit#SaiCtSSSeS; Cb 编译原理编译原理编译原理编译原理 LL(1)文法文法vvLL(1)文法，其预测分析表中没有多重定义的文法，其预测分析表中没有多重定义的元素，则该文法被称为元素，则该文法被称为LL(1)文法。文法。vvLL(1)文法是无二义性的。文法是无二义性的。