资源描述：
《编译原理4.3.4-LL文法的判别.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序4.6LL(1)分析中的错误处理4.3LL(1)分析法4.3.1左递归的消除4.3.2消除回溯、提左因子4.3.3LL(1)分析条件4.3.4LL(1)文法的判别(4.5.2)4.3.4LL(1)文法的判别(4.5.2)文法中不得含有有害规则和多余规则消除左递归和提左公因子求出能ε的非终结符(补充)计算FIRST集计算FOLLOW集计算SELECT集(补充)*例4.7文法4.2P79G:E→E+T
2、TT→T*F
3、FF→(E)
4、
5、i消除左递归:G':E→TE'E'→+TE'
6、εT→FT'T'→*FT'
7、εF→(E)
8、i推出εENE'YTNT'YFN1.求出能推出ε的非终结符建立一个一维数组X[]，用以记录非终结符能否推出ε。①将数组X[]中对应每一非终结符的标记置初值为“未定”。算法描述补充②扫描文法中的产生式。(a)若某一非终结符的某一产生式右部为ε,则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。(b)若某一产生式右部含有终结符，则删除该产生式。(右部含有终结符，一定无法推出ε)若这使得以某一非终结符为左部的所有产生式都被删除，则将数
9、组中对应该非终结符的标记值改为"否"。③扫描产生式右部的每一符号。(此时产生式右部全部为非终结符)(a)若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。(b)若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”。④重复③，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。2.计算FIRST集对每一文法
10、符号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)P78(d)若X∈VN,且有产生式X→Y1Y2…Yi-1Yi…Yn,当Y1Y2…Yi-1都能推出ε时，则FIRST(Y1)－{ε}FIRST(Y2)－{ε}…FIRST(Yi-1)－{ε}FIRST(Yi)都包含在FIRST(X)中。(e)当(d)中X→Y1Y2…Yn所有Yj都可以推出ε,(j=1,2,…n),则FI
11、RST(Y1)FIRST(Y2)…FIRST(Yn)都包含在FIRST(X)中反复使用上述(b)～(e)步直到每个符号的FIRST集合不再增大为止。求一个符号串α的FIRST集合若符号串α∈V*，α=X1X2…Xi-1Xi…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推出εENE'YTNT'YFNG':E→TE'E'→+TE'
12、εT→FT'T'→*FT'
13、εF→(E)
14、iFIRST
15、集(,i+,ε(,i*,ε(,i解题过程见黑板!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集P79G':E→TE'E'→+TE'
16、εT→FT'T'→*FT'
17、εF→(E)
18、i推出εFIRST
19、集EN(,iE'Y+,εTN(,iT'Y*,εFN(,iFOLLOW集),#),#+,),#+,),#*,+,),#解题过程见黑板!例4.7文法4.2LL(1)文法判别P79G':E→TE'E'→+TE'
20、εT→FT'T'→*FT'
21、εF→(E)
22、iFIRST(+TE')∩FIRST(ε)=ØFIRST(E')∩FOLLOW(E')=ØFIRST(*FT')∩FIRST(ε)=ØFIRST(T')∩FOLLOW(T')=ØFIRST((E))∩FIRST(i)=Ø该文法是LL(1)文法!4.计算SELECT集给定上下文无关文法的产生式A→α,A∈
23、VN,α∈V*,若αε，SELECT(A→α)=FIRST(α)若αε，SELECT(A→α)=(FIRST(α)－{ε})∪FOLLO
