编译原理-语言与自动机课件.ppt

上次课程内容回顾 3.3.3 形式语言与自动机简介 3.3.3 形式语言与自动机简介（续1） 3.3.3 形式语言与自动机简介（续2） 3.4 自上而下语法分析3.4.1 自上而下分析的一般方法 3.4.1 自上而下分析的一般方法（续1） 3.4.2 消除左递归 1 消除文法的直接左递归(续1) 1 消除文法的直接左递归(续2) 1 消除文法的直接左递归(续3) 2 消除文法的左递归 2 消除文法的左递归（续1） 3.4.3 提取左因子 3.4.3 提取左因子（续1） 3.4.4 递归下降分析 稳妥的笨方法： 文法的状态转换图 ： 状态图的化简： 状态图的化简（续1） 结束 2010年4月6日 上次课程内容回顾 3 递归下降子程序 3 递归下降子程序（续） 3.4.5 预测分析器 3.4.5.1 非递归预测分析器的工作模式 1 预测分析表 2 工作方式 3 驱动器算法 4 用预测分析器分析句子 4 用预测分析器分析句子（续） 3.4.5.2 构造预测分析表 3.4.5.2 构造预测分析表（续1） 3.4.5.2 构造预测分析表（续2） 3.4.5.2 构造预测分析表（续3） 3.4.5.2 构造预测分析表（续4） 3.4.5.2 构造预测分析表（续5） 结束（2010年4月8日） 上次课程内容回顾 3.4.5.3 LL(1)文法 3.4.5.3 LL(1)文法（续1） 3.4.5.3 LL(1)文法（续2） 3.4.5.3 LL(1)文法（续3） 3.4.5.3 LL(1)文法（续4） 算法3.6 计算所有非终结符的FOLLOW集合 输入 文法G 输出 G中所有非终结符的FOLLOW集合 方法 应用下述规则: 步骤3的理解： 若 S =*δAa a紧跟A之后 则 =δαBa a也紧跟B之后（A→αB） 或者 =δαBβa =*δαBa （A→αBβ） 因为 ε∈FIRST(β) 使得B成为A产生式右部最右的文法符号 即 对任何a∈FOLLOW(A)，均有a∈FOLLOW(B) 加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记 若有产生式A→αBβ，则除ε外，FIRST(β)的全体加入到FOLLOW(B)。 若有产生式A→αB或A→αBβ且ε∈FIRST(β)，则FOLLOW(A)的全体加入到FOLLOW(B)。 ■ 例3.22 计算非终结符的FIRST 与FOLLOW。 提示：自下而上计算FIRST 自上而下计算FOLLOW(为什么?) L →E;L|ε E →TE E→+TE|-TE|ε T →FT T→*FT|/FT|mod FT|ε F →(E)|id|num FIRST(F) = {( id num} FIRST(T) = {* / mod ε} FIRST(T) = FIRST(F) = {( id num} FIRST(E) = {+ - ε} FIRST(E) = FIRST(T) = FIRST(F) = {( id num} FIRST(L) = {ε}∪FIRST(E) = {ε ( id num} FOLLOW(L) = {#} FOLL0W(E) = {) ;} FOLLOW(E) = {) ;} FOLLOW(T) = {+ - ; )} FOLLOW(T) = {+ - ; )} FOLLOW(F) = {+ - * / mod ) ;} 算法3.7 构造预测分析表 输入 文法G 输出 分析表M 方法 应用下述规则 对文法的每个产生式A→α，执行2和3； 对FIRST(α)的每个终结符a，加入α到M[A，a]； 若ε∈FIRST(α)，则对FOLLOW(A)的每个终结符b(包括#)加入α到M[A，b]； M中其它没有定义的条目均是error。 ■ M[A，a]如何指导下一步动作： 若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A→α，因为a∈FIRST(α)，所以展开后下一次正好匹配a。 若当前栈顶为A，当前输入为b且b∈FOLLOW(A)，则规则3表示下一步动作是展开A→ε，即栈顶弹出A，继续分析A之后的部分，因为b∈FOLLOW(A)，所以弹出A后下一次正好匹配A的后继b。 FIRST(F/T/E)= {( id num} FIRST(T) = {* / mod ε} FIRST(E) = {+ - ε} FIRST(L) = {ε ( id num} FOLLOW(L) = {#} FOLL0W(E/E)= {) ;} FOLLOW(T