天津大學(xué)編譯原理講義 - Part2高級(jí)語言及其語法描述

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

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

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

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

5、程序普遍采用的一我們將要介紹的是目前大多數(shù)編譯程序普遍采用的一種方法，即基于屬性文法的語法制導(dǎo)翻譯方法，雖然種方法，即基于屬性文法的語法制導(dǎo)翻譯方法，雖然還不是形式系統(tǒng)，但是比較接近形式化的。還不是形式系統(tǒng)，但是比較接近形式化的。 高級(jí)語言的一般特征高級(jí)語言的一般特征 高級(jí)語言的程序結(jié)構(gòu)高級(jí)語言的程序結(jié)構(gòu) 程序程序子程序子程序或或分程分程序序語句語句表達(dá)式表達(dá)式數(shù)據(jù)數(shù)據(jù)引用引用算符算符函數(shù)函數(shù)調(diào)用調(diào)用數(shù)據(jù)類型和操作數(shù)據(jù)類型和操作 數(shù)據(jù)類型的要素：數(shù)據(jù)類型的要素：用于區(qū)別這種類型的數(shù)據(jù)對(duì)象的屬性；用于區(qū)別這種類型的數(shù)據(jù)對(duì)象的屬性；這種類型的數(shù)據(jù)對(duì)象可以具有的值；這種類型的數(shù)據(jù)對(duì)象可以具有的值；可

6、以作用于這種類型的數(shù)據(jù)對(duì)象的操作；可以作用于這種類型的數(shù)據(jù)對(duì)象的操作； 數(shù)據(jù)類型分類：數(shù)據(jù)類型分類：初等數(shù)據(jù)類型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)、指初等數(shù)據(jù)類型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)、指針類型針類型數(shù)據(jù)結(jié)構(gòu)：數(shù)組、記錄、字符串、表格、棧、隊(duì)列和數(shù)據(jù)結(jié)構(gòu)：數(shù)組、記錄、字符串、表格、棧、隊(duì)列和抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（Ada通過程序包通過程序包package提供，其余通提供，其余通過類過類class提供）提供）語句與控制結(jié)構(gòu)語句與控制結(jié)構(gòu) 表達(dá)式：一個(gè)表達(dá)式是由運(yùn)算量（操作數(shù)，即數(shù)據(jù)引表達(dá)式：一個(gè)表達(dá)式是由運(yùn)算量（操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。用或函數(shù)調(diào)用）和算符組成的。語句

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

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

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

10、義定義3.3如果存在直接推導(dǎo)的序列：如果存在直接推導(dǎo)的序列：v=w0=w1=w2=wn=w，(n0)，則稱，則稱v推導(dǎo)出（產(chǎn)生）推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長(zhǎng)度為（推導(dǎo)長(zhǎng)度為n）。記）。記做做v=+w。定義定義3.4若有若有v=+w，或，或v=w，則記做，則記做v=*w。規(guī)范推導(dǎo)（最右推導(dǎo)）規(guī)范推導(dǎo)（最右推導(dǎo)）最左推導(dǎo)：若規(guī)則右端符號(hào)串中有兩個(gè)以上的非終結(jié)最左推導(dǎo)：若規(guī)則右端符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，先推導(dǎo)左邊的。符時(shí)，先推導(dǎo)左邊的。最右推導(dǎo)：若規(guī)則右端符號(hào)串中有兩個(gè)以上的非終結(jié)最右推導(dǎo)：若規(guī)則右端符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，先推導(dǎo)右邊的。符時(shí)，先推導(dǎo)右邊的。關(guān)于文法的定義（續(xù)）關(guān)于文法的

11、定義（續(xù)）定義定義3.5設(shè)設(shè)GS是一文法，如果符號(hào)串是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來的，即有是從識(shí)別符號(hào)推導(dǎo)出來的，即有S=*x，則稱，則稱x是文法是文法GS的句型。若的句型。若x只由終結(jié)符號(hào)組成，則稱只由終結(jié)符號(hào)組成，則稱x為為GS的句子。的句子。定義定義3.6文法文法G所產(chǎn)生的語言定義為集合所產(chǎn)生的語言定義為集合x | S=*x，其中，其中S為文法的開始為文法的開始符號(hào)，且符號(hào)，且xVT *?？捎谩？捎肔(G)表示該集合。表示該集合。例：例：G： S0S1， S01S 0S1 00S11 000S111 00001111L(G) = 0n1n | n1關(guān)于文法的定義（續(xù)）關(guān)于文法

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

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

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

15、統(tǒng)是線性界限自動(dòng)機(jī)。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。2型文法（上下文無關(guān)文法）型文法（上下文無關(guān)文法）產(chǎn)生式的形式為產(chǎn)生式的形式為A，取代取代A時(shí)與時(shí)與A的上下文無關(guān)。其識(shí)別系的上下文無關(guān)。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。統(tǒng)是不確定的下推自動(dòng)機(jī)。3型文法（正則文法）型文法（正則文法）產(chǎn)生的語言是有窮自動(dòng)機(jī)（產(chǎn)生的語言是有窮自動(dòng)機(jī)（FA）所接受的集合）所接受的集合上下文無關(guān)文法上下文無關(guān)文法上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)算術(shù)表達(dá)式算術(shù)表達(dá)式語句語句賦值語句賦值語句條件語句條件語句讀語句讀語句文法文法G=(E, +,*,

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

17、下文無關(guān)文法的語法樹推導(dǎo)過程中施用產(chǎn)生式的順序 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa文法的二義性最左（最右）推導(dǎo)：在推導(dǎo)的任何一步最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中，其中、是句型，都是對(duì)是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型文法的二義性文法的二義性例：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 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+E i*i+E i