《編譯原理及實踐教程》第2章高級語言設(shè)計基礎(chǔ)

1、高級語言設(shè)計基礎(chǔ)高級語言設(shè)計基礎(chǔ)第第2章章 本章要求本章要求 主要內(nèi)容主要內(nèi)容：符號串，文法和語言的概：符號串，文法和語言的概念及分類，高級語言的定義過程念及分類，高級語言的定義過程 重點掌握重點掌握：符號串及其運(yùn)算，上下文：符號串及其運(yùn)算，上下文無關(guān)文法、推導(dǎo)、句型、句子、語言，無關(guān)文法、推導(dǎo)、句型、句子、語言，語法樹、二義文法、文法的語言生成語法樹、二義文法、文法的語言生成過程，高級語言的設(shè)計過程過程，高級語言的設(shè)計過程 以C和PASCAL為例復(fù)習(xí)高級語言 1 語言的基本字符集的定義(字母, 數(shù)字, 符號) 2 單詞的定義 3 數(shù)據(jù)類型的定義 4 各種表達(dá)式的定義 5 各種語句的定義 6

2、程序定義 PASCAL和C的主要區(qū)別2.1 符號和符號串符號和符號串 1. 字母表字母表：高級語言程序能夠使用的全體字符構(gòu)成的集合，用表示，是一個有窮非空集合。 2. 符號符號：字母表中的每個元素。因此字母表也稱為符號集。 不同的語言可以有不同的字母表，例如英文的字母表中26個字母、數(shù)字及標(biāo)點符號等。 C語言的字母表是由字母、數(shù)字、若干專用符號組成。 符號是某語言能識別的字符，字母表是該語言能識別的所符號是某語言能識別的字符，字母表是該語言能識別的所有符號的全體（字符集）有符號的全體（字符集）?；靖拍罨靖拍? (續(xù)續(xù)) ) 3. 符號串符號串: 由字母表中的符號組成的任何有窮序列稱為符號串

3、，例如00 11 10 是字母表 =0，1上的符號串 字母表A=a,b,c上的一些符號串有：a,b,c,ab,aaca等。 在符號串中，符號的順序是很重要的，符號串a(chǎn)b就不同于ba，abca和aabc也不同。 符號串STR表示“由符號S、T和R，并按此順序組成基本概念(續(xù)) 4. 符號串的運(yùn)算符號串的運(yùn)算 符號串符號串s的長度的長度 :出現(xiàn)在出現(xiàn)在s中中符號的個數(shù)，記|s| 如：如001110的長度是6。 空符號串空符號串: 即不包含任何符號的符號串，用表示，其長度為0， 即|=0。 符號串的連接連接：字符串稱為字符串和的連接（即把放在的后面） 如：=01，=110，則=01110，=1100

4、1 集合U與V的乘積乘積 ：UV = | U & V 即: 集合UV是由U中的任一符號串與V中的任一符號串連接而成的符號串集合。 例：設(shè)U = aa,bb ，V=00,11 則UV=?UV VU 集合V的n次方冪方冪：V自身的n次乘積 Vn =VVVV . V 規(guī)定V0 = 例：設(shè)V=ab,x,y, 則V2=VV=ab,x,yab,x,y=abab,abx,aby,xab,xx,xy,yab,yx,yy例：例：=a,b=a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,

5、aab,=a,b,aa,ab,ba,bb,aaa,aab, 的閉包、正閉包閉包、正閉包的閉包的閉包 *: 表示上的所有符號串（包括）組成的集合。 包括長度為0，1，2， 的正閉包的正閉包 + ：表示 上的除外的所有符號串組成的集合。.32=+V=0,1 V* = ? V+ = ?.32= *形式語言的概念*中的任意一個按一定規(guī)則構(gòu)成的子集稱為上的一個（形式）語言（形式）語言，屬于該語言的符號串稱為該語言的句子句子。例：令LA, B, , Z, a, b, , z，D0, 1, , 9，。由于單個符號可以看成是長度為1的符號串，L和D可以分別看成是有窮的語言集。用集合的運(yùn)算作用于L和D所得到6種

6、新語言：（1）LD是字母和數(shù)字的集合；（2）LD是所有一個字母后隨一個數(shù)字的符號串的集合；（3）L6是由6個字母構(gòu)成的符號串的集合；（4）L*是所有字母串（包括）的集合；（5）L(LD )*是以字母開頭的所有字母數(shù)字串的集合； （6）D+是不含空串的數(shù)字串的集合。 語言的有窮表示 語言的有窮表示有兩種方法： 用產(chǎn)生的觀點來表示語言。方法：為語言定義一組規(guī)則，利用規(guī)則產(chǎn)生語言中的每個句子。 用識別的觀點表示語言。方法：利用一個算法（有限自動機(jī)）來判斷某個給定的符號串（句子）是否在某語言中。本章先從“產(chǎn)生的觀點”來描述語言文法。2.2 文法與語言文法與語言 程序設(shè)計語言的語法結(jié)構(gòu)的形式化描述稱為文

7、法（Grammar）。 文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。 文法是從產(chǎn)生語言中的句子的觀點來描述語言的，即語言中的每個句子都可以用嚴(yán)格定義的規(guī)則來產(chǎn)生。 文法描述語言的時候不考慮語言的含義。引引 例例例2.2：有如下規(guī)則 (表示由組成)| （|表示“或”）我大學(xué)生是| 根據(jù)如上9條規(guī)則可以得出句子：我是大學(xué)生。分析過程是： = = =我 =我 =我是 =我是 =我是大學(xué)生說明這是語法上正確的句子！文法的形式化定義文法的形式化定義 文法G由四部分組成：終結(jié)符號：出現(xiàn)在句子中的符號，是一個語言不可再分的基本單位,如保留字、標(biāo)識符等。用VT表示終結(jié)符的集合。非終結(jié)符號：規(guī)則中用尖括號

8、括起來的符號，表示一些語法成分，可以推導(dǎo)出其他的語法成分,表示一定符號串的集合，如表達(dá)式。用VN表示非終結(jié)符的集合。開始符號：規(guī)則中的一個特殊的非終結(jié)符號，語言中的句子都從它開始推導(dǎo),如程序、句子產(chǎn)生式：定義語法成分的規(guī)則，上例中有9個產(chǎn)生式。用P表示產(chǎn)生式的集合。|我大學(xué)生是|文法的形式化定義文法的形式化定義( (續(xù)續(xù)) ) 一個文法文法G抽象地表示為一個四元組 G=（VN，VT，P，S） 其中VN表示非終結(jié)符號集VT表示終結(jié)符號集，VNVT=(字母表)，VNVT=S是開始符號P是產(chǎn)生式集合 上例中： G=（VN,VT,P,） VN=（，） VT= (我，是，大學(xué)生) P = | 我 大學(xué)生

9、 是 |例2.3：某語言中標(biāo)識符定義的文法G=（VN，VT，P，S）其中：VN=標(biāo)識符，字母，數(shù)字 VT=a,b,c,y,z,0,1,9 S = P= abz09 產(chǎn)生式的形式為：A 左部符號，非終結(jié)符右部，可以含有非終結(jié)符和終結(jié)符又稱為一條規(guī)則。l注：有時不用將文法G的四元組顯式地表示出來，而只將產(chǎn)生式寫出。l書寫產(chǎn)生式的約定： 第一條產(chǎn)生式的左部是開始符號； 用大寫字母表示非終結(jié)符，小寫字母表示終結(jié)符； 用小寫希臘字母（如、和）代表文法的符號串； 如果S是文法G的開始符號，也可將文法G寫成GS。 有時為書寫簡潔，常把相同左部的產(chǎn)生式進(jìn)行縮寫。如： 其中，每個i是A的一個候選式。A1A2An

10、縮寫為A1|2|n例2.4：下面是一個文法的幾種等價寫法。 （1）G=(S,A,a,b,P,S) 其中 P：SaAb Aab AaAb A（2）G：SaAb Aab AaAb A（3）GS：SaAb Aab AaAb A（4）GS：SaAb Aab|aAb|例例2.5 2.5 某語言算術(shù)表達(dá)式的文法定義某語言算術(shù)表達(dá)式的文法定義 變量是表達(dá)式 表達(dá)式 + 表達(dá)式是表達(dá)式 表達(dá)式 * 表達(dá)式是表達(dá)式 (表達(dá)式) 是 表達(dá)式E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i若用E表示表達(dá)式，i表示變量，則表達(dá)式的文法可以表示為：簡寫為2.2.2 文法

11、產(chǎn)生的語言推導(dǎo)和規(guī)約 推導(dǎo):從文法的開始符號出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對左邊的非終結(jié)符進(jìn)行替換和展開，直到全部為終結(jié)符為止。這個過程就是推導(dǎo)。用=表示。 例：利用例2.5的算術(shù)表達(dá)式文法，推導(dǎo)表達(dá)式（i+i）。過程是：E E + E E E * E E ( E ) E iE=( E ) =( E+E ) =( i+E ) =( i + i )推導(dǎo)和規(guī)約推導(dǎo)和規(guī)約 直接推導(dǎo)直接推導(dǎo)：又稱一步推導(dǎo)(用 符號=表示),就是用某條規(guī)則的右部去替換該規(guī)則的左部。 歸約：歸約：推導(dǎo)的逆過程稱為歸約歸約（Reduction）。 直接歸約：直接歸約：直接推導(dǎo)的逆過程。 推導(dǎo)和規(guī)約推導(dǎo)和規(guī)約*+ 如果存在v=w

12、0=w1=w2.=Wn=w(n0)，則稱v推導(dǎo)出w（長度為n），記作v=w(至少一步) 若有=w或v=w，則記作v=w(0步或若干步) 最左推導(dǎo)：整個推導(dǎo)過程中，每一步都是替換句型中最左邊的非終結(jié)符。 最右推導(dǎo)： 例2.6 : G = (E, i, +, *, (, ) , P , E) P： E E+E | E*E | (E) | i 寫出表達(dá)式(i+i)*i的最左推導(dǎo)和最右推導(dǎo)。最左推導(dǎo)：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i最右推導(dǎo)：E E*E E*i (E + E)*i (E+i)*i (i + i)*i 句型句型：設(shè)(s

13、)是一文法，如果符號串x是從開始符號推導(dǎo)出來的，即有s=x,則稱x是文法G(s)的一個句型。 即: 任何由開始符推導(dǎo)出來的符號串都是句型。 句子句子：若x僅由終結(jié)符號組成，則稱x為G(S)的句子* 練習(xí)練習(xí) 文法文法G：SaAcB | Bd AAaB | c BbScA | b 寫出寫出句型句型aAcbBdcc和和句句子子acabcbbdcc的的推導(dǎo)推導(dǎo)過程。過程。 文法文法G所產(chǎn)生的語言所產(chǎn)生的語言定義為： 文法G產(chǎn)生的所有句子的集合稱為G產(chǎn)生的語言，記為L(G)，表示為： L(G)=X|S=X,XVT* 。* 例：考慮文法G: 它定義了什么語言。S bAA aA|a推導(dǎo)過程 ：S=bA =

14、ba S=bA =baA=baa . S=bA =baA= =baa歸納得： L(G1) = ban | n1 練習(xí)：文法(A,B,S,a,b,c,P,S) S Ac|aB A ab B bc寫出(G)的全部元素 L(G) = abc 例：考慮文法G2: 它定義的語言是：S ABA aA|aB bB|bL(G2) = ambn |m,n1 例2.8：構(gòu)造一個文法G使得：L(G) = anbn |n1 S aSbS ab a,b的個數(shù)相同,則文法G為： 文法等價：文法等價： 若文法G1和文法G2所產(chǎn)生的語言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價等價。例：有如下兩個文法，判

15、斷它們是否等價？ G1=（S，0，S0S，S0，S） G2=（S，0，SS0，S0，S）S0S0S00S0S 00S 0000 L(G1) = 0n | n1 對于對于G2： 對于對于G1 ：SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)，文法G1和G2等價 例 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (i+i)*i的推導(dǎo)過程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E

16、 E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*il 對給定的文法，定義的語言是由利用所有的產(chǎn)生式經(jīng)過各種方式推導(dǎo)出所有可能的句子構(gòu)成的，并沒有規(guī)定推導(dǎo)使用產(chǎn)生式的順序。l 因此從一個句型到另一個句型(句子)的推導(dǎo)過程不是唯一的。文法的二義性文法的二義性 語法樹語法樹（分析樹）（分析樹）：推導(dǎo)的形式化表示推導(dǎo)的形式化表示，有助于理解句子語法結(jié)構(gòu)的層次 每個結(jié)點都有一個標(biāo)記，該標(biāo)記屬字母集中的一個符號，根由開始符號標(biāo)記。 隨著推導(dǎo)，當(dāng)某個非終結(jié)符被它的某個候選式所替換時，就產(chǎn)生相應(yīng)的下一層的結(jié)點，候選式中自左至右的每個符號對應(yīng)一個新的結(jié)點，并標(biāo)記它，畫出其與

17、父結(jié)點之間的連線。 末結(jié)點從左到右排列起來構(gòu)成一個句型。 如果自左至右端末結(jié)點排列起來都是終結(jié)符，則這顆樹表示了一個句子的推導(dǎo)過程。例：對文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的最左推導(dǎo)的語法樹是？ 在語法樹的推導(dǎo)過程中的任何時刻，沒有后代的端末結(jié)點自左至右排列起來就是一個句型 一棵語法樹表示了一個句型很多可能的不同推導(dǎo)過程。(包括最左推導(dǎo)和最右推導(dǎo))例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子

18、 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*i+i 注意：并不是任何情況一個句型就唯一地對應(yīng)一棵語法樹。正常優(yōu)先級+優(yōu)先 定義定義：如果一個文法存在某個句型對應(yīng)兩棵或兩顆以上的語法樹，則稱這個文法是二義二義文法文法。 對二義文法中的某個句子的分析（最左或最右推導(dǎo)）不是唯一的，因此有些程序設(shè)計語言的分析器要求文法是無二義的。例2.9 證明下述文法是二義文法。 設(shè)if語句S的文法G=(E，S，if，then，else，a，e，P，S)，其中P為： Sif E then S （1）Sif

19、E then S else S （2）Sa （3）Ee （4）推導(dǎo)(1)：S if E then S if E then if E then S else S推導(dǎo)(2)：S if E then S else S if E then if E then S else S文法的分類文法的分類 文法有四種，不同類型的文法只是對產(chǎn)生式的要求不同。 設(shè)G=(VN,VT,P,S)，其中,(VNVT)*型文法型文法(短文文法)： 對產(chǎn)生式只要求中至少含有一個非終結(jié)符。（對每個產(chǎn)生式不加任何限制）型文法型文法(上下文有關(guān)文法)：每個產(chǎn)生式限制為形如1A212, 其中1,2,(VNVT)*,AVN,型文法型文法

20、(上下文無關(guān)文法)：每個產(chǎn)生式限制為形如 A, 其中AVN，(VNVT)*型文法型文法(正規(guī)文法)：G的每個產(chǎn)生式的形式都是：AB或A，其中A,BVN，VT*。(右線性文法）文法的分類 例2.10 例2.11 4類文法總結(jié)： 4類文法的定義是對產(chǎn)生式逐漸加限制的，對應(yīng)的語言描述能力越來越弱。 每種正規(guī)文法也都是上下文無關(guān)文法，每種上下文無關(guān)文法也都是上下文有關(guān)文法，而每種上下文有關(guān)文法也都是0型文法。 4類文法應(yīng)用 在編譯技術(shù)中通常使用正規(guī)文法（3型文法）描述高級程序設(shè)計語言的詞法部分，用有限自動機(jī)來識別單詞。 使用上下文無關(guān)文法（2型文法）描述高級程序語言的語法結(jié)構(gòu)，用下推自動機(jī)識別語法成分

21、。語言的層次語言的層次 這四種語言可被4種自動機(jī)識別： 0型圖靈機(jī) 1型線性界限自動機(jī) 2型下推自動機(jī) 3型有窮自動機(jī) 從外到內(nèi)，四種文法對產(chǎn)生式的限制越來越多，語言的描述能力越來越弱2.3 高級語言的設(shè)計高級語言的設(shè)計 語言涉及它的設(shè)計者、實現(xiàn)者和使用者 本書主要介紹語言的實現(xiàn)，但實現(xiàn)之前必須了解所實現(xiàn)的語言的特征、結(jié)構(gòu)和功能。 本節(jié)從宏觀上介紹高級語言的基本結(jié)構(gòu)和共同特征，讓讀者對高級語言的認(rèn)識達(dá)到新的高度，從語言使用者逐步向語言的實現(xiàn)者、設(shè)計者過渡。 例子 程序語言的定義 程序設(shè)計語言的定義包括三部分： 語法是定義程序的一組形式規(guī)則，用它可以形成和產(chǎn)生一個形式上正確的程序； 語義也是一組

22、規(guī)則的集合，用以定義語法正確的單詞符號和語法單位的含義； 語用主要是有關(guān)程序設(shè)計技術(shù)和語言成分的使用方法，它使語言的基本概念與語言的外界（如數(shù)學(xué)概念或計算機(jī)的對象和操作）聯(lián)系起來。 程序的本質(zhì)程序的本質(zhì) 程序是在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)的基礎(chǔ)上對抽象算法的具體描述。 沃斯（N.wirth）以“算法+數(shù)據(jù)結(jié)構(gòu)=程序” 來描述程序 程序設(shè)計語言必須以描述算法和數(shù)據(jù)結(jié)構(gòu)作為他自身的主要結(jié)構(gòu)。 各種高級語言均以數(shù)據(jù)類型來描述數(shù)據(jù)結(jié)構(gòu)，以控制結(jié)構(gòu)來描述算法。 馮.諾依曼體系結(jié)構(gòu)與高級語言 馮.諾依曼機(jī)的思想：一個存儲器（用來存放指令和數(shù)據(jù)），一個控制器和一個運(yùn)算器（控制器負(fù)責(zé)從存儲器中逐條取出指令

23、，運(yùn)算器通過算術(shù)或邏輯操作來處理數(shù)據(jù)），最后的處理結(jié)果必須送回存儲器中。 特點： （1）數(shù)據(jù)和指令均以二進(jìn)制形式存儲（它們在外形上沒有什么區(qū)別，但每位二進(jìn)制數(shù)有不同的含義）； （2）程序以“存儲程序”的方式工作（即事先編寫好程序，執(zhí)行之前先將程序存放到存儲器某個可知的地方）； （3）程序順序執(zhí)行（但可強(qiáng)制改變執(zhí)行順序）； （4）存儲器的內(nèi)容可以被修改（一旦放入新的數(shù)據(jù)，則該單元原來的數(shù)據(jù)立即消失，且被新數(shù)據(jù)代替）。 高級語言的特性： （1）變量：存儲器由大量存儲單元組成，數(shù)據(jù)就存放在這些單元中，匯編語言通過對存儲單元的命名來訪問數(shù)據(jù)。在高級語言中，存儲單元及其名稱由變量的概念來代替，變量代表一

24、個（或一組）已命名的存儲單元，存儲單元可存放變量的值。 （2）賦值：使用存儲單元概念的另一個結(jié)果是每個計算結(jié)果都必須存儲，即將其賦值到某個存儲單元，從而改變該單元的值。 （3）重復(fù)：指令存儲在有限的存儲器中，按順序執(zhí)行。若要完成復(fù)雜的計算，有效的方式就是重復(fù)執(zhí)行某些指令序列。 一個程序往往要涉及若干實體，如變量、語句和子程序等。實體具有某些特性，這些特性稱為實體的屬性。 變量的屬性有名字、類型和保留其值的存儲區(qū)等 語句的屬性是與之相關(guān)的一系列動作 子程序的屬性有名字、形參個數(shù)和類型、參數(shù)傳遞方式的約定等。 在處理實體之前，必須將實體與相關(guān)的屬性聯(lián)系起來，這個聯(lián)系的過程稱為綁定綁定（Bindin

25、g），每個實體的綁定信息存儲在特定的表格中。 把實體與它的某個屬性聯(lián)系起來的時刻稱為綁定時間。 一旦綁定，這種關(guān)系就一直存在，直到對這一實體的另一次綁定。 若一個綁定在運(yùn)行之前（即編譯時）完成，且在運(yùn)行時不會改變，則稱為靜態(tài)綁定靜態(tài)綁定（Static Binding）。 如一個綁定在運(yùn)行時完成（此后可能在運(yùn)行過程中被改變），則稱為動態(tài)綁定動態(tài)綁定（dynamic Binding）。 抽象 變量是高級語言中最重要的概念之一，它是一個抽象概念，是對存儲單元的抽象。馮.諾依曼機(jī)基于存儲單元組成的主存儲器概念，每個存儲單元用地址來標(biāo)識，可以對它進(jìn)行讀或?qū)懖僮?，寫操作就是指修改存儲單元的值。賦值語句就是

26、對修改存儲單元內(nèi)容的抽象。 數(shù)據(jù)類型 內(nèi)部類型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)和指針類型數(shù)據(jù)。內(nèi)部類型是對二進(jìn)制位串的抽象，其基本形式對程序員是不可見的，即程序員不能直接訪問表示一個整數(shù)的位串的某個特定位。 用戶定義類型：數(shù)組、記錄、聯(lián)合、字符串、表格、棧、隊列、鏈表和樹等，基本表示形式對程序員是可見的 抽象數(shù)據(jù)類型：數(shù)據(jù)對象的一個集合，作用于這些數(shù)據(jù)對象的抽象運(yùn)算的集合，以及這些類型對象的封裝，C+中的類。基本表示對程序員是不可見的 語句和控制結(jié)構(gòu) 程序結(jié)構(gòu)表達(dá)式表達(dá)式 表達(dá)式由運(yùn)算對象（數(shù)據(jù)引用或函數(shù)調(diào)用）和運(yùn)算符組成。 分為邏輯表達(dá)式、關(guān)系表達(dá)式和算術(shù)表達(dá)式 運(yùn)算符之間的優(yōu)先關(guān)系和結(jié)合性規(guī)定了表達(dá)式的計算次序。 邏輯表達(dá)式 | |() | not | and | or 關(guān)系表達(dá)式 |=| =算術(shù)表達(dá)式|變量|()| + |-| *|/|()|語句語句 語句 說明性語句 可執(zhí)行語句 說明性語句旨在定義各種不同數(shù)據(jù)類型的變量或運(yùn)算，不需要由編譯程序生成目標(biāo)代碼，主要用來告訴編譯程序一些實體的屬性，供編譯程序生成目標(biāo)代碼時使用。 可執(zhí)行語句旨在描述程序的動作，需要由編譯程序生成目標(biāo)代碼來實現(xiàn)它的語義。 說明語句說明語句 | const 標(biāo)識符 = var : |, integer|real|char|boolean執(zhí)行語句 | | read () wri