第2章高級(jí)語言及其語法描述本章概述高級(jí)語言的結(jié)構(gòu)和主要的共同特征，并介紹程序語言的語法描述方法。要學(xué)習(xí)和構(gòu)造編譯程序，理解和定義高級(jí)語言是必不可少的與機(jī)器語言或匯編語言比較，高級(jí)語言的優(yōu)點(diǎn)：較接近數(shù)學(xué)語言和工程語言，比較直觀、自然和易于理解便于驗(yàn)證其正確性，易于改錯(cuò)編寫效率高易于移植2常用的高級(jí)語言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ì)31程序語言的定義2高級(jí)語言的一般特性3程序語言的語法描述4任何語言實(shí)現(xiàn)的基礎(chǔ)是語言的定義在語言定義方面：語言用戶把語言定義理解為用戶使用手冊(cè)而編譯程序研制者與一般用戶有所不同，他們對(duì)哪些構(gòu)造允許出現(xiàn)更感興趣。即使一時(shí)不能看出某種構(gòu)造的實(shí)際應(yīng)用，或者判斷實(shí)現(xiàn)該結(jié)構(gòu)會(huì)導(dǎo)致嚴(yán)重的困難，但仍必須嚴(yán)格根據(jù)語言的定義實(shí)現(xiàn)它程序語言主要由兩方面定義：語法語義1程序語言的定義5語法任何語言程序都可以看成是一定字符集（稱為字母表）上的字符串（有限序列）。但是，什么樣的字符串才算是一個(gè)合式的程序呢所謂一個(gè)語言的語法是指這樣的一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合式(well-formed)的程序。這些規(guī)則一部分稱為詞法規(guī)則，另一部分稱為語法規(guī)則（或產(chǎn)生規(guī)則）不規(guī)范的總結(jié)：語法=形式結(jié)構(gòu)=詞法規(guī)則+語法規(guī)則=合式的程序1程序語言的定義6語法詞法規(guī)則：單詞符號(hào)的形成規(guī)則單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等描述工具：有限自動(dòng)機(jī)語法規(guī)則：語法單位的形成規(guī)則語法單位通常包括：表達(dá)式、語句、分程序、過程、函數(shù)、程序等描述工具：上下文無關(guān)文法1程序語言的定義7語法語法規(guī)則和詞法規(guī)則定義了程序的的形式結(jié)構(gòu)。定義語法單位的意義屬于語義問題A→0|0B B→1CC→0|0BE→iE→E+EE→E*EE→(E)1程序語言的定義8語義對(duì)于一個(gè)語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號(hào)和語法單位的意義。這就是語義問題離開語義，語言只不過是一堆符號(hào)的集合。在許多語言中有形式上完全相同的語法單位（一樣的源代碼字符串片段），但含義卻不一樣。例如：加減乘除運(yùn)算的結(jié)合律和交換律方向不同是否允許函數(shù)計(jì)算產(chǎn)生副作用相同until語句的不同翻譯語義是指這樣的一組規(guī)則，使用它可以定義一個(gè)程序的意義目前還沒有公認(rèn)的形式系統(tǒng)可自動(dòng)構(gòu)造出實(shí)用的編譯程序我們采用基于屬性文法的語法制導(dǎo)翻譯方法。雖然這還不是一種形式系統(tǒng)，但比較接近形式化1程序語言的定義9語義一個(gè)程序語言的基本功能是描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序，從本質(zhì)上來說是描述一定數(shù)據(jù)的處理過程程序的層次結(jié)構(gòu)：1程序語言的定義程序子程序或分程序語句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用10語義自上而下看上述層次結(jié)構(gòu)：頂端是程序本身，它是完整的執(zhí)行單位。一個(gè)程序通常是由若干個(gè)子程序或分程序組成的，它們常常含有自己的數(shù)據(jù)（局部名）。子程序或分程序是由于語句組成的。而組成語句的成分是各種類型的表達(dá)式。表達(dá)式是描述數(shù)據(jù)運(yùn)算的基本結(jié)構(gòu)，它通常含有數(shù)據(jù)引用、算符和函數(shù)調(diào)用自下而上看上述層次結(jié)構(gòu)：我們希望通過對(duì)下層成分的理解來掌握上層成分，從而掌握整個(gè)程序1程序語言的定義11語義程序語言的每個(gè)組成成分都有（抽象的）邏輯和計(jì)算機(jī)實(shí)現(xiàn)兩方面的意義：當(dāng)從數(shù)學(xué)上考慮時(shí)，我們注重它的邏輯意義當(dāng)從計(jì)算機(jī)角度來看時(shí)，我們注重它在機(jī)內(nèi)的表示和實(shí)現(xiàn)的可能性與效率舉例：一個(gè)表示實(shí)數(shù)的名字從邏輯上說，可以看成是一個(gè)變量或一個(gè)可用于保存實(shí)數(shù)的場所從計(jì)算機(jī)實(shí)現(xiàn)上說，可以看成是一個(gè)或若干個(gè)相繼的存儲(chǔ)單元，這些存儲(chǔ)單元的每位都有特殊的解釋（如符號(hào)位、階碼和尾數(shù)），它們能表示一個(gè)一定大小和精度的數(shù)值1程序語言的定義121程序語言的定義2高級(jí)語言的一般特性3程序語言的語法描述13高級(jí)語言的分類程序結(jié)構(gòu)數(shù)據(jù)類型與操作語句與控制結(jié)構(gòu)2高級(jí)語言的一般特性14高級(jí)語言的分類強(qiáng)制式語言(ImperativeLanguge)也稱過程式語言：命令驅(qū)動(dòng)，面向語句如：FORTRAN、C、Pascal，Ada應(yīng)用式語言（ApplicativeLanguage）：注重程序所表示的功能，而不是一個(gè)接一個(gè)語句地執(zhí)行如：LISP、ML基于規(guī)則的語言（Rule-basedLanguage）：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作如：Prolog面向?qū)ο笳Z言（Object-OrientedLanguage）：封裝性、繼承性和多態(tài)性如：Smalltalk，C++，Java2高級(jí)語言的一般特性15程序結(jié)構(gòu)FORTRAN一個(gè)程序由一個(gè)主程序段和若干輔程序段組成輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊每個(gè)程序段有一系列的說明語句和執(zhí)行語句組成。各段可以獨(dú)立編譯模塊結(jié)構(gòu)，沒有嵌套和遞歸各程序段中的名字相互獨(dú)立，同一個(gè)標(biāo)識(shí)符在不同的程序段中代表不同的名字2高級(jí)語言的一般特性16程序結(jié)構(gòu)FORTRAN2高級(jí)語言的一般特性主程序 PROGRAM… …end輔程序1

SUBROUTINE… …end輔程序2

FUNCTION… …end17程序結(jié)構(gòu)PASCALPASCAL程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個(gè)PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end2高級(jí)語言的一般特性18程序結(jié)構(gòu)PASCAL作用域：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。允許同一個(gè)標(biāo)識(shí)符在不同的過程中代表不同的名字名字作用域規(guī)則："最近嵌套原則"一個(gè)在子程序B1中說明的名字X只在B1中有效（局部于B1）如果B2是B1的一個(gè)內(nèi)層子程序且B2中對(duì)標(biāo)識(shí)符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對(duì)X重新作了說明，那么，B2對(duì)X的任何引用都是指重新說明過的這個(gè)X2高級(jí)語言的一般特性19程序結(jié)構(gòu)PASCAL2高級(jí)語言的一般特性programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integer)20程序結(jié)構(gòu)PASCALPASCAL提供了豐富的數(shù)據(jù)類型和運(yùn)算方式，它允許用戶動(dòng)態(tài)地申請(qǐng)和退還存貯空間2高級(jí)語言的一般特性21程序結(jié)構(gòu)ADA程序包(package)：把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象一個(gè)程序包分為兩部分：可見的規(guī)范說明部分，它定義了程序包外面可以訪問的對(duì)象程序包體，它實(shí)際定義程序包的實(shí)現(xiàn)細(xì)節(jié)2高級(jí)語言的一般特性22程序結(jié)構(gòu)ADA2高級(jí)語言的一般特性packageSTACKSis typeELEMisprivate; typeSTACKislimitedprivate; procedurepush(S:inoutSTACK;E:inELEM); procedurepop(S:inoutSTACK;E:outELEM); …endSTACK;packagebodySTACKSis procedurepush(S:inoutSTACK;E:inELEM); begin ……實(shí)現(xiàn)細(xì)節(jié) endpush; procedurepop(S:inoutSTACK;E:outELEM); begin ……實(shí)現(xiàn)細(xì)節(jié) endpop;end;23程序結(jié)構(gòu)JAVAJava是一種面向?qū)ο蟮母呒?jí)語言類（Class）繼承(Inheritance)多態(tài)性(Polymorphism)和動(dòng)態(tài)綁定(Dynamicbinding)2高級(jí)語言的一般特性24程序結(jié)構(gòu)JAVA2高級(jí)語言的一般特性classCar{ intcolor_number; intdoor_number; intspeed; … push_break(){ … } add_oil(){ … }}

classTrash_Carextendscar{ doubleamount; fill_trash(){ … }}25數(shù)據(jù)類型與操作一個(gè)數(shù)據(jù)類型通常包括以下三種要素：用于區(qū)別這種類型數(shù)據(jù)對(duì)象的屬性這種類型的數(shù)據(jù)對(duì)象可以具有的值可以作用于這種類型的數(shù)據(jù)對(duì)象的操作2高級(jí)語言的一般特性26數(shù)據(jù)類型與操作初等數(shù)據(jù)類型數(shù)值類型：可施行算術(shù)運(yùn)算：+，-，*，/等整型、實(shí)型、復(fù)數(shù)、雙精度邏輯類型：可施行布爾運(yùn)算：∨，∧，┑等字符類型：可施行符號(hào)處理指針類型：指針的值指向另一些數(shù)據(jù)。假定P是指針，P:=addr(X)意味著P指向X，或說P的值將是變量X的地址有些語言用P↑表示指針P的內(nèi)容。在P:=addr(X)的情況下，如令P↑:=0.3，則意味著X的值是0.32高級(jí)語言的一般特性27數(shù)據(jù)類型與操作初等數(shù)據(jù)類型標(biāo)識(shí)符與名字標(biāo)識(shí)符：以字母開頭的，由字母數(shù)字組成的字符串標(biāo)識(shí)符與名字兩者有本質(zhì)區(qū)別：標(biāo)識(shí)符只是語法概念名字有確切的意義和屬性2高級(jí)語言的一般特性28數(shù)據(jù)類型與操作初等數(shù)據(jù)類型標(biāo)識(shí)符與名字2高級(jí)語言的一般特性Jordan?29數(shù)據(jù)類型與操作初等數(shù)據(jù)類型標(biāo)識(shí)符與名字名字：值：單元中的內(nèi)容屬性：類型和作用域名字的性質(zhì)的說明方式：靜態(tài)確定：由說明語句來明確規(guī)定的隱含說明：FORTRAN中以I,J,K,…N為首的名字代表整型，否則為實(shí)型動(dòng)態(tài)確定：走到哪里，是什么，算什么2高級(jí)語言的一般特性30數(shù)據(jù)類型與操作初等數(shù)據(jù)類型用計(jì)算機(jī)術(shù)語來說，名字可以看成是代表一個(gè)抽象的存儲(chǔ)單元。這個(gè)單元的內(nèi)容則認(rèn)為是此名字的值。名字的值就是它所表示的對(duì)象此外，我們還必須指出名字的屬性一個(gè)名字的屬性包括類型和作用域：名字的類型決定了它能具有什么樣的值，值在計(jì)算機(jī)內(nèi)的表示方式，以及對(duì)他能施加什么運(yùn)算名字的作用域規(guī)定了他的值存在范圍只有在作用域內(nèi)，名字才有對(duì)應(yīng)的存儲(chǔ)單元2高級(jí)語言的一般特性31數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)許多程序語言提供了一種由初級(jí)數(shù)據(jù)定義復(fù)雜數(shù)據(jù)的手段。下面我們將概述其中常見的定義方式：數(shù)組邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)，沿著每一維的距離，稱為下標(biāo)數(shù)組可變與不可變：編譯時(shí)能否確定其存貯空間的大小訪問：給出數(shù)組名和下標(biāo)值存放方式：按行存放，按列存放2高級(jí)語言的一般特性32數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)數(shù)組編譯程序要做的就是實(shí)現(xiàn)地址計(jì)算公式，使數(shù)組元素得到正確的引用在編譯過程中，當(dāng)碰到數(shù)組說明時(shí)，必須把數(shù)組的有關(guān)的信息記錄在一個(gè)“內(nèi)情向量”之中，以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息每個(gè)數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上下限，首地址，以及數(shù)組元素的類型等2高級(jí)語言的一般特性33數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)數(shù)組數(shù)組元素地址計(jì)算：數(shù)組A[10,20]的A[1，1]為a，各維下標(biāo)為1，按行存放，那么A[i，j]地址為：a+(i-1)*20+(j-1)2高級(jí)語言的一般特性34數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)數(shù)組數(shù)組元素地址計(jì)算公式：2高級(jí)語言的一般特性35數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)數(shù)組內(nèi)情向量包括：維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的類型2高級(jí)語言的一般特性atypeCndnunln………d2u2l2d1u1l136數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)記錄從邏輯上說，記錄結(jié)構(gòu)是由已知類型的數(shù)據(jù)組合起來的一種結(jié)構(gòu)如：Pascal語言采用下面形式定義記錄：CARD:recordNAME:array[1…20]ofchar;

AGE:integer;

MARRIED:booleanend;2高級(jí)語言的一般特性37數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)記錄假定CARD的首地址為a，那么：CARD.NAME 地址為 aCARD.AGE 地址為 a+20CARD.MARRIED 地址為 a+24每個(gè)CARD記錄需用25B，由于整型量AGE必須從字（4B大?。┑倪吔玳_始。因此每個(gè)CARD記錄最好用28B。其中MARRIED占4B僅用1B，浪費(fèi)3B2高級(jí)語言的一般特性38數(shù)據(jù)類型與操作數(shù)據(jù)結(jié)構(gòu)字符串、表格、棧和隊(duì)列字符串：符號(hào)處理、公式處理表格：本質(zhì)上是一種記錄結(jié)構(gòu)線性表：一組順序化的記錄結(jié)構(gòu)棧：一種線性表，后進(jìn)先出，POP，PUSH2高級(jí)語言的一般特性39數(shù)據(jù)類型與操作抽象數(shù)據(jù)類型一個(gè)抽象數(shù)據(jù)類型包括：數(shù)據(jù)對(duì)象的一個(gè)集合作用于這些數(shù)據(jù)對(duì)象的抽象運(yùn)算的集合這種類型對(duì)象的封裝，即，除了使用類型中所定義的運(yùn)算外，用戶不能對(duì)這些對(duì)象進(jìn)行操作程序設(shè)計(jì)語言對(duì)抽象數(shù)據(jù)類型的支持Ada語言通過程序包（package）提供數(shù)據(jù)封裝的支持Smalltalk、C++和Java語言則通過類（Class）對(duì)抽象數(shù)據(jù)類型提供支持2高級(jí)語言的一般特性40語句與控制結(jié)構(gòu)表達(dá)式表達(dá)式由運(yùn)算量（也稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴：如X*Y、前綴：如-A、后綴：如P↑表達(dá)式形成規(guī)則：變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式若E1、E2為表達(dá)式，θ為二元算符，則E1θE2為表達(dá)式（一般采用中綴形式）若E為表達(dá)式，θ為一元算符，則θE（或Eθ）為表達(dá)式若E為表達(dá)式，則(E)是表達(dá)式2高級(jí)語言的一般特性41語句與控制結(jié)構(gòu)表達(dá)式在多數(shù)語言中算術(shù)和邏輯算符的優(yōu)先順序一般規(guī)定如下：乘冪 （**或↑）一元負(fù) （-）乘、除 （*，/，÷）加、減 （+，-）關(guān)系符 （<，=，>，<=，<>，>=）非 （﹁，not，或.NOT.）與 （∧，&，and或.AND.）或 （∨，∣，or或.OR.）隱含 （或imp）等值 （≡，～或equi）2高級(jí)語言的一般特性42語句與控制結(jié)構(gòu)表達(dá)式算符的代數(shù)性質(zhì)（交換率、結(jié)合率和分配率）常?？捎脕韮?yōu)化目標(biāo)程序的質(zhì)量。但是必須注意兩點(diǎn)：代數(shù)性質(zhì)引用到什么程度視具體語言的不同而不同如在ALGOL中把A*B+C*D處理成C*D+A*B，則至少是對(duì)ALGOL不夠忠實(shí)數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完全成立如：(A+B)+C=A+(B+C)在計(jì)算機(jī)上并不普遍成立2高級(jí)語言的一般特性43語句與控制結(jié)構(gòu)語句從功能上說，語句大體可分兩大類：說明性語句旨在定義不同數(shù)據(jù)類型的變量或運(yùn)算執(zhí)行性語句旨在描述程序的動(dòng)作。執(zhí)行性語句又可分：賦值語句控制語句輸入/輸出語句從形式上說，語句還可分為：簡單句、復(fù)合句和分程序等2高級(jí)語言的一般特性44語句與控制結(jié)構(gòu)語句賦值語句每個(gè)名字有兩方面的特征：一方面它代表一定的存儲(chǔ)單元另一方面它又以該單元的內(nèi)容作為值賦值語句A:=B的意義：“把B的值送入A所代表的單元”對(duì)賦值號(hào)右邊的B我們需要的是它的值（右值）對(duì)左邊的A我們需要的是它所代表的存儲(chǔ)單元的地址（左值）2高級(jí)語言的一般特性45語句與控制結(jié)構(gòu)語句控制語句多數(shù)語言中所含的控制語句有：無條件轉(zhuǎn)移語句：gotoL條件語句： ifBthenS ifBthenS1elseS2循環(huán)與句： whileBdoS repeatSuntilB fori:=E1stepE2untilE3doS過程調(diào)用語句： callP(X1,X2,…,Xn)返回語句： return(E)2高級(jí)語言的一般特性46語句與控制結(jié)構(gòu)語句說明語句說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號(hào)表中，并檢查程序中名字的引用和說明是否相一致。許多說明語句沒有相應(yīng)的代碼。但有些語句，如過程說明語句，和可變數(shù)組說明語句則有相應(yīng)的目標(biāo)代碼簡單句和復(fù)合句簡單句是指那些不含其它語句成分的基本句，如賦值句、goto句等復(fù)合句則指那些句中有句的語句2高級(jí)語言的一般特性471程序語言的定義2高級(jí)語言的一般特性3程序語言的語法描述48上下文無關(guān)文法語法分析樹與二義性形式語言鳥瞰3程序語言的語法描述49在引入文法定義前，首先介紹幾個(gè)概念：設(shè)Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)符號(hào)Σ上的一個(gè)符號(hào)串是指由Σ中的符號(hào)所構(gòu)成的一個(gè)有窮序列不包含任何符號(hào)的序列稱為空字，記為ε用Σ*表示Σ上的所有符號(hào)串的全體，空字ε也包括在其中舉例：若Σ={a,b}則Σ*={ε,a,b,aa,ab,bb,aaa,…}Φ表示不含任何元素的空集{}這里要注意ε、{}和{ε}的區(qū)別3程序語言的語法描述50在引入文法定義前，首先介紹幾個(gè)概念：Σ*的子集U和V中的（連接）積定義為： UV={αβ∣α∈U&β∈V}即集合UV中的符號(hào)串是由U和V的符號(hào)串連接而成的。注意，一般UVVU，但(UV)W=U(VW)。V自身的n次（連接）積記為： Vn=VV…V(n個(gè)V)規(guī)定V0={ε}。令 V*=V0∪V1∪V2∪V3∪…稱V*是V的閉包。記V+=VV*，稱V+是V的正則閉包閉包V*中的每個(gè)符號(hào)都是由V中的符號(hào)串經(jīng)有限次連接而成的3程序語言的語法描述51在引入文法定義前，首先介紹幾個(gè)概念：舉例1： 設(shè)： U＝{a，aa}，V＝{b，bb} 那么： UV={ab，abb，aab，aabb}舉例2： 設(shè)： U＝{a，aa} 那么： U*={ε，a，aa，aaa，aaaa，…} U+={a，aa，aaa，aaaa，…}3程序語言的語法描述52上下文無關(guān)文法文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）所謂上下文無關(guān)文法是這樣一種文法，它所定義的語法范疇（或語法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的在自然語言中，語法性質(zhì)和所處的上下文往往有密切的關(guān)系。因此，上下文無關(guān)文法當(dāng)然不適宜于描述任何自然語言，但對(duì)程序語言來說基本是夠用了3程序語言的語法描述53上下文無關(guān)文法舉例：Hegavemeabook<句子>→ <主語><謂語><間接賓語><直接賓語><主語>→ <代詞><謂語>→ <動(dòng)詞><間接賓語>→ <代詞><直接賓語>→ <冠詞><名詞><代詞>→ He<代詞>→ me<名詞>→ book<冠詞>→ a<動(dòng)詞>→ gave3程序語言的語法描述54上下文無關(guān)文法舉例：Hegavemeabook<句子>?<主語><謂語><間接賓語><直接賓語>?<代詞><謂語><間接賓語><直接賓語>?He<謂語><間接賓語><直接賓語>?He<動(dòng)詞><間接賓語><直接賓語>?Hegave<間接賓語><直接賓語>?Hegave<代詞><直接賓語>?Hegaveme<直接賓語>?Hegaveme<冠詞><名詞>?Hegavemea<名詞>?Hegavemeabook3程序語言的語法描述55上下文無關(guān)文法歸納起來，一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符號(hào)一組非終結(jié)符一個(gè)開始符號(hào)以及一組產(chǎn)生式3程序語言的語法描述56上下文無關(guān)文法終結(jié)符號(hào)所謂終結(jié)符號(hào)乃是組成語言的基本符號(hào)，即在程序語言中以前屢次提到的單詞符號(hào)，如基本字，標(biāo)識(shí)符，常數(shù)，算符和界符等非終結(jié)符所謂非終結(jié)符號(hào)（也稱語法變量）用來代表語法范疇。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過程”等。一個(gè)非終結(jié)符代表一個(gè)一定的語法概念。因此非終結(jié)符是一個(gè)類（或集合）記號(hào)，而不是一個(gè)個(gè)體記號(hào)3程序語言的語法描述57上下文無關(guān)文法開始符號(hào)開始符號(hào)是一個(gè)特殊的非終結(jié)符號(hào)，它代表所定義的語言中我們最感興趣的語法范疇，這個(gè)語法范疇通常稱為“句子”。但在程序語言中我們最終感興趣的是“程序”這個(gè)語法范疇，而其他的語法范疇都只不過是構(gòu)造“程序”的一塊塊磚石產(chǎn)生式產(chǎn)生式（也稱為產(chǎn)生規(guī)則或簡稱規(guī)則）是定義語法范疇的一種書寫規(guī)則。一個(gè)產(chǎn)生式的形式是A→α，其中箭頭左邊的A是一個(gè)終結(jié)符，稱為產(chǎn)生式的左部符號(hào)；箭頭右邊的α是終結(jié)符號(hào)或與非終結(jié)符號(hào)組成的一符號(hào)串，稱為產(chǎn)生式的右部產(chǎn)生式是用來定義語法范疇的3程序語言的語法描述58上下文無關(guān)文法產(chǎn)生式舉例：定義一類含+、*的算術(shù)表達(dá)式這個(gè)定義可以這樣給出：變量是一個(gè)算術(shù)表達(dá)式若E1和E2是算術(shù)表達(dá)式，則E1+E2、E1*E2和(E1)也是算術(shù)表達(dá)式對(duì)于這個(gè)定義，若用產(chǎn)生式來描述，可將它寫成：

E→i E→E＋E E→E＊E E→(E)其中E代表“算術(shù)表達(dá)式”，ｉ代表“變量”。3程序語言的語法描述59上下文無關(guān)文法形式上說，一個(gè)上下文無關(guān)文法Ｇ是一個(gè)四元式(VT，VN，S，P)，其中VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VT∩VN=ΦS是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)P是一個(gè)產(chǎn)生式（有限）集合，每個(gè)產(chǎn)生式形式是A→α，其中，A∈VN，α∈(VT∪VN)*。開始符號(hào)S至少必須在某一產(chǎn)生式的左部出現(xiàn)一次3程序語言的語法描述60上下文無關(guān)文法幾點(diǎn)規(guī)定：“→”也可以用“::="表示，稱為巴科斯范式(BNF) P→α1 P→α2 …

P→αn

可縮寫為P→α1|α2|…|αn其中，“|”讀成“或”，稱為P的一個(gè)候選式。表示一個(gè)文法時(shí)，通常只給出開始符號(hào)和產(chǎn)生式如上例，可表示為：G(E)：E→i|E+E|E*E|(E)3程序語言的語法描述61上下文無關(guān)文法定義：稱α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定義：α1?+αn：從α1出發(fā)，經(jīng)過一步或若干步，可以推出αnα1?*αn：從α1出發(fā)，經(jīng)過0步或若干步，可以推出αn換言之，α?*β意味著：或者α=β或者α?+β3程序語言的語法描述62上下文無關(guān)文法定義：假定G是一個(gè)文法，S是它的開始符號(hào)。如果S?*α，則α稱α是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G) L(G)={α|S?+α，α∈VT*}舉例：終結(jié)符號(hào)串(i*i+i)是文法E→E+E|E*E|(E)|i的一個(gè)句子。是因?yàn)橛袕拈_始符號(hào)E至(i*i+i)的一個(gè)推導(dǎo)：E?(E)?(E+E)?(E*E+E)?(i*E+E)?(i*i+E)?(i*i+i)E,(E),(E*E+E)等是文法的句型3程序語言的語法描述63上下文無關(guān)文法下面介紹幾個(gè)簡單文法的例子：舉例1：考慮一個(gè)文法G1(S)：

S→bA

A→aA|aG1(S)定義了一個(gè)什么語言呢？從開始符S出發(fā)，我們可以推出如下句子：

S?bA?ba

S?bA?baA?baa

S?bA?baA?…?baa…a可以寫為：L(G1)={ban|n≥1}3程序語言的語法描述64上下文無關(guān)文法下面介紹幾個(gè)簡單文法的例子：舉例2：考慮一個(gè)文法G2(S)：

S→AB

A→aA|a

B→bB|bG2(S)定義了一個(gè)什么語言呢？L(G2)={ambn|m，n≥1}3程序語言的語法描述65上下文無關(guān)文法下面介紹幾個(gè)簡單文法的例子：舉例3：構(gòu)造一個(gè)文法G3使

L(G3)={anbn|n≥1}可得G3(S)：S→aSb|ab3程序語言的語法描述66上下文無關(guān)文法定義：從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯一。例如：

E+E?i+E?i+i

E+E?E+i?i+i最左推導(dǎo)：任何一步α?β都是對(duì)α中的最左非終結(jié)符進(jìn)行替換最右推導(dǎo)：任何一步α?β都是對(duì)α中的最右非終結(jié)符進(jìn)行替換3程序語言的語法描述67語法分析樹與二義性可以用一張圖表示一個(gè)句型的推導(dǎo)，這種表示稱為語法分析樹，或簡稱語法樹：語法樹的根結(jié)由開始符號(hào)所標(biāo)記隨著推導(dǎo)的展開，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符的相應(yīng)結(jié)就產(chǎn)生出下一代新結(jié)。每個(gè)新結(jié)和其父結(jié)間都有一條連線在一棵語法樹生長過程中的任何時(shí)刻，所有那些沒有后代的端末結(jié)自左至右排列起來就是一個(gè)句型3程序語言的語法描述68語法分析樹與二義性一棵語法樹表示了一個(gè)句型種種可能的（但未必是所有的）不同推導(dǎo)過程，包括最左（最右）推導(dǎo)這樣的一棵語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表如果我們堅(jiān)持使用最左（最右）推導(dǎo)，那么一棵語法樹就完全等價(jià)于一個(gè)最左（最右）推導(dǎo)，這種等價(jià)性包括樹的步步成長和推導(dǎo)的步步展開之間的完全一致性3程序語言的語法描述69語法分析樹與二義性舉例：語法樹是這些不同推導(dǎo)過程的共性抽象3程序語言的語法描述E?(E)?(E+E)?(E*E+E)?(i*E+E)?(i*i+E)?(i*i+i)最左推導(dǎo)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)的語法樹70語法分析樹與二義性一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢？也就是說它是否只有唯一的一個(gè)最左（最右)推導(dǎo)呢？----不盡然舉例：文法G(E)：E→i|E+E|E*E|(E)中(i*i+i)的最左推導(dǎo)如下3程序語言的語法描述E?(E)?(E+E)?(E*E+E)?(i*E+E)?(i*i+E)?(i*i+i)E?(E)?(E*E)?(i*E)?(i*E+E)?(i*i+E)?(i*i+i)71語法分析樹與二義性定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹（或者有兩個(gè)不同的最左/最右推導(dǎo)），則稱此文法是二義的。如：文法G(E)：E→i|E+E|E*E|(E)是二義文法定義：文法的二義性和語言的二義性是兩個(gè)不同的概念一個(gè)語言是二義性的，如果它不存在無二義性的文法即能產(chǎn)生該語言的所有文法都是二義文法可能存在G和G’，一個(gè)為二義文法，一個(gè)為無二義文法。但兩文法產(chǎn)生的語言是相同的：L(G)=L(G’)3程序語言的語法描述72語法分析樹與二義性我們常常希望對(duì)每個(gè)語句的分析是唯一的，希望程序語言的文法是無二義的。但是只要能夠控制和駕馭文法的二義性，則文法二義性的存在并不一定是一件壞事參考第五章中對(duì)兩個(gè)二義性LR表項(xiàng)目集沖突的修改：算術(shù)運(yùn)算文法G(E)：E→i|E+E|E*E|(E)IFELSE文法G(S)：S→iSeS|iS|a定義：二義性問題是不可判定問題，即不存在一個(gè)算法，它能在有限步驟內(nèi)，確切地判定一個(gè)文法是否是二義的可以找到一組無二義文法的充分條件舉例：以下是二義文法和無二義文法的等價(jià)變換3程序語言的語法描述73語法分析樹與二義性舉例：二義文法和無二義文法的等價(jià)變換二義文法：

G(E)：E→i|E+E|E*E|(E)無二義文法：

G(E)：E → T|E+T T → F|T*F F → (E)|i

表達(dá)式→ 項(xiàng)|表達(dá)式+項(xiàng) 項(xiàng) → 因子|項(xiàng)*因子 因子 → (表達(dá)式)|i3程序語言的語法描述74語法分析樹與二義性舉例：二義文法和無二義文法的等價(jià)變換句子(i*