編譯原理：第二章高級(jí)語(yǔ)言及其語(yǔ)法描述.ppt

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