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

PAGE第1頁(yè)共4頁(yè)第3章程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述（Tsu版電子教案）第3章程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述文法：對(duì)語(yǔ)言結(jié)構(gòu)的定義和描述。3.1文法的引入先討論自然語(yǔ)言的文法。例：thebigelephentateabanana㈠語(yǔ)法樹(shù)根據(jù)英語(yǔ)的語(yǔ)法，上述句子的語(yǔ)法結(jié)構(gòu)可用圖（語(yǔ)法樹(shù)）表示如下：<句子><主語(yǔ)><謂語(yǔ)><冠詞><形容詞><名詞><動(dòng)詞><直接賓語(yǔ)>thebigelephant ate<冠詞><名詞> abanana①非葉結(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é)符。㈡規(guī)則可以通過(guò)建立一組規(guī)則，來(lái)描述上述句子的語(yǔ)法結(jié)構(gòu)，規(guī)則在形式語(yǔ)言中稱(chēng)為產(chǎn)生式。上述英文句子可用下述規(guī)則來(lái)描述：<句子>→<主語(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ò)誤。 <句子><主語(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)<句子>thebigbananaateanelephant故thebigbananaateanelephant也是文法的一個(gè)合法的句子。但意義是荒謬的，也就是說(shuō)句子的語(yǔ)義是錯(cuò)誤的。一個(gè)語(yǔ)法正確的句子不能保證其語(yǔ)義是正確的，故一個(gè)句子是否正確，需要進(jìn)行語(yǔ)法和語(yǔ)義兩方面檢查。㈣遞歸規(guī)則和遞歸文法=1\*GB3①遞歸定義=2\*GB3②遞歸規(guī)則（直接遞歸）=3\*GB3③間接遞歸=4\*GB3④遞歸文法利用遞歸文法我們可以用有窮的規(guī)則來(lái)描述無(wú)窮的語(yǔ)言，這不但解決了語(yǔ)言的定義問(wèn)題，而且使得對(duì)語(yǔ)言的語(yǔ)法檢查成為可能。例：定義無(wú)符號(hào)整數(shù)。=1\*GB3①不采用遞歸規(guī)則，描述無(wú)符號(hào)整數(shù)全體就要使用無(wú)窮多條的規(guī)則。 <無(wú)符號(hào)整數(shù)>→<數(shù)字>|<數(shù)字><數(shù)字>|<數(shù)字><數(shù)字><數(shù)字>|…<數(shù)字>→0|1|2|3|4|5|6|7|8|9|0=2\*GB3②采用遞歸規(guī)則，描述無(wú)符號(hào)整數(shù)全體僅需12條規(guī)則。 <無(wú)符號(hào)整數(shù)>→<無(wú)符號(hào)整數(shù)><數(shù)字>|<數(shù)字> N→ND|D <數(shù)字>→0|1|2|3|4|5|6|7|8|9|0 D→0|1|2|3|4|5|6|7|8|9|0例1：無(wú)符號(hào)整數(shù)1 ND1例2：無(wú)符號(hào)整數(shù)23 NNDDD2D23例3：無(wú)符號(hào)整數(shù)456 NNDNDDDDD4DD45D4563.2 上下文無(wú)關(guān)文法形式語(yǔ)言的奠基人喬姆斯基將文法分為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)文法”。㈠文法和語(yǔ)言 一個(gè)文法G是一個(gè)四元式(VT,VN,S,VP)，其中VT是一個(gè)終結(jié)符的非空有限集，終結(jié)符通常用小寫(xiě)字母表示。VN是一個(gè)非終結(jié)符的非空有限集，非終結(jié)符通常用大寫(xiě)字母表示。S是一個(gè)特殊的非終結(jié)符（S∈VN），稱(chēng)為開(kāi)始符號(hào)。VP是一個(gè)產(chǎn)生式（規(guī)則）的有限集合，每個(gè)產(chǎn)生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。例：G=（VT，VN，S，VP） VT={+，*，(，)，i} VN={E} S=E VP={E→E+E，E→E*E，E→(E)，E→i}可簡(jiǎn)記為： G：E→E+E|E*E|(E)|i根據(jù)上述文法，可推導(dǎo)出任何僅包含加乘的算術(shù)表達(dá)式。㈡基本術(shù)語(yǔ)①直接推出和直接歸約②推導(dǎo)和歸約③句型④句子⑤語(yǔ)言⑥等價(jià)文法⑦最左推導(dǎo)和最右推導(dǎo)㈢文法的二義性①語(yǔ)法樹(shù)我們可以用一個(gè)有向圖表示一個(gè)句型的推導(dǎo)，這種表示稱(chēng)為語(yǔ)法樹(shù)。在一般情況下，某一句型不論其推導(dǎo)過(guò)程如何，其最終形成的語(yǔ)法樹(shù)是相同的，故語(yǔ)法樹(shù)是不同推導(dǎo)過(guò)程的共性抽象。若僅進(jìn)行最左（右）推導(dǎo)，則語(yǔ)法樹(shù)和最左（右）推導(dǎo)等價(jià)。②二義文法某些文法的句型的推導(dǎo)可能對(duì)應(yīng)一棵以上的語(yǔ)法樹(shù)，或存在一個(gè)以上的最左（右）推導(dǎo)。

例：已知文法G：E→E+E|E*E|(E)|i和句子i+i*i，該句子存在二個(gè)最左（右）推導(dǎo)，即二棵語(yǔ)法樹(shù)。語(yǔ)法樹(shù)1（先形成+后形成*） E E + E E * E i i i語(yǔ)法樹(shù)2（先形成*后形成+） E E * E i E + E i i句子i+i*i的二個(gè)最左推導(dǎo)序列：EE+Ei+Ei+E*Ei+i*Ei+i*iEE*EE+E*Ei+E*Ei+i*Ei+i*i句子i+i*i的二個(gè)最右推導(dǎo)序列：EE+EE+E*EE+E*iE+i*ii+i*i EE*EE