4.5-预测分析程序.ppt

第四章 4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL(1)分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL(1)分析中的错误处理 4.5 预测分析程序 4.5.1 预测分析程序工作过程 2.预测分析程序的模型 2.预测分析程序的工作过程 # :句子括号 S :文法的开始符号 X :存放当前栈顶符号的工作单元 a :存放当前输入符号a的工作单元 把 ‘#’和S 推入 STACK 栈 把第一个输入符号读进a; FLAG:=TRUE； WHILE FIAG DO 把STACK栈顶符号上托出去, 并放入Ｘ IF X∈VT THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF M[X, a]={ X→X1X2...XK } THEN 把XK，XK-1，…X1 一一推 进 STACK 　　ELSE　ERROR END OF WHILE; 对输入串 i+i*i# 进行分析 输入串i+i*i# 课后练习: 请参照p78 例4.6的分析步骤, 画出输入串 i*i+i 的语法树. 体会确定的自上而下分析过程, 及预测分析表的应用. 4.5 预测分析程序 4.5.2 预测分析表的构造 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集不再增大