編譯原理課件Chapt2

第二章

高級語言及其語法描述

常用的高級語言

FORTRAN 數(shù)值計算COBOL 事務(wù)處理PASCAL 結(jié)構(gòu)程序設(shè)計ADA 大型程序、嵌入式實時系統(tǒng)PROLOG 邏輯程序設(shè)計ALGOL 算法語言C/C++ 系統(tǒng)程序設(shè)計Java Internet程序設(shè)計與機器語言或匯編語言比較，高級語言的優(yōu)點：較接近于數(shù)學(xué)語言和工程語言，比較直觀、自然和易于理解;便于驗證其正確性，易于改錯;編寫效率高;易于移植.2.1 程序語言的定義程序語言由兩方面定義：語法語義語用一.語法程序本質(zhì)上是一定字符集上的字符串。語法：一組規(guī)則，用它可以形成和產(chǎn)生一個合式(well-formed)的程序。語法詞法規(guī)則：單詞符號的形成規(guī)則。單詞符號是語言中具有獨立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識符、基本字、算符、界符等。描述工具：有限自動機語法規(guī)則：語法單位的形成規(guī)則。語法單位通常包括：表達(dá)式、語句、分程序、過程、函數(shù)、程序等;描述工具：上下文無關(guān)文法E→i E→E+E E→E*E E→(E)語法規(guī)則和詞法規(guī)則定義了程序的的形式結(jié)構(gòu)。定義語法單位的意義屬于語義問題。二.語義語義：一組規(guī)則，用它可以定義一個程序的意義。描述方法：自然語言描述：隱藏錯誤、二義性和不完整性形式描述：操作語義(PL/1)指稱語義(ADA)代數(shù)語義(PASCAL)三．程序語言的基本功能和層次結(jié)構(gòu)程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。程序的層次結(jié)構(gòu)程序|子程序或分程序、過程、函數(shù)|語句|表達(dá)式|數(shù)據(jù)引用算符函數(shù)調(diào)用程序語言每個組成成分的邏輯和實現(xiàn)意義

抽象的邏輯的意義數(shù)學(xué)意義計算機實現(xiàn)的意義具體實現(xiàn)2.2高級語言的一般特性

高級語言的分類

強制式語言(ImperativeLanguge)也稱過程式語言：命令驅(qū)動，面向語句FORTRAN、C、Pascal，Ada應(yīng)用式語言（ApplicativeLanguage）：注重程序所表示的功能，而不是一個語句接一個語句地執(zhí)行LISP、ML基于規(guī)則的語言（Rule-basedLanguage）：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭幼鱌rolog面向?qū)ο笳Z言（Object-OrientedLanguage）：封裝性、繼承性和多態(tài)性Smalltalk，C++，Java

2.3程序語言的語法描述2.2高級語言的一般特性2.2.2程序結(jié)構(gòu)FORTRAN一個程序由一個主程序段和若干輔程序段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。每個程序段有一系列的說明語句和執(zhí)行語句組成。各段可以獨立編譯。模塊結(jié)構(gòu)，沒有嵌套和遞歸各程序段中的名字相互獨立，同一個標(biāo)識符在不同的程序段中代表不同的名字。主程序PROGRAM…

…end輔程序1SUBROUTINE…

…end輔程序2FUNCTION…

…endPASCALPASCAL程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end作用域：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。允許同一個標(biāo)識符在不同的過程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個內(nèi)層子程序且B2中對標(biāo)識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2對X的任何引用都是指重新說明過的這個X。programmain

varA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integer)PASCAL提供了豐富的數(shù)據(jù)類型和運算方式，它允許用戶動態(tài)地申請和退還存貯空間。ADA程序包(package)：把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象。一個程序包分為兩部分：可見的規(guī)范說明部分，它定義了程序包外面可以訪問的對象。程序包體，它實際定義程序包的實現(xiàn)細(xì)節(jié)。packageSTACKSistypeELEMisprivate;typeSTACKislimitedprivate;procedurepush(S:inoutSTACK;E:inELEM);procedurepop(S:inoutSTACK;E:outELEM);…endSTACK;packagebodySTACKSisprocedurepush(S:inoutSTACK;E:inELEM);begin……實現(xiàn)細(xì)節(jié)endpush;procedurepop(S:inoutSTACK;E:outELEM);begin……實現(xiàn)細(xì)節(jié)endpop;end;JAVAJava是一種面向?qū)ο蟮母呒壵Z言類（Class）繼承(Inheritance)多態(tài)性(Polymorphism)和動態(tài)綁定(Dynamicbinding)classCar{intcolor_number;intdoor_number;intspeed;

…push_break(){

…}add_oil(){

…}}

classTrash_Carextendscar{doubleamount;fill_trash(){

…}}2.2.3數(shù)據(jù)類型與操作一個數(shù)據(jù)類型通常包括以下三種要素：用于區(qū)別這種類型數(shù)據(jù)對象的屬性這種類型的數(shù)據(jù)對象可以具有的值可以作用于這種類型的數(shù)據(jù)對象的操作2.2.3數(shù)據(jù)類型與操作一．初等數(shù)據(jù)類型數(shù)值類型：整型、實型、復(fù)數(shù)、雙精度，運算：+，-，*，/等邏輯類型：布爾運算：∨，∧，┑字符類型：符號處理指針類型標(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為首的名字代表整型，否則為實型。動態(tài)確定：走到哪里，是什么，算什么二數(shù)據(jù)結(jié)構(gòu)1數(shù)組邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)，沿著每一維的距離，稱為下標(biāo)。數(shù)組可變與不可變：編譯時能否確定其存貯空間的大小。訪問：給出數(shù)組名和下標(biāo)值存放方式:按行存放,按列存放數(shù)組元素地址計算數(shù)組A[10,20]的A[1，1]為a，各維下標(biāo)為1，按行存放，那么A[i，j]地址為：a+(i-1)*20+(j-1)數(shù)組元素地址計算公式內(nèi)情向量把數(shù)組的有關(guān)信息記錄在一個“內(nèi)情向量”中，每個數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的類型。2記錄邏輯上說，記錄結(jié)構(gòu)由已知類型的數(shù)據(jù)組合在一起的一種結(jié)構(gòu)。 record{charNAME[20]; integerAGE; boolMARRIED; }CARD[1000]訪問：復(fù)合名CARD[k].NAME存儲：連續(xù)存放域的地址計算：相對于記錄結(jié)構(gòu)起點的相對數(shù)OFFSET。3字符串、表格、棧字符串：符號處理、公式處理表格：本質(zhì)上是一種記錄結(jié)構(gòu)線性表：一組順序化的記錄結(jié)構(gòu)棧：一種線性表，后進(jìn)先出，POP,PUSH三抽象數(shù)據(jù)類型一個抽象數(shù)據(jù)類型包括：數(shù)據(jù)對象的一個集合；作用于這些數(shù)據(jù)對象的抽象運算的集合；這種類型對象的封裝，即，除了使用類型中所定義的運算外，用戶不能對這些對象進(jìn)行操作。程序設(shè)計語言對抽象數(shù)據(jù)類型的支持Ada語言通過程序包（package）提供了數(shù)據(jù)封裝的支持Smalltalk、C++和Java語言則通過類（Class）對抽象數(shù)據(jù)類型提供支持。2.2.4語句與控制結(jié)構(gòu)一．表達(dá)式表達(dá)式由運算量（也稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴、前綴、后綴X*Y-AP↑表達(dá)式形成規(guī)則算符的優(yōu)先次序一般的規(guī)定PASCAL：左結(jié)合A+B+C=(A+B)+CFORTRAN：對于滿足左、右結(jié)合的算符可任取一種，如A+B+C就可以處理成(A+B)+C，也可以處理成A+(B+C)。注意兩點：代數(shù)性質(zhì)能引用到什么程度視具體的語言不同而不同；在數(shù)學(xué)上成立的代數(shù)性質(zhì)在計算機上未必完全成立。二．語句賦值語句：A:=B名字左值：該名字代表的那個單元（地址）稱為該名字的左值。(所代表的存貯單元的地址)右值：一個名字的值稱為該名字的右值。(所代表的存貯單元的內(nèi)容)控制語句：無條件轉(zhuǎn)移語句gotoL條件語句ifBthenSifB

thenS1elseS2循環(huán)語句whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過程調(diào)用語句callP(X1,X2,...,Xn)返回語句

return(E)說明語句：定義各種不同數(shù)據(jù)類型的變量或運算，定義名字的性質(zhì)。簡單句和復(fù)合句簡單句：不包含其他語句成分的基本句復(fù)合句：句中有句的語句復(fù)習(xí)：程序語言的定義程序語言由兩方面定義：語法：一組規(guī)則，用它可以形成和產(chǎn)生一個合式(well-formed)的程序詞法規(guī)則：單詞符號的形成規(guī)則。常數(shù)、標(biāo)識符、基本字、算符、界符等。有限自動機語法規(guī)則：語法單位的形成規(guī)則。表達(dá)式、語句、分程序、過程、函數(shù)、程序等;上下文無關(guān)文法語義:一組規(guī)則，用它可以定義一個程序的意義復(fù)習(xí)：程序語言的基本功能和層次結(jié)構(gòu)程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。所謂程序，本質(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

程序語言的語法描述

基本概念(一、術(shù)語)元素的非空有窮集合。例如，∑={a,b,c}1.字母表

根據(jù)字母表的定義，Σ是字母表，它由a、b、c三個元素組成?；靖拍?一、術(shù)語)

是一個字母表，由0、1兩個元素組成。注意:例如，∑'={0,1}

(2)字母表中的元素,可以是字母、數(shù)字或其他符號。(1)字母表中至少包含一個元素?；靖拍?一、術(shù)語)

字母表中的元素稱為符號或稱為字符。例如，前述例子中2.符號（字符）a、b、c是字母表Σ中的符號；0、1是字母表Σ'中的符號?；靖拍?一、術(shù)語)

例如，設(shè)有字母表∑={a,b,c}

符號的有窮序列稱為符號串。

符號串總是建立在某個特定字母表上的且只由字母表上的有窮多個符號組成。

則有符號串a(chǎn)，b，ab，ba，cba，abc…

3.符號串（字）基本概念(一、術(shù)語)說明:不包含任何符號的符號串,稱為空符號串，用ε表示。符號串中符號的順序是很重要的。ab和ba是字母表Σ上的兩個不同的符號串。空符號串由0個符號組成，其長度|ε|=0基本概念(二、運算)

設(shè)x和y是符號串，則串xy稱為它們的連結(jié)。則XY＝ABC10A，YX＝10AABC。注意：對任意一個符號串x，1.符號串的連結(jié)例如，設(shè)X＝ABC，Y＝10A我們有εx＝xε＝x?；靖拍?二、運算)2.集合的乘積

設(shè)A和B是符號串的集合,則A和B的乘積定義為：

集合的乘積是滿足于x∈A,y∈B的所有符號串xy所構(gòu)成的集合。AB={xy|x∈A,y∈B}{}A=A{}=A基本概念(二、運算)例如：設(shè)A={a,b},B={c,d}則AB={ac,ad,bc,bd}由于對任意的符號串x，總有x=x=x所以,對任意集合A,我們有:基本概念(二、運算)

特別指出的是，是符號串,不是集合，而{}表示由空符號串所組成的集合,但這樣的集合不是空集合Φ={}

?；靖拍?二、運算)

3.符號串的冪運算

設(shè)x是符號串,則x的冪運算定義為：

x0=

x1=x

x2=xx

x3=xxx

…

xn=xx…x=xxn-1(n>0)n注意：x0≠1基本概念(二、運算)例如,設(shè)x＝abc則x0=x1=abcx2=xx=abcabc

…基本概念(二、運算)

4.集合的冪運算

設(shè)A是符號串的集合，則集合A的冪運算定義為：A0={}A1=AA2=AA

…

An=AA…A=AAn-1(n>0)n基本概念(二、運算)例如，設(shè)A={a,b}，則A0={}A1=A={a,b}A2=AA={aa,ab,ba,bb}

…A3=AAA=A2A={aaa,aab,aba,abb,baa,bab,bba,bbb}基本概念(二、運算)5.集合A的正則閉包A＋與自反閉包A*

設(shè)A是符號串的集合，則A的正則閉包A＋和A的自反閉包A*的定義為:A+=A1∪A2∪…∪AnA*=A0∪A1∪A2∪…

∪An={ε}∪A+基本概念(二、運算)

可見,集合A的正則閉包表示A上元素a,b構(gòu)成的所有符號串的集合,集合A的自反閉包比集合A的正則閉包多含一個空符號串。例如，設(shè)A={a,b},則：A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}∑*的子集U和V的連接（積）定義為UV＝{|U&V}

例：設(shè)：U＝{a,aa}V＝{b,bb}那么：

UV={ab,abb,aab,aabb}∑*的子集U和V的連接（積）定義為UV＝{|U&V}

V自身的n次積記為 Vn=VV…V規(guī)定V0={}，令V*=V0∪V1∪V2∪V3∪…稱V*是V的閉包;記V＋＝VV*，稱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ī)則Hegavemeabook.<句子><主語><謂語><間接賓語><直接賓語><主語><代詞><謂語><動詞><間接賓語><代詞><直接賓語><冠詞><名詞><代詞>He<代詞>me<名詞>book<冠詞>a<動詞>gave<句子><主語><謂語><間接賓語><直接賓語><主語><代詞><謂語><動詞><間接賓語><代詞><直接賓語><冠詞><名詞><代詞>He<代詞>me<名詞>book<冠詞>a<動詞>gave<句子><主語><謂語><間接賓語><直接賓語><代詞><謂語><間接賓語><直接賓語>He<謂語><間接賓語><直接賓語>He<動詞><間接賓語><直接賓語>Hegave<間接賓語><直接賓語>Hegave<代詞><直接賓語>Hegaveme<直接賓語>Hegaveme<冠詞><名詞>Hegavemea<名詞>Hegavemeabook終結(jié)符號【VT】：從語法角度看，終結(jié)符是一個語言的不可再分的基本符號。如：基本

字、標(biāo)識符、常數(shù)、算符和界符等。非終結(jié)符號（語法變量）【VN】：用來代表語法單位。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值句”、“子程序”、“函數(shù)”等。一個非終結(jié)符代表一個一定的語法概念，是一個類（集合）記號，而不是一個個體記號。上下文無關(guān)文法的定義：一個上下文無關(guān)文法G是一個四元式G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT

VN=S：文法的開始符號，SVNP：產(chǎn)生式集合(有限)，每個產(chǎn)生式形式為P，PVN，(VT

VN)*開始符S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。幾點規(guī)定：“”也可以用“::="表示，這種表示稱為巴科斯范式(BNF)P1

P2可縮寫為P1|2||n

Pn其中，“|”讀成“或”，稱為P的一個候選式。表示一個文法時，通常只給出開始符號和產(chǎn)生式，如上例，可表示為：G(E)：Ei|E+E|E*E|(E)例，定義只含+，*的算術(shù)表達(dá)式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列產(chǎn)生式組成：EiEE+EEE*EE(E)定義：稱A直接推出，即A僅當(dāng)A是一個產(chǎn)生式，且，(VT

VN)*。如果1

2

n，則我們稱這個序列是從1到n的一個推導(dǎo)。若存在一個從1到n的推導(dǎo)，則稱1可以推導(dǎo)出n。對文法G(E)：Ei|E+E|E*E|(E)E(E)(E+E)(i+E)(i+i)用表示：從1出發(fā)，經(jīng)過0步或若干步，可以推出n。

所以：即或定義：假定G是一個文法，S是它的開始符號。如果，則稱是一個句型。僅含終結(jié)符號的句型是一個句子。文法G所產(chǎn)生的句子的全體是一個語言，將它記為L(G)。通常，用

表示：從1出發(fā)，經(jīng)過一步或若干步，可以推出n。例：(i*i+i)是文法G(E)：Ei|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)：Ac|AbG1(A)的語言?L(G1)={c，cb，cbb，}以c開頭，后繼若干個b例：文法G2(S)：SABAaA|aBbB|bG2(S)的語言?L(G2)={ambn|m，n>0}例：給出產(chǎn)生語言為{anbn|n1}的文法。G3(S)：SaSbSab例：給出產(chǎn)生語言為{ambn|1≤n≤m≤2n}的文法。G4(S)：SaSb|aaSbSab|aab從一個句型到另一個句型的推導(dǎo)往往不唯一。E+Ei+Ei+iE+EE+ii+i最左推導(dǎo)：任何一步都是對中的最左非終結(jié)符進(jìn)行替換。

最右推導(dǎo)：任何一步都是對中的最右非終結(jié)符進(jìn)行替換。遞歸規(guī)則與遞歸文法遞歸規(guī)則是指那些在規(guī)則的右部含有與規(guī)則左部相同符號的規(guī)則。例如：U→xUy，右部含有與規(guī)則左部相同符號U，那么就是遞歸規(guī)則。如果這個相同的符號出現(xiàn)在右部的最左端，則為左遞歸規(guī)則。如U→Uy如果這個相同的符號出現(xiàn)在右部的最右端，則為右遞歸規(guī)則。如U→xU若文法中至少包含一條遞歸規(guī)則,則稱文法是直接遞歸的。若文法中不含遞歸規(guī)則，但有推導(dǎo)過程

U

xUy，所以該文法為間接遞歸文法。

遞歸文法使我們能用有窮的文法刻畫無窮的語言。

2.3.2語法樹與二義性用一張圖來表示一個句型的推導(dǎo)，有助于理解句子語法結(jié)構(gòu)的層次。定義：設(shè)文法G=(VN,VT,P,S),對于文法G的任意一個句型都存在一棵相應(yīng)的語法樹：結(jié)點由符號組成。根結(jié)點對應(yīng)于開始符號。只有非終結(jié)符號對應(yīng)的結(jié)點有子結(jié)點。一個結(jié)點和它的子結(jié)點分別對應(yīng)于文法中的一個規(guī)則的左部和右部。用一張圖表示一個句型的推導(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)：Ei|E+E|E*E|(E)(i*i+i)如果使用最左(右)推導(dǎo)，則一個最左(右)推導(dǎo)與語法樹一一對應(yīng)。一個句型是否只對應(yīng)唯一一棵語法樹？定義：如果一個文法存在某個句子對應(yīng)兩顆不同的語法樹，則說這個文法是二義的。G(E)：Ei|E+E|E*E|(E)是二義文法。語言的二義性：一個語言是二義性的，如果對它不存在無二義性的文法?？赡艽嬖贕和G’，一個為二義的，一個為無二義的。但L(G)=L(G’)二義性問題是不可判定問題，即不存在一個算法，它能在有限步驟內(nèi)，確切地判定一個文法是否是二義的。可以找到一組無二義文法的充分條件。二義文法：G(E)：Ei|E+E|E*E|(E)表達(dá)式項|表達(dá)式+項項因子|項*因子因子

(表達(dá)式)|i無二義文法：G(E)：ET|E+TTF|T*FF(E)|i)EEEFFTTTTi+*(EFiiET

F