形式語言與語法分析

形式語言與語法分析第一頁，共六十五頁，2022年，8月28日第三章語法分析介紹第二頁，共六十五頁，2022年，8月28日第3章outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯誤處理第三頁，共六十五頁，2022年，8月28日知識關(guān)系圖開發(fā)語法分析程序語法定義基于上下文無關(guān)文法使用實現(xiàn)自頂向下自底向上第四頁，共六十五頁，2022年，8月28日3.1語法分析概述部分語法分析程序的功能輸入：詞法分析程序輸出的Token/TokenList輸出：語法結(jié)構(gòu)的內(nèi)部表示(抽象語法樹，AST)

或語法錯誤信息分析過程：從左到右掃描Token序列，根據(jù)上下文無關(guān)文法，建立語法結(jié)構(gòu)的內(nèi)部表示，檢查語法錯誤。語法分析Token序列抽象語法樹語法錯誤第五頁，共六十五頁，2022年，8月28日語法分析過程C程序：Parser輸入：Parser輸出：if

(x=y)

{z=1;}else{z=0;}

IFLparenidEQidRparenLGidEQnumsemiRGelseLGidEQnumsemiRGIF_Stmt=idid=idnum=idnum第六頁，共六十五頁，2022年，8月28日程序設(shè)計語言的語法結(jié)構(gòu)(1)程序(2)聲明

-常量聲明

-類型聲明

-變量聲明

-過程/函數(shù)聲明(3)程序體(4)語句（賦值語句，條件語句，循環(huán)語句，函數(shù)調(diào)用語句）(5)表達式(算術(shù)表達式，邏輯表達式，關(guān)系表達式)第七頁，共六十五頁，2022年，8月28日語法錯誤語法錯誤的類型語法結(jié)構(gòu)的開始單詞錯誤表達式E的開始單詞是id,(,n---其他Token則出錯語法結(jié)構(gòu)的后繼單詞錯誤語句；語句----語句，語句標(biāo)識符或者常量錯id

:=E----begin:=E或123:=E關(guān)鍵字錯ifEthen語句else

語句----其他關(guān)鍵字則出錯括號配對錯（（）（））----）（（）第八頁，共六十五頁，2022年，8月28日語法錯誤的例子intGetMax(intx;inty){if(x>y){returnx}elsereturny;}}vodmain(){real10,y;10+;GetMax(x,y);}后繼單詞錯括號配對錯關(guān)鍵字錯,開始單詞錯標(biāo)識符錯開始單詞錯第九頁，共六十五頁，2022年，8月28日語法分析方法自頂向下的分析從上往下生成樹的過程自底向上的分析從下往上生成樹的過程IF_Stmt=idid=idnum=id0遞歸下降分析LL(1)分析LR(0),SLR(1),LR(1),LALR(1)第十頁，共六十五頁，2022年，8月28日語法分析與詞法分析的比較階段（Phase）輸入（Input）輸出（Output）詞法分析（scanner）字符序列Token序列語法分析（parser）Token序列抽象語法樹第十一頁，共六十五頁，2022年，8月28日第3章outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯誤處理√第十二頁，共六十五頁，2022年，8月28日3.2上下文無關(guān)文法

不是所有的Token串都是合法的程序，因此需要一個工具來描述合法的Token串。一般地，程序設(shè)計語言的結(jié)構(gòu)都是遞歸結(jié)構(gòu)(recursivestructure)例如：表達式，上下文無關(guān)文法非常適合描述這種結(jié)構(gòu)變量是表達式（表達式）是表達式表達式+表達式是表達式第十三頁，共六十五頁，2022年，8月28日3.2上下文無關(guān)文法上下文無關(guān)文法是一個四元組(VT,VN,S,P)VT是有限的終極符集合VN是有限的非終極符集合S是開始符，SVNP是產(chǎn)生式的集合，且具有下面的形式：

AX1X2…Xn

其中AVN，Xi(VTVN)符號約定：非終極符用大寫字母表示終極符用小寫字母表示開始符是第一條產(chǎn)生式左部的符號不絕對！第十四頁，共六十五頁，2022年，8月28日上下文無關(guān)文法的例子例1：簡單算術(shù)表達式的上下文無關(guān)文法，EidE(E)EE+EEE*EEid|(E)|E+E|E*EEid|(E)|E+E|E*EVT:{id,(,),+,*}VN:ES:E第十五頁，共六十五頁，2022年，8月28日上下文無關(guān)文法的例子例2：語句的上下文無關(guān)文法：

VT：{id，（，），+，*,=,if,else,while,;}VN：E,StmtS：StmtStmt

id=EStmtifEStmtelseStmtStmtwhileEStmtStmtStmt;Stmt

EidE(E)EE+EEE*E第十六頁，共六十五頁，2022年，8月28日上下文無關(guān)文法的例子例3：變量聲明的上下文無關(guān)文法：

變量聲明變量聲明一個變量定義;變量聲明一個變量定義;變量聲明變量定義類型標(biāo)識符序列標(biāo)識符序列一個標(biāo)識符標(biāo)識符序列一個標(biāo)識符,標(biāo)識符序列VarDecVarDecVarDef;VarDecVarDef;VarDecVarDefTypeIdListIdListidIdListid,IdList第十七頁，共六十五頁，2022年，8月28日上下文無關(guān)文法是怎樣定義語言的？第十八頁，共六十五頁，2022年，8月28日與上下文無關(guān)文法有關(guān)的一些概念直接推導(dǎo)()：如果A是一個產(chǎn)生式，則有A,其中表示一步推導(dǎo)(用A→)。這時稱是由A直接推導(dǎo)的?！啊钡暮x是，使用一條規(guī)則，代替左邊的某個符號，產(chǎn)生右端的符號串推導(dǎo)(+)：若通過一步或多步推導(dǎo)可從串導(dǎo)出串,則稱為的推導(dǎo),并記為+星推導(dǎo)(*):稱*當(dāng)且僅當(dāng)=或+第十九頁，共六十五頁，2022年，8月28日例子(E)(E+T)(應(yīng)用產(chǎn)生式2)(E)(T)(應(yīng)用產(chǎn)生式1)E直接推導(dǎo)出E+T或E直接推導(dǎo)出TETF（E）（E+T）（T+T）（F+T）（i+T）（i+F）（i+n),記作E+(i+n)E經(jīng)過多步推導(dǎo)出i+nE*EE*i+(i）E經(jīng)過若干步推導(dǎo)出i+(i）P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第二十頁，共六十五頁，2022年，8月28日與上下文無關(guān)文法有關(guān)的一些概念句型：如果有S*,S是文法的開始符,∈(VTVN)*，則稱是G的句型句子：如果有S+,S是文法的開始符,∈VT*，則稱是G的句子語言：

L(G)={|S+,∈VT*}即文法G的所有句子的集合文法等價：

G1和G2兩個文法,若L(G1)=L(G2),則稱G1和G2等價第二十一頁，共六十五頁，2022年，8月28日例子句型:E,T,E+T,F,T*F,i,n,(E),

…….句子:i,n,(i),(n),i+i,i+n,……

語言:{i,n,(i),(n),i+i,i+n,……}P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第二十二頁，共六十五頁，2022年，8月28日與上下文無關(guān)文法有關(guān)的一些概念最左(右)推導(dǎo)：在推導(dǎo)過程中，總是對當(dāng)前符號串中最左(右)邊的非終極符進行替換，稱為最左(右)推導(dǎo),記為l(r)m規(guī)范推導(dǎo)：最右推導(dǎo)左(右)句型：通過最左(右)推導(dǎo)得到的句型，稱為左(右)句型規(guī)范句型：右句型第二十三頁，共六十五頁，2022年，8月28日例子最左推導(dǎo):i+T*n+Flmi+F*n+F最右推導(dǎo): i+T*n+F

rmi+T*n+i左句型:i+i*F右句型:E+(i)P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第二十四頁，共六十五頁，2022年，8月28日特別注意例如文法G:ND|NDD0|1|2|…|9

NrmNDrm

N8rmND8rm

N98rm

D98rm198,句子198的最右推導(dǎo)

NrmNDNDD,句型NDD不存在最右推導(dǎo)每個句子一定有最右(規(guī)范)推導(dǎo)每個句型不一定有最右(規(guī)范)推導(dǎo)第二十五頁，共六十五頁，2022年，8月28日上下文無關(guān)文法小結(jié)ContextFreeGrammar,CFG(VT,VN,S,P)推導(dǎo)，句型，句子，語言的概念及含義語言與文法第二十六頁，共六十五頁，2022年，8月28日Chomsky文法分類第二十七頁，共六十五頁，2022年，8月28日Chomsky文法分類上下文無關(guān)文法只是文法的一種。文法有很多種。Chomsky將文法分為四類：0型文法：短語文法。產(chǎn)生式：，中至少有一個非終極符。0型語言。1型文法：上下文相關(guān)文法。產(chǎn)生式：A,,可為。1型語言(上下文有關(guān)語言)。2型文法：上下文無關(guān)文法。產(chǎn)生式：A，可為。2型語言(上下文無關(guān)語言)。3型文法：正則文法。產(chǎn)生式：AaB,Aa。3型語言(正則語言)。第二十八頁，共六十五頁，2022年，8月28日Chomsky文法分類描述能力：0型文法〉1型文法〉2型文法〉3型文法對應(yīng)自動機：0型文法對應(yīng)圖靈機1型文法對應(yīng)線性有屆自動機2型文法對應(yīng)下推自動機3型文法對應(yīng)有限自動機第二十九頁，共六十五頁，2022年，8月28日第3章outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯誤處理√√第三十頁，共六十五頁，2022年，8月28日3.3語法分析樹和抽象語法樹問題:推導(dǎo)是從開始符產(chǎn)生句型的一種方法;對同一個句型存在多個推導(dǎo)：NNDNDDND8N98…或N9DN98…

或DDDDD8D98198

或D9DD98198或1DD19D198或1D8198

……

即線性推導(dǎo)不能唯一地表示句子的結(jié)構(gòu)語法分析樹:(SyntaxAnalysisTree)用于表示句型結(jié)構(gòu)的一種較好方法;第三十一頁，共六十五頁，2022年，8月28日例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn句型（句子）:i+i*n該句型存在多個推導(dǎo)：語法分析樹：第三十二頁，共六十五頁，2022年，8月28日語法分析樹語法分析樹是針對某個特定CFG的帶標(biāo)號的樹樹的每個節(jié)點都標(biāo)記一個符號：樹的根節(jié)點標(biāo)記文法的開始符;樹的每個葉子節(jié)點標(biāo)記一個終極符;若有樹的中間節(jié)點標(biāo)記為A,它有n個兒子節(jié)點，從左到右標(biāo)記為B1,……,Bn,則G中定存在產(chǎn)生式AB1…Bn;第三十三頁，共六十五頁，2022年，8月28日抽象語法樹(AST)語法分析樹存在的問題包含很多不必要(對語義分析和代碼生成而言)的節(jié)點抽象語法樹只包含必要的節(jié)點作為語法分析程序輸出句型(句子):i+i*nP:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn第三十四頁，共六十五頁，2022年，8月28日第3章outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯誤處理√√√第三十五頁，共六十五頁，2022年，8月28日3.4二義性文法二義性文法(ambiguousgrammar)

如果文法的一個句子有兩棵或兩棵以上不同的語法分析樹，則稱該句子是二義性的。

包含二義性句子的文法，稱為二義性文法。第三十六頁，共六十五頁，2022年，8月28日二義性文法的例子P:ExpExp+ExpExpExp–ExpExpExp*ExpExpExp/ExpExp(Exp)ExpidExpnumid+id*id第三十七頁，共六十五頁，2022年，8月28日

<Stm>if<Exp>then<Stm>else<Stm> <Stm>if<Exp>then<Stm> <Stm>......假設(shè)有條件語句

ife1thenife2thens1elses2則可有下圖所示的兩棵不同的語法分析樹：

if語句的二義性ififthen<Stm><Stm><Stm><Stm>elsethen<Exp><Exp>e1e2s1s2<Stm><Stm><Stm><Stm>elsethenifthenif<Exp><Exp>e1e2s1s1第三十八頁，共六十五頁，2022年，8月28日二義性文法(ambiguousgrammar)二義性會給語法分析帶來不確定性，應(yīng)盡量避免寫出二義性的文法。但有時用二義性文法定義語法結(jié)構(gòu)更簡單直觀。文法二義性問題是不可判定的，也就是不存在一種算法，能在有限步內(nèi)確切的判定一個文法不是二義性文法。若要證明文法是二義性的，只要舉出一個有兩棵以上語法分析樹的句子即可。若能控制文法的二義性，即加入人為的附加條件，則二義文法的存在并非壞事，有時二義性文法可以簡化文法的表示。消除文法二義性的常用方法

1、規(guī)定符號的優(yōu)先級

2、規(guī)定符號的結(jié)合性第三十九頁，共六十五頁，2022年，8月28日表達式的無二義性文法有二義性的表達式文法:ExpExp+ExpExpExp–ExpExpExp*ExpExpExp/ExpExp(Exp)ExpidExpnum無二義性的表達式的文法：ETEE+T|E-TTFTT*F|T/FF(E)FidFnum第四十頁，共六十五頁，2022年，8月28日If語句的無二義性文法定義

StmtMatched_stmt|Unmatched_stmtMatched_stmtifEthenMatched_stmtelseMatched_stmt|otherUnmatched_stmtifEthenStmt|ifEthenMatched_stmt

elseUnmatched_stmt第四十一頁，共六十五頁，2022年，8月28日第3章outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上下文無關(guān)文法語法分析樹和抽象語法樹二義性文法文法變換算法語法錯誤處理√√√√第四十二頁，共六十五頁，2022年，8月28日文法變換有些語法分析方法要求被分析的文法滿足一定的約束條件，當(dāng)被分析的文法不滿足這些條件時，常常要進行文法變換。文法變換必須保證變換前后的兩個文法G1和G2是等價的，即L(G1)=L(G2)常用文法變換方法增補文法去除空產(chǎn)生式消除無用產(chǎn)生式消除特型產(chǎn)生式消除公共前綴消除左遞歸(直接，間接)第四十三頁，共六十五頁，2022年，8月28日文法變換算法（1）何時需要增補：在自底向上(bottomtoup)的語法分析方法中，要求文法開始符不能出現(xiàn)在產(chǎn)生式的右部.否則，需要對文法進行增補。變換方法：在原產(chǎn)生式基礎(chǔ)上，增加一條產(chǎn)生式：ZS，S為原文法的開始符，Z為增補文法的開始符第四十四頁，共六十五頁，2022年，8月28日文法變換算法（2）文法中空產(chǎn)生式的存在常常給語法分析帶來困難，因此最好將空產(chǎn)生式消除掉。變換依據(jù)：文法G中除了S以外的空產(chǎn)生式(A)可以消除;

變換方法：找出所有可以推導(dǎo)出的非終極符,記為S;對于所有產(chǎn)生式AX1X2……Xi-1XiXi+1……XnXiS增加AX1X2……Xi-1Xi+1……Xn直到?jīng)]有新的產(chǎn)生式產(chǎn)生刪除對應(yīng)空產(chǎn)生式,除了S不可以刪除第四十五頁，共六十五頁，2022年，8月28日消除空產(chǎn)生式的例子S|AaBBABB|aB|bS={S,B,A}ABABB

SaBBSAaBB

SAaBSAaSa

SaB

變換后得到的文法：S|AaBB|aBB|AaB|aB|Aa|aABB|B|aBb第四十六頁，共六十五頁，2022年，8月28日文法變換算法（3）無用產(chǎn)生式:A,A不出現(xiàn)在任何句型中;消除方法：關(guān)鍵是找到這樣的非終極符，how?生成會出現(xiàn)在句型中的非終極符集合SSSS={S}SiSS,Si1,……,Sin把1,……,n中的所有非終極符加入SS中;重復(fù)直到?jīng)]有新的非終極符加入;不屬于SS的非終極符,它們的產(chǎn)生式是無用產(chǎn)生式,刪除掉;第四十七頁，共六十五頁，2022年，8月28日消除無用產(chǎn)生式的例子S|AaBBABB|aB|bCcSS={S}SS={S,A,B}SS={S,A,B}Cc是無用產(chǎn)生式第四十八頁，共六十五頁，2022年，8月28日文法變換算法（4）特型產(chǎn)生式:AB消除算法對每個非終極符A,構(gòu)造SA={B|A+B,BVN}如果CSA,而且C不是特型產(chǎn)生式,則增加A;刪除特型產(chǎn)生式;刪除無用產(chǎn)生式;第四十九頁，共六十五頁，2022年，8月28日消除特型產(chǎn)生式的例子S|AAB|aBbSS={A,B}SA={B}SaSbAbS|a|bAa|bBbSB={}第五十頁，共六十五頁，2022年，8月28日文法變換算法（5）消除公共前綴(leftfactoring)公共前綴A1|…|n|1|…|m提取公因子AA’|1|…|mA’

1|…|n第五十一頁，共六十五頁，2022年，8月28日文法變換算法（6-1）消除左遞歸(leftrecursion)

遞歸分為直接左遞歸和間接左遞歸直接左遞歸:A

A1|…|An|1|…|m消除方法:A1A’|…|mA’A’

1A’|…|nA’|第五十二頁，共六十五頁，2022年，8月28日消除左遞歸的例子P:(1)ET(2)EE+T(3)TF(4)TT*F(5)F(E)(6)Fi(7)Fn

ETE’E’+TE’|

EE+T|T

=+T1=T第五十三頁，共六十五頁，2022年，8月28日文法變換算法（6-2）消除左遞歸(leftrecursion)間接左遞歸:

消除方法:非終極符排序消元法

SAb

ASa|b

1:S2:AAAba|bAbA’A’baA’|第五十四頁，共六十五頁，2022年，8月28日文法變換算法（6-2）消除左遞歸(leftrecursion)間接左遞歸:

消除方法:非終極符排序消元法

SQc|

cQRb|b

RSa|a

1:R2:Q3:SRSa|aQRb|bSab|ab|bSQc|cSabc|abc|bc|cS(abc|bc|c)S’S’abcS’|第五十五頁，共六十五頁，2022年，8月28日文法變換算法（6-2）消除左遞歸(leftrecursion)間接左遞歸:

排序不同，變換后文法也不同

SQc|

cQRb|b

RSa|a

1:S2:Q3:RSQc|cQRb|bRSa|a(Qc|c)a|aQca|ca|a

(Rb|b)ca|ca|a

SQc|cQRb|bR(bca|ca|a)R’R’bcaR’|第五十六頁，共六十五頁，2022年，8月28日第3章outline語法分析概述1.功能需求(輸入，輸出，主要功能)2.分析算法+數(shù)據(jù)結(jié)構(gòu)3.構(gòu)造語法分析器的通用過程上