程序设计语言的语法描述课件

1

程式設計語言的語法描述

23.1

文法的引入3.2

上下文無關文法3.3文法舉例（略）

使用文法對程式設計語言的結構進行定義和描述。33.1文法的引入

先討論自然語言的文法。例：thebigelephentateabanana㈠語法樹根據英語的語法，上述句子的語法結構可用圖（語法樹）表示如下：非葉結點稱為語法單位，在形式語言中稱為非終結符。處於根結點位置的結點又稱為開始符號。葉結點稱為單詞符號，在形式語言中稱為終結符。4㈡規則可以通過建立一組規則，來描述上述句子的語法結構，規則在形式語言中稱為產生式。<句子>→<主語><謂語> <主語>→<冠詞><形容詞><名詞><冠詞>→the|a<形容詞>→big<名詞>→elephant|banana<謂語>→<動詞><直接賓語><直接賓語>→<冠詞><名詞><動詞>→ate㈢由規則推導句子可用規則來推導出句子。從開始符號出發，若能從規則推導出某符號串，則該符號串就是該文法的合法的句子，反之語法錯誤。上述英文句子可用下述規則來描述：5

<句子>

<主語><謂語>

<冠詞><形容詞><名詞><謂語>

the<形容詞><名詞><謂語>

thebig<名詞><謂語>

thebigelephant<謂語>

thebigelephant<動詞><直接賓語>

thebigelephantate<直接賓語>

thebigelephantate<冠詞><名詞>

thebigelephantatea<名詞>

thebigelephantateabanana

上述推導可簡單表示為：

<句子>

thebigelephantateabanana。值得注意的是用上述規則可推導出多個句子，因存在推導

<句子>

abigbananaatetheelephant

所以，abigbananaatetheelephant也是文法的一個合法的句子。但意義是荒謬的，也就是說句子的語義是錯誤的。一個語法正確的句子不能保證其語義是正確的，故一個句子是否正確，需要進行語法和語義兩方面檢查。綜上所述，語言結構通常是用文法來定義和描述，文法是由終結符、非終結符、開始符號（特殊非終結符）及產生式四個要素構成。從開始符號出發，根據產生式能推導出的句子全體稱為文法所規定的語言6㈣遞歸規則和遞歸文法遞歸是編譯技術中的一個重要概念。①遞歸定義：定義某事物，又用到該事物本身。②遞歸規則（直接遞歸）：在規則的左部和右部有相同的非終結符。例：U→xUy，通常用大寫字母表示非終結符，用小寫字母表示終結符。

⑴左遞歸規則：x=ε，U→Uy（ε表示空串）

⑵右遞歸規則：y=ε，U→xU③間接遞歸：由規則推導產生。例：V→Uy|Z，U→xV

因存在推導V

Uy

xVy，故存在間接遞歸。

⑴間接左遞歸：若x=ε，則V

Vy。

⑵間接右遞歸：若y=ε，則V

xU。④遞歸文法：含有遞歸規則和間接遞歸的文法，稱為遞歸文法。利用遞歸文法，可以用有窮的規則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法檢查成為可能。73.2 上下文無關文法

形式語言的奠基人喬姆斯基（Chomsky）將文法分為4種類型，它們是：短語文法（0型文法）上下文有關文法（1型文法）上下文無關文法（2型文法）正規文法（3型文法）這四種文法在形式語言中都有嚴格的定義。但對於程式設計語言來說，上下文無關文法已經夠用了，上下文無關文法有足夠的能力描述大多數現今使用的程式設計語言的語法結構。以後，“文法”一詞若無特別說明，則指“上下文無關文法”。8㈠文法和語言一個文法G是一個四元式(VT,VN,S,P)，其中VT是一個終結符的非空有限集，終結符通常用小寫字母表示。VN是一個非終結符的非空有限集，非終結符通常用大寫字母表示。S是一個特殊的非終結符（S∈VN），稱為開始符號。P是一個產生式（規則）的有限集合，每個產生式的形式是A→α

，其中A∈VN，α∈(VT∪VN)*。①終結符是語言的基本符號，即程式設計語言的單詞。語法分析時，終結符用單詞的種別表示。根據前面約定： 識別字（簡單變數）： i

無符號整常數： x

無符號實常數： y

單字符單詞： 用單詞本身表示（例單詞“+”的 種別用+表示） 多字元單詞： 需特別指定（例“++”用$表示）9②非終結符表示抽象的語法單位.

例“算術運算式”、“布爾運算式”、“賦值語句”、“說明語句”和“程式”等。非終結符通常用大寫字母表示，也可以用帶尖括弧的漢字表示。③開始符號是一個特殊的非終結符，它代表我們最感興趣的語法單位。例如討論算術運算式，那麼描述算術運算式文法的開始符號就是<算術運算式>。在程式設計語言中，我們最感興趣的語法單位是<程式>。④產生式是定義語法單位的一種書寫規則。上下文無關文法產生式的左部必定是一個非終結符，該非終結符稱為左部符號。產生式的右部是終結符和非終結符經有限次連接構成的文法符號串，可以是空字ε。四種文法的區別主要是對產生式的左部和右部的限制不同。若干個左部符號相同的產生式，可合併為一個，例： A→α1|α2|……|αn，其中αi

稱為A的候選式(1≤i≤n)。10

例1：描述算術運算式文法G=(VT,VN,S,P)，其中

VT={+,-,*,/,i,x,y,(,)} VN={<算術運算式>,<項>,<因數>} S=<算術運算式> P={ <算術運算式>→<算術運算式>+<項> <算術運算式>→<算術運算式>-<項> <算術運算式>→<項> <項>→<項>*<因數> <項>→<項>/<因數> <項>→<因數> <因數>→(<算術運算式>) <因數>→i //識別字

<因數>→x //無符號整常數

<因數>→y //無符號實常數

}

根據上述文法，可推導出任何僅包含加減乘除的算術運算式。11

因已約定非終結符和終結符的書寫方式，非終結符和終結符在產生式中一目了然，故終結符集VT和非終結符集VN無需再顯式列出。若規定左部符號為開始符號的產生式寫在所定義文法的第一行，上述文法G又可簡單表示為如下形式：

<算術運算式>→<算術運算式>+<項> <算術運算式>→<算術運算式>-<項> <算術運算式>→<項> <項>→<項>*<因數> <項>→<項>/<因數> <項>→<因數> <因數>→(<算術運算式>) <因數>→i <因數>→x <因數>→y

若用E表示<算術運算式>、T表示<項>、F表示<因數>，借助符號'|'，算術運算式文法G可表示成如下最簡形式：

E→E+T︱E–T︱T T→T*F︱T/F︱F

F→(E)︱i︱x︱y12

例2：描述算術運算式文法G=(VT,VN,S,P)，其中

VT={+,-,*,/,i,x,y,(,)} VN={<算術運算式} S=<算術運算式> P={ <算術運算式>→<算術運算式>+<算術運算式> <算術運算式>→<算術運算式>-<算術運算式> <算術運算式>→<算術運算式>*<算術運算式> <算術運算式>→<算術運算式>/<算術運算式> <算術運算式>→(<算術運算式>) <算術運算式>→i //識別字

<算術運算式>→x //無符號整常數

<算術運算式>→y //無符號實常數

}

根據上述文法，同樣可推導出任何僅包含加減乘除的算術運算式。用E表示<算術運算式>，上述文法可簡記為：

E→E+E|E-E|E*E|E/E|(E)|i|x|y13㈡基本術語

以文法G：

E→E+E|E*E|(E)|i為例，進行下述討論。①直接推出和直接歸約②推導和歸約若α1

α2

…

αn，則稱該直接推出序列是從α1到αn的一個推導，記作α1

αn或α1

αn。

α1

αn：從α1始，經一步或一步以上可推導出αn。

α1

αn：從α1始，經０步或０步以上可推導出αn，即 α1

αn或α1=αn。也可稱直接歸約序列αn,αn-1,…,α1為αn到α1的一個歸約。③句型若存在推導S

α（S為文法的開始符號），則稱α是文法的一個句型。④句子僅包含終結符的句型稱為句子。14⑤語言文法Ｇ所能推導出的句子全體稱為該文法的語言，記為：

L(G)={α|(S

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

1)根據條件修改文法，語言不變。 算符優先性：規定*優先於+，i+i*i等價於i+(i*i)。 算符結合性：規定同級運算服從左結合，i+i+i等價於 (i+i)+i。

2)根據條件修改編譯程序的語法分析表，文法保持不變（詳見第四、五章）。16

1）根據條件修改文法，語言不變。算符優先性：規定*優先於+，i+i*i等價於i+(i*i)。算符結合性：規定同級運算服從左結合，i+i+i等價於(i+i)+i。例文法GG：E→E+E|E*E|(E)|i是一個二義文法。根據上述條件將文法G修改成G’，如下所示

G'：E→E+T|TT→T*F|FF→(E)|i顯然G'不是二義文法，但L(G)=L(G')，故G和G'等價。例句子i+i*i的最右推導：

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

?+?*?

…先形成+，才有可能形成*。若先形成*，只有帶括弧才可能形成+。17

2）根據條件修改編譯程序的語法分析表，文法保持不變。例文法G：

<語句>→if

識別字

then<語句>else<語句> S→fitSeS<語句>→if

識別字

then<語句> S→fitS<語句>→識別字=<算術運算式> S→i=E<算術運算式>→無符號整常數

E→x程式段

a=2 ifxthenifythena=4elsea=6相應的語法結構表示為

i=x

fitfiti=xei=x句子fitfiti=xei=x的最左推