5章 自顶向下语法分析方法.pptVIP

第5章 自顶向下语法分析方法 确定的自顶向下分析思想 LL(1)文法的判别 某些非LL(1)文法到LL(1)文法的等 价变换 不确定的自顶向下分析思想 确定的自顶向下分析方法 确定的自顶向下分析思想 文法G1[S]:S→pAS→qBA→cAdA→aB→dBB→b 这个文法的特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 文法G2[S]:S→ApS→BqA→aA→cAB→bB→dB 这个文法的特点： 每个产生式的右部不全是由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。 文法中无空产生式。 定义： 设 G = (VT ,VN , S , P) 是上下文无关文法，FIRST(α) = {a|α aβ,a∈ VT,α ∈ V+, β ∈ V*,}若α ε，则规定ε∈FIRST(α) FIRST(Ap)={a,c} FIRST(Bq)={b,d} 文法G3[S]:S→aAS→dA→bASA→ε 定义：设 G = (VT ,VN , S , P) 是上下文无关文法，A∈VN , S是开始符号。 FOLLOW(A) = {a|S ?A?且a∈FRIST(?), ?∈VT*,?∈V+ } 若S ?A?,且? ε，则规定 #∈FOLLOW(A) 即：FOLLOW(A)={a|S …Aa… ,a∈VT}若S …A，则规定 #∈FOLLOW(A) #作为输入串的结束符，或称为句子括号，如：#输入串# 对A→α，A→β其中A∈VN , α, β ∈VN*，当α和β不同时推导出空时（设 α不推导出空，β推导出空），则当FIRST(α)∩(FIRST(β)∪FOLLOW(A))=Φ时，对于非终结符A的替换仍可唯一地确定候选。 定义：给定上下文无关文法的产生式A→α，A∈VN , α∈V*，若α ε，则SELECT(A→α)=FIRST(α)如果α ε，则SELECT(A→α)=FIRST(α)∪FOLLOW(A) 定义：一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的两个不同产生式A→α和A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ其中α,β不同时能 ε。 LL(1)文法的含义： 第一个L表示：自顶向下分析是从左向右扫描输入串。 第二个L表示：分析过程中将用最左推导。 1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。 类似也可以有LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。 文法G[S]是否是LL(1)文法:S→aAS→dA→bASA→ε 设文法G[S] 为:S→aASS→bA→bAA→ε LL(1)文法的判别 求出能推出ε的非终结符 计算FIRST集 计算FOLLOW集 计算SELECT集 判别是否是LL(1)文法 例：设文法G[S] 为:S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c判断它是否是LL(1)文法。 1.求出能推出ε的非终结符 S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c 2.计算FIRST集 1.若X?V?,则FIRST(X)={X} 2.若X?VN,且有产生式X?a…，则a∈FIRST(X);若X??也是一条产生式,则?∈FIRST(X). 3.若X?Y…是一个产生式且Y?VN,则把FIRST(Y)中的所有非?元素都加到FIRST(X)中;若X ? Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j ≤i-1,FIRST(Yj)都含有?(即Y1..Y(i-1) ? ),则把FIRST(Yj)中的所有非?元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,…,K)均含有?,则把?加到FRIST(X)中. S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c 3.计算FOLLOW集 1.对于文法的开始符号S,置#于FOLLOW(S)。; 2.若Ａ→αBβ是一个产生式,则把 ?? FIRST(β)\{?}加至FOLLOW(B)中; 3.若Ａ→αB是一个产生式,或Ａ→αBβ是 ?? 一个产生式而β ?(即??FIRST(β)），则把FOLLOW（A），加至FOLLOW（B）中． S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c 4.计