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

编译原理 第四章 语法分析—自上而下分析 第四章 语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结构进行描述。 采用正规式和有限自动机可以描述和识别语言的单词符号； 用上下文无关文法来描述语法规则。 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G VT，VN，S，P ，其中 VT：终结符集合 非空 VN：非终结符集合 非空 ，且VT ? VN ? S：文法的开始符号，S?VN P：产生式集合 有限 ，每个产生式形式为 P??， P?VN， ? ? VT ? VN * 开始符S至少必须在某个产生式的左部出现一次。 例，定义只含+，*的算术表达式的文法 G i，+，*， ， ， E ，E， P ， 其中，P由下列产生式组成： E ? i E ? E+E E ? E*E E ? E 定义：称?A?直接推出???，即 ?A????? 仅当A ? ?是一个产生式， 且?， ?? VT ? VN * 。 如果?1 ? ?2 ? ? ??n，则我们称这个序列是从?1到?n的一个推导。若存在一个从?1到?n的推导，则称?1可以推导出?n 。 例：对文法 1 E ? E ? E+E ? i+E ? i+i 通常，用 表示：从?1出发，经过一步或若干步，可以推出?n。 4.1 语法分析器的功能 语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式 语言的语法规则 ，识别输入符号串是否为一个句子 合式程序 。 语法分析的方法： 自下而上分析法 Bottom-up 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约 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 语法分析的方法： 自下而上分析法 Bottom-up 自上而下分析法 Top-down 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导。 递归下降分析法：对每一语法变量 非终结符 构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。 4.2 自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向下推导，推出句子。 带“回溯”的 不带回溯的递归子程序 递归下降 分析方法。 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号 根结点 出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。 例3.4.1 假定有文法G S : 1 S→xAy 2 A→**|* 分析输入串x*y 记为? 。 当某个非终结符有多个产生式候选时，可能带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P 4.3 LL 1 分析法 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 4.3.1 左递归的消除 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 P→P? | ? 其中?不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： P→?P? P?→?P?|? 一般而言，假定P关于的全部产生式是 P→P?1 | P?2 | … | P?m | ?1 | ?2|…|?n 其中，每个?都不等于?，每个?都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P→?1P? | ?2P? | … | ?nP? P?→?1P? | ?2P? |… | ?mP? | ? 例 文法G E : E→E＋T | T T→T*F | F F→ E | i 经消去直接左递归后变成： E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→ E | i 例如文法G S : S→Qc|c Q→Rb|b R→Sa|a 4.3 虽没有直接左递归，但S、Q、R都是左递归的 S?Qc?Rbc?Sabc 消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行； 2. FOR i: 1 TO n DO BEGIN FOR j: 1 TO i-1 DO 把形如Pi