（精）编译原理4.3.4-LL文法的判别.ppt

第四章 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1)分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL(1)分析中的错误处理 4.3 LL(1)分析法 4.3.1 左递归的消除 4.3.2 消除回溯、提左因子 4.3.3 LL(1)分析条件 4.3.4 LL(1)文法的判别 (4.5.2) 4.3.4 LL(1)文法的判别 (4.5.2) 文法中不得含有有害规则和多余规则 消除左递归和提左公因子 求出能 ε的非终结符 (补充) 计算FIRST集 计算FOLLOW集 计算SELECT集 (补充) 1. 求出能推出ε的非终结符 算法描述 建立一个一维数组X[ ]，用以记录非终结符能否推出ε。 ① 将数组X[ ]中对应每一非终结符的标记置初值为“未定”。 ② 扫描文法中的产生式。 (a) 若某一非终结符的某一产生式右部为ε, 则将数组中对应该非终结符的标志置为“是”， 并从文法中删除该非终结符的所有产生式。 (b) 若某一产生式右部含有终结符，则删除该产生式。(右部含有终结符，一定无法推出ε) 若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为否。 ③ 扫描产生式右部的每一符号。 (此时产生式右部全部为非终结符) (a) 若所扫描到的非终结符号在数组中对应的标志是是，则删去该非终结符， 若这使产生式右部为空， 则对产生式左部的非终结符在数组中对应的标志改是，并删除该非终结符为左部的所有产生式。 (b) 若所扫描到的非终结符号在数组中对应的标志是否，则删去该产生式， 若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”。 ④ 重复③，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。 2. 计算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), 例4.7 文法4.2 求FIRST集 P79 3. 计算FOLLOW集 (a) 设S为文法中开始符号， 把 # 加入FOLLOW(S)中 (b) 若A→αBβ是一个产生式， 则把FIRST(β)\{ε} 加入FOLLOW(B)中 (c) 若A→αB是一个产生式, 或A→αBβ是一个产生式, 且β可推出ε, 即ε∈FIRST(β) , 则把FOLLOW(A)也 加入FOLLOW(B)中。 (d) 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。 例4.7 文法4.2 求FOLLOW集 P79 例4.7 文法4.2 LL(1)文法判别 P79 G: E →TE E→+TE|ε T →FT T→*FT|ε F →(E) | i FIRST(+TE)∩FIRST(ε)=? FIRST(E)∩FOLLOW(E)=? FIRST(*FT)∩FIRST(ε)=? FIRST(T)∩FOLLOW(T)=? FIRST((E))∩FIRST(i)=? 4. 计算SELECT集 给定上下文无关文法的产生式A→α, A∈VN, α∈V*, 若α ε， SELECT(A→α) = FIRST(α) 若α ε， SELECT(A→α) = (FIRST(α)－{ε})∪