编译原理和技术讲义-第4章.ppt

编译原理与技术 主要内容 自顶向下语法分析概述 LL(1)文法 递归下降分析技术 预测分析技术 LL(1)分析中的错误处理 4.1 自顶向下语法分析的一般方法 基本思想： 对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下，从左到右地为输入串建立分析树。或者说，为输入串寻找最左推导。 特点： 本质上是一种试探过程，反复使用不同的产生式谋求匹配输入串。 4.1 自顶向下语法分析的一般方法 例4.1：设文法G[S]：S→cAd，A→ab|a，输入串为cad，自顶向下进行语法分析，并构造相应语法树。 4.1 自顶向下语法分析的一般方法 4.1 自顶向下语法分析的一般方法 这种一般方法存在一些问题： (1) 左递归问题 自顶向下分析采取最左推导，文法中含有左递归会使自上而下的分析过程陷入无限循环。因此，必须消除文法的左递归。 (2) 回溯问题 反复寻找可正确匹配的产生式时可能需要不断回溯，虚假匹配现象需要使用更复杂的回溯技术。这样将会产生许多额外工作，因此应设法消除回溯。 4.1 自顶向下语法分析的一般方法 (3) 出错处理 分析不成功时，要确定出错的具体位置比较困难。 (4) 效率问题 这种带回溯的自顶向下方法实际上是一种穷尽一切可能的试探法，因此效率很低，代价较高，从而该方法只有理论意义，在实际应用中价值不大。 4.2 LL(1)文法 要实现无回溯的自顶向下语法分析，对相应文法必须要有一定的限制。首先，文法应该不含左递归，若文法中含有左递归，则需使用文法的等价变换消除左递归。其次，还要消除回溯。 通过提取左因子消除某些文法的回溯，为什么？ 没有左递归和左因子的文法是否一定可以进行确定的自顶向下分析？ 4.2 LL(1)文法 首符集FIRST 4.2 LL(1)文法 文法G1[S]: S→pA | qB A→cAd | a B→dB | b 这个文法的特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 4.2 LL(1)文法 4.2 LL(1)文法 文法G2[S]: S→Aa | Bb A→a | cA  B→b | dB 这个文法的特点： 每个产生式的右部不全是由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。 文法中无空产生式。 4.2 LL(1)文法 由上面两个例子可知，一个文法在推导过程中是否会产生回溯，与文法中具有相同左部的每个产生式右部所能推出的开头符号有关系。 定义4.1: 设G = (VN,VT , P, S)是上下文无关文法，对于α∈V*，V=VN∪VT，定义首符集FIRST(α)为 FIRST(α) = {a | α β, a∈VT, α,β∈V*} 即 FIRST(α) = {a | α a…, a∈VT, α∈V*} 特别地，若α ε，则规定ε∈FIRST(α)，即FIRST(α)是α能推导出的所有在开头位置的终结符或空符。 4.2 LL(1)文法 4.2 LL(1)文法 后继符集FOLLOW 4.2 LL(1)文法 4.2 LL(1)文法 因此，一个文法能否进行确定的自顶向下语法分析，不仅仅与文法中具有相同左部的产生式右部的FIRST集有关系，若有产生式右部可能推出ε，则还与其左部非终结符的后继符号集合有关。 定义4.2: 设G = (VN,VT , P, S)是上下文无关文法，对于P∈VN，定义后继符集FOLLOW(P)为 FOLLOW(P) = {a | S ?P?且a∈FRIST(?), ?∈VT*, ?∈V+ } 即 FOLLOW(P)={a | S …Pa… , a∈VT }。 特别地，若S …P，则规定$∈FOLLOW(P)。即FOLLOW(P)是推导过程中所有可能紧跟在P之后的终结符或边界符号$（$用来界定输入串，表示为：$输入串$）。 4.2 LL(1)文法 4.2 LL(1)文法 一般地，文法中含有形如P→α|β，P∈VN，α,β∈V*的产生式时，若α, β不能同时推导出空符，不妨设 α ε, β ε，则当 FIRST(α)∩( FIRST(β)∪FOLLOW(P)) = ? 时，对于非终结符P可以确定地选取产生式。