1、編譯原理第二高級語言及其語法描述第1頁，共74頁，2022年，5月20日，20點32分，星期二第二章 高級語言及其語法描述 常用的高級語言 FORTRAN數值計算 COBOL事務處理 PASCAL結構程序設計 ADA大型程序、嵌入式實時系統 PROLOG邏輯程序設計 ALGOL算法語言 C/C+系統程序設計 JavaInternet程序設計第2頁，共74頁，2022年，5月20日，20點32分，星期二與機器語言或匯編語言比較，高級語言的優點：較接近于數學語言和工程語言，比較直觀、自然和易于理解;便于驗證其正確性，易于改錯;編寫效率高;易于移植.第3頁，共74頁，2022年，5月20日，20點3

2、2分，星期二2.1 程序語言的定義程序語言是一個記號系統程序語言由兩方面定義：語法語義語用第4頁，共74頁，2022年，5月20日，20點32分，星期二一. 語法程序本質上是一定字符集上的字符串。語法：一組規則，用它可以形成和產生一個合式(well-formed)的程序（形式上正確的程序）。第5頁，共74頁，2022年，5月20日，20點32分，星期二語 法詞法規則：單詞符號的形成規則。單詞符號是語言中具有獨立意義的最基本結構。一般包括：常數、標識符、基本字、算符、界符等。描述工具：有限自動機語法規則：語法單位的形成規則。規定了如何從單詞符號形成語法單位；語法單位通常包括：表達式、語句、分程序

3、、過程、函數、程序等;描述工具：上下文無關文法第6頁，共74頁，2022年，5月20日，20點32分，星期二 EiEE+EEE*EE(E)語法規則和詞法規則定義了程序的的形式結構，是判斷輸入字符串是否構成一個形式上正確的程序的依據。定義語法單位的意義屬于語義問題。第7頁，共74頁，2022年，5月20日，20點32分，星期二二. 語義對于語言來說，不僅要給出它的詞法、語法規則，而且要定義它的單詞符號和語法符號的意義。離開了語義的語言只是一堆符號的集合。各種語言中有形式上完全相同的語法單位，含義卻不相同。語義：對某種語言，定義一組規則，用它可以定義一個程序的意義，稱為語義規則。描述方法：自然語言

4、描述：隱藏錯誤、二義性和不完整性形式描述：操作語義(PL/1)、 指稱語義(ADA)、 代數語義(PASCAL)。目前大多數編譯程序使用基于屬性文法的語法制導翻譯方法來分析語義。第8頁，共74頁，2022年，5月20日，20點32分，星期二三程序語言的基本功能和層次結構程序語言的基本功能：描述數據和對數據的運算。所謂程序，本質上說是描述一定數據的處理過程。第9頁，共74頁，2022年，5月20日，20點32分，星期二程序的層次結構程序|子程序或分程序、過程、函數|語句|表達式|數據引用 算符 函數調用第10頁，共74頁，2022年，5月20日，20點32分，星期二程序語言每個組成成分的邏輯和實

5、現意義 抽象的邏輯的意義數學意義 計算機實現的意義具體實現第11頁，共74頁，2022年，5月20日，20點32分，星期二2.2 高級語言的一般特性（自學） 高級語言的分類 強制式語言(Imperative Languge)也稱過程式語言：命令驅動，面向語句FORTRAN、C、Pascal，Ada 應用式語言（Applicative Language）：注重程序所表示的功能，而不是一個語句接一個語句地執行LISP、ML 第12頁，共74頁，2022年，5月20日，20點32分，星期二基于規則的語言（Rule-based Language）：檢查一定的條件，當它滿足值，則執行適當的動作Prolo

6、g 面向對象語言（Object-Oriented Language）：封裝性、繼承性和多態性Smalltalk，C+，Java 2.2.1 高級語言的分類 第13頁，共74頁，2022年，5月20日，20點32分，星期二FORTRAN一個程序由一個主程序段和若干輔程序段組成。輔程序段可以是子程序、函數段或數據塊。每個程序段有一系列的說明語句和執行語句組成。各段可以獨立編譯。 模塊結構，沒有嵌套和遞歸各程序段中的名字相互獨立，同一個標識符在不同的程序段中代表不同的名字。2.2.2 程序結構第14頁，共74頁，2022年，5月20日，20點32分，星期二主程序 PROGRAM end輔程序1 SU

7、BROUTINE end輔程序2 FUNCTION end第15頁，共74頁，2022年，5月20日，20點32分，星期二PASCALPASCAL程序本身可以看成是一個操作系統所調用的過程，過程可以嵌套和遞歸。一個PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執行體（由一系列的執行語句組成）；end第16頁，共74頁，2022年，5月20日，20點32分，星期二作用域：一個名字能被使用的區域范圍稱作這個名字的作用域。允許同一個標識符在不同的過程中代表不同的名字。名字作用域規則-最近嵌套原則一個在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個內

8、層子程序且B2中對標識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2對X的任何引用都是指重新說明過的這個X。第17頁，共74頁，2022年，5月20日，20點32分，星期二program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integer)第18頁，共74頁，2022年，5月20日，20點32分，星期二PASCAL提供了豐富的數據類型和

9、運算方式，它允許用戶動態地申請和退還存貯空間。第19頁，共74頁，2022年，5月20日，20點32分，星期二ADA程序包(package)：把數據和操作代碼封裝在一起，支持數據抽象。一個程序包分為兩部分：可見的規范說明部分，它定義了程序包外面可以訪問的對象。程序包體，它實際定義程序包的實現細節。第20頁，共74頁，2022年，5月20日，20點32分，星期二package STACKS is type ELEM is private; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); pr

10、ocedure pop (S: in out STACK; E: out ELEM); end STACK;package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin 實現細節 end push; procedure pop (S: in out STACK; E: out ELEM); begin 實現細節 end pop;end; 第21頁，共74頁，2022年，5月20日，20點32分，星期二JAVAJava是一種面向對象的高級語言類（Class）繼承(Inheritance)多態性(Polymorp

11、hism)和動態綁定(Dynamic binding)第22頁，共74頁，2022年，5月20日，20點32分，星期二class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) 第23頁，共74頁，2022年，5月20日，20點32分，星期二2.2.3 數據類型與操作 一個數據類型通常包括以下三種要素：用于區別這種類型數據對象的屬性這種類型的數據對象可以具有的值可以作用于這種

12、類型的數據對象的操作第24頁，共74頁，2022年，5月20日，20點32分，星期二一初等數據類型數值類型：整型、實型、復數、雙精度， 運算：+，-，*，/等邏輯類型：布爾運算：，字符類型：符號處理指針類型第25頁，共74頁，2022年，5月20日，20點32分，星期二標識符與名字標識符：以字母開頭的，由字母數字組成的字符串。標識符與名字兩者有本質區別：標識符是語法概念名字有確切的意義和屬性第26頁，共74頁，2022年，5月20日，20點32分，星期二Jordan ?標識符！?第27頁，共74頁，2022年，5月20日，20點32分，星期二標識符與名字名字：值：單元中的內容屬性：類型和作用域

13、名字的性質的說明方式：由說明語句來明確規定的隱含說明：FORTRAN 以I,J,K,N為首的名字代表整型，否則為實型。動態確定：走到哪里，是什么，算什么 第28頁，共74頁，2022年，5月20日，20點32分，星期二二 數據結構1 數組邏輯上，數組是由同一類型數據所組成的某種n維矩形結構，沿著每一維的距離，稱為下標。數組可變與不可變：編譯時能否確定其存貯空間的大小。訪問：給出數組名和下標值存放方式: 按行存放,按列存放第29頁，共74頁，2022年，5月20日，20點32分，星期二數組元素地址計算數組A10,20的A1，1為a，各維下標為1，按行存放，那么Ai，j地址為：a+(i-1)*20

14、+(j-1)數組元素地址計算公式第30頁，共74頁，2022年，5月20日，20點32分，星期二第31頁，共74頁，2022年，5月20日，20點32分，星期二內情向量把數組的有關信息記錄在一個“內情向量”中，每個數組的內情向量必須包括：維數，各維的上、下限，首地址，以及數組（元素）的類型。第32頁，共74頁，2022年，5月20日，20點32分，星期二2 記錄邏輯上說，記錄結構由已知類型的數據組合在一起的一種結構。record char NAME20; integer AGE; bool MARRIED; CARD1000訪問：復合名 CARDk.NAME存儲：連續存放域的地址計算：相對于記

15、錄結構起點的相對數OFFSET。第33頁，共74頁，2022年，5月20日，20點32分，星期二3 字符串、表格、棧字符串：符號處理、公式處理表格：本質上是一種記錄結構線性表：一組順序化的記錄結構棧：一種線性表，后進先出，POP, PUSH第34頁，共74頁，2022年，5月20日，20點32分，星期二三 抽象數據類型 一個抽象數據類型包括：數據對象的一個集合；作用于這些數據對象的抽象運算的集合；這種類型對象的封裝，即，除了使用類型中所定義的運算外，用戶不能對這些對象進行操作。程序設計語言對抽象數據類型的支持Ada語言通過程序包（package）提供了數據封裝的支持Smalltalk、C+和J

16、ava語言則通過類（Class）對抽象數據類型提供支持。 第35頁，共74頁，2022年，5月20日，20點32分，星期二2.2.4 語句與控制結構一表達式表達式由運算量（也稱操作數，即數據引用或函數調用）和算符（操作符）組成。形式：中綴、前綴、后綴 X*Y -A P表達式形成規則第36頁，共74頁，2022年，5月20日，20點32分，星期二算符的優先次序一般的規定PASCAL：左結合A+B+C=(A+B)+CFORTRAN：對于滿足左、右結合的算符可任取一種，如A+B+C就可以處理成(A+B)+C，也可以處理成A+(B+C)。注意兩點：代數性質能引用到什么程度視具體的語言不同而不同；在數學

17、上成立的代數性質在計算機上未必完全成立。第37頁，共74頁，2022年，5月20日，20點32分，星期二二語句賦值語句： A := B 名字左值：該名字代表的那個單元（地址）稱為該名字的左值。(所代表的存貯單元的地址)右值：一個名字的值稱為該名字的右值。(所代表的存貯單元的內容)第38頁，共74頁，2022年，5月20日，20點32分，星期二控制語句： 無條件轉移語句 goto L條件語句 if B then S if B then S1 else S2循環語句 while B do S repeat S until B for i:=E1 step E2 until E3 do S過程調用語

18、句 call P(X1, X2, . ,Xn)返回語句 return (E)第39頁，共74頁，2022年，5月20日，20點32分，星期二說明語句：定義各種不同數據類型的變量或運算，定義名字的性質。第40頁，共74頁，2022年，5月20日，20點32分，星期二簡單句和復合句簡單句：不包含其他語句成分的基本句復合句：句中有句的語句第41頁，共74頁，2022年，5月20日，20點32分，星期二復習：程序語言的定義程序語言由兩方面定義：語法：一組規則，用它可以形成和產生一個合式(well-formed)的程序詞法規則：單詞符號的形成規則。常數、標識符、基本字、算符、界符等。有限自動機語法規則：

19、語法單位的形成規則。表達式、語句、分程序、過程、函數、程序等;上下文無關文法語義:一組規則，用它可以定義一個程序的意義第42頁，共74頁，2022年，5月20日，20點32分，星期二復習：程序語言的基本功能和層次結構程序語言的基本功能：描述數據和對數據的運算。所謂程序，本質上說是描述一定數據的處理過程。程序|子程序或分程序、過程、函數|語句|表達式|數據引用 算符 函數調用第43頁，共74頁，2022年，5月20日，20點32分，星期二復習：高級語言的一般特性 高級語言的分類 程序結構數據類型與操作初等數據類型數據結構抽象數據類型語句與控制結構第44頁，共74頁，2022年，5月20日，20點

20、32分，星期二2.3 程序語言的語法描述 幾個概念:考慮一個有窮 字母表 字符集其中每一個元素稱為一個字符（符號：是語言中最基本的不可再分的單位）上的字(也叫字符串、符號串) 是指由中的字符所構成的一個有窮序列不包含任何字符的序列稱為空字（空串），記為用*表示上的所有字的全體,包含空字例如: 設 =a， b，則 *=,a,b,aa,ab,ba,bb,aaa,.第45頁，共74頁，2022年，5月20日，20點32分，星期二*的子集U和V的連接（積）定義為UV | U & V 設：U a, aa V b, bb 那么：UV= ab, abb, aab, aabb 第46頁，共74頁，2022年，

21、5月20日，20點32分，星期二*的子集U和V的連接（積）定義為UV | U & V V自身的 n次積記為Vn=VVV規定V0=，令 V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規閉包。第47頁，共74頁，2022年，5月20日，20點32分，星期二設：U a, aa 那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, 第48頁，共74頁，2022年，5月20日，20點32分，星期二2.3.1 上下文無關文法文法： 描述語言的語法結構的形式規則He gave me a book. He me book a gave第

22、49頁，共74頁，2022年，5月20日，20點32分，星期二 He me book a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book第50頁，共74頁，2022年，5月20日，20點32分，星期二上下文無關文法的定義： 一個上下文無關文法G是一個四元式 G=(VT，VN，S，P)，其中VT：終結符集合(非空)VN：非終結符集合(非空)，且VT VN=S：文法的開始符號，SVNP：產生式集合(有限)，每個產生式形式為P， PVN， (VT VN)*開始符S至少必須在某個產生式的左部

23、出現一次。第51頁，共74頁，2022年，5月20日，20點32分，星期二例，定義只含+，*的算術表達式的文法 G=， 其中，P由下列產生式組成：E iE E+EE E*EE (E)第52頁，共74頁，2022年，5月20日，20點32分，星期二幾點規定：“ ”也可以用“:=表示， 這種表示稱為巴科斯范式(BNF) P 1 P 2 可縮寫為 P 1|2|n P n 其中，“|”讀成“或”，稱為P的一個候選式。表示一個文法時，通常只給出開始符號和產生式，如上例，可表示為：G(E)： E i | E+E | E*E | (E)例，定義只含+，*的算術表達式的文法 G=， 其中，P由下列產生式組成：

24、E iE E+EE E*EE (E)第53頁，共74頁，2022年，5月20日，20點32分，星期二定義：稱A直接推出，即A 僅當A 是一個產生式， 且， (VT VN)* 。如果1 2 n，則我們稱這個序列是從1到n的一個推導。若存在一個從1到n的推導，則稱1可以推導出n 。對文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)第54頁，共74頁，2022年，5月20日，20點32分，星期二通常，用 表示：從1出發，經過一步或若干步，可以推出n。 用 表示：從1出發，經過0步或若干步，可以推出n。 所以 ： 即 或定義：假定G是一個文法，S

25、 是它的開始符號。如果 ，則稱是一個句型。僅含終結符號的句型是一個句子。文法G所產生的句子的全體是一個語言，將它記為 L(G)。第55頁，共74頁，2022年，5月20日，20點32分，星期二例： (i*i+i)是文法G(E)： E i | E+E | E*E | (E)的一個句子。 證明： E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E，(E)，(E*E+E)，(i*i+i)是句型。第56頁，共74頁，2022年，5月20日，20點32分，星期二例：文法G1(A)：A c|AbG1(A)的語言?L(G1)=c，cb，cbb，以c開頭，后繼若干個b第

26、57頁，共74頁，2022年，5月20日，20點32分，星期二例：文法G2(S)：S ABA aA|aB bB|bG2(S)的語言?L(G2)=ambn|m，n0第58頁，共74頁，2022年，5月20日，20點32分，星期二例：給出產生語言為anbn|n1的文法。 G3(S)： S aSb S ab第59頁，共74頁，2022年，5月20日，20點32分，星期二例：給出產生語言為ambn|1nm2n的文法。 G4(S)： S aSb | aaSb S ab | aab 第60頁，共74頁，2022年，5月20日，20點32分，星期二從一個句型到另一個句型的推導往往不唯一。 E+Ei+Ei+i

27、 E+EE+ii+i最左推導：任何一步 都是對中的最左非終結符進行替換。 最右推導：任何一步 都是對中的最右非終結符進行替換。第61頁，共74頁，2022年，5月20日，20點32分，星期二2.3.2 語法樹與二義性用一張圖表示一個句型的推導,稱為語法樹。(i*i+i)的語法樹E (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)一棵語法樹是不同推導過程的共性抽象。G(E)：E i|E+E|E*E|(E)(i*i+i)第62頁，共74頁，2022年，5月20日，20點32分，星期二如果使用最左(右)推

28、導，則一個最左(右)推導與語法樹一一對應。一個句型是否只對應唯一一棵語法樹？第63頁，共74頁，2022年，5月20日，20點32分，星期二定義：如果一個文法存在某個句子對應兩顆不同的語法樹，則說這個文法是二義的。G(E)： E i|E+E|E*E|(E) 是二義文法。語言的二義性：一個語言是二義性的，如果對它不存在無二義性的文法。可能存在G和G，一個為二義的，一個為無二義的。但L(G)=L(G)二義性問題是不可判定問題，即不存在一個算法，它能在有限步驟內，確切地判定一個文法是否是二義的。可以找到一組無二義文法的充分條件。第64頁，共74頁，2022年，5月20日，20點32分，星期二二義文法：G(E)： E i|E+E|E*E|(E)表達式 項|表達式+項項 因子 | 項*因子因子 (表達式) | i無二義文法： G(E)：E T | E+T T F | T*F F (E) | i第65頁，共74頁，2022年，5月20日，20點32分，星期二)EEEFFTTTTi+*(EFiiE T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i)考慮句子(i*i+i)第66頁，共74頁，2022年