第04章自上而下语法分析2课件

第04章自上而下语法分析2第04章自上而下语法分析2第04章自上而下语法分析24.2.4递归下降分析法递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。12021/2/22第04章自上而下语法分析2第04章自上而下语法分析2第04章4.2.4递归下降分析法

递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。22021/2/224.2.4递归下降分析法递归下降分析法是确定的自4.2.4递归下降分析法基本思想

对文法中的每个非终结符编写一个函数(或子程序),每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。32021/2/224.2.4递归下降分析法基本思想对文法中的每个非4.2.4递归下降分析法构造递归下降分析程序的方法:

为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写。A→α1α2…αnαi∈VTαi∈VNα1α2…αn=ε42021/2/224.2.4递归下降分析法构造递归下降分析程序的方法:4.2.4递归下降分析法(1)当遇到终结符a时，则编写语句if(当前读来的输入符号==a)

读下一个输入符号；(2)当遇到非终结符A时，则编写语句调用A()；52021/2/224.2.4递归下降分析法(1)当遇到终结符a时，则编写(4)当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导。(3)当遇到规则A→ε

时，则编写语句4.2.4递归下降分析法if(当前读来的输入符号FOLLOW(A))

error()；62021/2/22(4)当某个非终结符的规则有多个候选式(3)当遇到规则AE→E+T|TT→T*F|FF→(E)|id例设有文法G[E]：试构造一个识别该文法句子的递归下降分析程序。4.2.4递归下降分析法72021/2/22E→E+T|T例设有文法G[E]：试构造一个识别

分析首先消去文法左递归，得到文法

G'[E]E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idE→E+T|TT→T*F|FF→(E)|id4.2.4递归下降分析法82021/2/22 分析首先消去文法左递归，得到文法E→TE'E→E

无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符E',T',F有：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id4.2.4递归下降分析法92021/2/22无左递归的文法不一定是LL(1)文法，根据LL(SELECT(E'→+TE')∩SELECT(E'→ε)=FIRST(+TE')∩{FIRST(ε)∪FOLLOW(E')}={+}∩{ε,),#}=ΦSELECT(T'→*FT')∩SELECT(T'→ε)=FIRST(*FT')∩{FIRST(ε)∪FOLLOW(T')}={*}∩{ε,),#,+}=Φ4.2.4递归下降分析法102021/2/22SELECT(E'→+TE')∩SELECT(E'SELECT(F→id)∩SELECT(F→(E))=FIRST(id)∩FIRST((E))={id}∩{(}=Φ所以文法G'[E]是LL(1)文法。4.2.4递归下降分析法112021/2/22SELECT(F→id)∩SELECT(F→(E)分析程序中定义两个函数：(1)函数

Scaner()

功能:读进源程序的下一个单词符号并将它放在全程变量sym。(2)函数error()

功能:出错处理程序。4.2.4递归下降分析法122021/2/22分析程序中定义两个函数：(1)函数Scaner()(2

对文法G'[E]可写出相应的递归下降分析程序如下：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idmain(){Scaner();E();if(sym==‘#’)printf(“success”);elseprintf(“fail”);}4.2.4递归下降分析法132021/2/22对文法G'[E]可写出相应的递归下降分析程序如下：E(){T();E'();}E'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sym!=‘#’))error();}4.2.4递归下降分析法E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id142021/2/22E()E'()4.2.4递归下降分析法E→TET(){F();T();}

E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|idT(){if(sym==‘*’){Scaner();F();T();}elseif(symfollow(T'))error();}4.2.4递归下降分析法152021/2/22T()E→TE'T()4.2.4递归下降分F(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();elseerror();}elseerror();}E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id4.2.4递归下降分析法162021/2/22F()E→TE'4.2.4递归下降分析法1624.2.4递归下降分析法main(){Scaner();E();if(sym==‘#’)printf(“success”);elseprintf(“fail”);}id+id#E(){T();E'();}T(){F();T();}

见F见E'见T'返回下一页172021/2/224.2.4递归下降分析法main()id+idF(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();elseerror();}elseerror();}4.2.4递归下降分析法返回T182021/2/22F()4.2.4递归下降分析法返回T182021/24.2.4递归下降分析法T(){if(sym==‘*’){Scaner();F();T();}elseif(symfollow(T'))error();}follow(T')={+,),#}返回T192021/2/224.2.4递归下降分析法T()follow(T')4.2.4递归下降分析法E'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sym!=‘#’))error();}返回E见T返回E202021/2/224.2.4递归下降分析法E'()返回E见T返回E20缺点:对文法要求高，必须是LL(1)文法，同时由于递归调用较多，影响分析器的效率。优点:递归下降分析法简单、直观，易于构造分析程序。4.2.4递归下降分析法212021/2/22缺点:对文法要求高，必须是LL(1)文优点:递归下降分析4.2.5预测分析法与预测分析表的构造

预测分析法(LL(1)分析法)是确定的自上而下分析的另一种方法，采用这种方法进行语法分析要求描述语言的文法是LL(1)文法。222021/2/224.2.5预测分析法与预测分析表的构造预测分析法预测分析器的逻辑结构预测分析表总控程序a1a2···ai···an#T[j]输入串X…#输出4.2.5预测分析法与预测分析表的构造分析栈232021/2/22预测分析器的逻辑结构预测分析表总控程序a1a2···a

输入缓冲区T[j]中存放待分析的输入符号串，它以右界符‘#’作为结束。

分析栈S[K]中存放替换当前非终结符的某规则右部符号串，句子左界符‘#’存入栈底。

预测分析表是一个二维形式的矩阵，其中矩阵的行为文法非终结符，矩阵的列为文法终结符和‘#’。4.2.5预测分析法与预测分析表的构造见表242021/2/22输入缓冲区T[j]中存放待分析的输入符号串，它以右界

预测分析器的总控程序在任何时候都是根据栈顶符号和当前输入符号a来决定分析器的动作。‘#’和文法开始符号进S栈第一个输入符号读进aS栈顶符号出栈放入X中X∈VT?X=a?Y将下一个输入符号读入aY出错NNX=‘#’?X=a?YSTOPYN查M[X,a]=X→y1y2···yn?N将y1y2∙∙∙yn逆序放入S栈中，若右部符号串为ε，则ε不进S栈Y出错N252021/2/22预测分析器的总控程序在任何时候都是根据栈顶符号和当前

预测分析器的总控程序对于不同的LL(1)文法都是相同的，而预测分析表对于不同的LL(1)文法是不相同的。构造预测分析表的方法：输入:文法G输出:预测分析表M4.2.5预测分析法与预测分析表的构造262021/2/22预测分析器的总控程序对于不同的LL(1)文法都是相方法：4.2.5预测分析法与预测分析表的构造1.计算文法G的每一非终结符的FIRST集和FOLLOW集。2.对文法的每个规则A→α,若a∈FIRST(α),

则置M[A,a]=A→α。3.若ε∈FIRST(α),则对任b∈FOLLOW(A),则置M[A,b]=A→α。272021/2/22方法：4.2.5预测分析法与预测分析表的构造1.计算文法4.把分析表中每个未定义的元素标上出错标志error（表中用空格表示）4.2.5预测分析法与预测分析表的构造例设有文法G[E]：试构造该文法的预测分析表。E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id282021/2/224.把分析表中每个未定义的元素标上出错标志error4.2.5预测分析法与预测分析表的构造

E

E'

TT'F{(,id}{),#}{(,id}{+,),#}{(,id}{+,),#,*}

{+,ε}{),#}{*,

ε}{+,),#}FIRSTFOLLOWE→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id292021/2/224.2.5预测分析法与预测分析表的构造E{(,id+*()#EE'TT'F对规则E→TE'∵FIRST(TE')={(,id}E→TE'E→TE'∵FIRST(+TE')={+}E'→+TE'∵FOLLOW(E')={),#}E'→εE'→εT→FT'T→FT'T'→εT'→εT'→εT'→*FT'F→idF→(E)E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id对规则E'→+TE'

对规则E'→ε302021/2/22id+*句子id+id*id#的分析过程

分析栈输入串#Eid+id*id##E'Tid+id*id##E'T'Fid+id*id##E'T'idid+id*id##E'T'

+id*id##E'+id*id##E'T++id*id##E'Tid*id###……见表312021/2/22句子id+id*id#的分析过程分析栈4.2.5预测分析法与预测分析表的构造

例设有文法G[S]S→a|∧|(T)T→T,S|S1.消去文法左递归,改写文法G[S]为G’[S]2.计算文法G’[S]每个非终结符的FIRST集和FOLLOW集。3.判断文法G’[S]是否LL(1)文法。4.试构造文法G’[S]的预测分析表。5.给出输入串(a)#的分析过程。322021/2/224.2.5预测分析法与预测分析表的构造 例设有文法G[4.2.5预测分析法与预测分析表的构造

分析引进新的非终结符,改写文法,得到文法G'[S]:S→a|∧|(T)T→ST'T'→,ST'|ε

根据FIRST集和FOLLOW集的定义,求出文法每个非终结符的FIRST集和FOLLOW集：S→a|∧|(T)T→T,S|S332021/2/224.2.5预测分析法与预测分析表的构造分析引进新的4.2.5预测分析法与预测分析表的构造

FIRSTFOLLOWSTT'

{a,∧,(}{)}S→a|∧|(T)T→ST'T'→,ST'|ε{,

,ε}{)}{a,∧,(}{#,,

,)}342021/2/224.2.5预测分析法与预测分析表的构造FIRST4.2.5预测分析法与预测分析表的构造

根据LL(1)文法的判断条件，对非终结符S和T'有：SELECT(S→a)∩SELECT(S→∧)=FIRST(a)∩FIRST(∧)={a}∩{∧}=ΦSELECT(S→a)∩SELECT(S→(T))=FIRST(a)∩FIRST((T))={a}∩{(}=ΦSELECT(S→∧)∩SELECT(S→(T))=FIRST(∧)∩FIRST((T))={∧}∩{(}=Φ352021/2/224.2.5预测分析法与预测分析表的构造根据LSELECT(T'→,ST')∩SELECT(T'→ε)=FIRST(,ST')∩{FIRST(ε)∪FOLLOW(T')}={,}∩{ε,)}=Φ所以文法G'[S]是LL(1)文法。S→a|∧|(T)T→ST'T'→,ST'|ε4.2.5预测分析法与预测分析表的构造362021/2/22SELECT(T'→,ST')∩SELECT(T'→ε)=∵FIRST(a)={a}∵FIRST(∧)={∧}

∵FIRST((T))={(}对规则S→a

对规则S→∧

对规则S→(T)a∧(),#S→aS→∧S→(T)T→STT→STT→STT'→εT'→,ST'对规则T→ST'∵FIRST(ST')={a,∧,(}对规则T'→ε∵FOLLOW(T')={)}对规则T'→,ST'∵FIRST(,ST')={,}STT'372021/2/22∵FIRST(a)={a}∵FIRST(∧)={∧}分析符号串(a)#的过程如下表:分析栈输入串#S(a)##)T((a)##)Ta)##)T'Sa)##)T'aa)##)T')##))###S→a|∧|(T)T→ST'T'→,ST'|ε4.2.5预测分析法与预测分析表的构造382021/2/22分析符号串(a)#的过程如下表:分析栈

可以证明,若一个文法G的分析表M不含多重定义元素,则该文法是LL(1)文法。

4.2.5预测分析法与预测分析表的构造 LL(1)分析表比其他分析方法中的分析表相对要小一些。预测分析法的主要优点是392021/2/22 可以证明,若一个文法G的分析表M不含多重定义元素,则该思考题P924.14.2本节完402021/2/22思考题P924.14.2本节完402021/2/22id+*()$EE'TT'FE→TE'E→TE'E'→+TE'E'→εE'→εT→FT'T→FT'T'→εT'→εT'→εT'→*FT'F→iF→(E)E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i返回4.2.5预测分析法与预测分析表的构造返回412021/2/22id+*汇报结束谢谢大家!请各位批评指正422021/2/22汇报结束谢谢大家!请各位批评指正422021/2/22第04章自上而下语法分析2第04章自上而下语法分析2第04章自上而下语法分析24.2.4递归下降分析法递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。432021/2/22第04章自上而下语法分析2第04章自上而下语法分析2第04章4.2.4递归下降分析法

递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。442021/2/224.2.4递归下降分析法递归下降分析法是确定的自4.2.4递归下降分析法基本思想

对文法中的每个非终结符编写一个函数(或子程序),每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。452021/2/224.2.4递归下降分析法基本思想对文法中的每个非4.2.4递归下降分析法构造递归下降分析程序的方法:

为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写。A→α1α2…αnαi∈VTαi∈VNα1α2…αn=ε462021/2/224.2.4递归下降分析法构造递归下降分析程序的方法:4.2.4递归下降分析法(1)当遇到终结符a时，则编写语句if(当前读来的输入符号==a)

读下一个输入符号；(2)当遇到非终结符A时，则编写语句调用A()；472021/2/224.2.4递归下降分析法(1)当遇到终结符a时，则编写(4)当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导。(3)当遇到规则A→ε

时，则编写语句4.2.4递归下降分析法if(当前读来的输入符号FOLLOW(A))

error()；482021/2/22(4)当某个非终结符的规则有多个候选式(3)当遇到规则AE→E+T|TT→T*F|FF→(E)|id例设有文法G[E]：试构造一个识别该文法句子的递归下降分析程序。4.2.4递归下降分析法492021/2/22E→E+T|T例设有文法G[E]：试构造一个识别

分析首先消去文法左递归，得到文法

G'[E]E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idE→E+T|TT→T*F|FF→(E)|id4.2.4递归下降分析法502021/2/22 分析首先消去文法左递归，得到文法E→TE'E→E

无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符E',T',F有：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id4.2.4递归下降分析法512021/2/22无左递归的文法不一定是LL(1)文法，根据LL(SELECT(E'→+TE')∩SELECT(E'→ε)=FIRST(+TE')∩{FIRST(ε)∪FOLLOW(E')}={+}∩{ε,),#}=ΦSELECT(T'→*FT')∩SELECT(T'→ε)=FIRST(*FT')∩{FIRST(ε)∪FOLLOW(T')}={*}∩{ε,),#,+}=Φ4.2.4递归下降分析法522021/2/22SELECT(E'→+TE')∩SELECT(E'SELECT(F→id)∩SELECT(F→(E))=FIRST(id)∩FIRST((E))={id}∩{(}=Φ所以文法G'[E]是LL(1)文法。4.2.4递归下降分析法532021/2/22SELECT(F→id)∩SELECT(F→(E)分析程序中定义两个函数：(1)函数

Scaner()

功能:读进源程序的下一个单词符号并将它放在全程变量sym。(2)函数error()

功能:出错处理程序。4.2.4递归下降分析法542021/2/22分析程序中定义两个函数：(1)函数Scaner()(2

对文法G'[E]可写出相应的递归下降分析程序如下：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idmain(){Scaner();E();if(sym==‘#’)printf(“success”);elseprintf(“fail”);}4.2.4递归下降分析法552021/2/22对文法G'[E]可写出相应的递归下降分析程序如下：E(){T();E'();}E'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sym!=‘#’))error();}4.2.4递归下降分析法E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id562021/2/22E()E'()4.2.4递归下降分析法E→TET(){F();T();}

E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|idT(){if(sym==‘*’){Scaner();F();T();}elseif(symfollow(T'))error();}4.2.4递归下降分析法572021/2/22T()E→TE'T()4.2.4递归下降分F(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();elseerror();}elseerror();}E→TE'E'→+TE'|ε

T→FT'T'→*FT'|εF→(E)|id4.2.4递归下降分析法582021/2/22F()E→TE'4.2.4递归下降分析法1624.2.4递归下降分析法main(){Scaner();E();if(sym==‘#’)printf(“success”);elseprintf(“fail”);}id+id#E(){T();E'();}T(){F();T();}

见F见E'见T'返回下一页592021/2/224.2.4递归下降分析法main()id+idF(){if(sym==‘id’)Scaner();elseif(sym==‘(’){Scaner();E();if(sym==‘)’)Scaner();elseerror();}elseerror();}4.2.4递归下降分析法返回T602021/2/22F()4.2.4递归下降分析法返回T182021/24.2.4递归下降分析法T(){if(sym==‘*’){Scaner();F();T();}elseif(symfollow(T'))error();}follow(T')={+,),#}返回T612021/2/224.2.4递归下降分析法T()follow(T')4.2.4递归下降分析法E'(){if(sym==‘+’){Scaner();T();E();}elseif((sym!=‘)’)&&(sym!=‘#’))error();}返回E见T返回E622021/2/224.2.4递归下降分析法E'()返回E见T返回E20缺点:对文法要求高，必须是LL(1)文法，同时由于递归调用较多，影响分析器的效率。优点:递归下降分析法简单、直观，易于构造分析程序。4.2.4递归下降分析法632021/2/22缺点:对文法要求高，必须是LL(1)文优点:递归下降分析4.2.5预测分析法与预测分析表的构造

预测分析法(LL(1)分析法)是确定的自上而下分析的另一种方法，采用这种方法进行语法分析要求描述语言的文法是LL(1)文法。642021/2/224.2.5预测分析法与预测分析表的构造预测分析法预测分析器的逻辑结构预测分析表总控程序a1a2···ai···an#T[j]输入串X…#输出4.2.5预测分析法与预测分析表的构造分析栈652021/2/22预测分析器的逻辑结构预测分析表总控程序a1a2···a

输入缓冲区T[j]中存放待分析的输入符号串，它以右界符‘#’作为结束。

分析栈S[K]中存放替换当前非终结符的某规则右部符号串，句子左界符‘#’存入栈底。

预测分析表是一个二维形式的矩阵，其中矩阵的行为文法非终结符，矩阵的列为文法终结符和‘#’。4.2.5预测分析法与预测分析表的构造见表662021/2/22输入缓冲区T[j]中存放待分析的输入符号串，它以右界

预测分析器的总控程序在任何时候都是根据栈顶符号和当前输入符号a来决定分析器的动作。‘#’和文法开始符号进S栈第一个输入符号读进aS栈顶符号出栈放入X中X∈VT?X=a?Y将下一个输入符号读入aY出错NNX=‘#’?X=a?YSTOPYN查M[X,a]=X→y1y2···yn?N将y1y2∙∙∙yn逆序放入S栈中，若右部符号串为ε，则ε不进S栈Y出错N672021/2/22预测分析器的总控程序在任何时候都是根据栈顶符号和当前

预测分析器的总控程序对于不同的LL(1)文法都是相同的，而预测分析表对于不同的LL(1)文法是不相同的。构造预测分析表的方法：输入:文法G输出:预测分析表M4.2.5预测分析法与预测分析表的构造682021/2/22预测分析器的总控程序对于不同的LL(1)文法都是相方法：4.2.5预测分析法与预测分析表的构造1.计算文法G的每一非终结符的FIRST集和FOLLOW集。2.对文法的每个规则A→α,若a∈FIRST(α),

则置M[A,a]=A→α。3.若ε∈FIRST(α),则对任b∈FOLLOW(A),则置M[A,b]=A→α。692021/2/22方法：4.2.5预测分析法与预测分析表的构造1.计算文法4.把分析表中每个未定义的元素标上出错标志error（表中用空格表示）4.2.5预测分析法与预测分析表的构造例设有文法G[E]：试构造该文法的预测分析表。E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id702021/2/224.把分析表中每个未定义的元素标上出错标志error4.2.5预测分析法与预测分析表的构造

E

E'

TT'F{(,id}{),#}{(,id}{+,),#}{(,id}{+,),#,*}

{+,ε}{),#}{*,

ε}{+,),#}FIRSTFOLLOWE→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id712021/2/224.2.5预测分析法与预测分析表的构造E{(,id+*()#EE'TT'F对规则E→TE'∵FIRST(TE')={(,id}E→TE'E→TE'∵FIRST(+TE')={+}E'→+TE'∵FOLLOW(E')={),#}E'→εE'→εT→FT'T→FT'T'→εT'→εT'→εT'→*FT'F→idF→(E)E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id对规则E'→+TE'

对规则E'→ε722021/2/22id+*句子id+id*id#的分析过程

分析栈输入串#Eid+id*id##E'Tid+id*id##E'T'Fid+id*id##E'T'idid+id*id##E'T'

+id*id##E'+id*id##E'T++id*id##E'Tid*id###……见表732021/2/22句子id+id*id#的分析过程分析栈4.2.5预测分析法与预测分析表的构造

例设有文法G[S]S→a|∧|(T)T→T,S|S1.消去文法左递归,改写文法G[S]为G’[S]2.计算文法G’[S]每个非终结符的FIRST集和FOLLOW集。3.判断文法G’[S]是否LL(1)文法。4.试构造文法G’[S]的预测分析表。5.给出输入串(a)#的分析过程。742021/2/224.2.5预测分析法与预测分析表的构造 例设有文法G[4.2.5预测分析法与预测分析表的构造

分析引进新的非终结符,改写文法,得到文法G'[S]:S→a|∧|(T)T→ST'T'→,ST'|ε

根据FIRST集和FOLLOW集的定义,求出文法每个非终结符的FIRST集和FOLLOW集：S→a|∧|(T)T→T,S|S752021/2/224.2.5预测分析法与预测分析表的构造分析引进新的4.2.5预测分析法与预测分析表的构造

FIRSTFOLLOWSTT'

{a,∧,(}{)}S→a|∧|(T)T→ST'T'→,ST'|ε{,

,ε}{)}