1、Part2Part2高級語言及其語法描述高級語言及其語法描述授課：胡靜授課：胡靜內容提要內容提要預備知識預備知識形式語言基礎形式語言基礎程序語言的定義（語法定義、語義定義）程序語言的定義（語法定義、語義定義） 高級語言的一般特性（程序結構、數據類型和操作、高級語言的一般特性（程序結構、數據類型和操作、語句與控制結構）語句與控制結構）程序語言的文法程序語言的文法文法的類型文法的類型上下文無關文法及其語法樹上下文無關文法及其語法樹有關文法實用中的一些說明有關文法實用中的一些說明預備知識預備知識更多的概念和一些約定更多的概念和一些約定A, B, C, 用來表示用來表示非終結符非終結符a, b, c,

2、 表示表示終結符終結符, X, Y, Z 可以用來表示可以用來表示終結符或者非終結符終結符或者非終結符, w, x, y, z 表示表示終結符號串終結符號串, , , , 表示由表示由終結符或非終結符構成的符號串終結符或非終結符構成的符號串在產生式在產生式A中，中，A 是產生式的左邊是產生式的左邊(lefthand side,LHS)是產生式的右邊是產生式的右邊( righthand side, RHS)A1|n 表示產生式表示產生式 A 1 , A n符號串和符號串集合的運算符號串和符號串集合的運算符號串和符號串集合的運算符號串和符號串集合的運算將字符看做符號，則單詞就是符號串，將字符看做符

3、號，則單詞就是符號串，單詞集合就是符號串的集合單詞集合就是符號串的集合將單詞看做符號，則句子就是符號串，將單詞看做符號，則句子就是符號串，而所有句子的集合（語言）就是符號串而所有句子的集合（語言）就是符號串的集合的集合程序語言的定義程序語言的定義程序語言的語法定義程序語言的語法定義所謂一個語言的語法是指這樣一組規則，用它可以形所謂一個語言的語法是指這樣一組規則，用它可以形成和產生一個合式的程序。這些規則一部分稱為詞法成和產生一個合式的程序。這些規則一部分稱為詞法規則則，另一部分稱為語法規則（或產生規則）規則則，另一部分稱為語法規則（或產生規則）詞法規則：詞法規則規定了字母表中哪樣的字符串是一詞

4、法規則：詞法規則規定了字母表中哪樣的字符串是一個單詞符號，是單詞符號的形成規則個單詞符號，是單詞符號的形成規則 語法規則：語言的語法規則規定了如何從單詞符號形成語法規則：語言的語法規則規定了如何從單詞符號形成更大的結構（即語法單位），換言之，語法規則是語法更大的結構（即語法單位），換言之，語法規則是語法單位的形成規則單位的形成規則程序語言的定義程序語言的定義程序語言的語義定義程序語言的語義定義所謂一個語言的語義是指這樣的一組規則，使用它可所謂一個語言的語義是指這樣的一組規則，使用它可以定義一個程序的意義。這些規則稱為語義。以定義一個程序的意義。這些規則稱為語義。 我們將要介紹的是目前大多數編譯

5、程序普遍采用的一我們將要介紹的是目前大多數編譯程序普遍采用的一種方法，即基于屬性文法的語法制導翻譯方法，雖然種方法，即基于屬性文法的語法制導翻譯方法，雖然還不是形式系統，但是比較接近形式化的。還不是形式系統，但是比較接近形式化的。 高級語言的一般特征高級語言的一般特征 高級語言的程序結構高級語言的程序結構 程序程序子程序子程序或或分程分程序序語句語句表達式表達式數據數據引用引用算符算符函數函數調用調用數據類型和操作數據類型和操作 數據類型的要素：數據類型的要素：用于區別這種類型的數據對象的屬性；用于區別這種類型的數據對象的屬性；這種類型的數據對象可以具有的值；這種類型的數據對象可以具有的值；可

6、以作用于這種類型的數據對象的操作；可以作用于這種類型的數據對象的操作； 數據類型分類：數據類型分類：初等數據類型：數值數據、邏輯數據、字符數據、指初等數據類型：數值數據、邏輯數據、字符數據、指針類型針類型數據結構：數組、記錄、字符串、表格、棧、隊列和數據結構：數組、記錄、字符串、表格、棧、隊列和抽象數據類型（抽象數據類型（Ada通過程序包通過程序包package提供，其余通提供，其余通過類過類class提供）提供）語句與控制結構語句與控制結構 表達式：一個表達式是由運算量（操作數，即數據引表達式：一個表達式是由運算量（操作數，即數據引用或函數調用）和算符組成的。用或函數調用）和算符組成的。語句

7、：不同程序語言含有不同形式和功能的各種語句語句：不同程序語言含有不同形式和功能的各種語句執行語句：描述程序的動作，分為賦值語句、控制語執行語句：描述程序的動作，分為賦值語句、控制語句、輸入句、輸入/輸出語句；輸出語句；說明性語句：定義各種不同數據類型的變量或運算說明性語句：定義各種不同數據類型的變量或運算從形式上分，語句可以分為簡單句、復合句和分程序從形式上分，語句可以分為簡單句、復合句和分程序等。等。 文法的直觀概念文法的直觀概念關于文法的定義關于文法的定義定義定義3.1文法文法G定義為四元組（定義為四元組（VN, VT, P, S）。）。其中其中VN為非終結符號（或語法實體，或變量）集；為

8、非終結符號（或語法實體，或變量）集；VT為終結符為終結符號集；號集；P為產生式（也稱規則）的集合；為產生式（也稱規則）的集合；VN, VT和和P是非空有窮是非空有窮集。集。S稱做識別符號或開始符號，是一個非終結符（稱做識別符號或開始符號，是一個非終結符（S VN），），至少要在一條規則中作為左部出現。至少要在一條規則中作為左部出現。VN和和VT不含公共元素，即不含公共元素，即VNVT=。通常。通常V表示表示VNVT，V稱稱為文法為文法G的字母表或字匯表。的字母表或字匯表。例例3.1 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號為

9、開始符號文法可以簡寫，只需要指出開始符號和產生式即可。文法可以簡寫，只需要指出開始符號和產生式即可。關于文法的定義（續）關于文法的定義（續）定義定義3.2如如是文法是文法G=(VN, VT, P, S)的規則的規則(或說是或說是P中第一中第一個產生式個產生式)，和和是是V*中的任意符號串，若有符號串中的任意符號串，若有符號串v，w滿足：滿足：v=，w=，則說，則說v（應用規則（應用規則）直）直接產生接產生w，或說，或說w是是v的直接推導。的直接推導。（v=w）例：例：GS： S0S1， S01 S 0S1 00S11 000S111 00001111G關于文法的定義（續）關于文法的定義（續）定

10、義定義3.3如果存在直接推導的序列：如果存在直接推導的序列：v=w0=w1=w2=wn=w，(n0)，則稱，則稱v推導出（產生）推導出（產生）w（推導長度為（推導長度為n）。記）。記做做v=+w。定義定義3.4若有若有v=+w，或，或v=w，則記做，則記做v=*w。規范推導（最右推導）規范推導（最右推導）最左推導：若規則右端符號串中有兩個以上的非終結最左推導：若規則右端符號串中有兩個以上的非終結符時，先推導左邊的。符時，先推導左邊的。最右推導：若規則右端符號串中有兩個以上的非終結最右推導：若規則右端符號串中有兩個以上的非終結符時，先推導右邊的。符時，先推導右邊的。關于文法的定義（續）關于文法的

11、定義（續）定義定義3.5設設GS是一文法，如果符號串是一文法，如果符號串x是從識別符號推導出來的，即有是從識別符號推導出來的，即有S=*x，則稱，則稱x是文法是文法GS的句型。若的句型。若x只由終結符號組成，則稱只由終結符號組成，則稱x為為GS的句子。的句子。定義定義3.6文法文法G所產生的語言定義為集合所產生的語言定義為集合x | S=*x，其中，其中S為文法的開始為文法的開始符號，且符號，且xVT *。可用。可用L(G)表示該集合。表示該集合。例：例：G： S0S1， S01S 0S1 00S11 000S111 00001111L(G) = 0n1n | n1關于文法的定義（續）關于文法

12、的定義（續）定義定義3.7若若L(G1) = L(G2)，則稱文法，則稱文法G1和和G2是等價的。是等價的。例例1：如文法：如文法G1A：A0R 與與G2S： S0S1 等價等價 A01 S01 RA1例例2：G1E: E i 與與 G2E：E T|E+T等價等價 E E+E T F|T*F E E*E F （E）|i E (E)文法的類型文法的類型 Chomsky將文法分為四種類型：將文法分為四種類型：0型文法：對任一產生式型文法：對任一產生式，都有，都有(VNVT)+， (VNVT)*1型文法：對任一產生式型文法：對任一產生式，都有，都有|， 僅僅僅僅 除外除外2型文法：對任一產生式型文法

13、：對任一產生式，都有，都有VN ， (VNVT)*3型文法：任一產生式型文法：任一產生式的形式都為的形式都為AaB或或Aa，其中其中AVN ，BVN ，aVT。上述叫做右線性文法，。上述叫做右線性文法，另有左線性文法，二者等價。另有左線性文法，二者等價。文法的類型舉例文法的類型舉例1型（上下文有關）文法型（上下文有關）文法 文法文法GS： SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*文法的類型舉例文法的類型舉例2型（上下文無關）文法型（上下文無關）文法 文法文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法文法GS：

14、S0A|1B|0A0A|1B|0SB1B|1|0文法的類型舉例文法的類型舉例定義標識符的定義標識符的3型（正規）文法型（正規）文法 文法文法GI：I lTI lT lTT dTT lT d文法和語言文法和語言0型文法型文法0型文法（短語文法）的能力相當于圖靈機，可以表征任何遞歸型文法（短語文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何可枚舉集，而且任何0型語言都是遞歸可枚舉的型語言都是遞歸可枚舉的1型文法（上下文有關文法）型文法（上下文有關文法）產生式的形式為產生式的形式為1A212，即只有，即只有A出現在出現在1和和2的上下文的上下文中時，才允許中時，才允許取代取代A。其識別系

15、統是線性界限自動機。其識別系統是線性界限自動機。2型文法（上下文無關文法）型文法（上下文無關文法）產生式的形式為產生式的形式為A，取代取代A時與時與A的上下文無關。其識別系的上下文無關。其識別系統是不確定的下推自動機。統是不確定的下推自動機。3型文法（正則文法）型文法（正則文法）產生的語言是有窮自動機（產生的語言是有窮自動機（FA）所接受的集合）所接受的集合上下文無關文法上下文無關文法上下文無關文法有足夠的能力描述現今程序設計語言的語法結構上下文無關文法有足夠的能力描述現今程序設計語言的語法結構算術表達式算術表達式語句語句賦值語句賦值語句條件語句條件語句讀語句讀語句文法文法G=(E, +,*,

16、I,(,), P, E ifthen P:E i | ifthenelse E E+EE E*EE (E)上下文無關文法的語法樹用于描述上下文無關文法的用于描述上下文無關文法的句型推導句型推導的直觀方法的直觀方法 例: GS:SaASASbAASSSaAba S a A S S b A b a句型句型aabbaa的語法樹（推導樹）的語法樹（推導樹）葉子結點：樹中沒有子孫的結點。葉子結點：樹中沒有子孫的結點。從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結果。也把該推導樹稱為該句型的語法樹。果。也把該推導樹稱為該句型的語法樹。a aa a上

17、下文無關文法的語法樹推導過程中施用產生式的順序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa文法的二義性最左（最右）推導：在推導的任何一步最左（最右）推導：在推導的任何一步，其中，其中、是句型，都是對是句型，都是對中的最左（右）非終結符進行替換中的最左（右）非終結符進行替換最右推導被稱為規范推導。最右推導被稱為規范推導。由規范推導所得的句型稱為規范句型由規范推導所得的句型稱為規范句型文法的二義性文法的二義性例：GE:E iE E+EE E*EE (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個不同的最左推導：的兩個不同的最左推導：推導推導1：E E+E E*E+E i*E+E i*i+E i*i+i推導推導2：E E*E i*E i*E+E i*i+E i