编译原理-国防科技大学课件Chapt4.ppt

《编译原理-国防科技大学课件Chapt4.ppt》由会员分享，可在线阅读，更多相关《编译原理-国防科技大学课件Chapt4.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理第四章第四章 语法分析语法分析自上而下分析自上而下分析四元式四元式单词符号单词符号语法单位语法单位四元式四元式目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码语义分析与中间代码生成器生成器优化段优化段源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器国防科技大学计算机系国防科技大学计算机系602教研室教研室第四章第四章 语法分析语法分析自上而下分析自上而下分析n本章主要介绍语法分析的处理本章主要介绍语法分析的处理n要进行语法分析，必须对语言的语法结构要进行语法分析，必须对语言的语法结构进行描述。进行描述。采用正规式和有限自动机可以描述和识

2、别语言采用正规式和有限自动机可以描述和识别语言的单词符号；的单词符号；用上下文无关文法来描述语法规则。用上下文无关文法来描述语法规则。国防科技大学计算机系国防科技大学计算机系602教研室教研室n上下文无关文法的定义：上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中其中V VT T：终结符集合终结符集合(非空非空)V VN N：非终结符集合非终结符集合(非空非空)，且，且V VT T V VN N=S S：文法的开始符号，文法的开始符号，S S V VN NP P：产生式集合产生式集合(有限有限

3、)，每个产生式形式为，每个产生式形式为P P，P P V VN N，(V VT T V VN N)*开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。国防科技大学计算机系国防科技大学计算机系602教研室教研室n例，定义只含例，定义只含+，*的算术表达式的文法的算术表达式的文法 G=，其中，其中，P由下列产生式组成：由下列产生式组成：E iE E+EE E*EE (E)国防科技大学计算机系国防科技大学计算机系602教研室教研室n定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。n如果如果 1

4、 2 n，则我们称这个序则我们称这个序列是从列是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n。n例：对文法例：对文法(1)E (E)(E+E)(i+E)(i+i)国防科技大学计算机系国防科技大学计算机系602教研室教研室n通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步，可以推出一步或若干步，可以推出 n n。用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。所以所以 ：即即 或或q定义：假定定义：假定G G是一个文法，是一个文法，

5、S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的全体所产生的句子的全体是一个是一个语言语言，将它记为，将它记为 L(G)L(G)。国防科技大学计算机系国防科技大学计算机系602教研室教研室4.1 语法分析器的功能语法分析器的功能n语法分析的任务是分析一个文法的句子语法分析的任务是分析一个文法的句子结构。结构。n语法分析器的功能：按照文法的产生式语法分析器的功能：按照文法的产生式(语言的语法规则语言的语法规则)，识别输入符号串是，识别输入符号串是否为一个句子否为一个句子

6、(合式程序合式程序)。国防科技大学计算机系国防科技大学计算机系602教研室教研室源程序源程序单词符号单词符号取下一单词取下一单词.语法分语法分析树析树词法分词法分析器析器语法分语法分析器析器符号表符号表编译程序编译程序后续部分后续部分国防科技大学计算机系国防科技大学计算机系602教研室教研室n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)n基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生构造语法树

7、。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。式规则，把产生式的右部替换成左部符号。n算符优先分析法：按照算符的优先关系和结合算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。性质进行语法分析。适合分析表达式。nLRLR分析法：规范归约分析法：规范归约国防科技大学计算机系国防科技大学计算机系602教研室教研室G(E)：E i|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE国防科技大学计算机系国防科技大学计算机系602教研室教研室n语法分析的方法：语法分析的方法：自下而上分析法自下而上

8、分析法(Bottom-up)(Bottom-up)自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它从文法的开始符号出发，反复基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找使用各种产生式，寻找 匹配匹配 的的推导推导。n递归下降分析法：对每一语法变量递归下降分析法：对每一语法变量(非终结非终结符符)构造一个相应的子程序，每个子程序识构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。馈和联合作用实现对输入串的识别。n预测分析程序预测分析程序F优点：直观、简单和宜

9、于手工实现。优点：直观、简单和宜于手工实现。国防科技大学计算机系国防科技大学计算机系602教研室教研室4.2 自上而下分析面临的问题自上而下分析面临的问题n自上而下就是从文法的开始符号出发，向自上而下就是从文法的开始符号出发，向下下推导推导，推出句子。，推出句子。带带“回溯回溯”的的不带回溯的递归子程序不带回溯的递归子程序(递归下降递归下降)分析方法。分析方法。n自上而下分析的主旨：对任何输入串，试自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号图用一切可能的办法，从文法开始符号(根根结点结点)出发，自上而下地为输入串建立一棵出发，自上而下地为输入串建立一棵语法树语法树。

10、或者说，为输入串寻找一个最。或者说，为输入串寻找一个最左推导。左推导。国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例3.4.1 假定有文法假定有文法G(S):(1)SxAy (2)A*|*分析分析输入串输入串x*y(记为记为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*国防科技大学计算机系国防科技大学计算机系602教研室教研室n当某个非终结符有多个产生式候选时，可当某个非终结符有多个产生式候选时，可能带来如下问题能带来如下问题:1.1.分析过程中，当一个非终结符用某一个候选分析过程中，当一个

11、非终结符用某一个候选匹配成功时，这种匹配可能是暂时的匹配成功时，这种匹配可能是暂时的。出错出错时时，不得不不得不“回溯回溯”。2.2.文法左递归问题文法左递归问题。一个文法是含有左递归的，一个文法是含有左递归的，如果存在非终结符如果存在非终结符P P含有左递归的文法将使自上而下的分含有左递归的文法将使自上而下的分析陷入无限循环。析陷入无限循环。国防科技大学计算机系国防科技大学计算机系602教研室教研室4.3 LL(1)分析法分析法n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯国防科技大学计算机系国防科技大学计算机系602教

12、研室教研室4.3.1 左递归的消除左递归的消除n直接消除见诸于产生式中的左递归：假直接消除见诸于产生式中的左递归：假定关于非终结符定关于非终结符P的规则为的规则为PP|其中其中 不以不以P开头。开头。我们可以把我们可以把P的规则等价地改写为如下的的规则等价地改写为如下的非直接左递归形式：非直接左递归形式：P P P P|左递归变右递归国防科技大学计算机系国防科技大学计算机系602教研室教研室n一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是PP 1|P 2|P m|1|2|n其中，每个其中，每个 都不等于都不等于，每个，每个 都不以都不以P开头开头 那么，消除那么，消除P的直

13、接左递归性就是把这些规的直接左递归性就是把这些规则改写成：则改写成：P 1P|2P|nP P 1P|2P|mP|左递归变右递归国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例 文法文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：经消去直接左递归后变成：ETE E+TE|TFT T*FT|F(E)|i(4.2)PP 1|P 2|P m|1|2|nP 1P|2P|nP P 1P|2P|mP|国防科技大学计算机系国防科技大学计算机系602教研室教研室n例如文法例如文法G(S):SQc|cQRb|bRSa|a (4.3)虽没有直接左递归，但虽没有直接左递归，但S

14、、Q、R都是左递归的都是左递归的SQcRbcSabc一个文法消除左递归的条件：一个文法消除左递归的条件：F不含以不含以 为右部的产生式为右部的产生式F不含回路。不含回路。国防科技大学计算机系国防科技大学计算机系602教研室教研室n消除左递归的算法消除左递归的算法:1.把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的规则改写成的规则改写成 Pi 1|2|k ;(其中其中Pj 1|2|k是关于是关于Pj的所有规则

15、的所有规则)消除关于消除关于Pi规则的直接左递归性规则的直接左递归性 END3.化简由化简由2所得的文法。去除那些从开始符号出发永所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。远无法到达的非终结符的产生规则。国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。n对于对于R，不存在直接左递归。不存在直接左递归。n把把R代入到代入到Q的有关候选后，把的有关候选后，把Q的规则的规则变为变为 QSab|ab|b国防科技大学计算机系国防科技大学计算机系602

16、教研室教研室n例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an令它的非终结符的排序为令它的非终结符的排序为R、Q、S。nQ的规则变为的规则变为 QSab|ab|bn现在的现在的Q不含直接左递归，把它代入到不含直接左递归，把它代入到S的有关候选后，的有关候选后，S变成变成SSabc|abc|bc|c国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|anS变成变成SSabc|abc|bc|cn消除消除S的直接左递归后：的直接左递归后：SabcS|bcS|cS S abcS|QSab|ab|bRSa|a国防科技大学计算

17、机系国防科技大学计算机系602教研室教研室n例例 考虑文法考虑文法G(S)SQc|cQRb|bRSa|an消除消除S的直接左递归后：的直接左递归后：SabcS|bcS|cS S abcS|QSab|ab|bRSa|an关于关于Q和和R的规则已是多余的，化简为：的规则已是多余的，化简为：SabcS|bcS|cS S abcS|(4.4)国防科技大学计算机系国防科技大学计算机系602教研室教研室n注意，由于对非终结符排序的不同，最注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。不难证明，它们都是等价的。n例如，若对文法

18、例如，若对文法(4.3)的非终结符排序选的非终结符排序选为为S、Q、R，那么，最后所得的无左递那么，最后所得的无左递归文法是：归文法是：SQc|cQRb|bRbcaR|caR|a R (4.5)R bca R|n文法文法(4.4)和和(4.5)的等价性是显然的。的等价性是显然的。国防科技大学计算机系国防科技大学计算机系602教研室教研室4.3.2 消除回溯、提左因子消除回溯、提左因子n为了消除回溯就必须保证：对文法的任为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指能够根据它所面临的输入符号准确地指派它的一

19、个候选去执行任务，并且此候派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。选的工作结果应是确信无疑的。nA 1|2|nSa.IPA.国防科技大学计算机系国防科技大学计算机系602教研室教研室n令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所的所有非终结符的每个候选有非终结符的每个候选 定义它的终结首定义它的终结首符集符集FIRST()为：为：特别是，若特别是，若 ，则规定，则规定FIRST()。如果非终结符如果非终结符A的所有候选首符集两两不相交，的所有候选首符集两两不相交，即即A的任何两个不同候选的任何两个不同候选 i和和 jFIRST(i)FIRST(j)当要

20、求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的就能根据它所面临的第一个输入符号第一个输入符号a，准确地指派某一个候选前去准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含执行任务。这个候选就是那个终结首符集含a的的。国防科技大学计算机系国防科技大学计算机系602教研室教研室n提取公共左因子提取公共左因子:假定关于假定关于A的规则是的规则是 A 1|2|n|1|2|m(其中，每个其中，每个 不以不以 开头开头)那么，可以把这些规则改写成那么，可以把这些规则改写成A A|1|2|mA 1|2|nn经过反复提取左因子，就能够把每个非终经过反复提取左因子，就能够把每个非终结符结

21、符(包括新引进者包括新引进者)的所有候选首符集变的所有候选首符集变成为两两不相交。成为两两不相交。国防科技大学计算机系国防科技大学计算机系602教研室教研室n ETE E+TE|TFT T*FT|F(E)|in i +i4.3.3 LL(1)分析条件分析条件国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPEnG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEnG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i I

22、PETEFTnG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTinG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTinG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi nG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEnG

23、(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEnG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEFTnG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEFTinG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi

24、+TEFTinG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEFTi nG(E):ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEFTi nG(E):ETE E+TE|TFT T*FT|F(E)|iS T+国防科技大学计算机系国防科技大学计算机系602教研室教研室n假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何的任何非终结符非终结符A，我们定义我们定义特别是，若特别是，若 ，则规定，则规定

25、 FOLLOW(A)4.3.3 LL(1)分析条件分析条件国防科技大学计算机系国防科技大学计算机系602教研室教研室n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1.文法不含左递归，文法不含左递归，2.对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的各个产生式的候选首符集两两不相交。即，若的候选首符集两两不相交。即，若A 1|2|n 则则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个若它存在某个候选首符集包含候选首符集包含，则，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一

26、个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为为LL(1)LL(1)文法文法。国防科技大学计算机系国防科技大学计算机系602教研室教研室n对于一个满足上述条件的文法，可以对其输对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假入串进行有效的无回溯的自上而下分析。假设要用非终结符设要用非终结符A进行匹配，面临的输入符进行匹配，面临的输入符号为号为a，A的所有产生式为的所有产生式为A 1|2|n1.若若a FIRST(i)，则指派则指派 i执行匹配任务；执行匹配任务；2.若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则：(1)若若

27、 属于某个属于某个FIRST(i)且且 a FOLLOW(A)，则让则让A与与 自动匹配。自动匹配。(2)否则，否则，a的出现是一种语法错误。的出现是一种语法错误。国防科技大学计算机系国防科技大学计算机系602教研室教研室回顾：回顾：LL(1)分析法分析法n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯国防科技大学计算机系国防科技大学计算机系602教研室教研室n一般而言，假定一般而言，假定P关于的全部产生式是关于的全部产生式是PP 1|P 2|P m|1|2|n其中，每个其中，每个 都不等于都不等于，每个，每个 都不以都不以

28、P开头开头 那么，消除那么，消除P的直接左递归性就是把这些规的直接左递归性就是把这些规则改写成：则改写成：P 1P|2P|nP P 1P|2P|mP|国防科技大学计算机系国防科技大学计算机系602教研室教研室n消除左递归的算法消除左递归的算法:1.把文法把文法G的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；按此顺序执行；2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如把形如PiPj 的规则改写成的规则改写成 Pi 1|2|k ;(其中其中Pj 1|2|k是关于是关于Pj的所有规则的所有规则)消除关于

29、消除关于Pi规则的直接左递归性规则的直接左递归性 END3.化简由化简由2所得的文法。去除那些从开始符号出发永所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。远无法到达的非终结符的产生规则。国防科技大学计算机系国防科技大学计算机系602教研室教研室回顾：回顾：LL(1)分析法分析法n构造不带回溯的自上而下分析算法构造不带回溯的自上而下分析算法要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯国防科技大学计算机系国防科技大学计算机系602教研室教研室4.3.2 消除回溯、提左因子消除回溯、提左因子n为了消除回溯就必须保证：对文法的任为了消除回溯就必须保证：对文法的任何非

30、终结符，当要它去匹配输入串时，何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。选的工作结果应是确信无疑的。nA 1|2|nSa.IPA.国防科技大学计算机系国防科技大学计算机系602教研室教研室n令令G是一个不含左递归的文法，对是一个不含左递归的文法，对G的所的所有非终结符的每个候选有非终结符的每个候选 定义它的终结首定义它的终结首符集符集FIRST()为：为：特别是，若特别是，若 ，则规定，则规定FIRST()。如果非终结符如果非终结符A的所有

31、候选首符集两两不相交，的所有候选首符集两两不相交，即即A的任何两个不同候选的任何两个不同候选 i和和 jFIRST(i)FIRST(j)当要求当要求A匹配输入串时，匹配输入串时，A就能根据它所面临的就能根据它所面临的第一个输入符号第一个输入符号a，准确地指派某一个候选前去准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含执行任务。这个候选就是那个终结首符集含a的的。国防科技大学计算机系国防科技大学计算机系602教研室教研室n提取公共左因子提取公共左因子:假定关于假定关于A的规则是的规则是 A 1|2|n|1|2|m(其中，每个其中，每个 不以不以 开头开头)那么，可以把这些规则改写

32、成那么，可以把这些规则改写成A A|1|2|mA 1|2|nn经过反复提取左因子，就能够把每个非终经过反复提取左因子，就能够把每个非终结符结符(包括新引进者包括新引进者)的所有候选首符集变的所有候选首符集变成为两两不相交。成为两两不相交。国防科技大学计算机系国防科技大学计算机系602教研室教研室i +i IPETEFTi+TEn ETE E+TE|TFT T*FT|F(E)|i国防科技大学计算机系国防科技大学计算机系602教研室教研室n假定假定S是文法是文法G的开始符号，对于的开始符号，对于G的任何的任何非终结符非终结符A，我们定义我们定义特别是，若特别是，若 ，则规定，则规定 FOLLOW(

33、A)FOLLOW定义定义国防科技大学计算机系国防科技大学计算机系602教研室教研室n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1.文法不含左递归，文法不含左递归，2.对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的各个产生式的候选首符集两两不相交。即，若的候选首符集两两不相交。即，若A 1|2|n 则则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个若它存在某个候选首符集包含候选首符集包含，则，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一个文法如果一个文法G满足以上条件，

34、则称该文法满足以上条件，则称该文法G为为LL(1)LL(1)文法文法。国防科技大学计算机系国防科技大学计算机系602教研室教研室n对于一个满足上述条件的文法，可以对其输对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假入串进行有效的无回溯的自上而下分析。假设要用非终结符设要用非终结符A进行匹配，面临的输入符进行匹配，面临的输入符号为号为a，A的所有产生式为的所有产生式为A 1|2|n1.若若a FIRST(i)，则指派则指派 i执行匹配任务；执行匹配任务；2.若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则：(1)若若 属于某个属于某个FIRST(i)

35、且且 a FOLLOW(A)，则让则让A与与 自动匹配。自动匹配。(2)否则，否则，a的出现是一种语法错误。的出现是一种语法错误。国防科技大学计算机系国防科技大学计算机系602教研室教研室构造构造FIRST()国防科技大学计算机系国防科技大学计算机系602教研室教研室n对每一文法符号对每一文法符号X VTVN构造构造FIRST(X)连续使用下面的规则，直至每个集合连续使用下面的规则，直至每个集合FIRST不再增大为止：不再增大为止：1.若若X VT，则，则FIRST(X)X。2.若若X VN，且有产生式且有产生式Xa，则把则把a加入到加入到FIRST(X)中；若中；若X 也是一条产生式，则把也

36、是一条产生式，则把 也加到也加到FIRST(X)中。中。国防科技大学计算机系国防科技大学计算机系602教研室教研室3.l若若XY是一个产生式且是一个产生式且Y VN，则把则把FIRST(Y)中的所有非中的所有非-元素都加到元素都加到FIRST(X)中；中；l若若XY1Y2Yk是一个产生式，是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何都是非终结符，而且，对于任何j，1 j i-1，FIRST(Yj)都含有都含有(即即Y1Yi-1)，则把则把FIRST(Yi)中的所有非中的所有非-元素都加到元素都加到FIRST(X)中；中；特别是，若所有的特别是，若所有的FIRST(Yj)均含有均含有

37、，j1，2，k，则把则把 加到加到FIRST(X)中。中。国防科技大学计算机系国防科技大学计算机系602教研室教研室n对文法对文法G的任何符号串的任何符号串=X1X2Xn构造构造集合集合FIRST()。1.置置FIRST()FIRST(X1)；2.若对任何若对任何1 j i-1，FIRST(Xj)，则把则把FIRST(Xi)加至加至FIRST()中；特别是，中；特别是，若所有的若所有的FIRST(Xj)均含有均含有，1 j n，则把则把 也加至也加至FIRST()中。显然，若中。显然，若 则则FIRST()。国防科技大学计算机系国防科技大学计算机系602教研室教研室构造构造FOLLOW(A)国

38、防科技大学计算机系国防科技大学计算机系602教研室教研室n对于文法对于文法G的每个非终结符的每个非终结符A构造构造FOLLOW(A)的办法是，连续使用下面的的办法是，连续使用下面的规则，直至每个规则，直至每个FOLLOW不再增大为止：不再增大为止：1.对于文法的开始符号对于文法的开始符号S，置于置于FOLLOW(S)中；中；2.若若A B 是一个产生式，则把是一个产生式，则把FIRST()加至加至FOLLOW(B)中；中；3.若若A B是一个产生式，或是一个产生式，或AB 是一是一个产生式而个产生式而 (即即FIRST()，则把则把FOLLOW(A)加至加至FOLLOW(B)中。中。国防科技大

39、学计算机系国防科技大学计算机系602教研室教研室n例例4.6 对于文法对于文法G(E)ETE E+TE|TFT T*FT|F(E)|i构造每个非终结符的构造每个非终结符的FIRST和和FOLLOW集合：集合：FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)=(,i FOLLOW(E)=),#FOLLOW(E)=),#FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#国防科技大学计算机系国防科技大学计算机系602教研室教研室4.4 递归下降分析递归下降分析程序构造程序构造n构造不带回溯的自上而

40、下分析程序构造不带回溯的自上而下分析程序要消除文法的左递归性要消除文法的左递归性克服回溯克服回溯国防科技大学计算机系国防科技大学计算机系602教研室教研室n构造不带回溯的自上而下分析器构造不带回溯的自上而下分析器n分析程序由一组递归过程组成，文法中每分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。析程序称为递归下降分析器。(因为文法因为文法的定义通常是递归的的定义通常是递归的)n几个全局过程和变量：几个全局过程和变量：ADVANCE，把输入串指示器把输入串指示器IP指向下一个指向下一个输入符号，即读入一个单字

41、符号输入符号，即读入一个单字符号SYM，IP当前所指的输入符号当前所指的输入符号ERROR，出错处理子程序出错处理子程序国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例:文法文法G(E):G(E):ETE E+TE|TFT T*FT|F(E)|in每个非终结符有对应的子程序的定义，每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终首先在分析过程中，当需要从某个非终结符出发进行展开结符出发进行展开(推导推导)时，就调用这时，就调用这个非终结符对应的子程序。个非终结符对应的子程序。国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例:文法文法G(E):

42、G(E):ETE E+TE|TFT T*FT|F(E)|in对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE E；BEGIN T；E END；PROCEDURE E；IF SYM=+THEN BEGINADVANCE；T；E END国防科技大学计算机系国防科技大学计算机系602教研室教研室PROCEDURE T；BEGIN F；T ENDPROCEDURE T；IF SYM=*THENBEGIN ADVANCE；F；T END；n例例:文法文法G(E):G(E):ETE E+TE|TFT T*FT|F(E)|in对应的递归下降子程序为对应的递归下降子程序为:国防科技大学计算机系

43、国防科技大学计算机系602教研室教研室n例例:文法文法G(E):G(E):ETE E+TE|TFT T*FT|F(E)|in对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE F；IF SYM=i THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE;E；IF SYM=)THEN ADVANCE ELSE ERROR END ELSE ERROR;国防科技大学计算机系国防科技大学计算机系602教研室教研室主程序主程序:PROGRAM PARSER;BEGIN ADVANCE;E;IF SYM#THEN ERROREND;国防科技大学计算机系国防

44、科技大学计算机系602教研室教研室n对应的递归下降子程序为对应的递归下降子程序为:ETE|BCPROCEDURE E；BEGINIF SYM FIRST(TE)THEN T；E ELSE IF SYM FIRST(BC)THENB;CELSE ERROREND；国防科技大学计算机系国防科技大学计算机系602教研室教研室ETE E+TE|TFT T*FT|F(E)|I对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE E；BEGIN T；E END；PROCEDURE T；BEGIN F；T END国防科技大学计算机系国防科技大学计算机系602教研室教研室ETE E+TE|TFT

45、T*FT|F(E)|I对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE E；IF SYM=+THEN BEGINADVANCE；T；E END ELSE IF SYM#AND SYM)THEN ERROR国防科技大学计算机系国防科技大学计算机系602教研室教研室ETE E+TE|TFT T*FT|F(E)|I对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE T；IF SYM=*THEN BEGIN ADVANCE；F；T END ELSE IF SYM#AND SYM)AND SYM+THEN ERROR国防科技大学计算机系国防科技大学计算机系602教研室教研室

46、ETE E+TE|TFT T*FT|F(E)|i对应的递归下降子程序为对应的递归下降子程序为:PROCEDURE F；IF SYM=i THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE;E；IF SYM=)THEN ADVANCE ELSE ERROR END ELSE ERROR;国防科技大学计算机系国防科技大学计算机系602教研室教研室ETE E+TE|TFT T*FT|F(E)|i对应的递归下降子程序为对应的递归下降子程序为:主程序主程序:PROGRAM PARSER;BEGIN ADVANCE;EEND;国防科技大学计算机系国防科技大学计算机系6

47、02教研室教研室n在元符号在元符号“”和和“|”的基础上，扩充的基础上，扩充几个元语言符号：几个元语言符号：1.用花括号用花括号 表示闭包运算表示闭包运算*。2.用表示用表示 0n可任意重复可任意重复0次至次至n次，。次，。3.用方括号用方括号 表示表示 01，即表示，即表示 的出现的出现可有可无可有可无(等价于等价于|)。引入上述元符号的文法亦称引入上述元符号的文法亦称扩充的巴科扩充的巴科斯范式斯范式。文法的另一种表示法和转换图文法的另一种表示法和转换图国防科技大学计算机系国防科技大学计算机系602教研室教研室n例如，通常的例如，通常的“实数实数”可定义为：可定义为：decimalsigni

48、nteger.digitexponent exponentEsigninteger integerdigitdigit sign+|-n用扩充的巴科斯范式来描述语法，直观易用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。懂，便于表示左递归消去和因子提取。国防科技大学计算机系国防科技大学计算机系602教研室教研室n例例4.5 文法文法ET|E+TTF|T*FFi|(E)可表示成可表示成ET+TTF*FFi|(E)(4.6)国防科技大学计算机系国防科技大学计算机系602教研室教研室n ET+TTF*FFi|(E)(4.6)n可以用语法图来表示语言的文法。可以用语法图来表示语言

49、的文法。T+ETF*TFi)FE(国防科技大学计算机系国防科技大学计算机系602教研室教研室n ET+TTF*FFi|(E)(4.6)n可构造一组递归下降分析程序：可构造一组递归下降分析程序：PROCEDURE E；BEGIN T；WHILE SYM=+DO BEGIN ADVANCE；T ENDEND；国防科技大学计算机系国防科技大学计算机系602教研室教研室PROCEDURE T；BEGIN F；WHILE SYM=*DO BEGIN ADVANCE；F ENDEND；n ET+TTF*FFi|(E)(4.6)n可构造一组递归下降分析程序：可构造一组递归下降分析程序：国防科技大学计算机系国

50、防科技大学计算机系602教研室教研室n ET+TTF*FFi|(E)(4.6)n可构造一组递归下降分析程序：可构造一组递归下降分析程序：PROCEDURE F；IF SYM=i THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE;E；IF SYM=)THEN ADVANCE ELSE ERROR END ELSE ERROR;国防科技大学计算机系国防科技大学计算机系602教研室教研室 1.文法不含左递归，文法不含左递归，2.对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的各个产生式的候选首符集两两不相交。即，若的候选首符集两两不相交。即，若