编译原理SELECT()集新合的求法.ppt

编译原理;第5章 自顶向下语法分析方法;自顶向下语法分析方法;自顶向下语法分析要解决的关键问题;自顶向下语法分析方法;第5章 自顶向下语法分析方法;自顶向下语法分析要解决的关键问题; 一、确定的自顶向下分析思想 1、方法：从开始符号出发，不断替换非终结符，根据当前的单词符号就可以唯一选定要替换的产生式。;S;例1：文法G(S)：S→pA S→qB A→cAd A→a 该文法的特点： （1）每个产生式的右部都由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符开始。 对于这样的文法，其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导，因此，分析过程是唯一确定的。;例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 该文法的特点： （1）产生式的右部不全是由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。 （3）无空产生式。 ccap 如何根据输入串的第1个符号来确定产生式呢？ ;例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 当输入W=ccap推导： 自顶向下的推导过程为： ;例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 当输入W=ccap推导： 自顶向下的推导过程为： S ?Ap ?cAp ?ccAp ?ccap 语法树为：;例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 该文法的特点： （1）产生式的右部不全是由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。 （3）无空产生式。 ccap 如何根据输入串的第1个符号来确定产生式呢？ ;2、开始符号集合的定义：;2、开始符号集合的定义：;;例3：文法G[S] ： S ? aA | d A ? bAS|ε 若输入W=abd，则推导过程为： ;S;当某一非终结符的产生式中含有空产生式时，第二步推导的产生式该如何确定呢？根据后跟符号集合确定; Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。;换句话说： Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。;自上而下语法分析要解决的关键问题;4、选择集合的定义 给定上下文无关文法的产生式A??，A?VN， ??V*，若??ε，则Select（A??）=First(?)， 若??ε，则Select(A??)=（First(?)-{ε}）∪Follow(A) ;5、LL(1)文法的定义： 一个上下文无关文法是LL(1)文法的充分必要条件是对每个非终结符A的两个不同产生式： A??，A?β满足Select(A??)∩Select(A?β)=?，其中?、β不同时推出? 只有对满足LL(1)文法的句子，才能进行确定的自顶向下分析： 给定输入串，就可以根据产生式规则的选择集合确定唯一的产生式进行推导。 ;;例5：上例3文法： S?aA|d A?bAS|ε 证明该文法为LL(1)文法。;例5：上例3文法： S?aA|d A?bAS|ε 证明该文法为LL(1)文法