研究生院第四章_1_详解.ppt

自上而下分析（1） 自上而下分析的一般方法 对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下、从左到右地为输入串建立分析树，即为输入串寻找最左推导。这是一个试探的过程 可以执行一组递归的过程来处理输入，每个过程联系到文法的一个非终结符，称为递归下降分析 对于如下文法和输入串cad，自上而下的分析树建立 S→cAd A→ab|a 自上而下分析（2） 一般的自上而下分析存在的问题： 如果文法存在左递归( )，则使自上而下的分析过程陷入无限循环 当非终结符用某个选择匹配成功时，这种成功可能是暂时的。由于这种虚假现象的存在，需要回溯技术 由于回溯，需要把已做的一些语义工作推倒重来，费时费力，所以最好设法消除回溯 当最终报告分析不成功时，难以知道输入串出错的确切位置 带回溯的自上而下分析是一种穷举有哪些信誉好的足球投注网站，代价极高，只有理论意义，实践价值不大 自上而下分析（3） 确定的递归下降分析举例 对于文法G1[S]： S→pA S→qB A→cAd A→a 对输入串pccadd，自上而下的推导过程是： S = pA = pcAd = pccAdd = pccadd 对应的分析树： 自上而下分析（4） 文法G1的特点： 每个产生式的右部都由终结符号开始 如果两个产生式的左部相同，则它们的右部由不同的终结符号开始 显然，G1在推导过程中可以根据当前的输入符号唯一地选择哪个产生式继续推导 对于文法G2[S]： S→Ap S→Bq A→a A→cA B→b B→dB 对输入串ccap，自上而下的推导过程是： S = Ap = cAp = ccAp = ccap 自上而下分析（5） 对应的分析树： 文法G2的特点： 每个产生式的右部不全是由终结符号开始 如果两个产生式的左部相同，则它们的右部由不同的终结符号或非终结符号开始 文法中没有ε产生式 虽然不象G1那样直观，G2在推导过程中仍然可以根据当前的输入符号唯一地选择哪个产生式继续推导 自上而下分析（6） 对于文法G3[S]： S→aA S→d A→bAS A→ε 对输入串abd，自上而下的推导过程是： S = aA = abAS = abS = abd 对应的分析树： 自上而下分析（7） 不需要回溯的条件：对文法的任何非终结符，当要去匹配输入串时，它能够根据所面临的输入符号准确地指派它的一个选择去执行任务，并且这个选择的工作结果应是确信无疑的 FIRST集：令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合： 特别地，如果α可以推导出空串，则空串也是FIRST(α)的元素 如果非终结符A的任意两个选择的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ，且空串不是关于A的所有开始符号集的元素，则A可以根据所面临的第一个输入符号，准确地指派一个选择去去执行任务，这个选择是那个开始符号集含a的α，参考文法G1的例子 自上而下分析（8） 预测分析器： 在不含左递归且每个非终结符所有选择的开始符号集都两两不相交的条件下，存在可能构造专门的递归下降分析器，称为预测分析器，它仅向前看一个符号便无二义地为非终结符决定所需的处理 处理输入串时的过程调用序列隐含地定义了输入的分析树 文法：产生Pascal类型的子集，记号dotdot代表.. type→ simple | ↑id | array [ simple ] of type simple→ integer | char | num dotdot num 自上而下分析（9） 上述文法的预测分析器的代码（Pascal的程序） Procedure match(t : token); Begin if lookahead = t then lookahead := nexttoken else error End Procedure type; Begin if lookahead 属于 {integer,char, num} then simple else if lookahead = ‘↑’ then begin match(‘↑’); match(id) end else if lookahead = array then begin match(array);match(‘[’);simple;match(‘]’); match(of);type end else error end 自上而下分析（10） Procedure simple; Begin