1、编译原理,第四章 语法分析自上而下分析,国防科技大学计算机系602教研室,词法分析器,语法分析器,语义分析与中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,国防科技大学计算机系602教研室,第四章 语法分析自上而下分析,本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；用上下文无关文法来描述语法规则。,国防科技大学计算机系602教研室,上下文无关文法的定义：一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VT VN=S：文法的开始符号，S
2、VNP：产生式集合(有限)，每个产生式形式为P，PVN，(VT VN)*开始符S至少必须在某个产生式的左部出现一次。,国防科技大学计算机系602教研室,例，定义只含+，*的算术表达式的文法 G=，其中，P由下列产生式组成：E iE E+EE E*EE(E),国防科技大学计算机系602教研室,定义：称A直接推出，即A 仅当A 是一个产生式，且，(VT VN)*。如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。例：对文法(1)E(E)(E+E)(i+E)(i+i),国防科技大学计算机系602教研室,通常，用 表示：从1出发，经过一步或若干步，可以
3、推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,所以：即 或,定义：假定G是一个文法，S 是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为 L(G)。,国防科技大学计算机系602教研室,4.1 语法分析器的功能,语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。,国防科技大学计算机系602教研室,.,国防科技大学计算机系602教研室,语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文
4、法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约,国防科技大学计算机系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 E,i,+,*,i,i,国防科技大学计算机系602教研室,语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。递归下降分析法：对每一语法变量(非终结符
5、)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。,国防科技大学计算机系602教研室,4.2 自上而下分析面临的问题,自上而下就是从文法的开始符号出发，向下推导，推出句子。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,国防科技大学计算机系602教研室,例3.4.1 假定有文法G(S):(1)SxAy(2)A*|*分析输入串x*y(记为
6、)。,国防科技大学计算机系602教研室,当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P,含有左递归的文法将使自上而下的分析陷入无限循环。,国防科技大学计算机系602教研室,4.3 LL(1)分析法,构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯,国防科技大学计算机系602教研室,4.3.1 左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为PP|其中不以P开头。我们可以把P的规则等价地改写为如下
7、的非直接左递归形式：PPPP|,左递归变右递归,国防科技大学计算机系602教研室,一般而言，假定P关于的全部产生式是PP1|P2|Pm|1|2|n其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成：P1P|2P|nPP1P|2P|mP|,左递归变右递归,国防科技大学计算机系602教研室,例 文法G(E):EET|TTT*F|FF(E)|i经消去直接左递归后变成：ETE E+TE|TFT T*FT|F(E)|i,(4.2),PP1|P2|Pm|1|2|nP1P|2P|nPP1P|2P|mP|,国防科技大学计算机系602教研室,例如文法G(S):SQc|cQRb|
8、bRSa|a(4.3)虽没有直接左递归，但S、Q、R都是左递归的SQcRbcSabc,一个文法消除左递归的条件：不含以为右部的产生式不含回路。,国防科技大学计算机系602教研室,消除左递归的算法:1.把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k;(其中Pj1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性 END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,国防科技大学计算机系602教研室,
9、例 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q的有关候选后，把Q的规则变为 QSab|ab|b,国防科技大学计算机系602教研室,例 考虑文法G(S)SQc|cQRb|bRSa|a令它的非终结符的排序为R、Q、S。Q的规则变为 QSab|ab|b现在的Q不含直接左递归，把它代入到S的有关候选后，S变成SSabc|abc|bc|c,国防科技大学计算机系602教研室,例 考虑文法G(S)SQc|cQRb|bRSa|aS变成SSabc|abc|bc|c消除S的直接左递归后：SabcS|bcS|cSSabcS|QSab|ab|
10、bRSa|a,国防科技大学计算机系602教研室,例 考虑文法G(S)SQc|cQRb|bRSa|a消除S的直接左递归后：SabcS|bcS|cSSabcS|QSab|ab|bRSa|a关于Q和R的规则已是多余的，化简为：SabcS|bcS|cSSabcS|(4.4),国防科技大学计算机系602教研室,注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是：SQc|cQRb|bRbcaR|caR|a R(4.5)R bca R|文法(4.4)和(4.5)的等价性是显然的。,
11、国防科技大学计算机系602教研室,4.3.2 消除回溯、提左因子,为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A 1|2|n,国防科技大学计算机系602教研室,令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,特别是，若，则规定FIRST()。,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 jFIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去
12、执行任务。这个候选就是那个终结首符集含a的。,国防科技大学计算机系602教研室,提取公共左因子:假定关于A的规则是 A 1|2|n|1|2|m(其中，每个 不以开头)那么，可以把这些规则改写成AA|1|2|mA 1|2|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,国防科技大学计算机系602教研室,ETE E+TE|TFT T*FT|F(E)|i i+i,4.3.3 LL(1)分析条件,国防科技大学计算机系602教研室,i+i,IP,E,G(E):ETE E+TE|TFT T*FT|F(E)|i,国防科技大学计算机系602教研室,i+i,IP,E,T,E,G(E):ETE E+TE|TFT T*FT|F(E)|i,国防科技大学计算机系602教研室,i+i,IP,E,T,E,F,T,G(E):ETE E+TE|TFT T*FT|F(E)|i,国防科技大学计算机系602教研室,i+i,IP,E,T,E,F,T,i,G(E):ETE E+TE|TFT T*FT|F(E)|i,国防科技大学计算机系602教研室,i+i,IP,E,T,E,F,T,i,G(E):ETE E+TE|TFT T*FT|F(E)|i,国防科技大学计算机系602教研室,i+i,IP,E,T,E,
