第四章 编译原理语法分析--自上而下.ppt

Ch4.语法分析---自上而下分析 第四章 语法分析 --- 自上而下分析 4 自上而下分析方法 4.1 语法分析器的功能 4.2 自上而下分析面临的问题：左递归、回溯 讨论确定的自上而下分析需要的条件 消除左递归、提取左公因子、避免回溯 4.3 LL(1)分析法(预测分析法) 重点难点 FIRST集合的定义及计算 FOLLOW集合的定义及计算 LL(1)分析表(预测分析表)的构造 4.1 语法分析器的功能(P66.) 语法分析是编译程序的核心部分。 语法分析是在词法分析识别出单词符号的基础上，分析并判定（即识别）一串单词符号(称为输入串)的语法结构是否符合语法规则，是否是文法的一个句子。 分析判定的方法： 建立输入串α的从文法开始符号S出发的推导 S ?α1 ? … ?αn ?α 即建立以开始符号S为根的与输入串α相匹配(即α中的各个符号为叶结点)的语法树 4.2 自上而下分析法面临的问题 . 本小节首先通过例子P67： 说明自上而下分析的思想 认识自上而下分析时所遇到的主要困难 自上而下分析的主要困难是P66-68 : 文法的左递归性，可能使分析陷入无限循环 回溯的不确定性，要求将已完成的工作推倒重来 为解决这些问题，使得自上而下分析是确定的，考虑要消除文法左递归和避免回溯。 最后构造确定的有效的自上而下分析器：递归下降分析器 自上而下分析法的思想(P66.) 从文法的开始符号出发，逐步向下推导，不断替换和展开非终结符，去匹配输入符号串(终结符号串、句子)，即寻找输入串的最左推导，推出句子，（---自上而下的实质） 并按与最左推导相对应的顺序，从文法的开始符号(根结）出发，自上而下从左到右地建立输入串的语法分析树。---其末端节点正好与输入符号串相同 推导过程中，试图根据当前的输入符号判断使用非终结符的哪个候选式去进行替换和展开。 分析过程是一种穷尽一切可能的带回溯的试探过程，是反复使用不同产生式谋求匹配输入串的过程。 自上而下分析方法分为确定的和不确定的两类。 自上而下分析存在的不确定性(1) P67. 假定文法G[S]为： ⑴ S→xAy ⑵ A→ab ⑶ A→a 分析输入串α= xay 是否文法的句子的过程： 自上而下分析存在的不确定性(2) 自上而下分析存在的不确定性(3) 不确定的自上而下分析：说明 P68.自上而下分析过程是带回溯的试探过程： ⑴ 遇非终结符标记的结，就试图用该非终结符的某个候选式展开，期望此候选式能匹配输入串，若不能匹配，则要回溯。 ⑵ 遇终结符号标记的结，就试图进行匹配，若匹配成功则移动输入串指针ip指向下一个符号。 ⑶ 回溯是指分析工作要部分或全部地退回去重做的现象，这是一项复杂费时效率很低的工作。 上述过程面临的一些问题 左递归问题 回溯 成功的暂时性 不成功时找不到出错的位置 效率底、代价高（穷尽一切方法） 文法的左递归问题 P68.文法的左递归性包括： 直接左递归：文法存在产生式 A → Aα 间接左递归：存在推导 A ?+ Aα 文法具有左递归性，采用自上而下方法分析，可能会陷入无限循环，分析不下去。 候选式的确定与回溯问题 P68.自上而下分析是一种反复用可能的候选式去进行试探的过程，不能预知本次试探是否会成功，若不成功则需要回溯。 确定的自上而下分析 为了进行确定的有效的不带回溯的自上而下语法分析，要求文法满足下述两个条件： (1) 文法不含左递归，即对任何非终结符号A不存在这样的情况： A→Aα 或 A?+ Aα； (2) 无回溯，对文法的任一非终结符号A，当其有多个候选式可供选择 (即A??1 | ?2 |…| ?m ) 时，各候选式?i 所推导出的符号串其首终结符号集合 (即 FIRST(?i ) ) 要两两不相交。于是就可以根据当前输入符号准确指出唯一可使用的候选式 ?i 去代表A谋求与输入串相匹配，无需试探和回溯。 消除左递归 (P69.) （1）直接左递归：文法存在产生式 A→Aα。 （2）间接左递归：文法不存在产生式 A→Aα， 但存在推导 A ?+ Aα。 消除直接左递归的方法：引入新的非终结符号A’，将关于A的如下产生式 A→Aα|β (α非ε且β不以A打头) 替换为 A →βA’ A’ →αA’｜ε 例：表达式文法直接左递归的消除 E → E + T｜T T → T * F｜F F → ( E )｜i 文法直接左递归消除：练习1 文法直接左递归消除：练习2 消除直接左递归的一般方法 P69.一般而言，