编译原理课件Chapter5.ppt

《编译原理课件Chapter5.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、语法分析技术概况不确定的自顶向下分析法递归下降分析法确定的预测分析法LL(1)语法分析方法简单优先分析法优先分析法算符优先分析法自底向上分析法LR(0)分析法LR分析法SLR(1)分析法LR(1)分析法LALR(1)分析法第五章自顶向下语法分析方法自顶向下分析法的相关问题LL(1)文法的定义和判别文法等价变换确定的自顶向下分析法（递归下降程序法和预测分析法）5.1相关问题1、什么是语法分析？2、什么是自顶向下分析法？3、在自顶向下的分析过程中，存在的问题是什么？4、什么是确定的自顶向下分析法？文法G1[S]:SpA

2、[1]SqA[2]AcAd[3]Aa[4]输入串W=pccadd。自顶向下的推导过程为:SpApcAdpccAddpccadd相应的语法树为：pAcAdcAdaS存在的问题当一个非终结符号对应若干个规则时，选择哪个规则的右部对该非终结符号进行展开呢？例如：如果要被代换的最左非终结符号是U，且有n条规则：U::=A1

3、A2

4、…

5、An，那么如何确定用哪个规则的右部去替代U？文法G1[S]:SpA[1]SqA[2]AcAd[3]Aa[4]输入串W=pccadd。自顶向下的推导过程为:SpApcAd

6、pccAddpccadd相应的语法树为：pAcAdcAdaSFirst集的定义设G=(VT，VN，S，P)是上下文无关文法,其中(VTVN)*First()={aVT

7、a...}(ifεthen{ε})可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。**文法G3[S]:SaA[1]Sd[2]AbAS[3]Aε[4]输入串W=abd。自顶向下的推导过程为:SaAabASabSabd相应的语法树为：SaAbASεdFollow集的定义设G=(VT，V

8、N，S，P)是上下文无关文法，AVN，S是开始符号Follow(A)={aVT

9、S...Aa...}(ifS......Athen{#})当文法中存在推导形如：Aε时，如果当前的字符属于Follow(A)，则用空字符串取代A的出现。*++Select集的定义Select(A→)=First()，当εFirst()=(First()-{})Follow(A),当εFirst()结论:文法G是LL(1)文法的充要条件是,对于每个非终结符U有多个不同的产生式，比如为U→α和U→，满足:Sel

10、ect(U→α)∩Select(U→)=Φ5.2LL(1)文法的判别判别算法：1、计算非终结符是否能推出ε2、构造First集3、构造Follow集4、构造Select集并作判别文法G[E]：ETE’[1]E’+TE’[2]

11、[3]TFT’[4]T’*FT’[5]

12、[6]Fi[7]

13、(E)[8]EE’TT’FNYYNN计算First(X)集对每一文法符号X计算First(X)若XVT,First(X)={X}若XVN,且有产生式Xa…P,aVT,则aFirst(X)若XVN,且有产生式

14、Xε,则εFirst(X)若XVN,有产生式XY1Y2…Yn，且Y1,Y2,…,Yi任意一个文法符号，当Y1,Y2,…,Yi-1ε，则First(Y1)-{ε},First(Y2)-{ε},…First(Yi-1)-{ε},First(Yi)都包含在First(X)中。当Yiε(i=1,2,…n),将{ε}并入First(X)中。反复使用上述步骤，直到每个符号的First不再增大。**文法G[E]：ETE’[1]E’+TE’[2]

15、[3]TFT’[4]T’*FT’[5]

16、[6]Fi[7]

17、

18、(E)[8]First(E)First(T)First(E’)First(T’)First(F)*+i(计算First()集若符号串=X1X2…Xn，Xi为任意一文法符号当X1,X2,…Xi-1，Xi不能，则First()=(First(Xj)-{})First(Xi)若所有Xi都能，则First()=First(Xj)j=1ii-1j=1***文法G[E]：ETE’[1]E’+TE’[2]

19、[3]TFT’[4]T’*FT’[5]

20、[6]Fi[7]

21、(E)[8]First(

22、TE’)=First(+TE’)=First()=First(FT’)=First(*FT’)=First(i)=First((E))=First(T)={(,i}{+}{}First(F)={(,i}{*}{i}{(}计算Follow(X)集1:对所有XVN，令Follow(X)={}；对开始符S,令Follow(S)={#}；2:若有