5.2 ll(1)文法的判别.ppt

♨ LL(1)文法的判别别Ø文法化简简 - 不含有有害规则规则和多余规则规则Ø消除左递归递归和提左公因子Ø求出能 ε的非终结终结符Ø计计算FIRST集Ø计计算FOLLOW集Ø计计算SELECT集*(3). 求出能推出ε的非终结终结符例 G:E → E+T | TT → T*F | FF → (E) | i消除左递归: G': E → TE'E'→ +TE'|εT → FT'T'→ *FT'|εF → (E) | i推出ε EN E'Y TN T'Y FN解题过题过程见见黑板!算法描述建立一个一维维数组组X[ ]，用以记录记录非终结终结符能 否推出ε① 将数组组X[ ]中对应对应每一非终结终结符的标记标记置初 值为值为“未定”……② 扫扫描文法中的产产生式 (a) 若某一非终结终结符的某一产产生式右部为为ε, 则则将数组组中对应该对应该非终结终结符的标标志置为为“是”， 并从文法中删删除该该非终结终结符的所有产产生式 (b) 若某一产产生式右部含有终结终结符，则删则删除该产该产生式 右部含有终结终结符，一定无法推出ε) 若这这使得以某一非终结终结符为为左部的所有产产生式都被 删删除，则则将数组组中对应该对应该非终结终结符的标记值标记值改为为“否 “。

……③ 扫扫描产产生式右部的每一符号 (此时产时产生式右部全部为为非终结终结符) (a) 若扫扫描到的非终结终结符在数组组中对应对应的标标志是“是“, 则删则删去该该非终结终结符， 若这这使产产生式右部为为空,则对产则对产生式左部的非终结终结符 在数组组中对应对应的标标志改“是”,并删删除该该非终结终结符为为左 部的所有产产生式 (b) 若扫扫描到的非终结终结符在数组组中对应对应的标标志是“否“, 则删则删去该产该产生式， 若这这使产产生式左部非终结终结符的有关产产生式都被删删去 ，则则把在数组组中该该非终结终结符对应对应的标标志改成“否”……④ 重复③，直到扫扫描完一遍文法的产产生式，数 组组中非终结终结符对应对应的特征再没有改变为变为止4). 计计算FIRST集对对每一文法符号X∈V , 计计算FIRST(X) (a) 若X∈VT，则则FIRST(X)＝{X} (b) 若X∈VN，且有产产生式 X→ a… , a∈VT , 则则 a∈FIRST(X) 即把a加入到FIRSR(X)中 (c) 若X∈VN，且有产产生式 X→ε, 则则ε∈FIRST(X)……(d) 若X∈VN, 且有产产生式 X→Y1 Y2 …Yi-1 Yi … Yn,当Y1 Y2 … Yi-1都能推出ε时时， 则则 FIRST(Y1)－{ε} FIRST(Y2)－{ε} …… FIRST(Yi-1)－{ε} FIRST(Yi) 都包含在FIRST(X)中……(e) 当(d)中X→Y1 Y2 … Yn 所有Yj 都可以推出ε,(j=1,2,…n) , 则则FIRST(Y1) FIRST(Y2) …… FIRST(Yn) 都包含在FIRST(X)中反复使用上述(b)～(e)步直到每个符号的FIRST 集合不再增大为为止。

求一个符号串α的FIRST集合若符号串α∈V*，α= X1 X2 … Xi-1 Xi … Xn, • 若X1不能推导导出ε, 则则 FIRST(α)= FIRST(X1) • 若对对任何j (1≤j≤i-1, 2≤i≤n) ε∈FIRST(Xj)• 若对对任何j (1≤j≤n) ε∈FIRST(Xj), 例: 求FIRST集G': E → TE'E'→ +TE'|εT → FT'T'→ *FT'|εF → (E) | i推出ε ENE'YTNT'YFNFIRST集( , i + ,ε( , i* ,ε( , i解题过题过程见见黑板!(5). 计计算FOLLOW集(a) 设设S为为文法中开始符号， 把 # 加入FOLLOW(S)中 (b) 若 A→αBβ是一个产产生式， 则则把 FIRST(β)\{ε} 加入 FOLLOW(B) 中 (c) 若 A→αB是一个产产生式,或 A→αBβ是一个产产生式,且β可推出ε,即ε∈FIRST(β) , 则则把 FOLLOW(A) 也加入 FOLLOW(B) 中 (d) 反复使用(b)直到每个非终结终结符的FOLLOW 集不再增大为为止例: 求FOLLOW集G': E →TE' E'→+TE'|ε T →FT' T'→*FT'|ε F →(E) | i推出ε FIRST集EN ( , i E'Y+ ,εTN( , iT'Y * ,εFN( , iFOLLOW集) , #) , #+ , ) , #+ , ) , #* , + , ) , #解题过题过程见见黑板!例: LL(1)文法判别别G': E →TE' E'→+TE'|ε T →FT' T'→*FT'|ε F →(E) | iFIRST(+TE') ∩ FIRST(ε)=Ø FIRST(E') ∩ FOLLOW(E')=ØFIRST(*FT') ∩ FIRST(ε)=Ø FIRST(T') ∩ FOLLOW(T')=ØFIRST((E)) ∩ FIRST(i)=Ø该该文法是LL(1)文法!(6). 计计算SELECT集给给定上下文无关文法的产产生式A→α, A∈VN, α∈V*, • 若α ε， SELECT(A→α) = FIRST(α) • 若α ε， SELECT(A→α) = (FIRST(α)－{ε})∪ FOLLOW(A)**G': E → TE'E'→ +TE'|εT → FT'T'→ *FT'|ε F → (E) | i推出 ε FIRST 集 EN ( , i E'Y+ ,ε TN( , i T'Y * ,ε FN( , iFOLLOW 集 ) , # ) , # + , ) , # + , ) , # * , + , ) , #SELECT集合E→TE'( , i E'→+TE'+ E'→ε) , # T → FT'( , i T'→ *FT'* T'→ ε+ , ) , # F → (E) ( F → ii例: 判断文法是否是LL1文法G: S→ABS→bC A→b A→εB→ε B→aD C→b C→ADD→aSD→c1.文法化简简2.消除左递归递归和提左公因子 Ø 求出能推出ε的非终结终结符 Ø 计计算FIRST集 Ø 计计算FOLLOW集 Ø 计计算SELECT集求出能推出ε的非终结终结符G: S→ABS→bC A→b A→εB→ε B→aD C→b C→ADD→aSD→cSABCD初值 未定 未定 未定 未定 未定 1YYN 2YN计计算FIRST集G: S→ABS→bC A→b A→εB→ε B→aD C→b C→ADD→aSD→c推出ε SY AY BY CN DN1) 求每个非 终结终结符的 FIRST集FIRST集 { b , a ,ε} {ε, b} {ε, a} { b , a , c} {a , c}2) 求每个产产 生式右部的 FIRST集FIRST(AB) ={a, b,ε} FIRST(bC) ={b}FIRST(AB) ∩ FIRST(bC)= {b}≠ Ø所以,该该文法不是LL(1)文法!计计算FOLLOW集G: S→ABS→bC A→b A→εB→ε B→aD C→b C→ADD→aSD→c推出ε FIRST集 SY{b, a,ε} AY{ε,b} BY{ε, a} CN{ b,a,c} DN{a , c}FOLLOW集 { #} {#,a,c } {#} {#} {#}计计算SELECT集G: S→AB S→bC A→b A→εB→ε B→aD C→b C→ADD→aSD→c所以,该该文法不是 LL(1)文法!SELECT集合S→ABb,a,#S→bCbA→εa,c,#A→bbB→ε#B→aDaC→ADa,b,cC→bbD→aSaD→ccbØØbØG': E → TE'E'→ +TE'|εT → FT'T'→ *FT'|ε F → (E) | i推出 ε FIRST 集 EN ( , i E'Y+ ,ε TN( , i T'Y * ,ε FN( , iFOLLOW 集 ) , # ) , # + , ) , # + , ) , # * , + , ) , #SELECT集合E→TE'( , i E'→+TE'+ E'→ε) , # T → FT'( , i T'→ *FT'* T'→ ε+ , ) , # F → (E) ( F → ii。