编译原理及实现技术 教学课件 作者 刘磊 第04章 语法分析-自顶向下分析方法.ppt

《编译原理及实现技术 教学课件 作者 刘磊 第04章 语法分析-自顶向下分析方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析-自顶向下分析方法主要内容：语法分析简介三个重要的集合自顶向下分析的条件递归下降语法分析LL(1)语法分析语法分析简介语法分析的功能语法错误类别语法错误的处理自顶向下分析的基本思想语法分析器的功能语法错误类别1)程序的开始符，语句（表达式）的开始符（后继符）错2)标识符（常量）错：该出现时未出现3)括号类错误：不匹配4)分隔符错：assignmentToken/TokenListParser语法树/语法错误信息语法错误处理要求：报告错误出现的位置修复错误并继续检查后续部分执行开销不应太大处理策略：1）紧急方

2、式恢复；2）短语级恢复；3）出错产生式；4）全局纠正；自顶向下分析基本思想从文法开始符出发试图推导出所给的终极符串。例G[z]:[1]ZaBd[2]Bd[3]Bc[4]BbB对给定的终极符串abcd，推导过程：Z[1]aBd[4]abBd[3]abcdZaBdbBcaBd#abcd#MatchBd#bcd#DerivationbBd#bcd#MatchBd#cd#Derivationcd#cd#Matchd#d#Match##Success自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E

3、)】Z#abcd#Derivation三个重要的集合First集的定义设G=(VT，VN，S，P)是上下文无关文法,(VTVN)*，则：First()={aVT

4、*a...}(if*then{}else)作用：可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。文法G3[S]:SaA

5、dAbAS

6、输入串W=abd。自顶向下的推导过程为:SaAabASabSabd相应的语法树为：SaAbASdFollow集的定义设G=(VT，VN，S，P)是上下文无关文

7、法，AVN，S是开始符号，则：Follow(A)={aVT

8、S+...Aa...}(ifS*...Athen{#}else)作用：当文法中存在产生式形如：A时，如果当前的字符属于Follow(A)，则用空取代A的出现。Predict集的定义Predict(A→)=First()，当First()=First()-{}Follow(A)，当First()计算First(X)集对每一文法符号X计算First(X)若XVT,First(X)={X}若XVN则First(X)={a

9、X

10、a…PSet,aVT}若XVN,且有产生式X,则First(X)若XVN,有产生式XY1Y2…Yn，且Y1,Y2,…,YiVN，则当Y1,Y2,…,Yi-1*，则First(Y1)-{},First(Y2)-{},…First(Yi-1)-{},First(Yi)都包含在First(X)中。当Yi*(i=1,2,…n),将{}并入First(X)中。计算First()集若符号串=X1X2…Xn，当X1,X2,…Xi-1*，Xi不能*，则First()=1i-1(Firs

11、t(Xj)-{})First(Xi)若所有Xi都能*，则First()=1nFirst(Xj)计算Follow集1:对所有BVN，令Follow(B):={}；对开始符S,令Follow(S):={#}；2:若有产生式A→xBy，如果First(y)则：Follow(B):=First(y)否则Follow(B):=(First(y)－{})Follow(A)3:重复2，直至对所有BVN，Follow(B)收敛为止。计算Predict集Predict(A→)=First()，当First()

12、不含=First()-{}Follow(A)，当First()含例子ETE’E’+TE’

13、TFT’T’*FT’

14、Fid

15、(E)Predict(ETE’)=first(TE’)={id,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’)=follow(E’)={),#}Predict(TFT’)=first(FT’)={id,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’)=follow(T’)={+,

16、),#}Predict(Fid)=first(id)={id}Predict(F(E))=first((E))={(}自顶向下分析方法的条件：predict(A→k)predict(A→j)=，当kj产生式A→被选择的条件是：当前的输入符属于predict(A→)。至多一个产生式被选择的条件是：pr