资源描述
第四章第四章 语法分析语法分析自顶向下分析自顶向下分析(P61)(P61)n4.1自顶向下分析方法自顶向下分析方法n4.2FIRST集合和集合和FOLLOW集合集合n4.3递归下降分析递归下降分析n4.4LL(1)分析方法分析方法第1页学学 习习 重重 点点 nFIRST集合和集合和FOLLOW集合求法集合求法n递归子程序结构方法递归子程序结构方法nLL(1)文法及其分析表结构方法文法及其分析表结构方法 第2页第四章第四章 语法分析语法分析自顶向下分析自顶向下分析 n语法语法：是指怎样由语言基本符号组成程序中各个语法：是指怎样由语言基本符号组成程序中各个语法成份（包含程序）一组规则。成份（包含程序）一组规则。n语法分析与词法分析区分语法分析与词法分析区分：语法分析和词法分析都是对输入符号串识别，语法分析和词法分析都是对输入符号串识别，但词法分析输入符号串是一个单词，而语法分析输但词法分析输入符号串是一个单词，而语法分析输入符号串是一个句子或者说是一个程序。入符号串是一个句子或者说是一个程序。n语法分析任务语法分析任务：检验源程序语法上是否正确，并生成：检验源程序语法上是否正确，并生成对应内部表示（如分析树）供下一阶段使用。对应内部表示（如分析树）供下一阶段使用。n例例对于对于C程序语句程序语句“if(a10)b=5；”，词法分析，词法分析识别出了识别出了if、(、a、等单词符号，而语法分析则要检等单词符号，而语法分析则要检验这些单词之间搭配、结构是否正确，比如验这些单词之间搭配、结构是否正确，比如if后面是否后面是否为为(，(后面是否为正确表示式等等。后面是否为正确表示式等等。第3页第四章第四章 语法分析语法分析自顶向下分析自顶向下分析 n语法分析方法分类语法分析方法分类（分类标准是按照识别句子（分类标准是按照识别句子时建立语法树方法）：时建立语法树方法）：回溯示例回溯示例第4页4.1自顶向下分析方法自顶向下分析方法（P61P61）n自顶向下分析方法自顶向下分析方法就是从文法开始符号出发，按就是从文法开始符号出发，按最左推导方式向下推导，试图推导出要分析输入串。最左推导方式向下推导，试图推导出要分析输入串。即：即：开始符号开始符号输入符号串输入符号串+n自底向上分析方法自底向上分析方法从输入符号串开始，按最左归从输入符号串开始，按最左归约方式向上归约到文法开始符号。即：约方式向上归约到文法开始符号。即：开始符号开始符号输入符号串输入符号串归约归约第5页SaASaAaaSbAaaSbbaaaabbaa自上而下自上而下自底向上自底向上输入串输入串开始符号开始符号图示：图示：自上而下分析与自底向上分析自上而下分析与自底向上分析第6页4.2FIRST集合和集合和FOLLOW集合集合（P62P62）nFIRST集合定义集合定义：假定假定是文法是文法G任一符号串，任一符号串，则：则：FIRST()=a|a，aVt若若,则要求则要求FIRST()。*n实实际际上上，FIRST()就就是是从从可可能能推推导导出出全全部部开开头头终止符号或终止符号或。第7页n文法符号文法符号FIRST集合结构方法集合结构方法：对于文法中对于文法中符号符号XV，其，其FIRST(X)集合可重复应集合可重复应用以下规则计算，直到其用以下规则计算，直到其FIRST(X)集合不再增大为止：集合不再增大为止：1)若若XVt，则，则FIRST(X)=X。2)若若XVn，且含有形如，且含有形如Xa产生式产生式(aVt)，或含有，或含有形如形如X产生式，则把产生式，则把a或或加进加进FIRST(X)。3)设设G中有形如中有形如XY1Y2Yk产生式，若产生式，若Y1Vn，则把，则把FIRST(Y1)中一切非中一切非符号加进符号加进FIRST(X)；对于一切；对于一切2ik，若，若Y1，Y2，Yi-1均为非终止符号，且均为非终止符号，且FIRST(Yj)，1ji-1，则将，则将FIRST(Yi)中一切非中一切非符号加进符号加进FIRST(X)；但若对一切；但若对一切1ik，都有，都有FIRST(Yi)，则将，则将符号加符号加进进FIRST(X)。第8页n文法符号文法符号FIRST集合结构方法集合结构方法：对于文法中对于文法中符号符号XV，其，其FIRST(X)集合可重复应集合可重复应用以下规则计算，直到其用以下规则计算，直到其FIRST(X)集合不再增大为止：集合不再增大为止：1)若若X为终止符为终止符，则将，则将X加入加入FIRST(X)集合中。集合中。2)若若X为非终止符为非终止符，且含有形如，且含有形如Xa产生式产生式(aVt)，或含，或含有形如有形如X产生式，则把产生式，则把a或或加进加进FIRST(X)。3)设设X为非终止符为非终止符且有形如且有形如XY1Y2Yk产生式，若产生式，若Y1Vn，则把，则把FIRST(Y1)中一切非中一切非符号加进符号加进FIRST(X)；对于一切；对于一切2ik，若，若Y1，Y2，Yi-1均为非终止符号，且均为非终止符号，且FIRST(Yj)，1ji-1，则将，则将FIRST(Yi)中一切非中一切非符号加进符号加进FIRST(X)；但若对一切；但若对一切1ik，都有，都有FIRST(Yi)，则将，则将符号加进符号加进FIRST(X)。第9页n对对于于文文法法G任任一一符符号号串串=X1X2Xn可可按按以以下下步步骤骤结构其结构其FIRST()集合：集合：1)置置FIRST()=;2)将将FIRST(X1)中一切非中一切非符号加进符号加进FIRST()；3)若若FIRST(X1)，将将FIRST(X2)中中一一切切非非符符号号加加 进进 FIRST()；若若 FIRST(X1)和和 FIRST(X2)，将将 FIRST(X3)中一切非中一切非符号加进符号加进FIRST()；其余类推。；其余类推。4)若若对对于于一一切切1in，FIRST(Xi)，则则将将符符号号加加进进FIRST()。4.2FIRST集合和集合和FOLLOW集合集合第10页n例例4-1(P62)有有文法：文法：ETEE+TEETFTT*FTTF(E)|i求文法中非求文法中非终止符号以及终止符号以及各各产生式右部产生式右部符号符号串串FIRST集。集。解：该文法非终止符号有解：该文法非终止符号有E、E、T、T和和F。FIRST(E)=FIRST(TE)=FIRST(FTE)=(，iFIRST(+TE)=+FIRST()=FIRST(E)=FIRST(+TE)FIRST()=+，FIRST(T)=FIRST(FT)=(，iFIRST(*FT)=*FIRST(T)=FIRST(*FT)FIRST()=*，FIRST(E)=(FIRST(i)=iFIRST(F)=FIRST(E)FIRST(i)=(，i第11页4.2FIRST集合和集合和FOLLOW集合集合n例例S:=aABbcd|A:=ASd|B:=SAh|eC|C:=Sf|Cg|求此文法每求此文法每一个非终止符号一个非终止符号FIRST集。集。解：解：FIRST(S)=FIRST(aABbcd)FIRST()=a=a,FIRST(A)=FIRST(ASd)FIRST()=a,d=a,d,FIRST(B)=FIRST(SAh)FIRST(eC)FIRST()=a,d,he=a,d,h,e,FIRST(C)=FIRST(Sf)FIRST(Cg)FIRST()=a,fa,f,g=a,f,g,第12页4.2FIRST集合和集合和FOLLOW集合集合n练习练习S:=aAcB|BdA:=AaB|cB:=bBcA|b|求此文法每求此文法每一个非终止符号一个非终止符号FIRST集。集。解：解：FIRST(S)=FIRST(aAcB)FIRST(Bd)=ab,d=a,b,dFIRST(A)=FIRST(AaB)FIRST(c)=cc=cFIRST(B)=FIRST(bBcA)FIRST(b)FIRST()=bb=b,第13页4.2FIRST集合和集合和FOLLOW集合集合nFOLLOW集合定义集合定义（P63）：）：假假定定S是是文文法法开开始始符符号号，对对于于G任任何何非非终终止止符号符号A，则：，则：FOLLOW(A)=a|SAa，aVt若若SA，则要求，则要求#FOLLOW(A)。*n从从定定义义可可看看出出，FOLLOW(A)就就是是在在全全部部句句型型中中出出现现在在紧紧接接A之之后后终终止止符符号号或或#。注注意意：在在FOLLOW集合中无集合中无。第14页4.2FIRST集合和集合和FOLLOW集合集合n对于文法中符号对于文法中符号AVn，其，其FOLLOW(A)集合可集合可重复应用以下规则计算，直到其重复应用以下规则计算，直到其FOLLOW(A)集合集合不再增大为止：不再增大为止：1)对于文法对于文法开始符号开始符号S，令，令#FOLLOW(S)2)若若G中有形如中有形如AB产生式，且产生式，且，则将，则将FIRST()中一切非中一切非符号加进符号加进FOLLOW(B)。3)若若G中有形如中有形如AB或或AB产生式，且产生式，且FIRST()，则，则FOLLOW(A)中全部元素均属于中全部元素均属于FOLLOW(B)，即即FOLLOW(A)FOLLOW(B)。第15页例例设文法设文法GS:S:=SbA|aAA:=BcB:=Sb求此文法每一个非终止符号求此文法每一个非终止符号FOLLOW集。集。解：解：1.因为因为S为文法开始符号，所以为文法开始符号，所以#FOLLOW(S);由由S:=SbA，有，有FIRST(bA)=bFOLLOW(S);由由B:=Sb，有，有FIRST(b)=bFOLLOW(S);所以，所以，FOLLOW(S)=b,#。2.由由S:=SbA或或S:=aA，有，有FOLLOW(S)FOLLOW(A)。所以，。所以，FOLLOW(A)=b,#。3.由由A:=Bc，有，有FIRST(c)=cFOLLOW(B)。所以，。所以，FOLLOW(B)=c。第16页4.2FIRST集合和集合和FOLLOW集合集合n例例4-2（P63）有有文法文法ETE，E+TE，E，TFT，T*FT，T，F(E)|i，求各非终，求各非终止符号止符号FOLLOW集。集。解：解：FOLLOW(E)=#FIRST()=)，#FOLLOW(E)=FOLLOW(E)=)，#FOLLOW(T)=(FIRST(E)-)FOLLOW(E)FOLLOW(E)=+，)，#FOLLOW(T)=FOLLOW(T)=+，)，#FOLLOW(F)=(FIRST(T)-)FOLLOW(T)FOLLOW(T)=*，+，)，#第17页4.2FIRST集合和集合和FOLLOW集合集合n练习练习已知文法已知文法GS:S:=AA:=BAA:=iBA|B:=CBB:=+CB|C:=)A*|(求求FOLLOW(C)。解：解：FOLLOW(C)=(FIRST(B)-)FOLLOW(B)FOLLOW(B)=+,i,*,#第18页自顶向下语法分析碰到问题自顶向下语法分析碰到问题n(1)左递归问题左递归问题当文法中出现左递归时（存在非终止符号当文法中出现左递归时（存在非终止符号U，对于它有对于它有U:=U（直接左递归），或（直接左递归），或UU（间（间接左递归），它会使分析过程陷入无限循环。接左递归），它会使分析过程陷入无限循环。n(2)回溯问题回溯问题假如对于同一个非终止符号，存在若干个产生假如对于同一个非终止符号，存在若干个产生式右部式右部(如如U:=x1|x2|xn)时，要对时，要对U展开，那么按展开，那么按哪一个产生式右部展开呢？即怎样确定替换哪一个产生式右部展开呢？即怎样确定替换Uxi。假。假如选择错误，将造成回溯。如选择错误，将造成回溯。+回溯示例回溯示例第19页自顶向下语法分析问题处理方法自顶向下语法分析问题处理方法n(1)消除消除左递归左递归消除直接左递归消除直接左递归方法方法1：采取扩充：采取扩充BNF范式范式设有文法产生式设有文法产生式U:=Ux|y可改写为可改写为:U:=yx方法方法2：引进新非终止符号：引进新非终止符号设有文法产生式设有文法产生式U:=Ux1|Ux2|Uxm|y1|y2|yn其中，其中，yi(i=1,2,n)均不以符号均不以符号U为首，引进一个新非为首，引进一个新非终止符号终止符号U,将上述产生式等价变换为将上述产生式等价变换为:U:=y1U|y2U|ynUU:=x1U|x2U|xmU|第20页自顶向下语法分析问题处理方法自顶向下语法分析问题处理方法n例例4-4(P65)有文法：有文法：E:=E+T|E-T|T，T:=T*F|T/F|F，为其设计递归分析程序。，为其设计递归分析程序。方法方法1：采取扩充：采取扩充BNF范式范式E:=E+T|E-T|T可改成可改成E:=T+T|-TT:=T*F|T/F|F可改成可改成T:=F*F|/F方法方法2：引进新非终止符号：引进新非终止符号E:=E+T|E-T|T可改成可改成E:=TE，E:=+TE|-TE|T:=T*F|T/F|F可改成可改成T:=FT，T:=*FT|/FT|解：先消除文法中直接左递归。解：先消除文法中直接左递归。第21页自顶向下语法分析问题处理方法自顶向下语法分析问题处理方法n(2)防止回溯防止回溯为了防止回溯，对于文法中为了防止回溯，对于文法中任一非终止符号任一非终止符号U，若若U:=x1|x2|xn，要求满足以下两个条件，要求满足以下两个条件：相对于相对于x1,x2,xn各符号串终止首符号集总是两各符号串终止首符号集总是两两互不相交，即两互不相交，即FIRST(xi)FIRST(xj)=(ij)因为每一个因为每一个xi推出第一个终止符号均不相同，它推出第一个终止符号均不相同，它能确保只会选择惟一一个能确保只会选择惟一一个xi来替换来替换U。n例例设文法设文法GA：A:=aB|aC，B:=b，C:=cFIRST(aB)FIRST(aC)=aa=a 采取自顶向下语法分析时会引发回溯，比如推导句子采取自顶向下语法分析时会引发回溯，比如推导句子ac将造成回溯。将造成回溯。第22页自顶向下语法分析问题处理方法自顶向下语法分析问题处理方法n(2)防止回溯防止回溯假如假如xj，则有可能选择此，则有可能选择此xj来替换来替换U,而让句型而让句型中中U后面第一个终止符号与当前输入符号匹配，这么有后面第一个终止符号与当前输入符号匹配，这么有可能回溯。若要求文法不含可能回溯。若要求文法不含规则规则，则对文法要求太高，则对文法要求太高，所以用所以用FIRST(xi)FOLLOW(U)=来限制文法，确保只会选择惟一一个来限制文法，确保只会选择惟一一个xi来替换来替换U。*第23页n例例设文法为：设文法为：S:=bAB，A:=aC|，B:=aB|,C:=cFIRST(aC)FOLLOW(A)=aa,#=a采取自顶向下语法分析时会引发回溯，比如推导句子采取自顶向下语法分析时会引发回溯，比如推导句子baa将造成回溯。将造成回溯。第24页自顶向下语法分析问题处理方法自顶向下语法分析问题处理方法n(2)防止回溯防止回溯以上防止回溯两个条件等价于：以上防止回溯两个条件等价于：SELECT(U:=xi)SELECT(U:=xj)=(ij)其中：其中：SELECT(U:=xk)定义为：定义为：(i,j,k=1,2,n)SELECT(U:=xk)第25页自顶向下语法分析问题处理方法自顶向下语法分析问题处理方法n消除文法回溯方法：消除文法回溯方法：消除文法左递归；消除文法左递归；提公共因子；提公共因子；比如比如U:=xy|xz，则提公共因子，有，则提公共因子，有U:=x(y|z),再再引进新非终止符号引进新非终止符号V，U:=xy|xz可改写为：可改写为：U:=xV，V:=y|z。依据文法详细情况进行等价变换。依据文法详细情况进行等价变换。第26页采取自顶向下语法分析法对文法要求采取自顶向下语法分析法对文法要求n采取自顶向下语法分析法要求文法满足采取自顶向下语法分析法要求文法满足压缩、无压缩、无左递归、无回溯左递归、无回溯这三个条件，称满足这三个条件这三个条件，称满足这三个条件文法为文法为LL(1)文法文法。证实：因为是左递归文法，所以必存在左递归非终证实：因为是左递归文法，所以必存在左递归非终止符止符A及形如及形如A:=A|（可为可为）。因为）。因为SELECT(A:=A)SELECT(A:=)，所以左递，所以左递归文法不满足归文法不满足LL(1)文法条件。文法条件。推论推论1：任何左递归文法均不是：任何左递归文法均不是LL(1)文法。文法。第27页采取自顶向下语法分析法对文法要求采取自顶向下语法分析法对文法要求推论推论2：任何：任何LL(1)文法均为无二义性文法。文法均为无二义性文法。证实：证实：LL(1)文法在分析句子过程每一步，永远只有文法在分析句子过程每一步，永远只有惟一分析动作可进行。现在，假设文法惟一分析动作可进行。现在，假设文法G是二义性是二义性文法，则存在句子文法，则存在句子，它有两棵不一样语法树，即存，它有两棵不一样语法树，即存在着两个不一样最左推导。从而可知，用在着两个不一样最左推导。从而可知，用LL(1)方法方法对句子对句子进行分析某步，存在两种不一样产生式可用进行分析某步，存在两种不一样产生式可用于推导，且均能正确进行语法分析，即于推导，且均能正确进行语法分析，即LL(1)分析动分析动作存在不确定性。这与作存在不确定性。这与LL(1)性质相矛盾。所以，文性质相矛盾。所以，文法法G不是不是LL(1)文法。文法。第28页采取自顶向下语法分析法对文法要求采取自顶向下语法分析法对文法要求n例例验证以下文法是否为验证以下文法是否为LL(1)文法。文法。GS:S:=AB|CDaA:=ab|cB:=dD|C:=eC|D:=fD|f解：显然，文法解：显然，文法G已压缩且无左递归已压缩且无左递归。下面判断其是否有回溯。下面判断其是否有回溯。由由D:=fD|f，有：，有：SELECT(D:=fD)SELECT(D:=f)=FIRST(fD)FIRST(f)=ff=f该文法不是该文法不是LL(1)文法。文法。第29页采取自顶向下语法分析法对文法要求采取自顶向下语法分析法对文法要求n练习练习（见（见P77习题习题4第第2小题）小题）有文法有文法GA：A:=aABe|B:=Bb|b判断该文法是判断该文法是LL(1)文法吗？文法吗？解：解：文法中存在左递归文法中存在左递归B:=Bb该文法不是该文法不是LL(1)文法。文法。第30页4.3递归下降分析递归下降分析(P64)(P64)n递归下降分析递归下降分析(或或递归子程序分析递归子程序分析)基本方法基本方法其思绪极为简单：其思绪极为简单：为每个非终止符号结构一个子程为每个非终止符号结构一个子程序，以完成该非终止符号所对应语法成份分析和识别。序，以完成该非终止符号所对应语法成份分析和识别。1.若若U右部右部只有一个候选式只有一个候选式，则按从左向右次序结构，则按从左向右次序结构U识别识别过程代码。过程代码。（1 1）若有终止符号，则判断与输入符号是否匹配，假如）若有终止符号，则判断与输入符号是否匹配，假如相同，继续读入下一符号，不然就意味着有语法错误；相同，继续读入下一符号，不然就意味着有语法错误；（2 2）若有非终止符号，则调用该符号子程序。）若有非终止符号，则调用该符号子程序。2.若若U右部右部有多个候选式有多个候选式，则依据每个候选式第一个符号确，则依据每个候选式第一个符号确定该候选式分支。定该候选式分支。3.只有输入串每一个符号全部匹配成功，且正确返回时，该只有输入串每一个符号全部匹配成功，且正确返回时，该语法成份才算真正取得识别。语法成份才算真正取得识别。第31页4.3递归下降分析递归下降分析n总控程序总控程序可描述以下：可描述以下：beginREAD(ch);ifP(文法开始符号文法开始符号)thenif当前符号当前符号=#thenwrite(valid)elsewrite(invalid)endifelsewrite(invalid)endifendn递归下降分析算法递归下降分析算法它由一个总控程序和若干个非终止符号分析子程序它由一个总控程序和若干个非终止符号分析子程序P(U)组成组成。其中若有。其中若有n个非终止符号就有个非终止符号就有n个分析子程序。个分析子程序。第32页4.3递归下降分析递归下降分析n对对满满足足条条件件文文法法按按以以下下方方法法结结构构对对应应语语法法分分析析子子程程序：序：对于产生式对于产生式U:=1|2|n,iV，P(U)按如按如下方法结构：下方法结构：ifchFIRST(1)thenP(1)elseifchFIRST(2)thenP(2)elseifchFIRST(3)thenP(3)elseifchFIRST(n)thenP(n)elseerror其中，其中，ch(书本用书本用INPUTSYM)是一个全局变量，是一个全局变量，用于存放输入符号串当前要处理输入符号用于存放输入符号串当前要处理输入符号;error是犯是犯错处理程序；错处理程序；P(i)见后面说明。见后面说明。对于每个非终止符号对于每个非终止符号U,编写一个对应子程序编写一个对应子程序P(U)。第33页4.3递归下降分析递归下降分析对于产生式对于产生式U:=1|2|n|，P(U)按以下方法结按以下方法结构：构：ifchFIRST(1)thenP(1)elseifchFIRST(2)thenP(2)elseifchFIRST(3)thenP(3)elseifchFIRST(n)thenP(n)else ifchFOLLOW(U)thenreturn elseerror第34页4.3递归下降分析递归下降分析对于产生式对于产生式U:=12n，P(U)按以下方法按以下方法结构：结构：beginP(1);P(2);P(n)endn说明说明：假如：假如iVn，则，则P(i)就代表调用处理就代表调用处理i子程序；子程序；假如假如iVt，则，则P(i)为形以下述语句一段程序：为形以下述语句一段程序：ifch=ithenREAD(ch)elseerror即假如当前文法中符号与输入符号匹配，则继续读入输入即假如当前文法中符号与输入符号匹配，则继续读入输入符号串下一个符号到符号串下一个符号到ch中，不然犯错。中，不然犯错。第35页n例例设文法设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA|试结构该文试结构该文法递归子程序法递归子程序(或递归下降分析或递归下降分析程序程序)。解解：由由S:=(A)|aAb,则则P(S)为：为：ch=(?R E A D(ch)ch=a?YNP(A)ch=)?R E A D(ch)YNerrorR E A D(ch)YNerrorP(A)ch=b?R E A D(ch)YNerror第36页4.3递归下降分析递归下降分析由由A:=eA|dSA,则则P(A)为：为：n例例设文法设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA|试结构该文试结构该文法递归子程序法递归子程序(或递归下降分析或递归下降分析程序程序)。c h=e?R E A D(c h)c h=d?YNR E A D(c h)YNe r r o rP(S)P(A)第37页4.3递归下降分析递归下降分析由由A:=dA|，则则P(A)为：为：n例例设文法设文法GS:S:=(A)|aAbA:=eA|dSAA:=dA|试结构该文试结构该文法递归子程序法递归子程序(或递归下降分析或递归下降分析程序程序)。ch=d?READ(ch)ch FOLLOW(A)?YNYNerrorP(A)第38页4.3递归下降分析递归下降分析n例例4-3(P64)考虑文法考虑文法Z:=(U)|aUb，U:=dZ|e，为其结构递，为其结构递归下降分析子程序。归下降分析子程序。并对输入串并对输入串aebaeb进行语进行语法分析法分析。解：文法中有两个非终止符号解：文法中有两个非终止符号Z和和U，那么我们需要分别编，那么我们需要分别编两个过程来完成两个过程来完成Z和和U规则识规则识别。别。对于规则对于规则Z:=(U)|aUb，右部有两个候选式，所以，右部有两个候选式，所以，U识别过程有两个分支，分别依识别过程有两个分支，分别依据符号据符号(和和a来判别。来判别。同理对规则同理对规则U:=dZ|e设计设计过程也分为两个分支。过程也分为两个分支。第39页Z:=(U)|aUb非终止符号非终止符号Z分析程序分析程序第40页U:=dZ|e非终止符号非终止符号U分析程序分析程序 第41页Z:=(U)|aUbU:=dZ|e输入串为输入串为aeb，分析过程为：，分析过程为：ZaUbaeb aeeb#b第42页4.3递归下降分析递归下降分析n例例4-3(P64)考考虑文法虑文法Z:=(U)|aUb，U:=dZ|e，为其，为其结构递归下降结构递归下降分析子程序。分析子程序。并对输入串并对输入串aebaeb进行语法分析进行语法分析。aeb递归下降分析过程递归下降分析过程aeb语法树语法树第43页4.3递归下降分析递归下降分析n例例4-4(P65)有文法：有文法：E:=E+T|E-T|T，T:=T*F|T/F|F，为其设计递归分析程序。，为其设计递归分析程序。解：先消除文法中直接左递归：解：先消除文法中直接左递归：E:=E+T|E-T|T可改成可改成E:=T+T|-TT:=T*F|T/F|F可改成可改成T:=F*F|/F注意注意“”和和“”括起来内容采取循环设计。括起来内容采取循环设计。第44页E:=T|E+T|E-T改成改成E:=T+T|-TT:=F|T*F|T/F改成改成T:=F*F|/FE分析程序分析程序T分析程序分析程序第45页4.3递归下降分析递归下降分析n递归子程序分析法优缺点递归子程序分析法优缺点主要优点主要优点：能够依据文法规则直接写出对应识能够依据文法规则直接写出对应识别程序，各子程序流程图几乎就是文法规则图解别程序，各子程序流程图几乎就是文法规则图解描述，简单明了，易于掌握。描述，简单明了，易于掌握。主要缺点主要缺点：大量相互嵌套递归子程序频繁调用，大量相互嵌套递归子程序频繁调用，使分析器运行速度相当慢。使分析器运行速度相当慢。第46页4.4LL(1)分析方法分析方法(P70)(P70)nLL(1)分析法含义分析法含义：第一个第一个L表示自左向右次序扫描输入符号串表示自左向右次序扫描输入符号串第二个第二个L表示分析过程产生一个句子最左推导表示分析过程产生一个句子最左推导括号中括号中1表示每进行一步推导，只需要表示每进行一步推导，只需要向前查看向前查看1个输入符号个输入符号，便能确定当前所应选取规则，便能确定当前所应选取规则nLL(k)分析法含义分析法含义：两个两个L含义同上，括号中含义同上，括号中k表示每进行一步推表示每进行一步推导，导，需要向前查看需要向前查看k个输入符号个输入符号才能唯一确定当前才能唯一确定当前应选择规则。应选择规则。第47页4.4LL(1)分析方法分析方法 nLL(1)分析程序结构分析程序结构LL(1)分析器由一个总控程序、一张分析表和分析器由一个总控程序、一张分析表和一个分析栈组成。一个分析栈组成。是一个二维表，可用一是一个二维表，可用一个二维数组个二维数组MAMA，aa来来表示，它概括了文法全表示，它概括了文法全部信息，指出了分析器部信息，指出了分析器应采取动作。应采取动作。第48页4.4LL(1)分析方法分析方法输入符号串输入符号串：指要分析输入符号串。为了分析算指要分析输入符号串。为了分析算法统一，我们需要在输入串末尾放置一个特殊符号法统一，我们需要在输入串末尾放置一个特殊符号#，这个符号不属于终止符号集。，这个符号不属于终止符号集。分析表分析表M：是一个二维表，可用一个二维数组是一个二维表，可用一个二维数组MA，a来表示，它概括了文法全部信息，指出了分来表示，它概括了文法全部信息，指出了分析器应采取动作。分析表中每一行与文法中一个非析器应采取动作。分析表中每一行与文法中一个非终止符号、终止符号或终止符号、终止符号或#关联，即关联，即A能够是文法中一能够是文法中一个非终止符号、终止符号或个非终止符号、终止符号或#；而每一列则与文法；而每一列则与文法一个终止符号或一个终止符号或#关联，即关联，即a是文法一个终止符号或是文法一个终止符号或#。分析表列数是终止符号个数加。分析表列数是终止符号个数加1，行数是文法中，行数是文法中非终止符号和终止符号数目加非终止符号和终止符号数目加1。第49页4.4LL(1)分析方法分析方法分析栈分析栈（或（或符号栈符号栈）：用来存放一系列文法符号。）：用来存放一系列文法符号。分析开始时，先将分析开始时，先将#入栈，然后再将文法开始符号入入栈，然后再将文法开始符号入栈。栈。总控程序总控程序：分析器对输入串分析靠总控程序完成。分析器对输入串分析靠总控程序完成。依据分析栈栈顶符号和当前输入符号，总控程序按依据分析栈栈顶符号和当前输入符号，总控程序按照分析表指示来决定分析器动作。工作过程以下：照分析表指示来决定分析器动作。工作过程以下：输出流输出流：分析过程中使用产生式序列。分析过程中使用产生式序列。第50页p1)分析开始时，首先将符号分析开始时，首先将符号#及文法开始符号及文法开始符号S依次置于分依次置于分析栈底部，并把各指示器调整至起始位置。然后，重复执行析栈底部，并把各指示器调整至起始位置。然后，重复执行第二步操作。第二步操作。输入符号串：输入符号串：#ana2a1分析栈：分析栈：#S 分析开始时情况分析开始时情况p2)假设分析某一步，分析栈及余留符号串，则依据栈顶假设分析某一步，分析栈及余留符号串，则依据栈顶符号符号Xm，采取以下动作：，采取以下动作：aiai+1 an#X1X2Xm-1Xm 分析进行中情况分析进行中情况4.4LL(1)分析方法分析方法第51页(1)若若XmVn，则查分析表，则查分析表Xm所在行和所在行和ai所在列，假设所在列，假设MXm,ai为为POP,PUSH（WVU），则将，则将Xm出栈，并将出栈，并将WVU入栈，这意味着入栈，这意味着使用了规则使用了规则XmUVW；MXm,ai为为POP，则将，则将Xm出栈，这意味着出栈，这意味着使用了规则使用了规则Xm；若；若MXm，ai为空或为空或ERROR，则犯错。，则犯错。aiai+1 an#XmUVW(2)若若Xm=ai#，表表示示栈栈顶顶与与扫扫描描符符号号匹匹配配，则则查查分分析析表表为为POP，NEXTSYM，则则栈栈顶顶符符号号Xm出出栈栈，输输入入指指针针指指向下一个符号。向下一个符号。(3)若若Xm=ai=#，表示输入串完全匹配，分析成功。，表示输入串完全匹配，分析成功。#X1X2Xm-1WVU#X1X2Xm-1Xm#X1X2Xm-1 Xm第52页n例例(P72)算术表示式文法算术表示式文法ETE，E+TE，E，TFT,T*FT,T,F(E)|i，该文法，该文法LL(1)分析表为分析表为:第53页nLL(1)分析表中元素说明：分析表中元素说明：POP为过程，功效是将栈顶元素从栈内弹出。为过程，功效是将栈顶元素从栈内弹出。PUSH()为过程，其中为过程，其中V+,功效是将功效是将压栈。压栈。NEXTSYM为读符号过程，将读符号指针指向为读符号过程，将读符号指针指向下一个符号。下一个符号。ACCEPT表示分析成功，输入符号串语法正确。表示分析成功，输入符号串语法正确。表中空白处表中空白处表示错误入口，应该调用错误处理表示错误入口，应该调用错误处理程序。程序。4.4LL(1)分析方法分析方法第54页n例例4-7(P73)依据表依据表4-1，对符号串对符号串i+i*i进行分析。进行分析。符号串符号串i+i*i分析过程分析过程i+i*i最左推导：最左推导：ETEFTEiTEiEi+TEi+FTEi+iTEi+i*FTEi+i*iTEi+i*iEi+i*i 第55页4.4LL(1)分析方法分析方法n对文法对文法G中每个产生式中每个产生式A，按以下规则确定，按以下规则确定LL(1)分分析表中元素析表中元素M(P74，LL(1)分析表结构方法分析表结构方法)：1)对对FIRST()中每个终止符中每个终止符a（即（即不是不是时）时），置，置MA,a=“POP，PUSH()”或或MA，a=“A”，其中，其中为为倒置。倒置。2)若若FIRST()（即（即A），则对属于，则对属于FOLLOW(A)每个符号每个符号b(b为终止符或为终止符或#)，置，置MA,b=“POP”或或MA,b=“A”。3)把把M中全部中全部Ma,a置为置为“POP，NEXTSYM”，aVt，置，置M#,#=“ACCEPT”。（该项能够不要）（该项能够不要）4)把把M中全部不按上述规则定义元素均置为空或中全部不按上述规则定义元素均置为空或“ERROR”。第56页4.4LL(1)分析方法分析方法n例例 有有 文文 法法 ETE，E+TE，E，TFT，T*FT，T，F(E)|i对对规规则则ETE：FIRST(TE)=(，i)，那那么么在在分分析析表表符符号号E所所在在行行、符符号号(和和i所所在在列列对对应应位位置置分分别别填填入入“POP,PUSH(ET)”，见表，见表4-1E行。行。对对规规则则E+TE：FIRST(+TE)=+，在在符符号号E行行符符号号+列列对对应应位位置置填填入入“POP,PUSH(ET+)”，见见表表4-1E行。行。对对规规则则E：因因为为FIRST()，FOLLOW(E)=)，#，所所以以在在符符号号E行行符符号号)和和#列列对对应应位位置置填填入入“POP”，见表，见表4-1E行。行。其它规则处理方法相同（略）。其它规则处理方法相同（略）。n对于一个文法，若按上述方法结构分析表对于一个文法，若按上述方法结构分析表M不含多重定不含多重定义，则称它是一个义，则称它是一个LL(1)文法文法。第57页4.4LL(1)分析方法分析方法n观察表观察表4-1LL(1)分析表及表分析表及表4-2分析过程，分析过程，会发觉当压栈最终一个符号是终止符时，那会发觉当压栈最终一个符号是终止符时，那么下一步分析动作必定是这个终止符号出栈，么下一步分析动作必定是这个终止符号出栈，所以，我们能够对分析表进行简化。方法是所以，我们能够对分析表进行简化。方法是当压栈最终一个符号是终止符时，那么，这当压栈最终一个符号是终止符时，那么，这个终止符不入栈，并加入读下一个符号，这个终止符不入栈，并加入读下一个符号，这么，分析表中全部终止符行都能够去掉。么，分析表中全部终止符行都能够去掉。第58页对表对表4-1分析表简化后分析表以下表所表示分析表简化后分析表以下表所表示:E+TET*FTETEETEEETFTTFTTTTFiF(E)第59页n例例有文法有文法GS:S:=A，A:=BA，A:=iBA|，B:=CB，B:=+CB|，C:=)A*|(，请结构文法，请结构文法GLL(1)分析表。分析表。第60页4.4LL(1)分析方法分析方法n练习练习已知文法已知文法GS:S:=(S)S|(1)该文法是该文法是LL(1)文法吗？为何？文法吗？为何？(2)请给出该文法请给出该文法LL(1)分析表。分析表。(3)若输入符号串是若输入符号串是“()”，请给出其，请给出其LL(1)语法分语法分析过程。析过程。解：解：(1)显然，文法显然，文法G是经压缩、无左递归文法。下是经压缩、无左递归文法。下面判断它是否有回溯。面判断它是否有回溯。由由S:=(S)S|，有：，有：SELECT(S:=(S)S)SELECT(S:=)=FIRST(S)S)(FIRST()FOLLOW(S)=(,),#=文法文法G是是LL(1)文法。文法。第61页4.4 LL(1)4.4 LL(1)分析方法分析方法n练习练习已知文法已知文法GS:S:=(S)S|(1)该文法是该文法是LL(1)文法吗？为何？文法吗？为何？(2)请给出该文法请给出该文法LL(1)分析表。分析表。(3)若输入符号串是若输入符号串是“(
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
