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

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