语法分析-自顶向下分析.ppt

《语法分析-自顶向下分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章语法分析—自顶向下分析Pursuebreakthroughsinyourlife.追求自我的突破。第四章语法分析—自顶向下分析(P61)4.1自顶向下分析方法4.2FIRST集合和FOLLOW集合4.3递归下降分析4.4LL(1)分析方法学习重点FIRST集合和FOLLOW集合的求法递归子程序的构造方法LL(1)文法及其分析表的构造方法第四章语法分析—自顶向下分析语法：是指如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则。语法分析与词法分析的区别：语法分析和词法分析都是对输入符号串的识别，但词法分析的输入符号串是一

2、个单词，而语法分析的输入符号串是一个句子或者说是一个程序。语法分析任务：检查源程序语法上是否正确，并生成相应的内部表示（如分析树）供下一阶段使用。例对于C程序语句“if(a<10)b=5；”，词法分析识别出了if、(、a、…等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确，例如if后面是否为(，(后面是否为正确的表达式等等。第四章语法分析—自顶向下分析语法分析方法的分类（分类标准是按照识别句子时建立语法树的方法）：回溯示例√√√4.1自顶向下的分析方法（P61）自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向

3、下推导，试图推导出要分析的输入串。即：开始符号输入符号串+自底向上的分析方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：开始符号输入符号串归约←SaASaAaaSbAaaSbbaaaabbaa自上而下自底向上输入串开始符号图示：自上而下分析与自底向上分析4.2FIRST集合和FOLLOW集合（P62）FIRST集合定义：假定α是文法G的任一符号串，则：FIRST(α)={a

4、αa…，a∈Vt}若αε,则规定ε∈FIRST(α)。**实际上，FIRST(α)就是从α可能推导出的所有开头终结符号或ε。文法

5、符号的FIRST集合构造方法：对于文法中的符号X∈V，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止：1)若X∈Vt，则FIRST(X)={X}。2)若X∈Vn，且具有形如X→aα的产生式(a∈Vt)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。3)设G中有形如X→Y1Y2…Yk的产生式，若Y1∈Vn，则把FIRST(Y1)中的一切非ε符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi

6、)中的一切非ε符号加进FIRST(X)；但若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε符号加进FIRST(X)。文法符号的FIRST集合构造方法：对于文法中的符号X∈V，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止：1)若X为终结符，则将X加入FIRST(X)集合中。2)若X为非终结符，且具有形如X→aα的产生式(a∈Vt)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。3)设X为非终结符且有形如X→Y1Y2…Yk的产生式，若Y1∈Vn，则把FIRST(Y1)中的一切非ε符

7、号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi)中的一切非ε符号加进FIRST(X)；但若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε符号加进FIRST(X)。对于文法G的任一符号串α=X1X2…Xn可按下列步骤构造其FIRST(α)集合：1)置FIRST(α)=φ;2)将FIRST(X1)中的一切非ε符号加进FIRST(α)；3)若ε∈FIRST(X1)，将FIRST(X2)中的一切非ε符号加进FIRST(α)；若ε∈FIR

8、ST(X1)和FIRST(X2)，将FIRST(X3)中的一切非ε符号加进FIRST(α)；其余类推。4)若对于一切1≤i≤n，ε∈FIRST(Xi)，则将ε符号加进FIRST(α)。4.2FIRST集合和FOLLOW集合例4-1(P62)有文法：E→TE′E′→+TE′E′→εT→FT′T′→*FT′T′→εF→(E)

9、i求文法中非终结符号以及各产生式右部符号串的FIRST集。解：该文法的非终结符号有E、E′、T、T′和F。FIRST(E)=FIRST(TE′)=FIRST(FT′E′)={(，i}FIRST(+TE′)={+}FI

10、RST(ε)={ε}FIRST(E′)=FIRST(+TE′)∪FIRST(ε)={+，ε}FIRST(T)=FIRST(FT′)={(，i}FIRST(*FT′)={*}FIRST(T′)=FIRST(*FT′)∪FI