ch4自顶向下语法分析.pptVIP

第四章 语法分析 ——自顶向下语法分析 自顶向下语法分析 4.1 语法分析概述 4.2 自顶向下分析方法 4.2.1 自顶向下分析的一般过程 4.2.2 自顶向下分析存在的问题 4.2.3 LL(1)分析法 4.2.4 递归子程序法（递归下降分析法） 4.1 语法分析概述 高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。 语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。规则是用文法的产生式来定义的。 根据文法的产生式规则，从开始符号出发，看能否推导出这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。 语法分析器的输出 分析树 错误处理信息 语法分析的方法： 自上而下分析法(Top-down) 基本思想：从文法的开始符号出发，向下推导，尽可能使用各种产生式，推导出与输入串匹配的句子。 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。 4.2.1自顶向下分析的一般过程 给定符号串S，若预测是某一语法成分， 那么可根据该语法成分的文法,设法为S构造一棵语法树. 若成功,则S最终被识别为某一语法成分,即 S?L(G[Z])其中G[Z]为某语言成分的文法. 若不成功,则 S?L(G[Z]) 自顶向下分析方法特点 1.分析过程是带有预测的，对输入符号串要预测属于什么语法成分，然后根据该语法成分的文法建立语法树。 2.分析过程是一种试探过程，是尽一切办法(选用不同规则) 设法建立语法树的过程，由于是试探过程，故难免有失败， 所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。 4.2.2 自上而下分析面临的问题 问题1：回溯 问题2：左递归 左递归：是左递归的，如果一个文法中存在某个非终结符号A，使A A?。 如果是A ? A?，则称为直接左递归，否则称为间接左递归。 例：设有文法： E-E+T|T T-T*F|F F-(E)|i 现有输入串i*i+i, 其分析过程是： 结论 左递归和回溯问题的产生直接与描述语言的文法有关。 因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯。 左递归的消除 消除直接左递归： 直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 P→P? | ? 其中?不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： P→?P? P?→?P?|? 证明的关键步骤： P-Pα | β 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? | ? 练习：消除下列文法的直接左递归 1.设文法G(S)： 　　　 S→(L)|a S|a 　　　 L→L，S|S  2. G(S)： 　　　 S→SaP|Sf|P 　　 P→QbP|Q Q→cSd|e 消除一般左递归 消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi→Pj?的规则改写成 Pi→?1?|?2?|…|?k? ; (其中Pj→?1|?2|…|?k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。 消除回溯 消除回溯的思路：假设轮到用A去执行匹配任务, A→?1| ?2|…|?n,若能根据面临的输入符从产生式的多个候选式中选出