編譯原理：第二章高級語言及其語法描述.ppt

編譯原理,第二章 高級語言及其語法描述,第二章 高級語言及其語法描述,常用的高級語言 FORTRAN 數值計算 COBOL 事務處理 PASCAL 結構程序設計 ADA 大型程序、嵌入式實時系統(tǒng) PROLOG 邏輯程序設計 ALGOL 算法語言 C/C+ 系統(tǒng)程序設計 Java Internet程序設計,與機器語言或匯編語言比較，高級語言的優(yōu)點： 較接近于數學語言和工程語言，比較直觀、自然和易于理解; 便于驗證其正確性，易于改錯; 編寫效率高; 易于移植.,2.1 程序語言的定義,程序語言是一個記號系統(tǒng) 程序語言由兩方面定義： 語法 語義 語用,一. 語法,程序本質上是一定字符集上的字符串。 語法：一組規(guī)則，用它可以形成和產生一個合式(well-formed)的程序（形式上正確的程序）。,語 法,詞法規(guī)則：單詞符號的形成規(guī)則。 單詞符號是語言中具有獨立意義的最基本結構。一般包括：常數、標識符、基本字、算符、界符等。 描述工具：有限自動機 語法規(guī)則：語法單位的形成規(guī)則。 規(guī)定了如何從單詞符號形成語法單位； 語法單位通常包括：表達式、語句、分程序、過程、函數、程序等; 描述工具：上下文無關文法,Ei EE+E EE*E E(E) 語法規(guī)則和詞法規(guī)則定義了程序的的形式結構，是判斷輸入字符串是否構成一個形式上正確的程序的依據。 定義語法單位的意義屬于語義問題。,二. 語義,對于語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法符號的意義。離開了語義的語言只是一堆符號的集合。各種語言中有形式上完全相同的語法單位，含義卻不相同。 語義：對某種語言，定義一組規(guī)則，用它可以定義一個程序的意義，稱為語義規(guī)則。 描述方法： 自然語言描述：隱藏錯誤、二義性和不完整性 形式描述：操作語義(PL/1)、 指稱語義(ADA)、 代數語義(PASCAL)。 目前大多數編譯程序使用基于屬性文法的語法制導翻譯方法來分析語義。,三程序語言的基本功能和層次結構,程序語言的基本功能：描述數據和對數據的運算。 所謂程序，本質上說是描述一定數據的處理過程。,程序的層次結構,程序 | 子程序或分程序、過程、函數 | 語句 | 表達式 | 數據引用 算符 函數調用,程序語言每個組成成分的邏輯和實現(xiàn)意義,抽象的邏輯的意義 數學意義 計算機實現(xiàn)的意義 具體實現(xiàn),2.2 高級語言的一般特性（自學）,高級語言的分類 強制式語言(Imperative Languge)也稱過程式語言：命令驅動，面向語句 FORTRAN、C、Pascal，Ada 應用式語言（Applicative Language）：注重程序所表示的功能，而不是一個語句接一個語句地執(zhí)行 LISP、ML,基于規(guī)則的語言（Rule-based Language）：檢查一定的條件，當它滿足值，則執(zhí)行適當的動作 Prolog 面向對象語言（Object-Oriented Language）：封裝性、繼承性和多態(tài)性 Smalltalk，C+，Java,2.2.1 高級語言的分類,FORTRAN 一個程序由一個主程序段和若干輔程序段組成。 輔程序段可以是子程序、函數段或數據塊。 每個程序段有一系列的說明語句和執(zhí)行語句組成。各段可以獨立編譯。 模塊結構，沒有嵌套和遞歸 各程序段中的名字相互獨立，同一個標識符在不同的程序段中代表不同的名字。,2.2.2 程序結構,主程序 PROGRAM end 輔程序1 SUBROUTINE end 輔程序2 FUNCTION end,PASCAL PASCAL程序本身可以看成是一個操作系統(tǒng)所調用的過程，過程可以嵌套和遞歸。 一個PASCAL過程： 過程頭； 說明段（由一系列的說明語句組成）； begin 執(zhí)行體（由一系列的執(zhí)行語句組成）； end,作用域：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。 允許同一個標識符在不同的過程中代表不同的名字。 名字作用域規(guī)則-“最近嵌套原則“ 一個在子程序B1中說明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一個內層子程序且B2中對標識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2對X的任何引用都是指重新說明過的這個X。,program main var A, B : real; procedure P1 var B:boolean; begin end procedure P2 var A:integer; begin end begin end,A(real),B(real),B(bool),A(integer),PASCAL提供了豐富的數據類型和運算方式，它允許用戶動態(tài)地申請和退還存貯空間。,ADA 程序包(package)：把數據和操作代碼封裝在一起，支持數據抽象。 一個程序包分為兩部分： 可見的規(guī)范說明部分，它定義了程序包外面可以訪問的對象。 程序包體，它實際定義程序包的實現(xiàn)細節(jié)。,package STACKS is type ELEM is private; type STACK is limited private; procedure push (S: in out STACK; E: in ELEM); procedure pop (S: in out STACK; E: out ELEM); end STACK; package body STACKS is procedure push(S: in out STACK; E: in ELEM); begin 實現(xiàn)細節(jié) end push; procedure pop (S: in out STACK; E: out ELEM); begin 實現(xiàn)細節(jié) end pop; end;,JAVA Java是一種面向對象的高級語言 類（Class） 繼承(Inheritance) 多態(tài)性(Polymorphism)和動態(tài)綁定(Dynamic binding),class Car int color_number; int door_number; int speed; push_break ( ) add_oil ( ) class Trash_Car extends car double amount; fill_trash ( ) ,2.2.3 數據類型與操作,一個數據類型通常包括以下三種要素： 用于區(qū)別這種類型數據對象的屬性 這種類型的數據對象可以具有的值 可以作用于這種類型的數據對象的操作,一初等數據類型 數值類型：整型、實型、復數、雙精度， 運算：+，-，*，/等 邏輯類型：布爾運算：， 字符類型：符號處理 指針類型,標識符與名字,標識符：以字母開頭的，由字母數字組成的字符串。 標識符與名字兩者有本質區(qū)別： 標識符是語法概念 名字有確切的意義和屬性,Jordan ?,標識符！,?,?,標識符與名字,名字： 值：單元中的內容 屬性：類型和作用域 名字的性質的說明方式： 由說明語句來明確規(guī)定的 隱含說明：FORTRAN 以I,J,K,N為首的名字代表整型，否則為實型。 動態(tài)確定：走到哪里，是什么，算什么,二 數據結構,1 數組 邏輯上，數組是由同一類型數據所組成的某種n維矩形結構，沿著每一維的距離，稱為下標。 數組可變與不可變：編譯時能否確定其存貯空間的大小。 訪問：給出數組名和下標值 存放方式: 按行存放,按列存放,數組元素地址計算,數組A10,20的A1，1為a，各維下標為1，按行存放，那么Ai，j地址為： a+(i-1)*20+(j-1) 數組元素地址計算公式,內情向量,把數組的有關信息記錄在一個“內情向量”中，每個數組的內情向量必須包括：維數，各維的上、下限，首地址，以及數組（元素）的類型。,2 記錄,邏輯上說，記錄結構由已知類型的數據組合在一起的一種結構。 record char NAME20; integer AGE; bool MARRIED; CARD1000 訪問：復合名 CARDk.NAME 存儲：連續(xù)存放 域的地址計算：相對于記錄結構起點的相對數OFFSET。,3 字符串、表格、棧,字符串：符號處理、公式處理 表格：本質上是一種記錄結構 線性表：一組順序化的記錄結構 棧：一種線性表，后進先出，POP, PUSH,三 抽象數據類型,一個抽象數據類型包括： 數據對象的一個集合； 作用于這些數據對象的抽象運算的集合； 這種類型對象的封裝，即，除了使用類型中所定義的運算外，用戶不能對這些對象進行操作。 程序設計語言對抽象數據類型的支持 Ada語言通過程序包（package）提供了數據封裝的支持 Smalltalk、C+和Java語言則通過類（Class）對抽象數據類型提供支持。,2.2.4 語句與控制結構,一表達式 表達式由運算量（也稱操作數，即數據引用或函數調用）和算符（操作符）組成。 形式：中綴、前綴、后綴 X*Y -A P 表達式形成規(guī)則,算符的優(yōu)先次序,一般的規(guī)定 PASCAL：左結合A+B+C=(A+B)+C FORTRAN：對于滿足左、右結合的算符可任取一種，如A+B+C就可以處理成(A+B)+C，也可以處理成A+(B+C)。 注意兩點： 代數性質能引用到什么程度視具體的語言不同而不同； 在數學上成立的代數性質在計算機上未必完全成立。,二語句,賦值語句： A := B 名字左值：該名字代表的那個單元（地址）稱為該名字的左值。(所代表的存貯單元的地址) 右值：一個名字的值稱為該名字的右值。(所代表的存貯單元的內容),控制語句：,無條件轉移語句 goto L,條件語句 if B then S if B then S1 else S2,循環(huán)語句 while B do S repeat S until B for i:=E1 step E2 until E3 do S,過程調用語句 call P(X1, X2, . ,Xn),返回語句 return (E),說明語句：定義各種不同數據類型的變量或運算，定義名字的性質。,簡單句和復合句,簡單句：不包含其他語句成分的基本句 復合句：句中有句的語句,復習：程序語言的定義,程序語言由兩方面定義： 語法：一組規(guī)則，用它可以形成和產生一個合式(well-formed)的程序 詞法規(guī)則：單詞符號的形成規(guī)則。 常數、標識符、基本字、算符、界符等。 有限自動機 語法規(guī)則：語法單位的形成規(guī)則。 表達式、語句、分程序、過程、函數、程序等; 上下文無關文法 語義:一組規(guī)則，用它可以定義一個程序的意義,復習：程序語言的基本功能和層次結構,程序語言的基本功能：描述數據和對數據的運算。 所謂程序，本質上說是描述一定數據的處理過程。,程序 | 子程序或分程序、過程、函數 | 語句 | 表達式 | 數據引用 算符 函數調用,復習：高級語言的一般特性,高級語言的分類 程序結構 數據類型與操作 初等數據類型 數據結構 抽象數據類型 語句與控制結構,2.3 程序語言的語法描述,幾個概念: 考慮一個有窮 字母表 字符集 其中每一個元素稱為一個字符（符號：是語言中最基本的不可再分的單位） 上的字(也叫字符串、符號串) 是指由中的字符所構成的一個有窮序列 不包含任何字符的序列稱為空字（空串），記為 用*表示上的所有字的全體,包含空字 例如: 設 =a， b，則 *=,a,b,aa,ab,ba,bb,aaa,.,*的子集U和V的連接（積）定義為 UV | U & V 設： U a, aa V b, bb 那么： UV= ab, abb, aab, aabb,*的子集U和V的連接（積）定義為 UV | U 記 VVV* ，稱V+是V的正規(guī)閉包。,設： U a, aa 那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, ,2.3.1 上下文無關文法,文法： 描述語言的語法結構的形式規(guī)則 He gave me a book. He me book a gave, 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,上下文無關文法的定義： 一個上下文無關文法G是一個四元式 G=(VT，VN，S，P)，其中 VT：終結符集合(非空) VN：非終結符集合(非空)，且VT VN= S：文法的開始符號，SVN P：產生式集合(有限)，每個產生式形式為 P， PVN， (VT VN)* 開始符S至少必須在某個產生式的左部出現(xiàn)一次。,例，定義只含+，*的算術表達式的文法 G=， 其中，P由下列產生式組成： E i E E+E E E*E E (E),幾點規(guī)定： “ ”也可以用“:=“表示， 這種表示稱為巴科斯范式(BNF) P 1 P 2 可縮寫為 P 1|2|n P n 其中，“|”讀成“或”，稱為P的一個候選式。 表示一個文法時，通常只給出開始符號和產生式，如上例，可表示為： G(E)： E i | E+E | E*E | (E),例，定義只含+，*的算術表達式的文法 G=， 其中，P由下列產生式組成： E i E E+E E E*E E (E),定義：稱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),通常，用 表示：從1出發(fā)，經過一步或若干步，可以推出n。,用 表示：從1出發(fā)，經過0步或若干步，可以推出n。,所以 ： 即 或,定義：假定G是一個文法，S 是它的開始符號。如果 ，則稱是一個句型。僅含終結符號的句型是一個句子。文法G所產生的句子的全體是一個語言，將它記為 L(G)。,例： (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)是句型。,例：文法G1(A)： A c|Ab G1(A)的語言? L(G1)=c，cb，cbb， 以c開頭，后繼若干個b,例：文法G2(S)： S AB A aA|a B bB|b G2(S)的語言? L(G2)=ambn|m，n0,例：給出產生語言為anbn|n1的文法。 G3(S)： S aSb S ab,例：給出產生語言為ambn|1nm2n的文法。 G4(S)： S aSb | aaSb S ab | aab,從一個句型到另一個句型的推導往往不唯一。 E+Ei+Ei+i E+EE+ii+i 最左推導：任何一步 都是對中的最左非終結符進行替換。 最右推導：任何一步 都是對中的最右非終結符進行替換。,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),如果使用最左(右)推導，則一個最左(右)推導與語法樹一一對應。 一個句型是否只對應唯一一棵語法樹？,定義：如果一個文法存在某個句子對應兩顆不同的語法樹，則說這個文法是二義的。 G(E)： E i|E+E|E*E|(E) 是二義文法。 語言的二義性：一個語言是二義性的，如果對它不存在無二義性的文法。 可能存在G和G，一個為二義的，一個為無二義的。但L(G)=L(G) 二義性問題是不可判定問題，即不存在一個算法，它能在有限步驟內，確切地判定一個文法是否是二義的。 可以找到一組無二義文法的充分條件。,二義文法： G(E)： E i|E+E|E*E|(E),表達式 項|表達式+項 項 因子 | 項*因子 因子 (表達式) | i,無二義文法： G(E)：E T | E+T T F | T*F F (E) | i,E T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T)