第3章 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述

1第3章程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述3.1

文法的引入3.2

上下文無(wú)關(guān)文法3.3文法舉例（略）

使用文法對(duì)程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)進(jìn)行定義和描述。23.1文法的引入

先討論自然語(yǔ)言的文法。例：thebigelephentateabanana㈠語(yǔ)法樹(shù)根據(jù)英語(yǔ)的語(yǔ)法，上述句子的語(yǔ)法結(jié)構(gòu)可用圖（語(yǔ)法樹(shù)）表示如下：非葉結(jié)點(diǎn)稱(chēng)為語(yǔ)法單位，在形式語(yǔ)言中稱(chēng)為非終結(jié)符。處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱(chēng)為開(kāi)始符號(hào)。葉結(jié)點(diǎn)稱(chēng)為單詞符號(hào)，在形式語(yǔ)言中稱(chēng)為終結(jié)符。3㈡規(guī)則可以通過(guò)建立一組規(guī)則，來(lái)描述上述句子的語(yǔ)法結(jié)構(gòu)，規(guī)則在形式語(yǔ)言中稱(chēng)為產(chǎn)生式。<句子>→<主語(yǔ)><謂語(yǔ)> <主語(yǔ)>→<冠詞><形容詞><名詞><冠詞>→the|a<形容詞>→big<名詞>→elephant|banana<謂語(yǔ)>→<動(dòng)詞><直接賓語(yǔ)><直接賓語(yǔ)>→<冠詞><名詞><動(dòng)詞>→ate㈢由規(guī)則推導(dǎo)句子可用規(guī)則來(lái)推導(dǎo)出句子。從開(kāi)始符號(hào)出發(fā)，若能從規(guī)則推導(dǎo)出某符號(hào)串，則該符號(hào)串就是該文法的合法的句子，反之語(yǔ)法錯(cuò)誤。上述英文句子可用下述規(guī)則來(lái)描述：4 <句子><主語(yǔ)><謂語(yǔ)> <冠詞><形容詞><名詞><謂語(yǔ)> the<形容詞><名詞><謂語(yǔ)> thebig<名詞><謂語(yǔ)> thebigelephant<謂語(yǔ)> thebigelephant<動(dòng)詞><直接賓語(yǔ)> thebigelephantate<直接賓語(yǔ)> thebigelephantate<冠詞><名詞> thebigelephantatea<名詞> thebigelephantateabanana

上述推導(dǎo)可簡(jiǎn)單表示為：

<句子>thebigelephantateabanana。值得注意的是用上述規(guī)則可推導(dǎo)出多個(gè)句子，因存在推導(dǎo)

<句子>abigbananaatetheelephant

所以，abigbananaatetheelephant也是文法的一個(gè)合法的句子。但意義是荒謬的，也就是說(shuō)句子的語(yǔ)義是錯(cuò)誤的。一個(gè)語(yǔ)法正確的句子不能保證其語(yǔ)義是正確的，故一個(gè)句子是否正確，需要進(jìn)行語(yǔ)法和語(yǔ)義兩方面檢查。綜上所述，語(yǔ)言結(jié)構(gòu)通常是用文法來(lái)定義和描述，文法是由終結(jié)符、非終結(jié)符、開(kāi)始符號(hào)（特殊非終結(jié)符）及產(chǎn)生式四個(gè)要素構(gòu)成。從開(kāi)始符號(hào)出發(fā)，根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱(chēng)為文法所規(guī)定的語(yǔ)言5㈣遞歸規(guī)則和遞歸文法遞歸是編譯技術(shù)中的一個(gè)重要概念。①遞歸定義：定義某事物，又用到該事物本身。②遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。例：U→xUy，通常用大寫(xiě)字母表示非終結(jié)符，用小寫(xiě)字母表示終結(jié)符。 ⑴左遞歸規(guī)則：x=ε，U→Uy（ε表示空串） ⑵右遞歸規(guī)則：y=ε，U→xU③間接遞歸：由規(guī)則推導(dǎo)產(chǎn)生。例：V→Uy|Z，U→xV

因存在推導(dǎo)VUyxVy，故存在間接遞歸。 ⑴間接左遞歸：若x=ε，則VVy。 ⑵間接右遞歸：若y=ε，則VxU。④遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱(chēng)為遞歸文法。利用遞歸文法，可以用有窮的規(guī)則來(lái)描述無(wú)窮的語(yǔ)言，這不但解決了語(yǔ)言的定義問(wèn)題，而且使得對(duì)語(yǔ)言的語(yǔ)法檢查成為可能。63.2 上下文無(wú)關(guān)文法

形式語(yǔ)言的奠基人喬姆斯基（Chomsky）將文法分為4種類(lèi)型，它們是：短語(yǔ)文法（0型文法）上下文有關(guān)文法（1型文法）上下文無(wú)關(guān)文法（2型文法）正規(guī)文法（3型文法）這四種文法在形式語(yǔ)言中都有嚴(yán)格的定義。但對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，上下文無(wú)關(guān)文法已經(jīng)夠用了，上下文無(wú)關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)。以后，“文法”一詞若無(wú)特別說(shuō)明，則指“上下文無(wú)關(guān)文法”。7㈠文法和語(yǔ)言一個(gè)文法G是一個(gè)四元式(VT,VN,S,P)，其中VT是一個(gè)終結(jié)符的非空有限集，終結(jié)符通常用小寫(xiě)字母表示。VN是一個(gè)非終結(jié)符的非空有限集，非終結(jié)符通常用大寫(xiě)字母表示。S是一個(gè)特殊的非終結(jié)符（S∈VN），稱(chēng)為開(kāi)始符號(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

無(wú)符號(hào)整常數(shù)： x

無(wú)符號(hào)實(shí)常數(shù)： y

單字符單詞： 用單詞本身表示（例單詞“+”的 種別用+表示） 多字符單詞： 需特別指定（例“++”用$表示）8②非終結(jié)符表示抽象的語(yǔ)法單位.

例“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值語(yǔ)句”、“說(shuō)明語(yǔ)句”和“程序”等。非終結(jié)符通常用大寫(xiě)字母表示，也可以用帶尖括號(hào)的漢字表示。③開(kāi)始符號(hào)是一個(gè)特殊的非終結(jié)符，它代表我們最感興趣的語(yǔ)法單位。例如討論算術(shù)表達(dá)式，那么描述算術(shù)表達(dá)式文法的開(kāi)始符號(hào)就是<算術(shù)表達(dá)式>。在程序設(shè)計(jì)語(yǔ)言中，我們最感興趣的語(yǔ)法單位是<程序>。④產(chǎn)生式是定義語(yǔ)法單位的一種書(shū)寫(xiě)規(guī)則。上下文無(wú)關(guān)文法產(chǎn)生式的左部必定是一個(gè)非終結(jié)符，該非終結(jié)符稱(chēng)為左部符號(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稱(chēng)為A的候選式(1≤i≤n)。9

例1：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中

VT={+,-,*,/,i,x,y,(,)} VN={<算術(shù)表達(dá)式>,<項(xiàng)>,<因子>} S=<算術(shù)表達(dá)式> P={ <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)> <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>-<項(xiàng)> <算術(shù)表達(dá)式>→<項(xiàng)> <項(xiàng)>→<項(xiàng)>*<因子> <項(xiàng)>→<項(xiàng)>/<因子> <項(xiàng)>→<因子> <因子>→(<算術(shù)表達(dá)式>) <因子>→i //標(biāo)識(shí)符

<因子>→x //無(wú)符號(hào)整常數(shù)

<因子>→y //無(wú)符號(hào)實(shí)常數(shù)

}

根據(jù)上述文法，可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。10

因已約定非終結(jié)符和終結(jié)符的書(shū)寫(xiě)方式，非終結(jié)符和終結(jié)符在產(chǎn)生式中一目了然，故終結(jié)符集VT和非終結(jié)符集VN無(wú)需再顯式列出。若規(guī)定左部符號(hào)為開(kāi)始符號(hào)的產(chǎn)生式寫(xiě)在所定義文法的第一行，上述文法G又可簡(jiǎn)單表示為如下形式：

<算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<項(xiàng)> <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>-<項(xiàng)> <算術(shù)表達(dá)式>→<項(xiàng)> <項(xiàng)>→<項(xiàng)>*<因子> <項(xiàng)>→<項(xiàng)>/<因子> <項(xiàng)>→<因子> <因子>→(<算術(shù)表達(dá)式>) <因子>→i <因子>→x <因子>→y

若用E表示<算術(shù)表達(dá)式>、T表示<項(xiàng)>、F表示<因子>，借助符號(hào)'|'，算術(shù)表達(dá)式文法G可表示成如下最簡(jiǎn)形式：

E→E+T︱E–T︱T T→T*F︱T/F︱F F→(E)︱i︱x︱y11

例2：描述算術(shù)表達(dá)式文法G=(VT,VN,S,P)，其中

VT={+,-,*,/,i,x,y,(,)} VN={<算術(shù)表達(dá)式} S=<算術(shù)表達(dá)式> P={ <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>+<算術(shù)表達(dá)式> <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>-<算術(shù)表達(dá)式> <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>*<算術(shù)表達(dá)式> <算術(shù)表達(dá)式>→<算術(shù)表達(dá)式>/<算術(shù)表達(dá)式> <算術(shù)表達(dá)式>→(<算術(shù)表達(dá)式>) <算術(shù)表達(dá)式>→i //標(biāo)識(shí)符

<算術(shù)表達(dá)式>→x //無(wú)符號(hào)整常數(shù)

<算術(shù)表達(dá)式>→y //無(wú)符號(hào)實(shí)常數(shù)

}

根據(jù)上述文法，同樣可推導(dǎo)出任何僅包含加減乘除的算術(shù)表達(dá)式。用E表示<算術(shù)表達(dá)式>，上述文法可簡(jiǎn)記為：

E→E+E|E-E|E*E|E/E|(E)|i|x|y12㈡基本術(shù)語(yǔ)以文法G：

E→E+E|E*E|(E)|i為例，進(jìn)行下述討論。①直接推出和直接歸約②推導(dǎo)和歸約若α1α2…αn，則稱(chēng)該直接推出序列是從α1到αn的一個(gè)推導(dǎo)，記作α1αn或α1αn。

α1αn：從α1始，經(jīng)一步或一步以上可推導(dǎo)出αn。

α1αn：從α1始，經(jīng)０步或０步以上可推導(dǎo)出αn，即 α1αn或α1=αn。也可稱(chēng)直接歸約序列αn,αn-1,…,α1為αn到α1的一個(gè)歸約。③句型若存在推導(dǎo)Sα（S為文法的開(kāi)始符號(hào)），則稱(chēng)α是文法的一個(gè)句型。④句子僅包含終結(jié)符的句型稱(chēng)為句子。13⑤語(yǔ)言文法Ｇ所能推導(dǎo)出的句子全體稱(chēng)為該文法的語(yǔ)言，記為：

L(G)={α|(Sα)∧(α∈VT*)}⑥等價(jià)文法Ｇ1和Ｇ2是二個(gè)不同的文法，若L(G1)=L(G2)，則稱(chēng)G1和G2是等價(jià)文法。等價(jià)文法的存在，使我們能夠在不改變文法所規(guī)定的語(yǔ)言的前提下，為了某種目的改造文法。⑦最左推導(dǎo)和最右推導(dǎo)在各種推導(dǎo)中，考慮今后語(yǔ)法分析的需要，我們僅對(duì)兩種推導(dǎo)感興趣。1）最左推導(dǎo)在推導(dǎo)過(guò)程中始終對(duì)最左面的非終結(jié)符進(jìn)行替換，記為。2）最右推導(dǎo)在推導(dǎo)過(guò)程中始終對(duì)最右面的非終結(jié)符進(jìn)行替換，記為。14㈢文法的二義性①語(yǔ)法樹(shù)我們可以用一個(gè)有向圖表示一個(gè)句型的推導(dǎo)，這種表示稱(chēng)為語(yǔ)法樹(shù)。語(yǔ)法樹(shù)有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次。在一般情況下，某一句型不論其推導(dǎo)過(guò)程如何，其最終形成的語(yǔ)法樹(shù)是相同的，故語(yǔ)法樹(shù)是不同推導(dǎo)過(guò)程的共性抽象。若僅進(jìn)行最左（右）推導(dǎo)，則語(yǔ)法樹(shù)和最左（右）推導(dǎo)等價(jià)。②二義文法若一個(gè)文法所產(chǎn)生的語(yǔ)言中，只要存在一個(gè)句子，它有二個(gè)最左推導(dǎo)，或有二個(gè)最右推導(dǎo)，或句子的推導(dǎo)對(duì)應(yīng)兩棵語(yǔ)法樹(shù)，則稱(chēng)該文法為二義文法。③二義文法的利用和處理

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ǔ)法分析表，文法保持不變（詳見(jiàn)第四、五章）。151）根據(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)：

EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*F?+?*?…先形成+，才有可能形成*。若先形成*，只有帶括號(hào)才可能形成+。162）根據(jù)條件修改編譯程序的語(yǔ)法分析表，文法保持不變。例文法G：

<語(yǔ)句>→if

標(biāo)識(shí)符

then<語(yǔ)句>else<語(yǔ)句> S→fitSeS<語(yǔ)句>→if

標(biāo)識(shí)符

then<語(yǔ)句> S→fitS<語(yǔ)句>→標(biāo)識(shí)符=<算術(shù)表達(dá)式> S→i=E<算術(shù)表達(dá)式>→無(wú)符號(hào)整常數(shù)

E→x程序段

a=2 ifxthenifythena=4elsea=6相應(yīng)的語(yǔ)法結(jié)構(gòu)表示為

i=x fitfiti=xei=x句子fitf