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

1、第3章 程序設(shè)計語言的語法描述,3.1 文法的引入,文法：對語言結(jié)構(gòu)的定義和描述。 先討論自然語言的文法。例： the big elephent ate a banana,3.1 文法的引入,語法樹 根據(jù)英語的語法，上述句子的語法結(jié)構(gòu)可用圖（語法樹）表示如下：,3.1 文法的引入,3.1 文法的引入,非葉結(jié)點(diǎn)稱為語法單位，在形式語言中稱為非終結(jié)符。 處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱為開始符號。 葉結(jié)點(diǎn)稱為單詞符號，在形式語言中稱為終結(jié)符。,3.1 文法的引入,規(guī)則 可以通過建立一組規(guī)則，來描述上述句子的語法結(jié)構(gòu)，規(guī)則在形式語言中稱為產(chǎn)生式。上述英文句子可用下述規(guī)則來描述：,3.1 文法的引入,1. 2

2、. 3. the| a 4. big 5. elephant| banana 6. 7. 8. ate,3.1 文法的引入,由規(guī)則推導(dǎo)句子 可用規(guī)則來推導(dǎo)出句子。從開始符號出發(fā)，若能從規(guī)則推導(dǎo)出某符號串，則該符號串就是該文法的合法的句子，反之語法錯誤。,3.1 文法的引入, the the big the big elephant the big elephant the big elephant ate the big elephant ate the big elephant ate a the big elephant ate a banana,3.1 文法的引入,上述推導(dǎo)可簡單表示為：

3、 the big elephant ate a banana。,3.1 文法的引入,值得注意的是用上述規(guī)則可推導(dǎo)出多個句子，因存在推導(dǎo) the big banana ate an elephant 故the big banana ate an elephant也是文法的一個合法的句子。但意義是荒謬的，也就是說句子的語義是錯誤的。 一個語法正確的句子不能保證其語義是正確的，故一個句子是否正確，需要進(jìn)行語法和語義兩方面檢查。,3.1 文法的引入,遞歸規(guī)則和遞歸文法 遞歸定義 定義某事物，又用到某事物。 在規(guī)則的左部和右部有相同的非終結(jié)符 U xUy U為非終結(jié)符，xy為終結(jié)符。,3.1 文法的引入

4、,遞歸規(guī)則和遞歸文法 遞歸規(guī)則（直接遞歸） 在產(chǎn)生式的左部和右部都含有非終結(jié)符U，故U xUy是遞歸規(guī)則。 若x= , U Uy稱為左遞歸規(guī)則， 若y= ，U xU稱為右遞歸規(guī)則。,3.1 文法的引入,遞歸規(guī)則和遞歸文法 間接遞歸 文法的遞歸性還可以在推導(dǎo)過程中由規(guī)則間接產(chǎn)生： V Uy|z, U xV 上述規(guī)則不是遞歸規(guī)則，但存在推導(dǎo)VUy xVy,即V xVy，稱文法含有間接遞歸。,3.1 文法的引入,遞歸規(guī)則和遞歸文法 遞歸文法 含有遞歸規(guī)則或間接遞歸的文法稱為遞歸文法,3.1 文法的引入,利用遞歸文法我們可以用有窮的規(guī)則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法

5、檢查成為可能。,3.1 文法的引入,例：定義無符號整數(shù)。 不采用遞歸規(guī)則，描述無符號整數(shù)全體就要使用無窮多條的規(guī)則。 | 0|1|2|3|4|5|6|7|8|9|0 采用遞歸規(guī)則，描述無符號整數(shù)全體僅需12條規(guī)則。 |NND|D 0|1|2|3|4|5|6|7|8|9|0D0|1|2|3|4|5|6|7|8|9|0,3.1 文法的引入,例1：無符號整數(shù)1 N D 1 例2：無符號整數(shù)23 N ND DD 2D 23 例3：無符號整數(shù)456 N ND NDD DDD 4DD 45D 456,3.2上下文無關(guān)文法,文法是描述語言結(jié)構(gòu)的形式規(guī)則（語法規(guī)則），這些規(guī)則必須是準(zhǔn)確的，易于理解的，應(yīng)當(dāng)有較

6、強(qiáng)的描述能力，足以描述各種不同的結(jié)構(gòu),3.2上下文無關(guān)文法,形式語言的奠基人喬姆斯基將文法分為4種類型，它們是： l 短語文法（0型文法） l 上下文有關(guān)文法（1型文法） l 上下文無關(guān)文法（2型文法） l 正規(guī)文法（3型文法） 這四種文法在形式語言中都有嚴(yán)格的定義。但對于程序設(shè)計語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計語言的語法結(jié)構(gòu)。以后，“文法”一詞若無特別說明，則指“上下文無關(guān)文法”。,3.2上下文無關(guān)文法,上下文無關(guān)文法所定義的語法單位和該語法單位可能出現(xiàn)的環(huán)境無關(guān)。 自然語言中，一個句子或一個字，其意義和它們所處的上下文有密切關(guān)系，因

7、此上下文無關(guān)文法不適合描述自然語言。,3.2上下文無關(guān)文法,文法和語言 一個文法G是一個四元式(VT,VN,S,VP)，其中 l VT是一個終結(jié)符的非空有限集，終結(jié)符通常用小寫字母表示。 l VN是一個非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母表示。 l S是一個特殊的非終結(jié)符（SVN），稱為開始符號。 l VP是一個產(chǎn)生式（規(guī)則）的有限集合，每個產(chǎn)生式的形式是A ，其中AVN，(VTVN)*。,3.2上下文無關(guān)文法,終結(jié)符是語言的基本符號，就是源程序中的單詞，是語言不可分割的最小單位。 單詞經(jīng)過詞法分析后，語法分析只使用單詞二元式的種別code。 語法分析關(guān)心的是：單詞是標(biāo)識符還是常數(shù)，不

8、考慮是哪個標(biāo)識符，常數(shù)是多少。,3.2上下文無關(guān)文法,因此，終結(jié)符用單詞的種別表示。 i 表示標(biāo)識符 x 表示整形或?qū)嵭巫兞?y 表示無符號實(shí)常數(shù) 單字符單詞種別與單詞本身相同+ 基本字借用原單詞形式,3.2上下文無關(guān)文法,非終結(jié)符用來表示抽象的語法單位，算術(shù)表達(dá)式，賦值語句，說明語句，程序。 通常用大寫字母表示，也用表示 開始符號是特殊的非終結(jié)符，定義文法的出發(fā)點(diǎn),3.2上下文無關(guān)文法,產(chǎn)生式是定義語法單位的一種書寫規(guī)則。 上下文無關(guān)文法產(chǎn)生式的左部必定是一個非終結(jié)符，該非終結(jié)符稱為產(chǎn)生式的左部符號，簡稱左部符號。 產(chǎn)生式的右部是終結(jié)符和非終結(jié)符經(jīng)過有限次連接構(gòu)成的文法符號串，可以是空字。,

9、3.2上下文無關(guān)文法,為方便，若干個左部符號相同的產(chǎn)生式，如 A 1 A 2 A 3 A 4 A N 合并：A 1 | 2| | N,3.2上下文無關(guān)文法,例： G=（VT，VN，S，VP） VT=+，*，(，)，i VN=E S=E VP=EE+E，EE*E，E(E)，Ei 可簡記為： G：EE+E|E*E| (E)|i 根據(jù)上述文法，可推導(dǎo)出任何僅包含加乘的算術(shù)表達(dá)式。,3.2上下文無關(guān)文法,基本術(shù)語 直接推出和直接歸約 推導(dǎo)和歸約 句型 句子 語言 等價文法 最左推導(dǎo)和最右推導(dǎo),3.2上下文無關(guān)文法,文法的二義性 語法樹 我們可以用一個有向圖表示一個句型的推導(dǎo)，這種表示稱為語法樹。 在一

10、般情況下，某一句型不論其推導(dǎo)過程如何，其最終形成的語法樹是相同的，故語法樹是不同推導(dǎo)過程的共性抽象。若僅進(jìn)行最左（右）推導(dǎo)，則語法樹和最左（右）推導(dǎo)等價。,3.2上下文無關(guān)文法,二義文法 某些文法的句型的推導(dǎo)可能對應(yīng)一棵以上的語法樹，或存在一個以上的最左（右）推導(dǎo)。,3.2上下文無關(guān)文法,例：已知文法G：EE+E|E*E|(E)|i和句子i+i*i，該句子存在二個最左（右）推導(dǎo)，即二棵語法樹。,3.2上下文無關(guān)文法,語法樹1（先形成+后形成*）,3.2上下文無關(guān)文法,語法樹2（先形成*后形成+）,3.2上下文無關(guān)文法,句子i+i*i的二個最左推導(dǎo)序列： EE+Ei+Ei+E*Ei+i*Ei+i*i EE*EE+E*Ei+E*Ei+i*Ei+i*i 句子i+i*i的二個最右推導(dǎo)序列： EE+EE+E*EE+E*iE+i*ii+i*i EE*EE*