《自顶向下语法分析》PPT课件

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

1、第5章语法分析—自顶向下的方法语法分析是编译过程的核心部分，主要任务是按照程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成份，并进行语法检查，为语义分析和代码生成作准备。方法：自顶向下分析方法和自底向上分析方法（算符优先，LR分析）。1自上而下分析(面向目标的分析方法)从文法的开始符号出发,企图推导出与输入符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则不是。第5章语法分析—自顶向下的方法2自上而下分析又分为不确定的和确定的两种不确定的分析方法（带回溯的分析方法），它实际上是

2、一种穷举的试探方法。因效率低，故极少使用。确定的分析方法需对文法有一定的限制，又分为递归子程序方法，预测表法确定的自上而下分析要求文法不能含有左递归规则,本章重点研究LL(1)文法（定义、判定、分析方法）。第5章语法分析—自顶向下的方法3确定的分析方法的基本思想：从文法的开始符号出发，考虑如何根据当前输入符号唯一地确定选用哪个产生式代替相应非终结符以往下推导（构造一棵相应的语法树）。5.1确定的自顶向下分析思想4例5.1:识别输入串w=pccadd是否是文法G[S]的句子S→pA

3、qBA→cAd

4、aB→dB

5、c可预测

6、的试探推导过程：SpApcAdpccAddpccadd5.1确定的自顶向下分析思想文法G[s]特点：每个产生式右部都是由终结符开始；若两个产生式左部相同则右部由不同的终结符开始。5例5.2:对文法G[S]写出w=ccap的推导过程S→Ap

7、BqA→cA

8、aB→dB

9、b推导过程:SApcApccApccap5.1确定的自顶向下分析思想文法特点产生式右部不全有终结符开始相同左部的产生式右部有不同的终结符或非终结符文法中无空产生式6FIRST集的定义设G=(VT,VN,P,S)是上下文无关文法FIRST(

10、)={a

11、=>*a,a∈VT,,∈V*}若=>*ε则规定ε∈FIRST()FIRST(α)就是从α可能推导出的所有开头终结符号和可能的ε所构成的集合。虽然例5.2中文法关于S的两个产生式都是以非终结符开始，但是它们右部的FIRST集不相交，故仍能构造确定的自顶向下分析。5.1确定的自顶向下分析思想75.1确定的自顶向下分析思想文法符号的FIRST集合构造方法：对于文法中的符号X∈VN∪VT，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止：1)若X∈VT，则FIRST(

12、X)={X}2)若X∈VN，且具有形如X→aα的产生式(a∈VT)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。83)设G中有形如X→Y1…Yk的产生式,其中X,Y1…Yk∈VN，且Y1…Yi-1均能=>*ε(1≤i≤k)，则FIRST(Y1)-{ε},…,FIRST(Yi-1)-{ε},FIRST(Yi)都包含在FIRST(X)中。4)若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε符号加进FIRST(X)。5.1确定的自顶向下分析思想9对于文法G的任一符号串α=X1X2…Xn可按下列步骤构造其

13、FIRST(α)集合：1)置FIRST(α)=φ2)将FIRST(X1)中的一切非ε符号加进FIRST(α)；3)若ε∈FIRST(X1)，将FIRST(X2)中的一切非ε符号加进FIRST(α)；若ε∈FIRST(X1)和FIRST(X2)，将FIRST(X3)中的一切非ε符号加进FIRST(α)；依次类推。4)若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε符号加进FIRST(α)。5.1确定的自顶向下分析思想10例5.3，有文法E→TE’E’→+TE’E’→εT→FT’T’→*FT’T’→εF→(E)

14、i求

15、文法中非终结符及符号串的FIRST集。解：首先求各符号的FIRST集：该文法共有非终结符号为{E，E’，T，T’，F}FIRST(E)=FIRST(T)=FIRST(F)={(，i}FIRST(E’)={+，ε}FIRST(T’)={*，ε}求文法中各产生式右部符号串的FIRST集：FIRST(TE’)=FIRST(T)={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)={(，i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)={i}5

16、.1确定的自顶向下分析思想11例5.4:G[S]:含有空产生式的例子S→aAS→dA→bASA→ε对输入串abd的推导:SaAabASabSabd当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。5.1确定的自顶向下