编译第四章自顶向下的分析.pptVIP

第四章 自顶向下的分析 学习目标: 掌握 LL(1)文法的判别， LL(1)分析（预测分析法），递归子程序的构造方法 理解 First 集合, Follow 集合, LL(1) 文法 了解 回溯分析, 自顶向下分析的错误恢复，自顶向下分析的语法树的构造 自顶向下的分析 定义 分析是从文法的开始符号出发，通过在最左推导中描述出各个步骤来分析记号串输入。 分析树的构造： 将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。 自顶向下分析的关键 因此自顶而下分析的主要问题是推导时所选择的产生式 : 假定要被代换的最左非终结符号是B, 且B有 n 条产生式: B→A1|A2|…|An, 那么如何确定用哪个右部去替代B？ 自顶向下的分析程序有两类 回溯分析程序 一个非终结符有一个以上的产生式 并且根据当前的输入符号，分析程序无法确定选择哪个产生式 它会尝试分析其他可能的输入，当一种可能失败时就要求输入中备份任意数量的字符。 预测分析程序 分析程序试图利用一个或多个先行记号来预测输入串中的下一个构造 预测分析方法分为两类 递归下降分析法 LL(1) 分析 4.1 预测分析方法 4.2 LL(1)文法的判别 4.3 非 LL(1) 文法到 LL(1)文法的等价转换 4.4 递归下降分析算法进行自顶向下分析 4.5 LL(1)分析 4.6 自顶向下分析的错误恢复 4.1 预测分析方法 1 预测分析的条件 2 先行符号集合的定义 3 LL(1) 文法的定义 1 预测分析方法的条件 输入字符串的分析从文法的开始符号开始出发 如果能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。 预测分析的条件 预测分析要求文法必须是 LL(1) 文法 什么是LL(1) 文法? 它的定义依赖先行符号集合——开始符号集合和后跟符号集合 2 先行符号集合的定义 开始符号集合 定义 文法G=(VN, VT, P, S), ??(VN?VT)* FIRST(?) = { a ?VT | ? ?* a......} 如果 ??* ε 则 ε ∈FIRST(?) 直观上说文法符号串? 的开始符号集是由?推导出的开头的终结符（包括ε）组成。 例如 G[S]: 后跟符号集合 定义 文法G=(VT, VN, S,P) ，A∈VN ， FOLLOW(A)={a ∈VT |S=*…Aa…}， 若 S=* …A, 则 $ ∈FOLLOW(A) ($ 用来作为输入串的结束符) 直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括$）组成。 非终结符A有两个产生式： A→bAS 和 A→ε，让 “x”表示当前输入符号 如果 x ∈FIRST(bAS)={b} ,则选择 A→bAS 进行推导 如果 x ∈FOLLOW(A)={$,a,d } , 则选择 A→ε进行推导 由于 FIRST(bAS)∩FOLLOW(A)=ф, 可确定选择哪个产生式进行推导 3 LL(1) 文法的定义 LL(1) 文法 一个文法是 LL(1) 文法，则需要满足下面的条件: 每一个产生式 A-α1|α2|…|αn 对于所有 i 和 j,1≤i,j ≤ n,i≠j， First(αi) ∩First(αj) = Φ 对于每一个非终结符 A ，如果 First(A) 中包含ε, 则First(A) ∩Follow(A) = Φ 4.2 LL(1) 文法的判别 LL(1) 文法的判别分为四步: 计算能推出ε的非终结符集 计算每一个产生式的右边串α的 FIRST(α) 集合 计算每个非终结符A的FOLLOW(A) 集合 按照LL(1)文法的定义识别 1计算能推出ε的非终结符集 可空的 当存在一个推导A=*ε 时，非终结符 A 称作是可空的。 算法 让 S 表示所有能推导出ε的非终结符集合 首先, S={ Aj | Aj→ ε 是一个产生式} 对每一个产生式 p: Ap→X1....Xn, 如果 X1....Xn?S, 则 S:= S? {Ap } 重复第二步的循环，直至S 收敛（不再变化）为止 2 计算每个产生式右部符号串α的FIRST(α)集 为每个文法符号A (A?VT ?VN )计算First(A)的算法 计算符号串α 的 First(α) 算法 为每个文法符号A (A?VT ?VN )计算First(A) 的算法 对于所有 a? VT 则 First(a)={ a } 对于所有 A? VN ,若 A ?*ε则 First(A)={ε} else First(A)={ } 对于每一个产生式 A→X1…Xj…Xn