资源描述
武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 第第5 5章章 自顶向下语法分析办法自顶向下语法分析办法语法分析主要工作：语法分析主要工作：是辨认由词法分析给出单词序列是否是给定正确是辨认由词法分析给出单词序列是否是给定正确句子（程序）。句子（程序）。语法分析惯用办法：语法分析惯用办法：自顶向下语法分析和自底向上语法分析两大类。自顶向下语法分析和自底向上语法分析两大类。第1页第1页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌自顶向下分析思想自顶向下分析思想自顶向下办法：自顶向下办法：从文法开始符号（设为从文法开始符号（设为程序程序）开始进行分析，逐步推导）开始进行分析，逐步推导往下结构语法树，使其树叶正好结构出所给定源程序串。往下结构语法树，使其树叶正好结构出所给定源程序串。自顶向下主要思想：自顶向下主要思想：从开始符出发导出句型并一个符号一个符号地与给定终止从开始符出发导出句型并一个符号一个符号地与给定终止符串进行匹配。假如所有匹配成功，则表示开始符号可推导出符串进行匹配。假如所有匹配成功，则表示开始符号可推导出给定终止符串。因此鉴定给定终止符号串是正确句子。给定终止符串。因此鉴定给定终止符号串是正确句子。自顶向下办法关键：自顶向下办法关键：是拟定在推导过程中选择候选式问题。当进行推导时，是拟定在推导过程中选择候选式问题。当进行推导时，一个非终止符也许相应多个产生式，这样我们就无法事先知道一个非终止符也许相应多个产生式，这样我们就无法事先知道应当用哪个产生式，因此实用都作了一些限制。以便在任何情应当用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能拟定应当用产生式。况下都能拟定应当用产生式。第2页第2页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌自顶向下缺点自顶向下缺点:在推导过程中，假如对文法不做限制。那么产生在推导过程中，假如对文法不做限制。那么产生式选择成为无依据，只好一一去试所有也许产生式，式选择成为无依据，只好一一去试所有也许产生式，直至成功为止。这种办法致命弱点是不断地回溯，大直至成功为止。这种办法致命弱点是不断地回溯，大大影响速度。大影响速度。因此自顶向下分析法又分为拟定和不拟因此自顶向下分析法又分为拟定和不拟定两种：定两种：拟定分析办法需对文法有一定限制，但由于实现拟定分析办法需对文法有一定限制，但由于实现办法简朴，直观，便于手工结构或自动生成语法分析办法简朴，直观，便于手工结构或自动生成语法分析器，因此仍是当前常有办法之一。器，因此仍是当前常有办法之一。不拟定办法即回溯分析办法。这种办法事实上是不拟定办法即回溯分析办法。这种办法事实上是一个穷举试探办法，因此效率低，代价高，因此很少一个穷举试探办法，因此效率低，代价高，因此很少使用。使用。第3页第3页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌5.1 5.1 5.1 5.1 拟定自顶向下分析思想拟定自顶向下分析思想拟定自顶向下分析思想拟定自顶向下分析思想例例5.1若有文法若有文法GS：S pA S qB A cAd A a 若有输入串若有输入串w=pccadd.w=pccadd.解：解：推导过程为：推导过程为：其相应语法树见右图：其相应语法树见右图：SS这个文法特点：1每个产生式右部都由终止符号开始。2假如两个产生有相同左部，那么它们右部由不同终止符开始。显然对于这样推导中完全能够依据当前输入符号决定选择哪个显然对于这样推导中完全能够依据当前输入符号决定选择哪个产生式往下推导。因此分析过程是唯一。产生式往下推导。因此分析过程是唯一。pcAdcAdpccAddcAdpccaddapApA考察自顶向下推导过程。考察自顶向下推导过程。第4页第4页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例例例5.25.2：若有文法若有文法G2S：S Ap S Bq A a A cA B b B dB 若有输入串若有输入串w=ccapw=ccap。考察自顶向下推导过程。考察自顶向下推导过程。解：解：自顶向下推导过程为：自顶向下推导过程为：其相应语法树见右图：其相应语法树见右图：SS这个文法特点：1产生式右部不全是由终止符号开始。2假如两个产生有相同左部，它们右部由不同终止符或非终止符开始。3文法中无空产生式。ccApcAAppAAcApcccapa第5页第5页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌小结：小结：小结：小结：在上述推导过程中，对于产生式中相同左部含有在上述推导过程中，对于产生式中相同左部含有非终止符打头右部时，在推导中选取哪个产生式是不非终止符打头右部时，在推导中选取哪个产生式是不能直接知道。能直接知道。对输入串对输入串W=ccap为输入串时，其第一个符号为为输入串时，其第一个符号为c，这时从，这时从S出发选择出发选择S Ap，还是选择，还是选择S Bq。其依。其依据是要知道据是要知道 A或或B它们是否能推导以它们是否能推导以c打头符号串，即打头符号串，即它们首符集是什么。若它们首符集是什么。若c是是Ap首符集元素，且不在首符集元素，且不在Bq首符集中，则选择首符集中，则选择S Ap往下推导。反之，若往下推导。反之，若c在在Bq首首符集中，不在符集中，不在Ap首符集中，则选择首符集中，则选择S Bq往下推导。往下推导。其它情况为不拟定推导或犯错。其它情况为不拟定推导或犯错。因此，在推导前有必要求出每个文法符号首符集。因此，在推导前有必要求出每个文法符号首符集。第6页第6页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌一一一一.首符集，后继符集与选择集定义：首符集，后继符集与选择集定义：首符集，后继符集与选择集定义：首符集，后继符集与选择集定义：定义定义定义定义4-14-1（首符集定义）：（首符集定义）：（首符集定义）：（首符集定义）：设设G=(VN，VT，P，S）是上下文无关文法，）是上下文无关文法，是是G任一符号串，则有：任一符号串，则有：FIRST（）=a|*a,a VT，、V*尤其地，若尤其地，若*，则要求，则要求 FIRST()即：即：FIRST()是从是从出发推导出所有符号串首终止符出发推导出所有符号串首终止符或也许或也许构成集合。构成集合。第7页第7页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌这样在文法这样在文法 G2中，关于中，关于S两个产生式即使都以非两个产生式即使都以非终止符开始，但它们右部符号串能够推导出首符集合终止符开始，但它们右部符号串能够推导出首符集合互不相交，因此可依据当前输入符号是属于哪个产生互不相交，因此可依据当前输入符号是属于哪个产生式右部首符号集合而决定选择相应产生式进行推导。式右部首符号集合而决定选择相应产生式进行推导。因此是拟定自顶向下分析。因此是拟定自顶向下分析。有文法有文法G2S：S Ap S Bq A a A cA B b B dB 第8页第8页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例例例5.3:5.3:5.3:5.3:若有文法若有文法G3S:SaAS dA bASA若有输入串若有输入串W=abd。考察自顶向下推导过程。考察自顶向下推导过程。解：解：相应语法树为右图：相应语法树为右图：SSaAaAabASb A SabSabdd当文法中有空产生式时当文法中有空产生式时,如例：如例：第9页第9页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌小小 结：结：由此能够看出，当某一非终止符产生式中含有空产由此能够看出，当某一非终止符产生式中含有空产生式时，它非空产生式右部首符号集两两不相交，并与生式时，它非空产生式右部首符号集两两不相交，并与在推导过程中紧跟该非终止符右边也许出现终止符集也在推导过程中紧跟该非终止符右边也许出现终止符集也不相交，则仍可结构拟定自顶向下分析。为此可定义一不相交，则仍可结构拟定自顶向下分析。为此可定义一个文法符号后继符集合为：个文法符号后继符集合为：（定义（定义5.2）从上述推导过程中我们能够在第二步到第三步推导从上述推导过程中我们能够在第二步到第三步推导中，即中，即abAS abS时，因当前面临输入符号为时，因当前面临输入符号为d，而最，而最左非终止符左非终止符A产生式右部开始集合都不包括产生式右部开始集合都不包括d，但有，但有，因，因此对于此对于d匹配自然认为只能依赖于在也许推导过程中匹配自然认为只能依赖于在也许推导过程中A后后面符号。因此这时选取产生式面符号。因此这时选取产生式A 往下推导，而当前往下推导，而当前A后面符号为后面符号为S，S产生式右部开始符号包括了产生式右部开始符号包括了d，因此匹配。，因此匹配。第10页第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)(这里这里#不是文法中符号，而一个尤其表示输入串结束符或称句子不是文法中符号，而一个尤其表示输入串结束符或称句子括号如括号如#输入串输入串#）表示：所有在句型中紧挨着表示：所有在句型中紧挨着A出现终止符或出现终止符或#均是均是 FOLLOW(A)元素。元素。因此当文法中含有形如：A和 A产生式时，其中AVN,V*,当和不同时推导出空串时，设*，则当FIRST()(FIRST()FOLLOW(A)=时，对于非终止符A替换仍可唯一地确定候选。设设G=(VN,VT,P,S)是上下文无关文法，是上下文无关文法，AVN后继符集合为：后继符集合为：*第11页第11页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌定义定义5.35.3：定义选择符集合定义选择符集合SELECT下列：下列：对于给出上下文无关文法产生式对于给出上下文无关文法产生式A,AVN,V*，则，则 SELECT(A)=FIRST()，当当 时时FIRST()FOLLOW(A)，不然，不然*第12页第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,三种集合结构算法：三种集合结构算法：注：三注：三种集合均为终止符集种集合均为终止符集 当当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页第13页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌（二）求（二）求（二）求（二）求 FIRST()FIRST()算法（算法（算法（算法（=x=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;即每个即每个FIRST(xi)中都有中都有。则将。则将加加 到到FIRST()中。尤其地，中。尤其地，若若=，则，则FIRST()=.第14页第14页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌(三三三三)求求求求FOLLOW(A)FOLLOW(A)算法算法算法算法(A(A V VN N):):(a)对文法开始符号对文法开始符号S，令，令#FOLLOW(S).(b)若若BABA是一个产生式，则令是一个产生式，则令FIRST()-属于属于FOLLOW(A);(c)若若BA是一个产生式，或是一个产生式，或BA是一个产生是一个产生 式且有式且有FIRST()，则令，则令FOLLOW(B)是是 FOLLOW(A)子集。即把子集。即把FOLLOW(B)所有元素所有元素 加入到加入到FOLLOW(A)中。中。(d)重复使用重复使用(b)直到每个非终止符直到每个非终止符 FOLLOW集合集合 不再增长为止。不再增长为止。第15页第15页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌(四四四四)求求求求SELECT(A)SELECT(A)算法：算法：算法：算法：(a)求求FIRST()；(b)若若 FIRST(),则令则令SELECT(A)=FIRST()不然求不然求FOLLOW(A),并令并令SELECT(A)=FIRST()FOLLOW(A).例：有文法：例：有文法：ETE E+TE|TFT T*FT|Fi|(E)求其三种集合。求其三种集合。第16页第16页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌解：解：FIRST(E)=FIRST(T)=FIRST(F)=i,(FIRST(E)=+,FIRST(T)=*,FOLLOW(E)=FOLLOW(E)=),#FOLLOW(T)=FOLLOW(T)=+,),#FOLLOW(F)=*,+,),#SELECT(ETE)=FIRST(T)=i,(SELECT(E+TE)=FIRST(+TE)=+SELECT(E)=FIRST()FOLLOW(E)=,),#SELECT(TFT)=FIRST(F)=i,(SELECT(T*FT)=FIRST(*FT)=*SELECT(T)=FIRST()FOLLOW(T)=,+,),#SELECT(Fi)=FIRST(i)=iSELECT(F(E)=FIRST(E)=(例：有文法：例：有文法：ETE E+TE|TFT T*FT|Fi|(E)求其三种集合。求其三种集合。第17页第17页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例：例：设有文法设有文法GS：SaAS ，Sb，AbA ，A 5.2 LL(1)5.2 LL(1)文法判别文法判别文法判别文法判别定义5.4：一个上下文无关文法是LL(1)文法充分必要条件是每个非终止符A两个不同产生式，A ,A ；满足 SELECT(A )SELECT(A )=。其中，、不能同时 *。SELECT(SaAS)=FIRST(aAS)=a SELECT(Sb)=b SELECT(AbA)=b SELECT(A)=FIRST()FOLLOW(A)=a,b,SELECT(SaAS)SELECT(Sb)=ab=SELECT(AbA)SELECT(A)=ba,b 故文法故文法 GS不是不是LL(1)文法。文法。当一个文法是当一个文法是LL(1)文法时，则该文法一定能够采用拟定自顶文法时，则该文法一定能够采用拟定自顶向下分析办法进行分析。向下分析办法进行分析。第18页第18页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌5.35.35.35.3文法等价变换文法等价变换文法等价变换文法等价变换 拟定自顶向下分析要求给定语言文法必须是拟定自顶向下分析要求给定语言文法必须是 LL(1)形式，然而，不一定每个语言都是形式，然而，不一定每个语言都是LL(1)文法，对一个语言文法，对一个语言非非LL(1)文法是否能变换为等价文法是否能变换为等价LL(1)形式以及如何变换是形式以及如何变换是我们讨论主要问题。由我们讨论主要问题。由LL(1)文法定义可知若文法中含有文法定义可知若文法中含有左递归或含有左公共因子，则该文法必定不是左递归或含有左公共因子，则该文法必定不是LL(1)文法，因文法，因而，我们设法消除文法中左递归，提取左公共因子对文法而，我们设法消除文法中左递归，提取左公共因子对文法进行等价变换。进行等价变换。1.1.提取左公共因子提取左公共因子 若文法中含有形如：若文法中含有形如：A A|产生式，这造成了对相同产生式，这造成了对相同产生式右部产生式右部FIRST集相交。集相交。即有即有SELECT(A )SELECT(A )不满足不满足LL(1)文法充要条件。等价互换为：文法充要条件。等价互换为：A(|)A A A|第19页第19页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌更普通地更普通地更普通地更普通地:对对A 1|2|n提取左公因子为：提取左公因子为：A A A 1|2|n若在若在i,j,k中仍含有左公共因子，可再进行提取，这样重复中仍含有左公共因子，可再进行提取，这样重复进行提取直到所引进新非终止符相关产生式均无左公共因子为止。进行提取直到所引进新非终止符相关产生式均无左公共因子为止。结论：结论：1）不一定每个文法左公共因子都能在有限环节内替换成无左公）不一定每个文法左公共因子都能在有限环节内替换成无左公共因子文法。共因子文法。2）一个文法提取了左公共因子后，只处理了相同左部产生式）一个文法提取了左公共因子后，只处理了相同左部产生式右部右部FIRST集不相交问题。当改写后文法不含有空产生式，且集不相交问题。当改写后文法不含有空产生式，且无左递归时，则改写后文法是无左递归时，则改写后文法是LL(1)文法。不然还需用文法。不然还需用LL(1)文文法判别办法进行判断才干拟定是否为法判别办法进行判断才干拟定是否为LL(1)文法。文法。第20页第20页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌2.2.消除左递归消除左递归消除左递归消除左递归 一个文法含有下列形式产生式之一时：一个文法含有下列形式产生式之一时：1)AA,AVN,V*2)AB,BA,A,BVN,V*则称该文法是左递归。则称该文法是左递归。然而，一个文法是左递归时，不能采用自顶向下分析法。然而，一个文法是左递归时，不能采用自顶向下分析法。消除左递归办法有：消除左递归办法有：a)把直接左递归改写为右递归：把直接左递归改写为右递归：设有文法产生式：设有文法产生式：AA|.其中其中非空，非空，不以不以A打头。打头。可写为：可写为：AA AA|普通情况下，假定关于普通情况下，假定关于A产生式是：产生式是：AA 1|A 2|A m|1|2|n 其中，其中，i(1im)均不为空，均不为空，j(1jn)均不以均不以A打头。打头。则消除直接左递归后改写为：则消除直接左递归后改写为：A 1 A|2 A|n A A 1 A|2 A|m A|第21页第21页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例：例：例：例：有文法有文法G(E)：EE+T|T TT*F|F Fi|(E)消除该文法直接左递归。消除该文法直接左递归。解：解：ETE E+TE|TFT T*FT|Fi|(E)AA|改写为：改写为：AA AA|第22页第22页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌b)b)消除间接左递归：消除间接左递归：消除间接左递归：消除间接左递归：对于间接左递归消除需要先将间接左递归变为直接左递对于间接左递归消除需要先将间接左递归变为直接左递归，然后再按归，然后再按a)清除左递归。清除左递归。以文法以文法G6为例：为例：(1)AaB (2)ABb (3)BAc (4)Bd用产生式用产生式(1)，(2)右部代替产生右部代替产生式式(3)中非终止中非终止A得到左部为得到左部为B产生式产生式:(1)BaBc (2)BBbc (3)Bd消除左递归后得到：消除左递归后得到：BaBcB|dB BbcB|再把本来其余产生式再把本来其余产生式AaB,ABb加入，最后加入，最后得到等价文法为得到等价文法为:(1)AaB(2)ABb(3)B(aBc|d)B(4)BbcB|第23页第23页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌c)c)消除文法中一切左递归算法消除文法中一切左递归算法消除文法中一切左递归算法消除文法中一切左递归算法设非终止符按某种规则排序为设非终止符按某种规则排序为A1,A2,An。For i:=1 to n do begin For j:=1 to i-1 do begin 若若Aj所有产生式为：所有产生式为：Aj 1|2|n 替换形如替换形如Ai Aj 产生式为：产生式为：Ai 1|2|n end 消除消除Ai中一切直接左递归中一切直接左递归 end第24页第24页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌5.4 5.4 5.4 5.4 不拟定自顶向下分析思想不拟定自顶向下分析思想不拟定自顶向下分析思想不拟定自顶向下分析思想 当文法不满足当文法不满足 LL(1)时，则不能用拟定自顶向下分析，但有时可用不拟定自时，则不能用拟定自顶向下分析，但有时可用不拟定自顶向下分析法，也就是带回溯自顶向下分析法。顶向下分析法，也就是带回溯自顶向下分析法。引起回溯原因是在文法中当关于某个非终止符产生式有多个候选时，而面临引起回溯原因是在文法中当关于某个非终止符产生式有多个候选时，而面临当前输入符无法拟定选取唯一产生式，从而引起回溯，有三种情况：当前输入符无法拟定选取唯一产生式，从而引起回溯，有三种情况：2。由于相同左部非终止符右部能。由于相同左部非终止符右部能*且该非终止符且该非终止符FOLLOW集合中含有其右集合中含有其右部部FIRST集合元素。集合元素。带回溯自顶向下分析是一个试探过程，当分析不成功是则推翻分析退回带回溯自顶向下分析是一个试探过程，当分析不成功是则推翻分析退回到适当位置再重新试探其余候选也许推导。这样需要统计推导每步所选过产到适当位置再重新试探其余候选也许推导。这样需要统计推导每步所选过产生式，直到把所有也许推导序列都试空仍不成功才干拟定输入串是不是该文生式，直到把所有也许推导序列都试空仍不成功才干拟定输入串是不是该文法句子而报错。法句子而报错。由于在编辑程序真正实现时往往是边分析边插入语义动作，因而带回溯分由于在编辑程序真正实现时往往是边分析边插入语义动作，因而带回溯分析代价高，效率很低，在实用编译程序中几乎不用。析代价高，效率很低，在实用编译程序中几乎不用。1。由于相同左部产生式右部。由于相同左部产生式右部 FIRST集交集不为空而引起回溯。集交集不为空而引起回溯。3。由于文法含有左递归而引起回溯。由于文法含有左递归而引起回溯。第25页第25页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌5.5 5.5 5.5 5.5 拟定自顶向下分析办法拟定自顶向下分析办法拟定自顶向下分析办法拟定自顶向下分析办法5.5.1 递归下降法（递归子程序法）递归下降法（递归子程序法）在程序语言语法定义中有许多采用递归定义。我们在对在程序语言语法定义中有许多采用递归定义。我们在对它进行语法分析时，编译处理程序也采用递归方式，可使其它进行语法分析时，编译处理程序也采用递归方式，可使其结构简朴易读。但由于频繁地调用子程序大大地减少了分析速度。结构简朴易读。但由于频繁地调用子程序大大地减少了分析速度。一、递归下降法主要思想是：对每个非终止符按其产生式一、递归下降法主要思想是：对每个非终止符按其产生式结构写出相应语法分析子程序。由于文法递归相应子程序也结构写出相应语法分析子程序。由于文法递归相应子程序也递归，子程序结构与产生式结构几乎一致。因此称此种办法递归，子程序结构与产生式结构几乎一致。因此称此种办法称为递归子程序法或递归下降法。称为递归子程序法或递归下降法。二、用程序表示递归子程序内部结构：二、用程序表示递归子程序内部结构：设设A是一个非终止符：是一个非终止符：A1 A2 An第26页第26页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌则写则写 (A)if charfirst(1)then(1)else if charfirst(2)then(2)else if charfirst(n)then(n)else ERROR其中其中(i)表示调用处理符号串表示调用处理符号串i子程序。子程序。对文法加限制：对文法加限制：1。任一非终止符。任一非终止符B都不是左递归，不然会产生死循环。都不是左递归，不然会产生死循环。2。对。对A任意两个右部任意两个右部i,j,有：有：first(i)first(j)=First(i)表示表示i所能导出串第一个符号集合。显然，每个所能导出串第一个符号集合。显然，每个ifirst(i)是互不相同，不然则无法判断应执行哪个是互不相同，不然则无法判断应执行哪个(i)。对对A任一右部任一右部i 设为：设为：i=y1 y2 yn则定义则定义(i)begin(y1);(y2);(yn)end其中其中yj可分为下列两种情况（可分为下列两种情况（j=1,n):1)yjVT,则则 (yj)if char yj then ERROR else READ(char)2)yjVN,则则(yj)表示调用关于表示调用关于yj递归子程序。递归子程序。A1 A2 An第27页第27页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例例例例1.1.1.1.设有文法设有文法G:A aABa BbBb|a则有则有(A)if char=a then (aABa)else ERROR if char=a then begin(a);(A);(B);(a)end else ERROR if char=a then begin if char a then ERROR else READ(char);(A);(B);if char a then ERROR else READ(char)end else ERROR 第28页第28页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌(B)if char=b then(bBb)else if char=a then(a)else ERROR if char=b then begin if char b then ERROR else READ(char);(B);if char b then ERROR else READ(char)end else if char=a then if char a then ERROR else READ(char)else ERROR if char=b then begin(b);(B);(b)end else if char=a then (a)else ERROR BbBb|a第29页第29页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌关于关于表示式表示式处理：处理：=|+=|*=|()=i|i()例例例例2 2 2 2：E:procedure E;begin T;while char=+do begin READ(char);T end end即：即：ET|E+T TF|T*F FP|(E)P i|i(E)为了处理以便，把上述文法变为：为了处理以便，把上述文法变为：ET+T TF*F FP|(E)Pi|i(E)第30页第30页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌T:procedure T;begin F;while char=*do begin READ(char);F end endE:procedure E;begin T;while char=+do begin READ(char);T end endF:procedure F;begin if char=(then begin READ(char);E;if char )then ERROR else READ(char)end else P endET+TTF*FFP|(E)P i|i(E)第31页第31页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌P:procedure P begin if char i then ERROR else begin READ(char);if char=(then begin READ(char);E;if char)then ERROR else READ(char)end end end ET+TTF*FFP|(E)P i|i(E)第32页第32页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌5.5.2 5.5.2 5.5.2 5.5.2 预测分析办法（预测分析办法（预测分析办法（预测分析办法（LLLLLLLL办法）办法）办法）办法）LL(k)文法是采用拟定自左至右扫描（输入串）和自文法是采用拟定自左至右扫描（输入串）和自顶向下分析技术最大一类文法。顶向下分析技术最大一类文法。LL系指：自系指：自左左向右扫描向右扫描（输入串），自上而下进行最（输入串），自上而下进行最左左推导。推导。普通来说，一个文法当其分析器对输入串进行自左普通来说，一个文法当其分析器对输入串进行自左至右扫描并采用自顶向下办法进行分析过程中，假如每至右扫描并采用自顶向下办法进行分析过程中，假如每步仅利用当前非终止符（事实上此时它已位于分析栈顶）步仅利用当前非终止符（事实上此时它已位于分析栈顶）和至多向前查看和至多向前查看k个输入符号就能唯一个输入符号就能唯一 决定采用什么动决定采用什么动作，那么这个文法称为作，那么这个文法称为LL(K)文法。文法。对于大多数程序设计语言而言。对于大多数程序设计语言而言。K=0或或1就足够了。就足够了。因此我们将主要讨论因此我们将主要讨论k1情形。情形。第33页第33页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌一、一、一、一、LL(1)LL(1)办法分析过程办法分析过程办法分析过程办法分析过程 从实现角度来说，上述替换过程需要花较多时间，由于从实现角度来说，上述替换过程需要花较多时间，由于它除了把一个候选式替换掉它除了把一个候选式替换掉x1,还需要还需要x2 xn统统进行移位处理统统进行移位处理,这时很麻烦。我们处理办法是用栈来保留这时很麻烦。我们处理办法是用栈来保留x1x2 xn,并且并且是把是把xn作为栈底，作为栈底，x1作为栈顶，那么上述替换动作就简朴了，作为栈顶，那么上述替换动作就简朴了，只需在栈顶进行替换。即去掉只需在栈顶进行替换。即去掉x1把候选式符号串按逆序方式把候选式符号串按逆序方式压入栈中即可。压入栈中即可。设分析当前格局为（设分析当前格局为（x1x2.xn#,y1y2.ym#)，其中，其中xi表示句型表示句型后端部分，诸后端部分，诸yj表示输入流后端部分（终止符串）。则也许有下述表示输入流后端部分（终止符串）。则也许有下述动作之一：动作之一：1.替换：当替换：当x1VN时，则选相应候选式去替换时，则选相应候选式去替换x1。2.匹配：当匹配：当x1VT时，它与时，它与y1进行匹配，其结果为两种也许，如进行匹配，其结果为两种也许，如 果匹配成功，则去掉果匹配成功，则去掉x1和和y1（即只指针后移一位）不然报错。（即只指针后移一位）不然报错。3.接受：当格局为接受：当格局为(#,#）时，汇报分析成功结束。）时，汇报分析成功结束。第34页第34页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌bBc#bbbdc#Bc#bbbdc#aBc#abbbdc#例：例：例：例：设有文法：设有文法：SaBc|bB BbB|d 且给定输入串且给定输入串abbbdc，看其自顶向下分析过程。，看其自顶向下分析过程。栈：栈：流：流：替替 S#abbbdc#匹匹 替替 匹匹 Bc#bbdc#替替 bBc#bbdc#匹匹 Bc#bdc#替替 bBc#bdc#匹匹Bc#dc#替替 dc#dc#匹匹c#c#匹匹#接受接受结束结束第35页第35页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌二、二、二、二、LL(1)LL(1)LL(1)LL(1)办法实现：办法实现：办法实现：办法实现：LL(1)办法在实现时用到一个办法在实现时用到一个LL(1)分析矩阵和一个分析矩阵和一个分析栈以及预测分析总控程序。分析栈以及预测分析总控程序。分析矩阵元素分析矩阵元素MA,a中下标中下标A为非终止符，为非终止符，a为终为终止符或句子结束标识止符或句子结束标识#，矩阵元素，矩阵元素MA,a内容为一条内容为一条关于关于A产生式。产生式。它表明当用非终止符它表明当用非终止符A向下推导而当前输入符为向下推导而当前输入符为a时，所应采用候选式。当矩阵元素为空时，则表示用时，所应采用候选式。当矩阵元素为空时，则表示用A往下推导时碰到了不应当出现符号，即往下推导时碰到了不应当出现符号，即A与与a不能匹配。不能匹配。因此应当转向犯错处理。因此应当转向犯错处理。预测分析程序见下图：预测分析程序见下图：第36页第36页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌流程图：流程图：流程图：流程图：#S 进栈，读输入流一符号进栈，读输入流一符号 a栈顶元素出栈并送栈顶元素出栈并送X对产生式右部对产生式右部x1 x2xn按逆序即按逆序即xnxn-1x1 压入栈中压入栈中读入符号读入符号 aXVT?X=a?MX,a为产生式？为产生式？X=#?犯错处理犯错处理X=a?犯错处理犯错处理结束结束yyyNNyyNN此时输入流也到尾部。此时输入流也到尾部。N开始开始N第37页第37页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例：现以表示式文法为例结构预测分析表。例：现以表示式文法为例结构预测分析表。例：现以表示式文法为例结构预测分析表。例：现以表示式文法为例结构预测分析表。GE:EE+T|T TT*F|F Fi|(E)SELECT(ETE)=(,i SELECT(E+TE)=+SELECT(E=,),#SELECT(TFT)=(,i SELECT(T*FT)=*SELECT(T)=,+,),#SELECT(Fi)=i SELECT(F(E)=(可知含有相同左部产生式可知含有相同左部产生式SELECT集合互不相交，因此该集合互不相交，因此该文法是文法是LL(1)文法。文法。解：解：(1)判断判断GE是否为是否为LL(1)文法文法,因文法中含有左递归，因文法中含有左递归，故必须先消去左递归，使文法故必须先消去左递归，使文法 变为：变为：ETE E+TE|TFT T*FT|Fi|(E)求三种集合（前面已举例，求三种集合（前面已举例，图略）最后得到：图略）最后得到：第38页第38页武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌（2 2）结构预测分析表）结构预测分析表）结构预测分析表）结构预测分析表 对每个终止符或对每个终止符或#号用号用a表示，则若表示，则若aSELECT(A)。令令MA,a=A(普通为了简化，取普通为了简化，取MA,a=)把所有没有定义把所有没有定义MA,a标上标上ERR
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
