《編譯原理實踐及應用》第2章高級語言設計基礎

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

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

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

4、=11001 集合U、V的乘積乘積 ：UV = | U & V 長度相加即: 集合UV中的符號串是由U和V的符號串連接而成。 U = aa,bb V=00,11 則UV=?UV VU 集合的方冪方冪：n個相同集合的乘積 Vn =VVVV . V 規(guī)定V0 = 例：例：=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,aab,=a,b,aa,ab,ba,bb,aaa,aab, 集合的閉包、正閉包閉包、正閉包的閉包的閉包 * 表示上的所有符號串（包括）組成的集合。 包括長

5、度為0，1，2， 的正閉包的正閉包 + 表示 *上的除外的所有符號串組成的集合。.32=+V=0,1 V* = ? V+ = ?.32= *形式語言的概念*中的任意一個按一定規(guī)則構成的子集稱為上的一個（形式）語言（形式）語言，屬于該語言的符號串稱為該語言的句子句子。例：令LA, B, , Z, a, b, , z，D0, 1, , 9，。由于單個符號可以看成是長度為1的符號串，L和D可以分別看成是有窮的語言集。用集合的運算作用于L和D所得到新語言：（1）LD是字母和數(shù)字的集合；（2）LD是所有一個字母后隨一個數(shù)字的符號串的集合；（3）L*是所有字母串（包括）的集合；（4）L(LD )*是以字母

6、開頭的所有字母數(shù)字串的集合 2.2 文法與語言文法與語言 程序設計語言的語法結構的形式化描述稱為文法。是一種工具，用于嚴格定義句子的結構；用有窮的規(guī)則刻劃無窮的集合 文法是被用來精確而無歧義地描述語言的句子的構成方式. 文法描述語言的時候不考慮語言的含義。引引 例例例1：有如下規(guī)則 (表示由組成)|我大學生是| 現(xiàn)要求根據(jù)如上規(guī)則得出句子：我是大學生 = = = =我是大學生句子“我是大學生”也可以如下圖示分析 在有規(guī)則的情況下，每一次用上述規(guī)則的右邊去替換左邊，得到“我是大學生”是符合上述規(guī)則的句子大學生大學生我我是是上下文無關文法的形式定義上下文無關文法的形式定義 由四部分組成：終結符號：

7、是組成該語言的最基本的符號，是不可再分的基本符號,如保留字、標識符等。非終結符號：規(guī)則中用尖括號括起來的符號，表示一些語法成分，可以推導出其他的語法成分,表示一定符號串的集合，是一個類，如表達式。開始符號：規(guī)則中的一個特殊的非終結符號，語言中的句子都從它開始推導,如程序、句子產生式：定義語法成分的規(guī)則，上例中的產生式為所有規(guī)則|我大學生是|文法的形式定義文法的形式定義( (續(xù)續(xù)) ) 一個文法文法G抽象地表示為四元組 G=（Vn,Vt,P,S） 其中Vn表示非終結符號Vt表示終結符號，VnVt=(字母表)，VnVt=S是開始符號，P是產生式，形如：(V+且至少含有一個非終結符號，V*) 上例中

8、： G=（Vn,Vt,P,） Vn=（，） Vt= (我，是，大學生) P = | 我 大學生 是 |例：某語言中標識符定義的文法G=（VN，VT，P，S）其中：VN=標識符，字母，數(shù)字 VT=a,b,c,y,z,0,1,9 S = P= abz09 產生式的形式為：A 左部符號，非終結符右部，可以含有非終結符和終結符又稱為一條規(guī)則有時一個產生式不足以描述該語法范疇，就用多個產生式，如算術表達式的描述為：(遞歸定義) E E + E E E * E E i E E+E | E*E | i相同左部的一個右部又稱一個候選式上下文無關上下文無關文法所定義的語法成分獨立于它可能出現(xiàn)的環(huán)境，即不考慮上下

9、文。算術表達式的文法定義算術表達式的文法定義 變量是表達式 表達式 + 表達式是表達式 表達式 * 表達式是表達式 (表達式) 是 表達式E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i 從上下文無關文法得到某個符號串的方法從上下文無關文法得到某個符號串的方法:從文法的開始符號出發(fā),反復連續(xù)使用產生式,對左邊的非終結符進行替換和展開，直到全部為終結符為止。 例：表達式定義規(guī)則E E + E E E * E E ( E ) E i( i+i )E=( E ) =( E+E ) =( i+E ) =( i + i ) 推導推導: 連續(xù)使用產生式右部

10、去替換左部某個非終結符的過程,得到的連續(xù)序列稱為一個推導。 直接推導直接推導：又稱一步推導(用 符號=表示),就是用某條規(guī)則的右部去替換該規(guī)則的左部。 歸約：歸約：推導的逆過程稱為歸約歸約（Reduction）。 直接歸約：直接歸約：直接推導的逆過程。 幾個概念的形式定義幾個概念的形式定義 直接推導: 如果是文法 G=（Vn,Vt,P,S）的產生式，和是*中的任意符號，若有符號串v,w滿足：v=,w=,則說v直接產生w，(w是v的直接推導)記作：v=w*+例：S01, 0S0=0010(直接推導,) 如果存在v=w0=w1=w2.=Wn=w(n0)，則稱v推導出w（長度為n），記作v=w(至少

11、一步) 若有=w或v=w，則記作v=w(0步或若干步) 例3 : G = (E, i, +, *, (, ) , P , E) P： E E+E | E*E | (E) | i 表達式(i)和(i+i)*i的推導：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i E E 0步推導 E (i + i)*i 6步推導 E (i + i)*i 6步推導 E (E) 直接推導 句型句型：設(s)是一文法，如果符號串x是從開始符號推導出來的，即有s=x,則稱x是文法G(s)的一個句型。 即: 任何由開始符推導出來的符號串都是句型。

12、句子句子：若x僅由終結符號組成，則稱x為G(S)的句子* 練習練習 文法文法G：SaAcB | Bd AAaB | c BbScA | b 寫出句型寫出句型aAcbBdcc和句子和句子acabcbbdcc的的推導推導過程。過程。 文法文法G所產生的語言所產生的語言定義為： L(G)=x|S=x,其中S為文法的開始符號，xVt* 。即: 一個文法G可以推導出的所有句子構成的一個集合, 就確定了一個語言。* 例：考慮文法G: 它定義了什么語言。S bAA aA|a推導過程 ：S=bA =ba S=bA =baA=baa . S=bA =baA= =baa歸納得： L(G1) = ban | n1

13、練習：文法(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 思考：構造一個文法G3使得：L(G3) = anbn |n1 S aSbS ab a,b的個數(shù)相同,則文法G3為： 文法等價：文法等價： 若文法G1和文法G2所產生的語言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價等價。例：有如下兩個文法，判斷它們是否等價？ G1=（S，0，S，S0S，S0） G2=（S，0，S，SS0，S0）S0S0S00S0S

14、00S 0000 L(G1) = 0n | n1 對于對于G2： 對于對于G1 ：SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)，文法G1和G2等價 例3 : 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 E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*il 對給定的文法，定

15、義的語言是由利用所有的產生式經過各種方式推導出所有可能的句子構成的，并沒有規(guī)定推導使用產生式的順序。l 因此從一個句型到另一個句型(句子)的推導過程不是唯一的。 最左推導最左推導: 在整個推導過程中,任何一步推導=都是對中最左邊的非終結符進行替換。 最右推導最右推導: 在推導之前確定推導的順序，是對句子進行確定性分析所必須的例3： 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最右推導

16、過程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i文法的二義性文法的二義性 語法樹語法樹：推導的形式化表示推導的形式化表示，有助于理解句子語法結構的層次 每個結點都有一個標記，該標記屬字母集中的一個符號，根由開始符號標記。 當某個非終結符被它的某個候選式所替換時，就產生相應的下一層的結點，候選式中自左至右的每個符號對應一個新的結點，并標記它，畫出其與父結點之間的連線。例：對文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的語法樹： 在語法樹的推導過程中的任何時刻

17、，沒有后代的端末結點自左至右排列起來就是一個句型 一棵語法樹表示了一個句型很多可能的不同推導過程。(包括最左推導和最右推導)例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | 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*i+i 并不是任何情況下一個句型就唯一地對應一棵語法樹。 定義定義：如果一個文法存在某個句子對應兩棵不同的語法樹，則說這個文法是二二義義的 對二義文法中的某個句子的分析不是唯一的

18、，因此總是希望文法是無二義的。 但是二義文法有時也是有用的。證明下述文法是二義文法。 例：設if語句S的文法G=(E，S，if，then，else，a，e，P，S)，其中P為： Sif E then S （1）Sif 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),不同類型的文法只是對產生式的要求不同： 型文法型

19、文法(短文文法)： G的每個產生式滿足：V+且中至少含有一個非終結符,V*型文法型文法(上下文有關文法)：如果G的每個產生式 均滿足|=|,僅當除外，但S不得出現(xiàn)在任何產生式的右部型文法型文法(上下文無關文法)：G的每個產生式為A, A是一非終結符，V*型文法型文法(正規(guī)文法)：G的每個產生式的形式都是：AB或A，其中A,B是非終結符，是終結符串。(右線性文法)語言的層次語言的層次 這四種語言可被4種自動機識別： 0型圖靈機 1型線性界限自動機 2型下推自動機 3型有窮自動機 從外到內，四種文法對產生式的限制越來越多，語言的描述能力越來越弱 正規(guī)文法的描述能力比上下文無關文法的描述能力弱 正規(guī)

20、文法只能用于描述單詞的構成 上下文無關文法有足夠的能力描述現(xiàn)今大多數(shù)程序設計語言的語法結構例.3: L(G3) = anbn |n1 a,b的個數(shù)相同, 不能由任何正規(guī)文法產生，可以由下述上下文無關文法產生。S aSbS ab 同樣，上下文無關語言的描述能力比上下文有關語言的描述能力弱。2.3 高級語言的設計高級語言的設計 語言涉及它的設計者、實現(xiàn)者和使用者 本書主要介紹語言的實現(xiàn)，但實現(xiàn)之前必須了解所實現(xiàn)的語言的特征、結構和功能。 本節(jié)從宏觀上介紹高級語言的基本結構和共同特征，讓讀者對高級語言的認識達到新的高度，從語言使用者逐步向語言的實現(xiàn)者、設計者過渡。 例子 程序語言的定義 程序設計語言

21、的定義包括三部分： 語法是定義程序的一組形式規(guī)則，用它可以形成和產生一個形式上正確的程序； 語義也是一組規(guī)則的集合，用以定義語法正確的單詞符號和語法單位的含義； 語用主要是有關程序設計技術和語言成分的使用方法，它使語言的基本概念與語言的外界（如數(shù)學概念或計算機的對象和操作）聯(lián)系起來。 程序的本質程序的本質 程序是在數(shù)據(jù)的某些特定的表示方式和結構的基礎上對抽象算法的具體描述。 沃斯（N.wirth）以“算法+數(shù)據(jù)結構=程序” 來描述程序 程序設計語言必須以描述算法和數(shù)據(jù)結構作為他自身的主要結構。 各種高級語言均以數(shù)據(jù)類型來描述數(shù)據(jù)結構，以控制結構來描述算法。 馮.諾依曼體系結構與高級語言 馮.諾

22、依曼機的思想：一個存儲器（用來存放指令和數(shù)據(jù)），一個控制器和一個運算器（控制器負責從存儲器中逐條取出指令，運算器通過算術或邏輯操作來處理數(shù)據(jù)），最后的處理結果必須送回存儲器中。 特點： （1）數(shù)據(jù)和指令均以二進制形式存儲（它們在外形上沒有什么區(qū)別，但每位二進制數(shù)有不同的含義）； （2）程序以“存儲程序”的方式工作（即事先編寫好程序，執(zhí)行之前先將程序存放到存儲器某個可知的地方）； （3）程序順序執(zhí)行（但可強制改變執(zhí)行順序）； （4）存儲器的內容可以被修改（一旦放入新的數(shù)據(jù)，則該單元原來的數(shù)據(jù)立即消失，且被新數(shù)據(jù)代替）。 高級語言的特性： （1）變量：存儲器由大量存儲單元組成，數(shù)據(jù)就存放在這些單元

23、中，匯編語言通過對存儲單元的命名來訪問數(shù)據(jù)。在高級語言中，存儲單元及其名稱由變量的概念來代替，變量代表一個（或一組）已命名的存儲單元，存儲單元可存放變量的值。 （2）賦值：使用存儲單元概念的另一個結果是每個計算結果都必須存儲，即將其賦值到某個存儲單元，從而改變該單元的值。 （3）重復：指令存儲在有限的存儲器中，按順序執(zhí)行。若要完成復雜的計算，有效的方式就是重復執(zhí)行某些指令序列。 一個程序往往要涉及若干實體，如變量、語句和子程序等。實體具有某些特性，這些特性稱為實體的屬性。 變量的屬性有名字、類型和保留其值的存儲區(qū)等 語句的屬性是與之相關的一系列動作 子程序的屬性有名字、形參個數(shù)和類型、參數(shù)傳遞

24、方式的約定等。 在處理實體之前，必須將實體與相關的屬性聯(lián)系起來，這個聯(lián)系的過程稱為綁定綁定（Binding），每個實體的綁定信息存儲在特定的表格中。 把實體與它的某個屬性聯(lián)系起來的時刻稱為綁定時間。 一旦綁定，這種關系就一直存在，直到對這一實體的另一次綁定。 若一個綁定在運行之前（即編譯時）完成，且在運行時不會改變，則稱為靜態(tài)綁定靜態(tài)綁定（Static Binding）。 如一個綁定在運行時完成（此后可能在運行過程中被改變），則稱為動態(tài)綁定動態(tài)綁定（dynamic Binding）。 抽象 變量是高級語言中最重要的概念之一，它是一個抽象概念，是對存儲單元的抽象。馮.諾依曼機基于存儲單元組成的主

25、存儲器概念，每個存儲單元用地址來標識，可以對它進行讀或寫操作，寫操作就是指修改存儲單元的值。賦值語句就是對修改存儲單元內容的抽象。 數(shù)據(jù)類型 內部類型：數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)和指針類型數(shù)據(jù)。內部類型是對二進制位串的抽象，其基本形式對程序員是不可見的，即程序員不能直接訪問表示一個整數(shù)的位串的某個特定位。 用戶定義類型：數(shù)組、記錄、聯(lián)合、字符串、表格、棧、隊列、鏈表和樹等，基本表示形式對程序員是可見的 抽象數(shù)據(jù)類型：數(shù)據(jù)對象的一個集合，作用于這些數(shù)據(jù)對象的抽象運算的集合，以及這些類型對象的封裝，C+中的類?；颈硎緦Τ绦騿T是不可見的 語句和控制結構 程序結構表達式表達式 表達式由運算對象（數(shù)

26、據(jù)引用或函數(shù)調用）和運算符組成。 分為邏輯表達式、關系表達式和算術表達式 運算符之間的優(yōu)先關系和結合性規(guī)定了表達式的計算次序。 邏輯表達式 | |() | not | and | or 關系表達式 |=| =算術表達式|變量|()| + |-| *|/|()|語句語句 語句 說明性語句 可執(zhí)行語句 說明性語句旨在定義各種不同數(shù)據(jù)類型的變量或運算，不需要由編譯程序生成目標代碼，主要用來告訴編譯程序一些實體的屬性，供編譯程序生成目標代碼時使用。 可執(zhí)行語句旨在描述程序的動作，需要由編譯程序生成目標代碼來實現(xiàn)它的語義。 說明語句說明語句 | const 標識符 = var : |, integer|real|char|boolean執(zhí)行語句 | | read () write ()= | | begin end程序和子程