合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所编译原理第四章 语法分析自上而下分析合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码 生成器优化段源程序表格管理出错处理 目标代码生成器合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所第四章 语法分析自上而下分析o 本章主要介绍语法分析的处理 o 要进行语法分析，必须对语言的语法结构进 行描述。 n 采用正规式和有限自动机可以描述和识别语言 的单词符号； n 用上下文无关文法来描述语法规则。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o上下文无关文法的定义： 一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中nVT：终结符集合(非空) nVN：非终结符集合(非空)，且VT VN=nS：文法的开始符号，SVNnP：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* n开始符S至少必须在某个产生式的左部出现一次。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例，定义只含+，*的算术表达式的文法G=， 其中 ，P由下列产生式组成： E i E E+E E E*E E (E)合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 定义：称A直接推出，即 A仅当A 是一个产生式，且， (VT VN)* 。o 如果1 2 n，则我们称这个序列 是从1到n的一个推导。若存在一个从1到 n的推导，则称1可以推导出n 。o 例：对文法(1) E (E) (E+E) (i+E) (i+i)合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所n通常，用 表示：从1出发，经过 一步或若干步，可以推出n。用 表示：从1出发，经过0步或 若干步，可以推出n。所以 ： 即 或q定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全体 是一个语言，将它记为 L(G)。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所4.1 语法分析器的功能o 语法分析的任务是分析一个文法的句子结 构。 o 语法分析器的功能：按照文法的产生式(语 言的语法规则)，识别输入符号串是否为一 个句子(合式程序)。 n 注：语法分析是编译程序的核心部分合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所源程序单词符号取下一单词.语法分 析树词法分 析器语法分 析器符号表编译程序 后续部分合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o语法分析的方法： n自下而上分析法(Bottom-up)o基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构 造语法树。所谓归约，是指根据文法的产生式 规则，把产生式的右部替换成左部符号。 o算符优先分析法：按照算符的优先关系和结 合性质进行语法分析。适合分析表达式。 oLR分析法：规范归约合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所G(E)： E i| E+E | E-E | E*E | E/E | (E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 语法分析的方法： n 自下而上分析法(Bottom-up) n 自上而下分析法(Top-down)o 基本思想：它从文法的开始符号出发，反 复使用各种产生式，寻找“匹配“的推导。o 递归下降分析法：对每一语法变量(非终结 符)构造一个相应的子程序，每个子程序识 别一定的语法单位，通过子程序间的信息 反馈和联合作用实现对输入串的识别。o 预测分析程序F优点：直观、简单和宜于手工实现。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所4.2 自上而下分析面临的问题o自上而下就是从文法的开始符号出发，向下 推导，推出句子。n带“回溯”的 n不带回溯的递归子程序(递归下降)分析方法。 o自上而下分析的主旨：对任何输入串，试图 用一切可能的办法，从文法开始符号(根结点) 出发，自上而下地为输入串建立一棵语法树 。或者说，为输入串寻找一个最左推导。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例3.4.1 假定有文法G(S):(1) SxAy(2) A*|*分析输入串x*y(记为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 当某个非终结符有多个产生式候选时，可能 带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选 匹配成功时，这种匹配可能是暂时的。出错 时，不得不“回溯”。2. 文法左递归问题。一个文法是含有左递归的 ，如果存在非终结符P 含有左递归的文法将使自上而下的分 析陷入无限循环。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所4.3 LL(1)分析法o 构造不带回溯的自上而下分析算法n 要消除文法的左递归性n 克服回溯合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所4.3.1 左递归的消除o 直接消除见诸于产生式中的左递归：假定 关于非终结符P的规则为PP | 其中不以P开头。我们可以把P的规则等价地改写为如下的非 直接左递归形式： PP PP|左递归变 右递归合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 一般而言，假定P关于的全部产生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改 写成： P1P | 2P | | nP P1P | 2P | | mP | 左递归变 右递归合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例 文法G(E): EET | T TT*F | F F(E) | i经消去直接左递归后变成：ETEE+TE | TFTT*FT | F(E) | i(4.2) PP1 | P2 | | Pm | 1 | 2|n P1P | 2P | | nP P1P | 2P | | mP | 合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例如文法G(S): SQc|c QRb|b RSa|a (4.3) 虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc一个文法消除左递归的条件： F不含以为右部的产生式 F不含回路。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1， P2，Pn；按此顺序执行； 2. FOR i:=1 TO n DOBEGINFOR j:=1 TO i-1 DO把形如PiPj的规则改写成Pi1|2|k ; (其中Pj1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性END 3. 化简由2所得的文法。去除那些从开始符号出发永 远无法到达的非终结符的产生规则。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 注：消除左递归算法的注意事项: 1. 此算法适用于，消除了PP 产生式和不以为 右部的产生式的文法。 2. 该算法的第二步所做的工作可以理解为： a) 若产生式出现直接左递归，则用消除直接左递归 的方法消除； b) 若产生式右部的最左符号是非终结符且序号大于 左部的非终结符，则不作替换处理； c) 若序号小于左部的非终结符， 则将序号小的非终 结符（已处理过）用其右部串替换，然后消除新的 直接左递归； d) 因此每次替换的非终结符均为前面已经处理过的 非终结符。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例 考虑文法G(S) SQc|c QRb|b RSa|ao 令它的非终结符的排序为R、Q、S。 o 对于R，不存在直接左递归。 RSa|a产生 式中S的序号大于R，不作替换处理 o 对于Q， QRb|b中R的序号小于Q，把R 代入到Q的有关候选后，把Q的规则变为 QSab | ab | b不存在直接左递归，并且产生式中S的序号 大于Q，不再做替换处理。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例 考虑文法G(S) SQc|c QRb|b RSa|ao 令它的非终结符的排序为R、Q、S。 o Q的规则变为 QSab | ab | b o 对于S， SQc|c产生式中Q序号小于S，把 Q的产生式代入到S的有关候选后，S变成 SSabc | abc | bc | c合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例 考虑文法G(S) SQc|c QRb|b RSa|a o S变成 SSabc | abc | bc | c o 出现左递归，消除S的直接左递归后： SabcS | bcS | cS SabcS | QSab |ab | b RSa|a合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 例 考虑文法G(S) SQc|c QRb|b RSa|a o 消除S的直接左递归后： SabcS | bcS | cS SabcS | QSab |ab | b RSa|a o 关于Q和R的规则已是多余的，化简为： SabcS | bcS | cS SabcS | (4.4)合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 注意，由于对非终结符排序的不同，最后 所得的文法在形式上可能不一样。但不难 证明，它们都是等价的。 o 例如，若对文法(4.3)的非终结符排序选为S 、Q、R，那么，最后所得的无左递归文法 是： SQc | c QRb | b RbcaR | caR |a R (4.5) R bca R | o 文法(4.4)和(4.5)的等价性是显然的。合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所4.3.2 消除回溯、提左因子n 产生回溯的原因：推导时，若产生式存在多个候选式 ，选择哪个进行推导存在不确定性。n 为了消除回溯就必须保证：对文法的任何非终结符， 当要它去匹配输入串时，能够根据它所面临的输入符 号准确地指派它的一个候选去执行任务，并且此候选 的工作结果应是确信无疑的。A 1 | 2 | | n Sa.IPA合肥工业大学合肥工业大学 计算机与信息学院软件所计算机与信息学院软件所o 令G是一个不含左递归的文法，对G的所有 非终结符的每个候选定义它的终结首符集