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

《编译原理自上而下语法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理自上而下语法分析.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 编译原理编译原理编译原理编译原理 第四章第四章 自上向下语法分析自上向下语法分析vv语法分析的任务语法分析的任务vv本章要点：本章要点：自上而下语法分析的思想自上而下语法分析的思想LL（1）方法）方法递归下降分析递归下降分析预测分析预测分析 编译原理编译原理编译原理编译原理 基本思想基本思想vv主旨主旨 对任何输入串，试图用一切可能，从文法的对任何输入串，试图用一切可能，从文法的开始符号出发，自上而下地为输入串建立一开始符号出发，自上而下地为输入串建立一棵语法树，或者为输入串寻找一个最左推导。棵语法树，或者为输入串寻找一个最左推导。vv本质上是一种试探过程本质上是一种试探过程 编译原理编译原

2、理编译原理编译原理 要解决的基本问题要解决的基本问题 例：例：GS：SxAy A*|*考虑输入串考虑输入串x*y 对于特定的非终结符号，使用哪个产生式来对于特定的非终结符号，使用哪个产生式来替换？替换？编译原理编译原理编译原理编译原理 带回溯的自上而下语法分析带回溯的自上而下语法分析存在的困难和缺点存在的困难和缺点vv文法的递归性文法的递归性vv虚假匹配虚假匹配vv错误的位置难以确定错误的位置难以确定vv效率低，代价高效率低，代价高 编译原理编译原理编译原理编译原理 无回溯的自上向下分析技术无回溯的自上向下分析技术vv先决条件：先决条件：无左递归无左递归 既没有直接左递归，也没有间接左递归。既

3、没有直接左递归，也没有间接左递归。既没有直接左递归，也没有间接左递归。既没有直接左递归，也没有间接左递归。无回溯性无回溯性对于任一非终结符号对于任一非终结符号对于任一非终结符号对于任一非终结符号U U的产生式右部的产生式右部的产生式右部的产生式右部x x1 1|x|x2 2|x|xn n，各，各，各，各x xi i的首终结符号两两不相交。的首终结符号两两不相交。的首终结符号两两不相交。的首终结符号两两不相交。编译原理编译原理编译原理编译原理 文法的左递归性文法的左递归性vv定义：定义：文法的左递归性是指文法具有以下形式的直文法的左递归性是指文法具有以下形式的直接左递归：接左递归：U Ux|y

4、或间接左递归：或间接左递归：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|cQR

5、b|bRSa|a 以上文法不含直接左递归，但以上文法不含直接左递归，但S，Q，R都是左递归的，因为：都是左递归的，因为：S=QcQc=RbcRbc=SabcSabcQ Q=RbRb=SabSab=QabcQabcR=SaSa=QcaQca=RbcaRbca 编译原理编译原理编译原理编译原理 消除文法的左递归消除文法的左递归前提：如果一个文法不含回路（形如前提：如果一个文法不含回路（形如P+P的推导），也不含以的推导），也不含以 为右部的产生式，为右部的产生式，那么可以通过执行消除文法左递归的算那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法消除文法的一切左递归（改写后的文

6、法可能含有以法可能含有以 为右部的产生式）。为右部的产生式）。编译原理编译原理编译原理编译原理 消除文法的一切左递归的算法消除文法的一切左递归的算法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 P

7、j j1 1|k k是关于是关于是关于是关于P Pj j的所有规则的所有规则的所有规则的所有规则 (2)(2)消除关于规则的直接左递归消除关于规则的直接左递归消除关于规则的直接左递归消除关于规则的直接左递归3 3、化简由、化简由、化简由、化简由2 2所得的文法所得的文法所得的文法所得的文法 编译原理编译原理编译原理编译原理 例子例子vvABcdvvBCe|fvvCAb|c 编译原理编译原理编译原理编译原理 消除回溯的基本思想消除回溯的基本思想 必须保证对文法的任何非终结符，当要它去必须保证对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符匹配输入串时，能够根据它所面临的输入符

8、号，指派它的一个候选（右部）去执行任务，号，指派它的一个候选（右部）去执行任务，并且此候选的工作结果应是确定无疑的：即并且此候选的工作结果应是确定无疑的：即要么匹配成功，要么不可能获得匹配。要么匹配成功，要么不可能获得匹配。编译原理编译原理编译原理编译原理 消除回溯对文法的要求消除回溯对文法的要求1 1、首先，文法不得含有左递归；、首先，文法不得含有左递归；、首先，文法不得含有左递归；、首先，文法不得含有左递归；2 2、设文法、设文法、设文法、设文法GG不含左递归，对不含左递归，对不含左递归，对不含左递归，对GG的所有非终结符的每个的所有非终结符的每个的所有非终结符的每个的所有非终结符的每个候

9、选候选候选候选 定义其终结首符集定义其终结首符集定义其终结首符集定义其终结首符集FIRST()FIRST()为为为为 FIRST()=a|=FIRST()=a|=*a,a*a,aV VT T 特别是，若特别是，若特别是，若特别是，若=*，则规定，则规定，则规定，则规定 FIRST()FIRST()。如果。如果。如果。如果非终结符非终结符非终结符非终结符A A的所有候选首符集两两不相交，那么，的所有候选首符集两两不相交，那么，的所有候选首符集两两不相交，那么，的所有候选首符集两两不相交，那么，当要求当要求当要求当要求A A匹配输入串时，匹配输入串时，匹配输入串时，匹配输入串时，A A就能根据它所

10、面临的第一就能根据它所面临的第一就能根据它所面临的第一就能根据它所面临的第一个输入符号个输入符号个输入符号个输入符号a a，准确地指派某一个候选去执行任务。，准确地指派某一个候选去执行任务。，准确地指派某一个候选去执行任务。，准确地指派某一个候选去执行任务。这个候选就是那个终结首符集含这个候选就是那个终结首符集含这个候选就是那个终结首符集含这个候选就是那个终结首符集含a a的的的的。编译原理编译原理编译原理编译原理 消除回溯方法：提取公共左因子消除回溯方法：提取公共左因子vv假设关于假设关于假设关于假设关于A A的产生式是的产生式是的产生式是的产生式是 A A1 1|2 2|n n|n+1n+

11、1 那么，可以将其改写为那么，可以将其改写为那么，可以将其改写为那么，可以将其改写为 A A|A A|n+1n+1 A A 1 1|2 2|n n vv经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符经过反复提取左因子，就能够把每个非终结符（包括新引进者）的多有候选首符集变成为两两（包括新引进者）的多有候选首符集变成为两两（包括新引进者）的多有候选首符集变成为两两（包括新引进者）的多有候选首符集变成为两两不相交。不相交。不相交。不相交。vv代价：引入大量新的非终结符和空产生式。代价：引入大量新的非终结符和空产生式。代价：引

12、入大量新的非终结符和空产生式。代价：引入大量新的非终结符和空产生式。编译原理编译原理编译原理编译原理 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当当 FIR

13、ST(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|=F

14、IRST()=a|=*a,a*a,aV VT T,（V VN NV VT T)*)*；特别地，；特别地，；特别地，；特别地，如果如果如果如果 =*=*，那么，我们规定，那么，我们规定，那么，我们规定，那么，我们规定 FIRST()FIRST()。2 2、FOLLOW(U)=b|S=FOLLOW(U)=b|S=*xUby,b*xUby,bV VT T,x,y,x,y（V VN NV VT T)*)*；特别地，；特别地，；特别地，；特别地，#FOLLOW(S)FOLLOW(S)。vv直观地讲：直观地讲：直观地讲：直观地讲：FIRST(u)FIRST(u)包含了包含了包含了包含了u u对应的字的所有

15、可能的首终结符号。对应的字的所有可能的首终结符号。对应的字的所有可能的首终结符号。对应的字的所有可能的首终结符号。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：若若若若

16、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 Y

17、2 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

18、(XFIRST(Xi i)FIRST(FIRST()；若若若若X X1 1X X2 2XXn 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集合增长为止。集合增长为止。编译原理编译原理编译

19、原理编译原理 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)=#,)FOL

20、LOW(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举例：举例：文法

21、文法GA:AB BXB BAB|XaX|bX XaX|bX|编译原理编译原理编译原理编译原理 递归下降分析程序（实现思想）递归下降分析程序（实现思想）vv实现思想：实现思想：识别程序由一组子程序组成。每个子程序对应于识别程序由一组子程序组成。每个子程序对应于识别程序由一组子程序组成。每个子程序对应于识别程序由一组子程序组成。每个子程序对应于一个非终结符号。一个非终结符号。一个非终结符号。一个非终结符号。每一个子程序的功能是：选择正确的右部，扫描每一个子程序的功能是：选择正确的右部，扫描每一个子程序的功能是：选择正确的右部，扫描每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终

22、结符号时，调用该完相应的字。在右部中有非终结符号时，调用该完相应的字。在右部中有非终结符号时，调用该完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。非终结符号对应的子程序来完成。非终结符号对应的子程序来完成。非终结符号对应的子程序来完成。编译原理编译原理编译原理编译原理 基本架构基本架构(1)vv变量：变量：变量：变量：sym sym：当前符号：当前符号：当前符号：当前符号vv函数：函数：函数：函数：advance()advance()：读输入串下一符号：读输入串下一符号：读输入串下一符号：读输入串下一符号vv对于每个非终结符号对于每个非终结符号对于每个非终结符号对于每

23、个非终结符号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

24、sym else if sym FOLLOW(U)then return FOLLOW(U)then return/处理空产生式情况处理空产生式情况处理空产生式情况处理空产生式情况 else error else error vv对于无回溯的文法保证选择是唯一的。对于无回溯的文法保证选择是唯一的。对于无回溯的文法保证选择是唯一的。对于无回溯的文法保证选择是唯一的。编译原理编译原理编译原理编译原理 基本架构基本架构(2)vv对于每个右部对于每个右部对于每个右部对于每个右部=x=x1 1x x2 2xxn n的处理架构如下：的处理架构如下：的处理架构如下：的处理架构如下：P()P()P(x P(x

25、1 1););/处理处理处理处理x x1 1的程序的程序的程序的程序 P(x P(x2 2););/处理处理处理处理x x2 2的程序的程序的程序的程序 P(x P(xn n););/处理处理处理处理x xn n的程序的程序的程序的程序 vv说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。说明：如果右部为空，则不处理。编译原理编译原理编译原理编译原理 基本架构基本架构(3)vv对于右部中的每个符号对于右部中的每个符号对于右部中的每个符号对于右部中的每个符号x xi ivv如果如果如果如果x xi i为终结符号：为终结符号：为终结符号：为终结符号：if(

26、sym=a)if(sym=a)sym=sym=下一输入符号下一输入符号下一输入符号下一输入符号 /对于终结符，直接将指针前调对于终结符，直接将指针前调对于终结符，直接将指针前调对于终结符，直接将指针前调elseelseerrorerrorvv如果如果如果如果x xi i为非终结符号，直接调用相应的过程：为非终结符号，直接调用相应的过程：为非终结符号，直接调用相应的过程：为非终结符号，直接调用相应的过程：P(x P(xi i)编译原理编译原理编译原理编译原理 扩展的扩展的BNF表示法表示法vv花括号花括号花括号花括号 x:x:表示符号串表示符号串表示符号串表示符号串x x出现出现出现出现0 0次

27、或多次，即次或多次，即次或多次，即次或多次，即 x*x*x xn nmm:m:m表示符号串表示符号串表示符号串表示符号串x x能出现的最大次数，能出现的最大次数，能出现的最大次数，能出现的最大次数，n n表示符表示符表示符表示符号串号串号串号串x x能出现的最小次数能出现的最小次数能出现的最小次数能出现的最小次数vv方括号方括号方括号方括号 表示表示表示表示xx0 01 1 。vv圆括号（）圆括号（）圆括号（）圆括号（）利用圆括号可以提出非终结符的多个产生式右部的利用圆括号可以提出非终结符的多个产生式右部的利用圆括号可以提出非终结符的多个产生式右部的利用圆括号可以提出非终结符的多个产生式右部的

28、公共因子。公共因子。公共因子。公共因子。编译原理编译原理编译原理编译原理 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语法错误：语法错误：输入串少输入串

29、少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|Bd ZAcB|Bd A A AaB|cAaB|c B B aA|aaA|a设计递归下降分析程序。设计递归下降分析程序。设计递归下降分析程序。设计递归

30、下降分析程序。思考题思考题 编译原理编译原理编译原理编译原理 预测分析程序的结构预测分析程序的结构 使用一个二维分析表和栈联合进行控制来实现语法分析。使用一个二维分析表和栈联合进行控制来实现语法分析。使用一个二维分析表和栈联合进行控制来实现语法分析。使用一个二维分析表和栈联合进行控制来实现语法分析。总控程序大同小异，而总控程序大同小异，而总控程序大同小异，而总控程序大同小异，而LLLL（1 1）分析表却千差万别。分析表却千差万别。分析表却千差万别。分析表却千差万别。LLLL（1 1）分析表是进行分析表是进行分析表是进行分析表是进行LLLL（1 1）分析的核心。分析的核心。分析的核心。分析的核心

31、。输入符号串：输入符号串：分析栈分析栈a a1 1a a2 2a an n#X XZ ZS S#LL（1）总控程序总控程序分析表分析表输出流输出流 编译原理编译原理编译原理编译原理 预测分析表的结构预测分析表的结构 分析表实际上是一个从分析表实际上是一个从VN(VT#)到到产生式的映射，通常以矩阵表示。产生式的映射，通常以矩阵表示。其元其元素素MU,a中可能存放一条非终结符中可能存放一条非终结符U的产的产生式，说明当符号栈生式，说明当符号栈S的栈顶元素非终结的栈顶元素非终结符符U遇到当前输入字符遇到当前输入字符a时，所应选择的时，所应选择的产生式；元素产生式；元素MU,a也可存放一个出错也可存

32、放一个出错标志，说明符号栈标志，说明符号栈S的栈顶元素非终结符的栈顶元素非终结符U不应遇到当前输入符号不应遇到当前输入符号a。编译原理编译原理编译原理编译原理 预测分析器的总控原理预测分析器的总控原理vv在任何时候，总控程序都是按照栈顶符号在任何时候，总控程序都是按照栈顶符号在任何时候，总控程序都是按照栈顶符号在任何时候，总控程序都是按照栈顶符号X X和当前输入符号和当前输入符号和当前输入符号和当前输入符号a a工作的。对于任何（工作的。对于任何（工作的。对于任何（工作的。对于任何（X X，a a），总控程序每次都执行下述三种），总控程序每次都执行下述三种），总控程序每次都执行下述三种），总控

33、程序每次都执行下述三种可能的动作之一：可能的动作之一：可能的动作之一：可能的动作之一：vv1 1、若、若、若、若X Xa a ，则宣布分析成功，停止分析过程；，则宣布分析成功，停止分析过程；，则宣布分析成功，停止分析过程；，则宣布分析成功，停止分析过程；vv2 2、若、若、若、若X Xaa，则把，则把，则把，则把X X从栈顶逐出，让从栈顶逐出，让从栈顶逐出，让从栈顶逐出，让a a指向下一输入符指向下一输入符指向下一输入符指向下一输入符号；号；号；号；vv3 3、若、若、若、若X X是一个非终结符，则查看分析表是一个非终结符，则查看分析表是一个非终结符，则查看分析表是一个非终结符，则查看分析表M

34、M。若。若。若。若MM中存放着一中存放着一中存放着一中存放着一条关于条关于条关于条关于X X的产生式，那么，首先把的产生式，那么，首先把的产生式，那么，首先把的产生式，那么，首先把X X逐出栈顶，然后，把产生逐出栈顶，然后，把产生逐出栈顶，然后，把产生逐出栈顶，然后，把产生式的右部符号按式的右部符号按式的右部符号按式的右部符号按反序反序反序反序一一推进栈，同时做这个产生式相应的一一推进栈，同时做这个产生式相应的一一推进栈，同时做这个产生式相应的一一推进栈，同时做这个产生式相应的语义动作（目前不管）。若语义动作（目前不管）。若语义动作（目前不管）。若语义动作（目前不管）。若MX,aMX,a中存放

35、着一条出错标志，中存放着一条出错标志，中存放着一条出错标志，中存放着一条出错标志，则调用出错诊查程序则调用出错诊查程序则调用出错诊查程序则调用出错诊查程序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 编译原理编译原理编译原理编译原理 预

36、测分析表的生成预测分析表的生成vv从前面的论述我们看到，预测分析法的从前面的论述我们看到，预测分析法的总控程序是固定的。对于某个文法，分总控程序是固定的。对于某个文法，分析表是分析过程的核心。析表是分析过程的核心。vv表中表中MU,a=UX1X2Xn表示对应于表示对应于X1X2Xn字的首符号可以是字的首符号可以是a。就是说。就是说X1X2Xn=*a。我们可以通过这个方。我们可以通过这个方式来确定分析表中的值。式来确定分析表中的值。编译原理编译原理编译原理编译原理 预测分析表的生成预测分析表的生成vv一般来讲，对于一个符号串一般来讲，对于一个符号串X1X2Xn的字的的字的第一个终结符号就是第一个

37、终结符号就是X1对应的字的第一个终对应的字的第一个终结符号。但是空产生式的存在使情况有一点结符号。但是空产生式的存在使情况有一点复杂。复杂。vv对于对于U1U2Un，如果，如果U1=*，那么符号串对，那么符号串对应的字的首符号也可以是应的字的首符号也可以是U2对应的字的首符对应的字的首符号。计算一个符号串对应的字的首符号的算号。计算一个符号串对应的字的首符号的算法也需要考虑到这些。法也需要考虑到这些。编译原理编译原理编译原理编译原理 预测分析表的构造预测分析表的构造vv基本思想：基本思想：当我们需要将当我们需要将U选择某个产生式展开时，如果选择某个产生式展开时，如果当前的输入为当前的输入为a，

38、表示我们要将，表示我们要将U展开为以展开为以a为首符号的字。如果有产生式为首符号的字。如果有产生式Uu，且，且a FIRST(u)，那么表示这个，那么表示这个产生式产生式是个好的是个好的选择。选择。编译原理编译原理编译原理编译原理 分析表构造算法分析表构造算法vv对于每个产生式对于每个产生式U，执行一下步骤，执行一下步骤对于每个终结符号对于每个终结符号对于每个终结符号对于每个终结符号a a FIRST()FIRST()，MU,a=U.MU,a=U.如果如果如果如果 FIRST()FIRST()，对于每个终结符号，对于每个终结符号，对于每个终结符号，对于每个终结符号b b FOLLOW(U)FO

39、LLOW(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)文法是无二义性的。文法是无二义性的。