5.2LL文法的判别.pptVIP

? LL(1)文法的判别 文法化简 - 不含有有害规则和多余规则 消除左递归和提左公因子 求出能 ε的非终结符☆ 计算FIRST集☆ 计算FOLLOW集☆ 计算SELECT集☆ (3). 求出能推出ε的非终结符 算法描述 建立一个一维数组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 (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 例: LL(1)文法判别 (6). 计算SELECT集 给定上下文无关文法的产生式A→α, A∈VN, α∈V*, 若α ε， SELECT(A→α) = FIRST(α) 若α ε， SELECT(A→α) = (FIRST(α)－{ε})∪ FOLLOW(A) 例: 判断文法是否是LL1文法 G: S→AB S→bC A→b A→ε B→ε B→aD C→b C→AD D→aS D→c 求出能推出ε的非终结符 G: S→AB S→bC A→b A→ε B→ε B→aD C→b C→AD D→aS D→c 计算FIRST集 G: S→AB S→bC A→b A→ε B→ε B→aD C→b C→AD D→aS D→c 计算