第4章(小结)白底黑字

确定的自上而下分析法自下而上分析法递归下降分析法预测分析法本章小结本章介绍了四种典型的语法分析方法算符优先分析法LR分析法LR(0)分析法SLR(1)分析法LR(1)分析法LALR(1)分析法确定的自上而下分析法要求描述语言的文法是LL(1)文法。1.LL(1)文法的判别方法。(1)求文法每个产生式右部符号串的FIRST集。(2)求文法各个非终结符的FOLLOW集。本章小结一.确定的自上而下分析法(3)求文法每个产生式的SELECT集。(4)求相同左部产生式的SELECT交集。对文法G的每一个非终结符A的产生式SELECT(A→αi)∩SELECT(A→αj)=Φ(i≠j)则文法G是一个LL(1)文法本章小结A→α1|α2|…|αn下面条件成立:2.LL(1)文法是无左递归、无二义性文法。3.将非LL(1)文法改写为LL(1)文法的方法。(1)消除文法直接左递归P→Pα|β改写为P→βP',P'→αP'|ε或P→β{α}本章小结(2)提取公共左因子本章小结若A→αβ1|αβ2|…|αβn提取公共左因子将文法改写成:A→αA'A'→β1|β2|…|βn4.根据文法规则构造递归下降分析程序和预测分析表的方法5.注意LL(1)分析法与LR分析法的区别本章小结LL(1)分析法(预测分析法)是自上而下的语法分析法,要求文法为LL(1)文法LR分析法是自下而上的语法分析法,只要文法是上下文无关文法例1设有文法G[E]：为消除文法直接左递规,请改写文法,改写后的文法为:本章小结E→E+T|E－T|TT→T*F|T/F|FF→(E)|idT{+T|－T}E→本章小结E→E+T|E－T|TT→T*F|T/F|FF→(E)|idF{*F|/F}T→(E)|idF→例2设有文法G[S]S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε本章小结1.计算文法G[S]每个非终结符的FIRST集和FOLLOW集。2.判断文法G[S]是否LL(1)文法。本章小结对每一文法符号X∈V,求FIRST(X)的规则:FIRST(α)={a|αa…且a∈VT}*,则规定ε∈FIRST(α)若αε*1.若X∈VT,则FIRST(X)={X}2.若X∈VN且有X→a…,则把a加入FIRST(X)中,若X→ε,则把ε加入FIRST(X)中3.若X→Y…,Y∈VN,则把FIRST(Y)中所有非ε元素加入FIRST(X)中FIRST(S)=FIRST(aAbDe)∪FIRST(d)={a,d}本章小结FIRST(A)=FIRST(B)∪FIRST(e)=FIRST(S)∪FIRST(cD)∪{e}={a,d,c,e}S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε问:能否∪ε因为从A*/ε,所以εFIRST(A)FIRST(B)=FIRST(S)∪FIRST(cD)∪{ε}={a,d,c,ε}FIRST(D)=FIRST(Se)∪{ε}={a,d,ε}本章小结FOLLOW(A)={a|S…Aa…且a∈VT}*若有S…A,*则规定$∈FOLLOW(A)。求FOLLOW(A)的规则:1.对文法的开始符号S,令$∈FOLLOW(S)2.若A→αBβ是一条规则,则将FIRST(β)\{ε}加到FOLLOW(B)中3.若A→αB是一条规则,或A→αBβ是一条规则而βε,则把FOLLOW(A)加到FOLLOW(B)中*FOLLOW(S)={$,a,b,c,d,e}FOLLOW(A)={b,c}本章小结FOLLOW(B)={a,d}FOLLOW(D)={a,b,c,d,e}S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|εFIRST(D)={a,d,ε}FIRST(S)={a,d}FIRST(A)={a,d,c,e}根据LL(1)文法的定义有:SELECT(S→aAbDe)∩SELECT(S→d)=FIRST(aAbDe)∩FIRST(d)=Φ本章小结SELECT(A→BSD)∩SELECT(A→e)=FIRST(BSD)∩FIRST(e)=ΦS→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|εSELECT(B→SAc)∩SELECT(B→cD)=FIRST(SAc)∩FIRST(cD)=ΦSELECT(B→SAc)∩SELECT(B→ε)=FIRST(SAc)∩{ε,a,d}≠ΦFOLLOW(B)={a,d}所以该文法不是LL(1)文法例3已知一个有限输入字符集合Σ={a,b},请用高级程序语言编写一个能识别集合L={anbn|n≥0}的程序。本章小结分析首先给出识别该语言的文法为S→aSb|ε该文法无左递归且为LL(1)文法根据文法给出识别该语言的分析程序如下:本章小结main(){scaner();S();if(sym==‘$’)printf(“right”);elseerror();}S(){ifsym==‘a’{scaner();S();if(sym==‘b’)scaner();elseerror();}elseif((sym!=‘b’)&&(sym!=‘$’))error();}S→aSb|ε例设有文法G[E]：试构造该文法的预测分析表。E→E+T|TT→T*F|FF→(E)|id本章小结分析首先消去文法左递归，得到文法G'[E]E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idE→E+T|TT→T*F|FF→(E)|id本章小结无左递归的文法不一定是LL(1)文法，根据LL(1)文法的判断条件，对非终结符E',T',F有：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|idETE'ETE'TFT'F(E)(TE')ETE'TFT'+ETE'FT'+TE'+ETE'(FT')本章小结SELECT(E'→+TE')∩SELECT(E'→ε)=FIRST(+TE')∩{FIRST(ε)∪FOLLOW(E')}={+}∩{),$}=ΦSELECT(T'→*FT')∩SELECT(T'→ε)=FIRST(*FT')∩{FIRST(ε)∪FOLLOW(T')}={*}∩{),$,+}=Φ本章小结SELECT(F→id)∩SELECT(F→(E))=FIRST(id)∩FIRST((E))={id}∩{(}=Φ所以文法G'[E]是LL(1)文法。本章小结EE'TT'F{(,id}{),$}{(,id}{+,),$}{(,id}{+,),$,*}{+,ε}{),$}{*,ε}{+,),$}FIRSTFOLLOWE→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|id本章小结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'→ε句子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$$$……1.算符优先分析法特别适合于分析算术表达式,但不是专用于分析算术表达式的。本章小结二.自下而上语法分析法(一).算符优先分析法2.算符优先文法的判别方法(1)判所给文法G是否算符文法。若文法中没有形如A→∙∙∙BC∙∙∙规则，则称G为算符文法。本章小结(2)对算符文法G，计算每个非终结符的FIRSTVT和LASTVT集。(3)根据算符优先关系定义，计算文法G中任意两个终结符之间的优先关系,即构造优先关系表。本章小结(4)若任意两个终结符之间至多只有、、三种关系的一种成立，则G是一个算符优先文法。.=..3.算符优先分析法只在终结符之间定义了优先关系，因而它的归约过程与规范归约是不同的，它不是对句柄进行归约，而是对最左素短语进行归约。本章小结4.求最左素短语的方法(1)画出句型的语法树。(2)根据语法树求出句型的所有短语。(3)满足下列条件的短语:至少含有一个终结符;除自身之外不再包含其他素短语。本章小结5.根据优先关系定义构造优先关系表的方法。本章小结6.由于算符优先分析法忽略了非终结符在归约过程中的作用，可能导致把不是句子的输入串误认为是句子。例1设有文法G[S]:S→AA→B|AiBB→C|B+CC→)A*|(给出句型C+Ci(的所有短语、句柄和素短语。本章小结分析首先画出句型的语法树SAAiBB+CCC(短语:C+Ci(C+CC(句柄:C素短语:C+C(本章小结例2设有文法G[E]:E→ET+|TT→TF*|FF→F↑|a给出句型FF↑↑*的所有短语、句柄和素短语。本章小结分析首先画出句型的语法树本章小结ETTF*F↑FF↑根据语法树求短语FF↑↑*F↑↑F↑F素短语F↑句柄F例3设有表格结构文G[S]：S→a|∧|(T)T→T,S|S(1)计算文法G[S]的FIRSTVT集和LASTVT集。(2)构造G[S]的优先关系表，并判断G[S]是否算符优先文法。本章小结计算文法G[S]的FIRSVT集和LASTVT集如下:FIRSTVT(A)={b|Ab…或ABb…,b∈VT,B∈VN}++LASTVT(A)={a|A…a或A…aB,a∈VT,B∈VN}++本章小结FIRSTVTLASTVTSTS→a|∧|(T)T→T,S|S{a,∧,(}{a,∧,)}{,,a,∧,(}{,,a,∧,)}本章小结寻找终结符在左边，非终结符在右边的符号对有寻找非终结符在左边，终结符在右边的符号对有T)LASTVT(T)).T,LASTVT(T),.(T(FIRSTVT(T).,S,FIRSTVT(S).本章小结见表文法G[S]的优先关系表如下表所示a∧,()a∧,()...............=.本章小结返回S→a|∧|(T)T→T,S|S文法G[S]是一个算符优先文法。因为文法G[S]的任何规则右部都不含两个相邻的非终结符,并且任何两个终结符之间至多只存在一种优先关系。本章小结本章小结(二)LR分析法大多数用上下文无关文法描述的语言都可以用相应的LR分析器予以识别。1.LR分析法是一种规范归约分析法，本章小结2.从给定的上下文无关文法构造LR分析表的方法是：对LR(1)或LALR(1)分析表，构造LR(1)项目集规范族。(1)对LR(0)或SLR(1)分析表，构造LR(0)项目集规范族;本章小结(2)构造识别文法规范句型活前缀的DFA。(3)将DFA转换成相应的LR分析表。注意文法一定要拓广。四种分析表的构造基本相同，仅对含归约项目的项目集构造分析表元素不同。3.四种LR文法的判别方法(1)任何的二义性文法都不是LR类文法。本章小结②SLR(1)文法是LR(0)项目集中所有含冲突的项目集都能用SLR规则解决冲突。(或SLR(1)分析表中不含多重定义)(2)根据项目集中是否含冲突项目或相应分析表中是否含多重定义元素进行判断：①LR(0)文法是所有的LR(0)项目集中没有移进—归约冲突或归约—归约冲突。(或LR(0)分析表中不含多重定义)本章小结SLR规则：I:{A→α.bβB1→γ1.B2→γ2.}{b}∩FOLLOW(B1)=ΦFOLLOW(B1)∩FOLLOW(B2)=Φ{b}∩FOLLOW(B2)=Φa∈{b}移进a∈FOLLOW(B1)用B1→γ1归约a∈FOLLOW(B2)用B2→γ2归约本章小结③LR(1)项目集中无移进—归约冲突或归约—归约冲突。（或LR(1)分析表中不含多重定义）注意:搜索符只对归约项目起作用。I:{[A→α.bβ,a][B1→γ1.,a]}I:{[A→α.bβ,a][B