《程序設(shè)計語言的語法描述.ppt》由會員分享，可在線閱讀，更多相關(guān)《程序設(shè)計語言的語法描述.ppt（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019/12/16,第3章程序設(shè)計語言的語法描述,3.1文法的引入3.2上下文無關(guān)文法3.3文法舉例（略）,使用文法對程序設(shè)計語言的結(jié)構(gòu)進(jìn)行定義和描述。,2019/12/16,3.1文法的引入,先討論自然語言的文法。例：thebigelephentateabanana㈠語法樹根據(jù)英語的語法，上述句子的語法結(jié)構(gòu)可用圖（語法樹）表示如下：,,,非葉結(jié)點稱為語法單位，在形式語言中稱為非終結(jié)符。處于根結(jié)點位置的結(jié)點又稱為開始符號。葉結(jié)點稱為單詞符號，在形式語言中稱為終結(jié)符。,,2019/12/16,㈡規(guī)則可以通過建立一組規(guī)則，來描述上述句子的語法結(jié)構(gòu)，規(guī)則在形式語言中稱為產(chǎn)生式。,→→→the|a→big→elephant|banana→→→ate,㈢由規(guī)則推導(dǎo)句子可用規(guī)則來推導(dǎo)出句子。從開始符號出發(fā)，若能從規(guī)則推導(dǎo)出某符號串，則該符號串就是該文法的合法的句子，反之語法錯誤。,上述英文句子可用下述規(guī)則來描述：,2019/12/16,thethebigthebigelephantthebigelephantthebigelephantatethebigelephantatethebigelephantateathebigelephantateabanana上述推導(dǎo)可簡單表示為：thebigelephantateabanana。值得注意的是用上述規(guī)則可推導(dǎo)出多個句子，因存在推導(dǎo)abigbananaatetheelephant所以，abigbananaatetheelephant也是文法的一個合法的句子。但意義是荒謬的，也就是說句子的語義是錯誤的。一個語法正確的句子不能保證其語義是正確的，故一個句子是否正確，需要進(jìn)行語法和語義兩方面檢查。綜上所述，語言結(jié)構(gòu)通常是用文法來定義和描述，文法是由終結(jié)符、非終結(jié)符、開始符號（特殊非終結(jié)符）及產(chǎn)生式四個要素構(gòu)成。從開始符號出發(fā)，根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱為文法所規(guī)定的語言,2019/12/16,㈣遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中的一個重要概念。①遞歸定義：定義某事物，又用到該事物本身。②遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。例：U→xUy，通常用大寫字母表示非終結(jié)符，用小寫字母表示終結(jié)符。⑴左遞歸規(guī)則：x=ε，U→Uy（ε表示空串）⑵右遞歸規(guī)則：y=ε，U→xU③間接遞歸：由規(guī)則推導(dǎo)產(chǎn)生。例：V→Uy|Z，U→xV因存在推導(dǎo)VUyxVy，故存在間接遞歸。⑴間接左遞歸：若x=ε，則VVy。⑵間接右遞歸：若y=ε，則VxU。④遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱為遞歸文法。利用遞歸文法，可以用有窮的規(guī)則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法檢查成為可能。,2019/12/16,3.2上下文無關(guān)文法,形式語言的奠基人喬姆斯基（Chomsky）將文法分為4種類型，它們是：短語文法（0型文法）上下文有關(guān)文法（1型文法）上下文無關(guān)文法（2型文法）正規(guī)文法（3型文法）這四種文法在形式語言中都有嚴(yán)格的定義。但對于程序設(shè)計語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計語言的語法結(jié)構(gòu)。以后，“文法”一詞若無特別說明，則指“上下文無關(guān)文法”。,2019/12/16,,㈠文法和語言一個文法G是一個四元式(VT,VN,S,P)，其中VT是一個終結(jié)符的非空有限集，終結(jié)符通常用小寫字母表示。VN是一個非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母表示。S是一個特殊的非終結(jié)符（S∈VN），稱為開始符號。P是一個產(chǎn)生式（規(guī)則）的有限集合，每個產(chǎn)生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。,①終結(jié)符是語言的基本符號，即程序設(shè)計語言的單詞。語法分析時，終結(jié)符用單詞的種別表示。根據(jù)前面約定：標(biāo)識符（簡單變量）：i無符號整常數(shù)：x無符號實常數(shù)：y單字符單詞：用單詞本身表示（例單詞“+”的種別用+表示）多字符單詞：需特別指定（例“++”用$表示）,2019/12/16,②非終結(jié)符表示抽象的語法單位.例“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值語句”、“說明語句”和“程序”等。非終結(jié)符通常用大寫字母表示，也可以用帶尖括號的漢字表示。③開始符號是一個特殊的非終結(jié)符，它代表我們最感興趣的語法單位。例如討論算術(shù)表達(dá)式，那么描述算術(shù)表達(dá)式文法的開始符號就是。在程序設(shè)計語言中，我們最感興趣的語法單位是“程序”。④產(chǎn)生式是定義語法單位的一種書寫規(guī)則。上下文無關(guān)文法產(chǎn)生式的左部必定是一個非終結(jié)符，該非終結(jié)符稱為左部符號。產(chǎn)生式的右部是終結(jié)符和非終結(jié)符經(jīng)有限次連接構(gòu)成的文法符號串，可以是空字ε。四種文法的區(qū)別主要是對產(chǎn)生式的左部和右部的限制不同。若干個左部符號相同的產(chǎn)生式，可合并為一個，例：A→α1|α2|……|αn，其中αi稱為A的候選式(1≤i≤n)。,2019/12/16,例1：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中VT={+,-,*,/,i,x,y,(,)}VN={,,}S=P={→+→-→→*→/→→()→i//標(biāo)識符→x//無符號整常數(shù)→y//無符號實常數(shù)}根據(jù)上述文法，可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。,2019/12/16,因已約定非終結(jié)符和終結(jié)符的書寫方式，非終結(jié)符和終結(jié)符在產(chǎn)生式中一目了然，故終結(jié)符集VT和非終結(jié)符集VN無需再顯式列出。若規(guī)定左部符號為開始符號的產(chǎn)生式寫在所定義文法的第一行，上述文法G又可簡單表示為如下形式：→+→-→→*→/→→()→i→x→y若用E表示、T表示、F表示，借助符號|，算術(shù)表達(dá)式文法G可表示成如下最簡形式：E→E+T︱E–T︱TT→T*F︱T/F︱FF→(E)︱i︱x︱y,2019/12/16,例2：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中VT={+,-,*,/,i,x,y,(,)}VN={P={→+→-→*→/→()→i//標(biāo)識符→x//無符號整常數(shù)→y//無符號實常數(shù)}根據(jù)上述文法，同樣可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。用E表示，上述文法可簡記為：E→E+E|E-E|E*E|E/E|(E)|i|x|y,2019/12/16,㈡基本術(shù)語以文法G：E→E+E|E*E|(E)|i為例，進(jìn)行下述討論。①直接推出和直接歸約②推導(dǎo)和歸約若α1α2…αn，則稱該直接推出序列是從α1到αn的一個推導(dǎo)，記作α1αn或ααn。α1αn：從α1始，經(jīng)一步或一步以上可推導(dǎo)出αn。α1αn：從α1始，經(jīng)０步或０步以上可推導(dǎo)出αn，即α1αn或α1=αn。也可稱直接歸約序列αn,αn-1,…,α1為αn到α1的一個歸約。③句型若存在推導(dǎo)Sα（S為文法的開始符號），則稱α是文法的一個句型。④句子僅包含終結(jié)符的句型稱為句子。,2019/12/16,⑤語言文法Ｇ所能推導(dǎo)出的句子全體稱為該文法的語言，記為：L(G)={α|(Sα)∧(α∈VT*)}⑥等價文法Ｇ1和Ｇ2是二個不同的文法，若L(G1)=L(G2)，則稱G1和G2是等價文法。等價文法的存在，使我們能夠在不改變文法所規(guī)定的語言的前提下，為了某種目的改造文法。⑦最左推導(dǎo)和最右推導(dǎo)在各種推導(dǎo)中，考慮今后語法分析的需要，我們僅對兩種推導(dǎo)感興趣。1）最左推導(dǎo)在推導(dǎo)過程中始終對最左面的非終結(jié)符進(jìn)行替換，記為。2）最右推導(dǎo)在推導(dǎo)過程中始終對最右面的非終結(jié)符進(jìn)行替換，記為。,2019/12/16,㈢文法的二義性①語法樹我們可以用一個有向圖表示一個句型的推導(dǎo)，這種表示稱為語法樹。語法樹有助于理解一個句子語法結(jié)構(gòu)的層次。在一般情況下，某一句型不論其推導(dǎo)過程如何，其最終形成的語法樹是相同的，故語法樹是不同推導(dǎo)過程的共性抽象。若僅進(jìn)行最左（右）推導(dǎo)，則語法樹和最左（右）推導(dǎo)等價。②二義文法若一個文法所產(chǎn)生的語言中，只要存在一個句子，它有二個最左推導(dǎo)，或有二個最右推導(dǎo)，或句子的推導(dǎo)對應(yīng)兩棵語法樹，則稱該文法為二義文法。③二義文法的利用和處理1)根據(jù)條件修改文法，語言不變。算符優(yōu)先性：規(guī)定*優(yōu)先于+，i+i*i等價于i+(i*i)。算符結(jié)合性：規(guī)定同級運(yùn)算服從左結(jié)合，i+i+i等價于(i+i)+i。2)根據(jù)條件修改編譯程序的語法分析表，文法保持不變（詳見第四、五章）。,2019/12/16,1）根據(jù)條件修改文法，語言不變。算符優(yōu)先性：規(guī)定*優(yōu)先于+，i+i*i等價于i+(i*i)。算符結(jié)合性：規(guī)定同級運(yùn)算服從左結(jié)合，i+i+i等價于(i+i)+i。例文法GG：E→E+E|E*E|(E)|i是一個二義文法。根據(jù)上述條件將文法G修改成G’，如下所示G：E→E+T|TT→T*F|FF→(E)|i顯然G‘不是二義文法，但L(G)=L(G’)，故G和G‘等價。例句子i+i*i的最右推導(dǎo)：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*F?+?*?…先形成+，才有可能形成*。若先形成*，只有帶括號才可能形成+。,2019/12/16,2）根據(jù)條件修改編譯程序的語法分析表，文法保持不變。例文法G：→if標(biāo)識符thenelseS→fitSeS→if標(biāo)識符thenS→fitS→標(biāo)識符=S→i=E→無符號整常數(shù)E→x程序段a=2ifxthenifythena=4elsea=6相應(yīng)的語法結(jié)構(gòu)表示為i=xfitfiti=xei=x句子fitfiti=xei=x的最左推導(dǎo)序列有二個，如下所示：SfitSeSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efitfiti=xei=xSfitSfitfitSeSfitfiti=EeSfitfiti=xeSfitfiti=xei=Efifii=xei=x因句子fitfiti=xei=x存在二個最左推導(dǎo)，故文法G為二義文法。,2019/12/16,這樣對于該程序段有二個解釋：假設(shè)else和最近的if結(jié)合，即a=2ifxthenbeginifythena=4elsea=6end,當(dāng)x和y為下列值時，相應(yīng)a的值為：,假設(shè)else和最遠(yuǎn)的if結(jié)合，即a=2ifxthenbeginifythena=4endelsea=6,實際的編譯程序不可能、也不允許有兩種解釋，通常按第一種方式進(jìn)行翻譯執(zhí)行，即“else和最近的if結(jié)合”。,2019/12/16,結(jié)束,