《自顶向下语法分析方法名师优质课赛课一等奖市公开课获奖课件》由会员分享，可在线阅读，更多相关《自顶向下语法分析方法名师优质课赛课一等奖市公开课获奖课件（42页珍藏版）》请在金锄头文库上搜索。
1、 第第5 5章章 自顶向下语法分析方法自顶向下语法分析方法语法分析主要工作：语法分析主要工作：是识别由词法分析给出单词序列是否是给定正确是识别由词法分析给出单词序列是否是给定正确句子（程序）。句子（程序）。语法分析惯用方法：语法分析惯用方法：自顶向下语法分析和自底向上语法分析两大类。自顶向下语法分析和自底向上语法分析两大类。第1页自顶向下分析思想自顶向下分析思想自顶向下方法：自顶向下方法：从文法开始符号（设为从文法开始符号（设为程序程序）开始进行分析，逐步推导）开始进行分析，逐步推导往下结构语法树，使其树叶恰好结构出所给定源程序串。往下结构语法树，使其树叶恰好结构出所给定源程序串。自顶向下主要
2、思想：自顶向下主要思想：从开始符出发导出句型并一个符号一个符号地与给定终止从开始符出发导出句型并一个符号一个符号地与给定终止符串进行匹配。假如全部匹配成功，则表示开始符号可推导出符串进行匹配。假如全部匹配成功，则表示开始符号可推导出给定终止符串。所以判定给定终止符号串是正确句子。给定终止符串。所以判定给定终止符号串是正确句子。自顶向下方法关键：自顶向下方法关键：是确定在推导过程中选择候选式问题。当进行推导时，是确定在推导过程中选择候选式问题。当进行推导时，一个非终止符可能对应多个产生式，这么我们就无法事先知道一个非终止符可能对应多个产生式，这么我们就无法事先知道应该用哪个产生式，所以实用都作了
3、一些限制。方便在任何情应该用哪个产生式，所以实用都作了一些限制。方便在任何情况下都能确定应该用产生式。况下都能确定应该用产生式。第2页自顶向下缺点自顶向下缺点:在推导过程中，假如对文法不做限制。那么产生在推导过程中，假如对文法不做限制。那么产生式选择成为无依据，只好一一去试全部可能产生式，式选择成为无依据，只好一一去试全部可能产生式，直至成功为止。这种方法致命弱点是不停地回溯，大直至成功为止。这种方法致命弱点是不停地回溯，大大影响速度。大影响速度。所以自顶向下分析法又分为确定和不确所以自顶向下分析法又分为确定和不确定两种：定两种：确定分析方法需对文法有一定限制，但因为实现确定分析方法需对文法有
4、一定限制，但因为实现方法简单，直观，便于手工结构或自动生成语法分析方法简单，直观，便于手工结构或自动生成语法分析器，所以仍是当前常有方法之一。器，所以仍是当前常有方法之一。不确定方法即回溯分析方法。这种方法实际上是不确定方法即回溯分析方法。这种方法实际上是一个穷举试探方法，所以效率低，代价高，所以极少一个穷举试探方法，所以效率低，代价高，所以极少使用。使用。第3页5.1 5.1 5.1 5.1 确定自顶向下分析思想确定自顶向下分析思想确定自顶向下分析思想确定自顶向下分析思想例例5.1若有文法若有文法GS：S pA S qB A cAd A a 若有输入串若有输入串w=pccadd.w=pcca
5、dd.解：解：推导过程为：推导过程为：其对应语法树见右图：其对应语法树见右图：SS这个文法特点这个文法特点：1每个产生式右部都由终止符号开始。每个产生式右部都由终止符号开始。2假如两个产生有相同左部，那么它们右部由不一样终止符假如两个产生有相同左部，那么它们右部由不一样终止符开始。开始。显然对于这么推导中完全能够依据当前输入符号决定选择哪个显然对于这么推导中完全能够依据当前输入符号决定选择哪个产生式往下推导。所以分析过程是唯一。产生式往下推导。所以分析过程是唯一。pcAdcAdpccAddcAdpccaddapApA考查自顶向下推导过程。考查自顶向下推导过程。第4页例例例例5.25.2：若有文
6、法若有文法G2S：S Ap S Bq A a A cA B b B dB 若有输入串若有输入串w=ccapw=ccap。考查自顶向下推导过程。考查自顶向下推导过程。解：解：自顶向下推导过程为：自顶向下推导过程为：其对应语法树见右图：其对应语法树见右图：SS这个文法特点这个文法特点：1产生式右部不全是由终止符号开始。产生式右部不全是由终止符号开始。2假如两个产生有相同左部，它们右部由不一样终止符或非假如两个产生有相同左部，它们右部由不一样终止符或非终止符开始。终止符开始。3文法中无空产生式。文法中无空产生式。ccApcAAppAAcApcccapa第5页小结：小结：小结：小结：在上述推导过程中，
7、对于产生式中相同左部含有在上述推导过程中，对于产生式中相同左部含有非终止符打头右部时，在推导中选取哪个产生式是不非终止符打头右部时，在推导中选取哪个产生式是不能直接知道。能直接知道。对输入串对输入串W=ccap为输入串时，其第一个符号为为输入串时，其第一个符号为c，这时从，这时从S出发选择出发选择S Ap，还是选择，还是选择S Bq。其依。其依据是要知道据是要知道 A或或B它们是否能推导以它们是否能推导以c打头符号串，即打头符号串，即它们首符集是什么。若它们首符集是什么。若c是是Ap首符集元素，且不在首符集元素，且不在Bq首符集中，则选择首符集中，则选择S Ap往下推导。反之，若往下推导。反之
8、，若c在在Bq首首符集中，不在符集中，不在Ap首符集中，则选择首符集中，则选择S Bq往下推导。往下推导。其它情况为不确定推导或犯错。其它情况为不确定推导或犯错。所以，在推导前有必要求出每个文法符号首符集。所以，在推导前有必要求出每个文法符号首符集。第6页一一一一.首符集，后继符集与选择集定义：首符集，后继符集与选择集定义：首符集，后继符集与选择集定义：首符集，后继符集与选择集定义：定义定义定义定义4-14-1（首符集定义）：（首符集定义）：（首符集定义）：（首符集定义）：设设G=(VN，VT，P，S）是上下文无关文法，）是上下文无关文法，是是G任一符号串，则有：任一符号串，则有：FIRST（
9、）=a|*a,a VT，、V*尤其地，若尤其地，若*，则要求，则要求 FIRST()即：即：FIRST()是从是从出发推导出全部符号串首终止符出发推导出全部符号串首终止符或可能或可能组成集合。组成集合。第7页这么在文法这么在文法 G2中，关于中，关于S两个产生式即使都以非两个产生式即使都以非终止符开始，但它们右部符号串能够推导出首符集合终止符开始，但它们右部符号串能够推导出首符集合互不相交，所以可依据当前输入符号是属于哪个产生互不相交，所以可依据当前输入符号是属于哪个产生式右部首符号集合而决定选择对应产生式进行推导。式右部首符号集合而决定选择对应产生式进行推导。所以是确定自顶向下分析。所以是确
10、定自顶向下分析。有文法有文法G2S：S Ap S Bq A a A cA B b B dB 第8页例例例例5.3:5.3:5.3:5.3:若有文法若有文法G3S:SaAS dA bASA若有输入串若有输入串W=abd。考查自顶向下推导过程。考查自顶向下推导过程。解：解：对应语法树为右图：对应语法树为右图：SSaAaAabASb A SabSabdd当文法中有空产生式时当文法中有空产生式时,如例：如例：第9页小小 结：结：由此能够看出，当某一非终止符产生式中含有空产由此能够看出，当某一非终止符产生式中含有空产生式时，它非空产生式右部首符号集两两不相交，并与生式时，它非空产生式右部首符号集两两不相
11、交，并与在推导过程中紧跟该非终止符右边可能出现终止符集也在推导过程中紧跟该非终止符右边可能出现终止符集也不相交，则仍可结构确定自顶向下分析。为此可定义一不相交，则仍可结构确定自顶向下分析。为此可定义一个文法符号后继符集合为：个文法符号后继符集合为：（定义（定义5.2）从上述推导过程中我们能够在第二步到第三步推导从上述推导过程中我们能够在第二步到第三步推导中，即中，即abAS abS时，因当前面临输入符号为时，因当前面临输入符号为d，而最，而最左非终止符左非终止符A产生式右部开始集合都不包含产生式右部开始集合都不包含d，但有，但有，所，所以对于以对于d匹配自然认为只能依赖于在可能推导过程中匹配自
12、然认为只能依赖于在可能推导过程中A后后面符号。所以这时选取产生式面符号。所以这时选取产生式A 往下推导，而当前往下推导，而当前A后面符号为后面符号为S，S产生式右部开始符号包含了产生式右部开始符号包含了d，所以匹配。，所以匹配。第10页FOLLOW(A)=a|S *A且且aVT,a FIRST(),VT*,V*或或 FOLLOW(A)=a|S *Aa,aVT定义定义定义定义5.2:5.2:尤其地，若尤其地，若S *A,则则#FOLLOW(A)(这里这里#不是文法中符号，而一个尤其表示输入串结束符或称句子不是文法中符号，而一个尤其表示输入串结束符或称句子括号如括号如#输入串输入串#）表示：全部在
13、句型中紧挨着表示：全部在句型中紧挨着A出现终止符或出现终止符或#均是均是 FOLLOW(A)元素。元素。所以当文法中含有形如：所以当文法中含有形如：A和和 A产生式时，其中产生式时，其中AVN,V*,当当和和不一样时推导出空串时，设不一样时推导出空串时，设*，则当则当FIRST()(FIRST()FOLLOW(A)=时，对于非终止符时，对于非终止符A替换仍可唯一地确定候选。替换仍可唯一地确定候选。设设G=(VN,VT,P,S)是上下文无关文法，是上下文无关文法，AVN后继符集合为：后继符集合为：*第11页定义定义5.35.3：定义选择符集合定义选择符集合SELECT以下：以下：对于给出上下文无
14、关文法产生式对于给出上下文无关文法产生式A,AVN,V*，则，则 SELECT(A)=FIRST()，当当 时时FIRST()FOLLOW(A)，不然，不然*第12页（一）（一）求求FIRST(X)算法算法 对每一文法符号对每一文法符号X(VNVT），求），求FIRST(X).(a)若若XVT,则令则令FIRST(X)=X;(b)若若XVN,且有产生式且有产生式Xa.,(aVT)，则令，则令aFIRST(X);(c)若若XVN,有有X，则令，则令 FIRST(X);(d)若若 XVN,y1,y2,.yi都都VN,且有产生式且有产生式X y1 y2.yn,三种集合结构算法：三种集合结构算法：注：
15、三注：三种集合均为终止符集种集合均为终止符集 当当y1,y2,.yi-1 都都 *时，（其中时，（其中1in),则则FIRST(y1)-,FIRST(y2)-,.,FIRST(yi-1)-,FIRST(yi)都包含在都包含在 FIRST(X)中。中。(e)当当(d)中全部中全部yi *(i=1,2,.,n),则则 FIRST(X)=FIRST(y1)FIRST(y2).FIRST(yn)重复使用上述（重复使用上述（b)(d)步直到每个符号步直到每个符号FIRST集合不再增加集合不再增加为止。为止。第13页（二）求（二）求（二）求（二）求 FIRST()FIRST()算法（算法（算法（算法（=x
16、=x1 1 x x2 2.x.xn n):):1.若若n=0,即即=,则令则令FIRST()=;2.不然，对不然，对1in,求求FIRST(xi)3.若若n=1,则令则令 FIRST()=FIRST(x1);4.若若n2且对一切且对一切j=1,2,.,i-1都有都有FIRST(xj).则令则令FIRST(xi)-=FIRST(),其中其中2in;若对一切若对一切 j=1,2,n都有都有FIRST(xj),则令则令FIRST()或：或：1.把把FIRST(x1)中全部非中全部非元素加入到元素加入到FIRST()中，即中，即 FIRST()=FIRST(x1)-;若若FIRST(x1)包含有包含有，则把，则把FIRST(x2)全部非全部非元素加入到元素加入到 FIRST()中，即中，即FIRST()=FIRST()(FIRST(x2)-);若若FIRST(x1)和和FIRST(x2)都包含有都包含有，则把，则把FIRST(x3)全部全部 非非元素加到元素加到FIRST()中；中；照此方法继续，一直到考查到照此方法继续，一直到考查到xn。2.若若FIRST(xi),i=1,2,n;即每个即每
