第四章自上而下语法分析.ppt

第四章 自顶向下语法分析方法 自顶向下分析的一般过程和问题 FIRST和FOLLOW集定义和计算 LL(1) 文法定义 LL(1)分析程序实现 4.1 语法分析概述 语法分析是编译过程的核心，其任务是在词法分析识别出正确的单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 高级语言的语法结构适合用上下文无关文法来描述，上下文无关文法是语法分析的基础。 语法分析在编译系统中所处的位置 语法分析的接口设计 语法分析器的功能 按照语言的语法构成规则, 识别输入的符号串能否构成一个句子。这些规则是用文法的产生式来定义的。 问题 对给定的一个输入串，如何判定它是不是一个句子？ 方法 根据文法的产生式规则，从开始符号出发，看能否推导出与这个输入串匹配的句子。这就需要建立与输入串匹配的语法分析树。 例1：判定输入串(i+i)*i是否是下述文法的句子？ G = ({E}, {i, +, *, (, ) } , P , E) P： E ? E + E E ? E * E E ? ( E ) E ? i 4.2 自顶向下语法分析 自上而下分析主要是：对任何输入串，试图用一切可能的办法，从文法的开始符号出发，自上而下地为输入串建立一个语法树。 从推导的角度看，从开始符号出发，使用最左推导，试图推导出与输入符号串相同的句子。 从语法树的角度看，从根节点出发，反复使用所有可能的产生式，谋求输入串的匹配，试图向下构造一棵语法树，其末端节点正好与输入符号串相同。 需要反复试探。 句型的推导 最左（最右）推导：在推导的任何一步α?β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。 自顶向下分析方法特点 问题1：回溯 回溯问题 问题2：左递归 左递归：文法中存在某个A?Vn，有A A?。 直接左递归：有产生式A ? A? 间接左递归： 结论 1. 左递归和回溯问题的产生直接与描述语言的文法有关 2. 应该改造文法，使其不含左递归和回溯，才能进行确定的自顶向下分析 4.3 问题的解决方法 消除左递归 消除回溯 4.3.1 消除左递归 证明的关键步骤： P-Pα | β P- β | βα | βαα | βααα | …… P- β (ε | α | αα | ααα | ……) P- βP’, P’- ε | α | αα | ααα | …… P- βP’, P’- ε | αP’ 一般而言，若产生式形式为： A→Aα1|Aα2|…|Aαn|β1|β2|…|βm 将其替换为： 练 习 消去文法G[S]的左递归 (2) 间接左递归的消除方法 例：给定间接左递归文法，请消除左递归 4.3.2消除回溯 方法是:反复 “提取公共左因子”，使得文法的每个非终结符号的各个候选式的首终结符集两两不相交，来避免回溯。 例3：有如下两个产生式： IF语句 ? if E then S1 else S2; IF语句 ? if E then S1; 练习 提取下述文法的左因子 问题: 如果希望没有回溯，对文法有什么要求？ 回溯产生的真正原因是：某非终结符对应多个侯选式，它们右部的第一个终结符相同，从而导致语法分析器选择了错误的侯选式。 如果希望没有回溯，对文法有什么要求？ 4.4 LL(1)文法 S?ApS?BqA?aA?cAB?bB?dB 在右边给定的文法中，A的候选式有两个，其首终结符集为： First(A1) = {} First(A2) = {} 相交,就会产生回溯 因此，不产生回溯的条件就是： 对非终结符A的任意两个不同的侯选式ai 和aj ，都有： First(ai)∩ First(aj) = φ 当要求用A进行匹配时，就能根据所面临的输入字符，准确地选取一个A的侯选式。 求非终结符A的First集的算法 求某一非终结符A的首终结符集First(A)的算法为： 1.若有产生式A?aα,a∈VT，把a加到First(A)中； 2.若有产生式A?ε, 把ε加到First(A)中； 3.若有产生式A?Xα，X∈VN，把First(X)中非ε元素加到First(A)中； 4.若有产生式A?X1X2X3...Xkα,其中X1X2...Xk∈VN。则 当X1X2X3...Xi =ε(1≤i≤k)时，把First(Xi+1...Xkα)的非ε元素加到 First(A)中；?? 当X1X2X3...Xk=ε时，把First(α)