5.2-LL(1)文法的判别.ppt

LL(1)LL(1)文法的判文法的判别(1)(1)文法化文法化简 -不含有有害不含有有害规则和多余和多余规则(2)(2)消除左消除左递归和提左公因子和提左公因子(3)(3)求出能求出能 的非的非终结符符(4)(4)计算算FIRSTFIRST集集(5)(5)计算算FOLLOWFOLLOW集集(6)(6)计算算SELECTSELECT集集*(3).(3).求出能推出求出能推出 的非的非终结符符例例G:G:E E+T|T E E+T|T T T*F|F T T*F|F F (E)|i F (E)|i消除左消除左递归:G:G:E TE E TE E+E+TE|TE|T FT T FT T*T*FT|FT|F (E)|i F (E)|i推出推出E EN NE E Y YT TN NT T Y YF FN N解解题过程程见黑板黑板!算法描述算法描述建立一建立一个个一一维数数组X X，用以，用以记录非非终结符能否符能否推出推出。将数将数组X X 中中对应每一非每一非终结符的符的标记置初置初值为“未定未定”。扫描文法中的描文法中的产生式。生式。(a)(a)若某一非若某一非终结符的某一符的某一产生式右部生式右部为,则将数将数组中中对应该非非终结符的符的标志置志置为“是是”，并从并从文法中文法中删除除该非非终结符的所有符的所有产生式。生式。(b)(b)若某一若某一产生式右部含有生式右部含有终结符，符则删除除该产生式。生式。(右部含有右部含有终结符，一定无法推出符，一定无法推出)若若这使得以某一非使得以某一非终结符符为左部的所有左部的所有产生式都被生式都被删除，除，则将数将数组中中对应该非非终结符的符的标记值改改为 否否。扫描描产生式右部的每一符生式右部的每一符号号。(此此时产生式右部全部生式右部全部为非非终结符符)(a)(a)若若扫描到的非描到的非终结符在符在数数组中中对应的的标志是志是 是是,则删去去该非非终结符，符，若若这使使产生式右部生式右部为空空,则对产生式左部的非生式左部的非终结符在符在数数组中中对应的的标志改志改“是是”,并并删除除该非非终结符符为左部的左部的所有所有产生式生式。(b)(b)若若扫描到的非描到的非终结符在符在数数组中中对应的的标志是志是 否否,则删去去该产生式，生式，若若这使使产生式左部非生式左部非终结符的有符的有关关产生式都被生式都被删去，去，则把在把在数数组中中该非非终结符符对应的的标志改成志改成“否否”。重重复复，直到，直到扫描完一遍文法的描完一遍文法的产生式，生式，数数组中非中非终结符符对应的特征再的特征再没没有改有改变为止。止。(4).(4).计算算FIRSTFIRST集集对每一文法符每一文法符号号XV,XV,计算算FIRST(X)FIRST(X)(a)(a)若若XVXVT T，则FIRST(X)FIRST(X)XX(b)(b)若若XVXVN N，且有，且有产生式生式 X aX a,aVaVT T,则 aFIRST(XaFIRST(X)即把即把a a加入到加入到FIRSR(X)FIRSR(X)中中(c)(c)若若XVXVN N，且有，且有产生式生式 XX,则FIRST(XFIRST(X)(d)(d)若若XVXVN N,且有且有产生式生式XXY Y1 1 Y Y2 2 Y Yi-1i-1 Y Yi i Y Yn n,当当Y Y1 1 Y Y2 2 Y Yi-1i-1都能推出都能推出 时，则 FIRST(YFIRST(Y1 1)FIRST(YFIRST(Y2 2)FIRST(YFIRST(Yi-1i-1)FIRST(YFIRST(Yi i)都包含在都包含在FIRST(X)FIRST(X)中中(e)(e)当当(d)(d)中中XYXY1 1 Y Y2 2 Y Yn n所有所有Y Yj j 都可以推出都可以推出,(j=1,2,n),(j=1,2,n),则 FIRST(YFIRST(Y1 1)FIRST(YFIRST(Y2 2)FIRST(YFIRST(Yn n)都包含在都包含在FIRST(X)FIRST(X)中中 反反复复使用上述使用上述(b)(b)(e)(e)步直到每步直到每个个符符号号的的FIRSTFIRST集合不再增大集合不再增大为止。止。求一求一个个符符号号串串 的的FIRSTFIRST集合集合若符若符号号串串VV*，=X X1 1 X X2 2 X Xi-1i-1 X Xi i X Xn n,若若X X1 1不能推不能推导出出,则 FIRST(FIRST()=FIRST(X)=FIRST(X1 1)若若对任何任何j(1ji-1,2in)j(1ji-1,2in)FIRST(XFIRST(Xj j)若若对任何任何j(1jn)j(1jn)FIRST(XFIRST(Xj j),),例例:求求FIRSTFIRST集集G:G:E TE E TE E+E+TE|TE|T FT T FT T*T*FT|FT|F (E)|i F (E)|i推出推出 E EN NEEY YT TN NTTY YF FN NFIRSTFIRST集集(,i (,i+,+,(,i(,i*,*,(,i(,i解解题过程程见黑板黑板!(5).(5).计算算FOLLOWFOLLOW集集(a)(a)设S S为文法中文法中开开始符始符号号，把把#加入加入FOLLOW(S)FOLLOW(S)中中 (b)(b)若若 ABAB 是一是一个个产生式，生式，则把把 FIRST()FIRST()加入加入 FOLLOW(B)FOLLOW(B)中中 (c)(c)若若 ABAB是一是一个个产生式生式,或或 ABAB 是一是一个个产生式生式,且且 可推出可推出,即即FIRST(FIRST(),),则把把 FOLLOW(A)FOLLOW(A)也加入也加入 FOLLOW(B)FOLLOW(B)中中(d)(d)反反复复使用使用(b)(b)直到每直到每个个非非终结符的符的FOLLOWFOLLOW集集不再增大不再增大为止。止。例例:求求FOLLOWFOLLOW集集G:G:E TEE TEE+TE|E+TE|T FTT FTT*T*FT|FT|F(E)|iF(E)|i推出推出 FIRSTFIRST集集E EN N(,i (,i E E Y Y+,+,T TN N(,i(,iT T Y Y*,*,F FN N(,i(,iFOLLOWFOLLOW集集),#),#),#),#+,),#+,),#+,),#+,),#*,+,),#*,+,),#解解题过程程见黑板黑板!例例:LL(1):LL(1)文法判文法判别G:G:E TEE TEE+TE|E+TE|T FTT FTT*T*FT|FT|F(E)|iF(E)|iFIRST(+TEFIRST(+TE)FIRST(FIRST()=)=FIRST(EFIRST(E)FOLLOW(EFOLLOW(E)=)=FIRST(*FTFIRST(*FT)FIRST(FIRST()=)=FIRST(TFIRST(T)FOLLOW(TFOLLOW(T)=)=FIRST(E)FIRST(E)FIRST(iFIRST(i)=)=该文法是文法是LL(1)LL(1)文法文法!(6).(6).计算算SELECTSELECT集集给定上下文无定上下文无关关文法的文法的产生式生式AA,AVAVN N,VV*,*,若若 ，SELECT(ASELECT(A)=)=FIRST(FIRST()若若 ，SELECT(ASELECT(A)=)=(FIRST(FIRST()FOLLOW(A)FOLLOW(A)*G G:E TEE TE E E +TETE|T FTT FT T T *FTFT|F (E)|iF (E)|i推出推出 FIRSTFIRST集集E EN N(,i (,i EEY Y+,+,T TN N(,i(,iTTY Y*,*,F FN N(,i(,iFOLLOWFOLLOW集集),#),#),#),#+,),#+,),#+,),#+),#*,+,),#*,+,),#SELECTSELECT集合集合ETEETE(,i(,iE E+TE+TE+E E),#),#T FTT FT(,i(,iT T *FT*FT*T T +,),#+,),#F (E)F (E)(F iF ii i例例:判判断断文法是否是文法是否是LL1LL1文法文法G:G:SABSAB SbCSbCAbAbAA BBBaDBaDCbCbCADCAD DaSDaS DcDc1.1.文法化文法化简2.2.消除左消除左递归和提左公因子和提左公因子3.3.求出能推出求出能推出 的非的非终结符符4.4.计算算FIRSTFIRST集集5.5.计算算FOLLOWFOLLOW集集6.6.计算算SELECTSELECT集集求出能推出求出能推出 的非的非终结符符G:G:SABSAB SbCSbCAbAbAA BBBaDBaDCbCbCADCAD DaSDaS DcDcS SA AB BC CD D初初值 未定未定 未定未定 未定未定 未定未定 未定未定1 1Y YY YN N2 2Y YN N计算算FIRSTFIRST集集G:G:SABSAB SbCSbCAbAbAA BBBaDBaDCbCbCADCAD DaSDaS DcDc推出推出 S SY YA AY YB BY YC CN ND DN N1)1)求每求每个个非非终结符的符的FIRSTFIRST集集FIRSTFIRST集集 b,a,b,a,b,b,a,a b,a,b,a,cca,ca,c2)2)求每求每个个产生式右部的生式右部的FIRSTFIRST集集FIRST(AB)=a,FIRST(AB)=a,b,b,FIRST(bCFIRST(bC)=b)=bFIRST(AB)FIRST(AB)FIRST(bCFIRST(bC)=b)=b 所以所以,该文法不是文法不是LL(1)LL(1)文法文法!计算算FOLLOWFOLLOW集集G:G:SABSAB SbCSbCAbAbAA BBBaDBaDCbCbCADCAD DaSDaS DcDc推出推出 FIRSTFIRST集集S SY Yb,b,a,a,A AY Y,b,b B BY Y,a,aC CN N b,a,cb,a,c D DN Na,ca,cFOLLOWFOLLOW集集#,#,a,ca,c#计算算SELECTSELECT集集G:G:SABSABSbCSbCAbAbAA BBBaDBaDCbCbCADCAD DaSDaS DcDc所以所以,该文法不是文法不是LL(1)LL(1)文法文法!SELECTSELECT集合集合SABSABb,ab,a,#,#SbCSbCb bAAa,ca,c,#,#AbAbb bBB#BaDBaDa aCADCADa,b,ca,b,cCbCbb bDaSDaSa aDcDcc cb b b b G G:E TEE TE E E +TETE|T FTT FT T T *FTFT|F (E)|iF (E)|i推出推出 FIRSTFIRST集集E EN N(,i (,i EEY Y+,+,T TN N(,i(,iTTY Y*,*,F FN N(,i(,iFOLLOWFOLLOW集集),#),#),#),#+,),#+,),#+,),#+,),#*,+,),#*,+,),#SELECTSELECT集合集合ETEETE(,i(,iE E+TE+TE+E E),#),#T FTT FT(,i(,iT T *FT*FT*T T +,),#+,),#F (E)F (E)(F iF ii i