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

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

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

4、1 集合U與V的乘積乘積 ：UV = | U & V 即: 集合UV是由U中的任一符號串與V中的任一符號串連接而成的符號串集合。 例：設U = aa,bb ，V=00,11 則UV=?UV VU 集合V的n次方冪方冪：V自身的n次乘積 Vn =VVVV . V 規定V0 = 例：設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= *形式語言的概念*中的任意一個按一定規則構成的子集稱為上的一個（形式）語言（形式）語言，屬于該語言的符號串稱為該語言的句子句子。例：令LA, B, , Z, a, b, , z，D0, 1, , 9，。由于單個符號可以看成是長度為1的符號串，L和D可以分別看成是有窮的語言集。用集合的運算作用于L和D所得到6種

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

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

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

9、 是 |例2.3：某語言中標識符定義的文法G=（VN，VT，P，S）其中：VN=標識符，字母，數字 VT=a,b,c,y,z,0,1,9 S = P= abz09 產生式的形式為：A 左部符號，非終結符右部，可以含有非終結符和終結符又稱為一條規則。l注：有時不用將文法G的四元組顯式地表示出來，而只將產生式寫出。l書寫產生式的約定： 第一條產生式的左部是開始符號； 用大寫字母表示非終結符，小寫字母表示終結符； 用小寫希臘字母（如、和）代表文法的符號串； 如果S是文法G的開始符號，也可將文法G寫成GS。 有時為書寫簡潔，常把相同左部的產生式進行縮寫。如： 其中，每個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 某語言算術表達式的文法定義某語言算術表達式的文法定義 變量是表達式 表達式 + 表達式是表達式 表達式 * 表達式是表達式 (表達式) 是 表達式E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i若用E表示表達式，i表示變量，則表達式的文法可以表示為：簡寫為2.2.2 文法

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

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

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

14、ba S=bA =baA=baa . S=bA =baA= =baa歸納得： L(G1) = ban | n1 練習：文法(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使得：L(G) = anbn |n1 S aSbS ab a,b的個數相同,則文法G為： 文法等價：文法等價： 若文法G1和文法G2所產生的語言相同，即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 表達式 (i+i)*i的推導過程： (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 對給定的文法，定義的語言是由利用所有的產生式經過各種方式推導出所有可能的句子構成的，并沒有規定推導使用產生式的順序。l 因此從一個句型到另一個句型(句子)的推導過程不是唯一的。文法的二義性文法的二義性 語法樹語法樹（分析樹）（分析樹）：推導的形式化表示推導的形式化表示，有助于理解句子語法結構的層次 每個結點都有一個標記，該標記屬字母集中的一個符號，根由開始符號標記。 隨著推導，當某個非終結符被它的某個候選式所替換時，就產生相應的下一層的結點，候選式中自左至右的每個符號對應一個新的結點，并標記它，畫出其與

17、父結點之間的連線。 末結點從左到右排列起來構成一個句型。 如果自左至右端末結點排列起來都是終結符，則這顆樹表示了一個句子的推導過程。例：對文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的最左推導的語法樹是？ 在語法樹的推導過程中的任何時刻，沒有后代的端末結點自左至右排列起來就是一個句型 一棵語法樹表示了一個句型很多可能的不同推導過程。(包括最左推導和最右推導)例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 注意：并不是任何情況一個句型就唯一地對應一棵語法樹。正常優先級+優先 定義定義：如果一個文法存在某個句型對應兩棵或兩顆以上的語法樹，則稱這個文法是二義二義文法文法。 對二義文法中的某個句子的分析（最左或最右推導）不是唯一的，因此有些程序設計語言的分析器要求文法是無二義的。例2.9 證明下述文法是二義文法。 設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）推導(1)：S if E then S if E then if E then S else S推導(2)：S if E then S else S if E then if E then S else S文法的分類文法的分類 文法有四種，不同類型的文法只是對產生式的要求不同。 設G=(VN,VT,P,S)，其中,(VNVT)*型文法型文法(短文文法)： 對產生式只要求中至少含有一個非終結符。（對每個產生式不加任何限制）型文法型文法(上下文有關文法)：每個產生式限制為形如1A212, 其中1,2,(VNVT)*,AVN,型文法型文法

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

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

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

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

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

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

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