程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述.ppt

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

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