高級語言及其語法描述

關于高級語言及其語法描述第1頁，共95頁，2022年，5月20日，18點11分，星期六2概述要學習和構(gòu)造編譯程序，理解和定義高級語言是必不可少的本章概述高級語言的結(jié)構(gòu)和主要共同特征，重點介紹程序設計語言的語法描述方法第2頁，共95頁，2022年，5月20日，18點11分，星期六3內(nèi)容線索程序設計語言的定義高級語言的一般特性程序語言的語法描述第3頁，共95頁，2022年，5月20日，18點11分，星期六4程序設計語言的定義程序設計語言是為書寫計算機程序而人為設計的符號語言。機器語言匯編語言高級語言第4頁，共95頁，2022年，5月20日，18點11分，星期六5各級語言的比較比較

機器語言匯編語言高級語言硬件識別是唯一可以識別的語言不可識別不可識別是否可直接執(zhí)行可直接執(zhí)行不可，需匯編、連接不可，需編譯/解釋、連接特點面向機器占用內(nèi)存少執(zhí)行速度快使用不方便面向機器占用內(nèi)存少執(zhí)行速度快較為直觀與機器語言一一對應面向問題/對象占用內(nèi)存大執(zhí)行速度相對慢標準化程度高便于程序交換，使用方便定位低級語言，極少使用低級語言，很少使用高級語言，種類多，常用第5頁，共95頁，2022年，5月20日，18點11分，星期六6程序語言的內(nèi)涵語法語義語用表示構(gòu)成語言句子的各個記號之間的組合規(guī)律(構(gòu)成規(guī)則)。表示按照各種表示方法所表示的各個記號的特定含義（各個記號和記號所表示的對象之間的關系）。表示各個記號或語言詞句與其使用之間的關系。第6頁，共95頁，2022年，5月20日，18點11分，星期六7舉例：C語言的賦值語句語法語義語用賦值語句由一個變量，后隨一個符號“=”，再在后面跟一個表達式所構(gòu)成。賦值語句先對該語句的右部表達式求值，然后把所得結(jié)果與語句左部的變量相結(jié)合，并取代該變量原有的值。賦值語句可用來計算和保存表達式的值。第7頁，共95頁，2022年，5月20日，18點11分，星期六8語法語言的語法是指可以形成和產(chǎn)生合式程序的一組規(guī)則。它包括詞法規(guī)則和語法規(guī)則。詞法規(guī)則是指程序中單詞符號的形成規(guī)則。單詞符號一般包括：標識符、基本字、常量、算符和界符。語法規(guī)則是指程序中語法單位的形成規(guī)則。程序語言的語法單位有：表達式、語句、分程序、過程、函數(shù)、程序。描述方式：詞法規(guī)則和語法規(guī)則都可以用自然語言、語法圖、BNF范式、或文法等描述。第8頁，共95頁，2022年，5月20日，18點11分，星期六9語法描述方式（1）（1）自然語言例1.標識符是由字母后跟若干個（包括0個）字母或數(shù)字的符號串組成的。例2.賦值語句由一個變量，后隨一個符號“=”，再在后面跟一個表達式所構(gòu)成。（2）語法圖是用圖解形式描述程序設計語言語法規(guī)則的工具。例1.標識符的構(gòu)成規(guī)則用語法圖描述為：標識符字母數(shù)字字母第9頁，共95頁，2022年，5月20日，18點11分，星期六10語法描述方式（2）（3）BNF范式巴科斯范式(BNF:Backus-NaurForm的縮寫)是由JohnBackus和PeterNaur首先引入的用來描述計算機語言語法的符號集。現(xiàn)在，新的編程語言幾乎都使用巴科斯范式來定義編程語言的語法規(guī)則。

第10頁，共95頁，2022年，5月20日，18點11分，星期六11簡單算術表達式的BNF范式<簡單表達式>∷＝<簡單表達式>+<簡單表達式><簡單表達式>∷＝<簡單表達式>*<簡單表達式><簡單表達式>∷＝(<簡單表達式>)<簡單表達式>∷＝i或者

<簡單表達式>∷＝<簡單表達式>+<簡單表達式>|<簡單表達式>*<簡單表達式>|(<簡單表達式>)|i第11頁，共95頁，2022年，5月20日，18點11分，星期六12附：BNF表示α→β表示為α∷＝β非終結(jié)符用“<”和“>”括起來終結(jié)符：基本符號集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}mn

[α]≡α|ε……第12頁，共95頁，2022年，5月20日，18點11分，星期六13語義對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義。這就是語義問題。語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義。我們采用的方法為：基于屬性文法的語法制導翻譯方法。第13頁，共95頁，2022年，5月20日，18點11分，星期六14程序語言的功能一個程序語言的基本功能是描述數(shù)據(jù)和對數(shù)據(jù)的運算。所謂程序，從本質(zhì)上來說是描述一定數(shù)據(jù)的處理過程。在現(xiàn)今的程序語言中，一個程序大體可以視為如圖所示的層次結(jié)構(gòu)第14頁，共95頁，2022年，5月20日，18點11分，星期六15內(nèi)容線索程序設計語言的定義高級語言的一般特性程序語言的語法描述第15頁，共95頁，2022年，5月20日，18點11分，星期六16高級語言的分類(1)強制式：ImperativeLanguage形式：語句序列舉例：Fortran、C、Pascal(2)應用式：ApplicativeLanguage形式：func1(…func(n))舉例：Lisp(3)基于規(guī)則：Rule-BasedLanguage形式：bird(x):-fly(x)&feather(x)舉例：Prolog(4)面向?qū)ο螅篛bject-OrientedLanguage形式：class,舉例：Smalltalk、C++、Java第16頁，共95頁，2022年，5月20日，18點11分，星期六17高級語言的一般特性程序結(jié)構(gòu)數(shù)據(jù)類型與操作語句與控制結(jié)構(gòu)第17頁，共95頁，2022年，5月20日，18點11分，星期六18程序結(jié)構(gòu)——單層結(jié)構(gòu)Fortran程序結(jié)構(gòu)主程序＋若干個輔程序段（子程序、函數(shù)）

ProgramMainRead(I,J)Callmax(I,J,K)Write(100,K)100Format(…)end

subroutinemax(x,y,z)integerx,y,zifx>ythenz＝xelsez＝y(tǒng)end第18頁，共95頁，2022年，5月20日，18點11分，星期六19程序結(jié)構(gòu)——多層結(jié)構(gòu)Pascal程序結(jié)構(gòu)程序允許嵌套定義ProgramP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;Varv:integer);varc,d:integer;begin…endbegin…endbegin….end第19頁，共95頁，2022年，5月20日，18點11分，星期六20作用域：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。允許同一個標識符在不同的過程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個內(nèi)層子程序且B2中對標識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2對X的任何引用都是指重新說明過的這個X。第20頁，共95頁，2022年，5月20日，18點11分，星期六21programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integer)第21頁，共95頁，2022年，5月20日，18點11分，星期六22初等類型、復合類型到抽象數(shù)據(jù)類型類型本不存在內(nèi)存里存儲的內(nèi)容，你認為它是什么，它就是什么高級語言設計了初等數(shù)據(jù)類型：整型、浮點型、字符型等。不同的語言也會定義不同的初等類型等。初等數(shù)據(jù)類型并不能方便地解決所有問題復合數(shù)據(jù)類型是初等數(shù)據(jù)類型迭代派生而來典型的代表就是“結(jié)構(gòu)”，數(shù)組也可算作此類抽象數(shù)據(jù)類型(ADT)在復合數(shù)據(jù)類型的基礎上增加了對數(shù)據(jù)的操作抽象數(shù)據(jù)類型進而進化為“類(Class)”第22頁，共95頁，2022年，5月20日，18點11分，星期六23類型每個被計算對象都帶有自己的類型，以類型作為值的屬性的概括，因此每個類型都意味著一個值的集合。不同類型的值具有不同的操作運算類型是一個值的集合和定義在這個值集上的一組操作的總稱。如C語言中的整型變量(int)，其值集為某個區(qū)間上的整數(shù)，定義在其上的操作為+,-,*,/等第23頁，共95頁，2022年，5月20日，18點11分，星期六24數(shù)據(jù)類型數(shù)據(jù)類型通常包括以下三種要素：a.用于區(qū)別這種類型的數(shù)據(jù)對象的屬性b.這種類型的數(shù)據(jù)對象可以具有的值c.可以作用于這種類型數(shù)據(jù)對象的操作第24頁，共95頁，2022年，5月20日，18點11分，星期六25抽象數(shù)據(jù)類型一個抽象數(shù)據(jù)類型（AbstractDataType，ADT）定義為：（1）一個數(shù)據(jù)對象集，數(shù)據(jù)對象由一個或多個類型定義；（2）一個作用于這些數(shù)據(jù)對象的抽象操作集；（3）完全封裝，用戶除了能使用該類型的操作來處理這類數(shù)據(jù)對象之外，不能作其他的處理。抽象數(shù)據(jù)類型有兩個重要特征：信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離第25頁，共95頁，2022年，5月20日，18點11分，星期六26抽象數(shù)據(jù)類型…FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口結(jié)構(gòu)數(shù)據(jù)維護接口結(jié)構(gòu)數(shù)據(jù)的物理實現(xiàn)第26頁，共95頁，2022年，5月20日，18點11分，星期六27抽象數(shù)據(jù)類型（續(xù)）FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口結(jié)構(gòu)數(shù)據(jù)維護接口結(jié)構(gòu)數(shù)據(jù)的物理實現(xiàn)第27頁，共95頁，2022年，5月20日，18點11分，星期六28抽象數(shù)據(jù)類型的特點數(shù)據(jù)抽象用ADT描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝將實體的外部特性和其內(nèi)部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)。第28頁，共95頁，2022年，5月20日，18點11分，星期六29數(shù)據(jù)抽象的優(yōu)點程序組織和修改可讀性、可靠性、可維護性通過隱藏數(shù)據(jù)表示，用戶代碼不能直接訪問該類型對象，不依賴于其表示，因此可以修改該類型對象的表示而不影響用戶代碼第29頁，共95頁，2022年，5月20日，18點11分，星期六30語句與控制結(jié)構(gòu)表達式語句簡單語句：不含其它語句成分的基本句。說明語句賦值語句控制語句過程調(diào)用語句復合語句：句中有句的語句第30頁，共95頁，2022年，5月20日，18點11分，星期六31表達式表達式：一個表達式是由運算量（亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符組成的。對于大多數(shù)程序語言來說，表達式的形成規(guī)則可概括為：（1）變量（包括下標變量）、常數(shù)是表達式；（2）若E1、E2為表達式，θ為二元算符，則E1θE2為表達式；（3）若E為表達式，θ為一元算符，則θE為表達式；（4）若E為表達式，則（E)是表達式。第31頁，共95頁，2022年，5月20日，18點11分，星期六32語句不同程序語言含有不同形式和功能的各種語句。從功能上說語句大體可分執(zhí)行性語句和說明性語句兩大類：說明性語句旨在定義不同數(shù)據(jù)類型的變量或運算。執(zhí)行性語句旨在描述程序的動作。執(zhí)行性語句又可分為賦值語句、控制語句和輸入/輸出語句從形式上說，語句可分為簡單句、復合句和分程序等。第32頁，共95頁，2022年，5月20日，18點11分，星期六33賦值語句A:=B意義是：“把B的值送入A所代表的單元”在賦值句中，賦值號‘：=’左右兩邊的變量名扮演著兩種不同的角色。對賦值號右邊的B我們需要的是它的值；對于左邊的A我們需要的是它們的所代表的存儲單元（的地址）。為了區(qū)分一個名字的這兩種特征，我們把一個名字所代表的那個存儲單元（地址）稱為該名字的左值；把一個名字的值稱為該名字的右值。第33頁，共95頁，2022年，5月20日，18點11分，星期六34控制語句多數(shù)語言中所含的控制語句有：無條件轉(zhuǎn)移語句:gotoL條件語句：ifBthenSifBthenS1elseS2循環(huán)語句：whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過程調(diào)用語句：callP(X1,X2,…,Xn)返回語句：return(E)第34頁，共95頁，2022年，5月20日，18點11分，星期六35說明語句說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否相一致。第35頁，共95頁，2022年，5月20日，18點11分，星期六36內(nèi)容線索程序設計語言的定義高級語言的一般特性程序語言的語法描述第36頁，共95頁，2022年，5月20日，18點11分，星期六37概述對于高級程序語言及編譯程序而言，語言的語法定義是非常重要的。本節(jié)將介紹語法結(jié)構(gòu)的形式描述問題。編譯原理=形式語言理論+編譯技術第37頁，共95頁，2022年，5月20日，18點11分，星期六38形式語言自然語言人們平時說話時所使用的一種語言，不同的國家和民族有著不同的語言。形式語言通過人們公認的符號、表達方式所描述的一種語言，是一種通用語言，沒有國籍之分。形式語言是某個字母表上的字符串的集合，有一定的描述范圍。第38頁，共95頁，2022年，5月20日，18點11分，星期六39為什么用形式語言形式語言的最初起因：語言學家喬姆斯基（Chomsky）想用一套形式化方法來描述語言。形式語言在自然語言研究中起步，在計算機科學中得到廣泛應用。最初的應用：編譯現(xiàn)在已廣泛應用在人工智能、圖象處理、通信協(xié)議、通信軟件等多個領域在計算機理論科學方面：是可計算理論（算法―在有限步驟內(nèi)求得解、算法復雜性、停機問題、）、定理自動證明、程序轉(zhuǎn)換（程序自動生成）、模式識別等的基礎。第39頁，共95頁，2022年，5月20日，18點11分，星期六40形式語言與自動機理論的發(fā)展1956年，喬姆斯基（Chomsky）從產(chǎn)生的角度研究語言文法1951-1956年間，克林（Kleene）從識別的角度研究語言自動機1959年，喬姆斯基不僅確定了文法和自動機分別從生成和識別的角度去表達語言，而且證明了文法與自動機的等價性。形式語言真正誕生第40頁，共95頁，2022年，5月20日，18點11分，星期六41基本概念字母表：元素的非空有窮集合。例：{a,b,c,…,z}（拉丁字母表）

{α,β,γ,…,ω}(希臘字母表）

{0,1} （二進制數(shù)字字母表）符號：字母表中的元素。如a,b,…第41頁，共95頁，2022年，5月20日，18點11分，星期六42基本概念符號串：字母表中的符號組成的任何有窮序列。例.設字母表∑={a,b,c}

其符號串有：a,b,c,ab,ac,aa,abc,…符號串與符號組成的順序有關。符號串的長度：符號串中符號的數(shù)目,用|x|表示空符號串（空字）：不包含任何符號的符號串，記為ε。第42頁，共95頁，2022年，5月20日，18點11分，星期六43子符號串設有非空符號串u=xvy，則稱v為符號串u的子符號串。例.符號串x=a+b-(c+d)

則a,a+b-,(c+d)等都是x的子符號串，且其長度分別為：|a|=1,|a+b-|=4,|(c+d)|=5第43頁，共95頁，2022年，5月20日，18點11分，星期六44符號串的前綴與后綴符號串的前綴與后綴符號串左部的任意子串，稱為符號串的前綴；符號串右部的任意子串，稱為符號串的后綴。例.字母表A={a,b,c}上的符號串x=ab,則x的前綴有：ε、a、ab；后綴有：ε、b、ab。第44頁，共95頁，2022年，5月20日，18點11分，星期六45基本概念符號串集合：若集合中所有元素都是某字母表上的符號串，則稱之為該字母表上的符號串集合。用*表示上的所有符號串的全體，空字也包括在其中。例.若={a,b}則*={,a,b,aa,ab,bb,aaa,…}。表示不含任何元素的空集{}注意區(qū)分：、ε、{ε}第45頁，共95頁，2022年，5月20日，18點11分，星期六46（連接）積*的子集U和V中的（連接）積定義為:UV={∣U&V}即集合UV中的符號串是由U和V的符號串連接而成的。例.設U={a,b},V={α，β，γ}

則UV={aα,aβ,aγ,bα,bβ,bγ}注意：一般UVVU，但（UV)W=U(VW).第46頁，共95頁，2022年，5月20日，18點11分，星期六47n次（連接）積V自身的n次（連接）積記為：規(guī)定V0={}.令：V*=V0V1V2…，稱V*是V的閉包。閉包V*中的每個符號都是由V中的符號串經(jīng)有限次連接而成的。記V+=VV*,稱V+是V的正則閉包。Vn=VVV…V

n第47頁，共95頁，2022年，5月20日，18點11分，星期六48閉包定理.若A是符號串集合，則A*=(A*)*。則x∈AM，因此推得x∈A*，所以(A*)*A*，故A*=(A*)*。證明：顯然A*(A*)*,現(xiàn)證(A*)*A*

任給符號串x∈(A*)*，則存在n，使得x∈(A*)n，x必存在n個子串x1,…,xn

，使得x=x1…xn

，且xi∈A*

(i=1,…,n)。由xi∈A*

，必存在整數(shù)pi,使得xi∈Api

，令 第48頁，共95頁，2022年，5月20日，18點11分，星期六49文法（Grammar）所謂文法是用來定義語言的一個數(shù)學模型。表示語言的方法：若語言L是有限集合，可用列舉法若L是無限集合（集合中的每個元素有限長度），用其他方法。方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語言的每個句子方法二：機器識別系統(tǒng)：當一個字符串能被一個語言的識別系統(tǒng)接受，則這個字符串是該語言的一個句子，否則不屬于該語言。第49頁，共95頁，2022年，5月20日，18點11分，星期六50Chomsky文法體系Chomsky文法體系中，任何一種文法必須包含兩個不同的有限符號的集合非終結(jié)符集合VN終結(jié)符集合VT一個起始符S一個形式規(guī)則的有限集合￡（產(chǎn)生式集合）。注意￡中的產(chǎn)生式是用來產(chǎn)生語言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個起始符S開始，不斷使用￡中的產(chǎn)生式而導出來。文法的核心是產(chǎn)生式的集合，它決定了語言中句子的產(chǎn)生。第50頁，共95頁，2022年，5月20日，18點11分，星期六51文法的形式定義文法G是一個四元組G=(VN,VT,S,￡)，其中VN

：非終結(jié)符的有限集合VT

：終結(jié)符的有限集合，VN∩VT=ΦS：開始符號且S∈VN

。￡：形式為P→α的產(chǎn)生式的有限集合，且P∈(VN∪VT)*VN(VN∪VT)*，α∈(VN∪VT)*第51頁，共95頁，2022年，5月20日，18點11分，星期六52文法示例文法G1=({N},{0,1},{N→0N,N→1N,N→0,N→1},N)

其中：VN={N}，

VT={0,1}，

S=N。

￡={N→0N,N→1N,N→0,N→1}，第52頁，共95頁，2022年，5月20日，18點11分，星期六53文法的解釋（1）非終結(jié)符號：需要進一步定義的符號，不會出現(xiàn)在程序中。用來代表語法范疇。如“算術表達式”、“布爾表達式”、“過程”等。一個非終結(jié)符代表一個一定的語法概念，因此非終結(jié)符是一個類（或集合）記號，而不是個體記號。終結(jié)符號：不需要再定義，會出現(xiàn)在程序中。組成語言的基本符號，即在程序語言中的單詞符號，如標識符，常數(shù)，算符和界符等開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次.第53頁，共95頁，2022年，5月20日，18點11分，星期六54文法的解釋（1）產(chǎn)生式（規(guī)則）：定義語法單位的一種書寫規(guī)則它的形式為：P→α（或P::=α）其中“→”讀作“定義為”，P，α為符號串，箭頭左邊稱為產(chǎn)生式左部，箭頭右邊稱為產(chǎn)生式右部。

例：S→0S1，0S→01若干個左部相同的產(chǎn)生式如P→α1,P→α2,P→α3,...,P→αn

可合并成一個,縮寫為

P→α1|α2|α3|...|αn,

其中,每個αi

稱為是P的一個候選式.第54頁，共95頁，2022年，5月20日，18點11分，星期六55習慣寫法VN:大寫字母A、B、C、S等VT: 小寫字母，0~9，+、－等運算符，α、β、γ: 文法符號串,∈(VT∪VN)*S:開始符號，第一個產(chǎn)生式中出現(xiàn)→

:定義符號（推出）|：或第55頁，共95頁，2022年，5月20日，18點11分，星期六56文法的約定為了簡化，文法表示只寫出產(chǎn)生式部分約定第一個產(chǎn)生式的左部符號為初始符號或在產(chǎn)生式前寫上“G[A]”，其中G為文法名，A為初始符號.

例.文法G[N]:N→0N,N→1N,N→0,N→1

文法G[E]:E→E+E│E*E│(E)│i第56頁，共95頁，2022年，5月20日，18點11分，星期六57如何由文法產(chǎn)生語言的句子？基本思想：從識別符號開始，把當前產(chǎn)生的符號串中的非終結(jié)符號替換為相應產(chǎn)生式右部的符號串，直到最終全由終結(jié)符號組成。這種替換過程稱為推導或產(chǎn)生句子的過程，每一步稱為直接推導或直接產(chǎn)生。第57頁，共95頁，2022年，5月20日，18點11分，星期六58直接推導與歸約直接推導如果A→γ是一個產(chǎn)生式，而α，β∈（VT∪VN）*，則將產(chǎn)生式A→γ用于符號串αAβ 得到符號串αγβ，記為αAβαγβ，稱αAβ直接推出αγβ。歸約是推導的逆過程若存在αAβαγβ，則稱αγβ能夠直接歸約成αAβ

。第58頁，共95頁，2022年，5月20日，18點11分，星期六59推導推導：設α1,α2,…,αn(n>0)∈(VT∪VN)*，且有

α1

α2

…αn

則稱這個序列是從α1到αn的一個推導。若存在一個α1到αn的推導，則稱α1可推導出αn。

α1

αn(經(jīng)一步或若干步推導）

α1

αn

（經(jīng)0步或若干步推導）+*第59頁，共95頁，2022年，5月20日，18點11分，星期六60最左（右）推導（規(guī)約）若在推導關系中，每次最先替換最左（右）的非終結(jié)符，則稱為最左（右）推導；若在歸約過程中，每次最先歸約最左（右）的非終結(jié)符，則稱為最左（右）歸約。第60頁，共95頁，2022年，5月20日，18點11分，星期六61例.文法G[S]:S→ABA→A0|1BB→0|S1，請給出句子101001的最左和最右推導。最右推導：

SAB

AS1AAB1

AA01

A1B01

A1001

1B1001

101001最左推導：

SAB1BB10B10S110AB1

101BB11010B1101001第61頁，共95頁，2022年，5月20日，18點11分，星期六62句型、句子和語言句型：假定G是一個文法，E是它的開始符號，如果Eα，則稱α是文法G的一個句型。

例

(E+E),(i+E),(i+i),E都是G[E]的句型。句子：僅由終結(jié)符組成的句型稱為句子。例(i×i+i),(i+i)都是G[E]的句子。語言：文法G所產(chǎn)生句子的全體，即：

L(G)={α|Sα，α∈VT*}*+第62頁，共95頁，2022年，5月20日，18點11分，星期六63例.設有文法G1[S]:S→bA,A→aA|a

試求此文法所描述的語言。解：因為從開始符號S出發(fā)可推出下列句子：

S

bA

ba S

bA

baA

baa S

bA

baA

baaA

baaa … S

bA

baA

…

baa…a

所以，L(G1)={ban|n>1}第63頁，共95頁，2022年，5月20日，18點11分，星期六64例.設文法G2[S]：S→AB A→aA|a B→bB|b 該文法所描述的語言是什么？解：從文法開始符號S出發(fā)，可推出下列句子： S

AB

ab S

AB

aAB

aaB

aab S

AB

aAB

aaB

aabB

aabbB

aabbb S

AB

aa…abb…bmn所以，L(G2)={ambn|m,n>=1}第64頁，共95頁，2022年，5月20日，18點11分，星期六65例.試對如下語言L(G3)={anbn|n>=1}構(gòu)造文法G3。解：L(G3)由以下一些符號串x組成： n=1,x=abn=2,x=aabbn=3,x=aaabbb…L(G3)={ab,aabb,aaabbb,… 由此可見，集合L（G3）有如下特點：每個符號串呈對稱形式，即a,b成對出現(xiàn)；L(G3)為無窮集合，描述它的規(guī)則中含遞歸定義；文法中終結(jié)符只有a,b。因此可用以下兩條產(chǎn)生式定義語言L(G3)

S→aSb|ab即：G3=（{S}，{a,b}，{S→aSb|ab}，S)第65頁，共95頁，2022年，5月20日，18點11分，星期六66例.文法G[<數(shù)>]：

<數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字><數(shù)字>→0|1|2|3|4|5|6|7|8|9

語言L(G)為非負整數(shù)。非負整數(shù)的另一定義：<數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字1><數(shù)字>→0|1|2|3|4|5|6|7|8|9<數(shù)字1>→1│2│3│4│5│6│7│8│9思考其他定義形式第66頁，共95頁，2022年，5月20日，18點11分，星期六67例.寫一文法G3，使其描述的語言為正奇數(shù)集合。令G3={VN,VT,P,<正奇數(shù)>}，其中，

VT={0,1,2,3,4,5,6,7,8,9}，

VN={<正奇數(shù)>,<一位奇數(shù)>,<一位偶數(shù)>,<數(shù)字串>,<數(shù)字>}S：<正奇數(shù)>P：<正奇數(shù)>→<一位奇數(shù)>│<數(shù)字串><一位奇數(shù)><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字><數(shù)字>→<一位奇數(shù)>│<一位偶數(shù)><一位奇數(shù)>→1│3│5│7│9<一位偶數(shù)>→0│2│4│6│8

思考：如果要求開頭元素非零，如何改造？第67頁，共95頁，2022年，5月20日，18點11分，星期六68<正奇數(shù)>→<一位奇數(shù)>│<數(shù)字串><一位奇數(shù)><數(shù)字串>→<數(shù)字串><數(shù)字>│<數(shù)字1><數(shù)字>→<一位奇數(shù)>│<一位偶數(shù)><數(shù)字1>→1│2│3│4│5│6│7│8│9<一位奇數(shù)>→1│3│5│7│9<一位偶數(shù)>→0│2│4│6│8或者：<正奇數(shù)>S,<一位奇數(shù)>A,<一位偶數(shù)>E,<數(shù)字串>B,<數(shù)字>C,<數(shù)字1>D.

S→A│BAB→BC│DC→0│E│AD→E│AE→2│4│6│8A→1│3│5│7│9第68頁，共95頁，2022年，5月20日，18點11分，星期六69同一句型有不同的推導序列設有文法G[N1]:N1→NN→ND|DD→0|1|2

則句子12可由若干種不同的推導序列推導出來：

(1)N1

NNDN2D212(2)

N1

NNDDD1D12可見，同一句型（句子）可以通過不同的推導序列推導出來。第69頁，共95頁，2022年，5月20日，18點11分，星期六70Chomsky文法體系分類文法G=(VN,VT,S,￡)，￡：P→α，其中P∈(VN∪VT)*VN(VN∪VT)*，α∈(VN∪VT)*屬于Chomsky文法體系該體系對產(chǎn)生式的形式做了一些規(guī)定，分為四類，即0型、1型、2型、3型文法第70頁，共95頁，2022年，5月20日，18點11分，星期六713型文法也稱正規(guī)文法右線性文法（Right-linearGrammar）：

A→ωB或A→ω，其中A、B∈VN,ω∈VT*。左線性文法（Left-linearGrammar）：

A→Bω或A→ω，其中A、B∈VN,ω∈VT*。對應的語言：正規(guī)語言對應的自動機：有限自動機（FiniteAutomaton）。例.文法SaS，Sa

對應正規(guī)式：a+，或者a*a第71頁，共95頁，2022年，5月20日，18點11分，星期六722型文法也稱上下文無關文法（CFG：Context-freeGrammar)產(chǎn)生式的形式為P→α,其中

P∈VN

，且α∈(VN∪VT)*對應的語言：上下文無關語言（CFL：Context-freeLanguage)對應的自動機：下推自動機（PDA：PushdownAutomaton)。第72頁，共95頁，2022年，5月20日，18點11分，星期六732型文法示例例.上下文無關文法

S01S0S1

產(chǎn)生的語言是L=0n1nn1，如0011,000111,01L,而10,1001,,010L.

但沒有任何有限自動機能夠接受語言L.第73頁，共95頁，2022年，5月20日，18點11分，星期六741型文法也稱上下文有關文法（CSG：Context-sensitiveGrammar)產(chǎn)生式的形式為P→α,其中

|P|≤|α|，α∈(VN∪VT)*

，P∈(VN∪VT)*VN(VN∪VT)*對應的語言：上下文有關語言（CSL：Context-sensitiveLanguage)若不考慮ε，與線性有界自動機（LBA,LinearBoundedAutomaton）等價。第74頁，共95頁，2022年，5月20日，18點11分，星期六751型文法示例例.下列文法是1型文法

SaBC|aSBCCBBCaBabbBbbbCbccCcc第75頁，共95頁，2022年，5月20日，18點11分，星期六760型文法0型文法：無限制文法，短語文法對應的語言：遞歸可枚舉語言與圖靈機等價。例.下列文法是0型文法

SaBC|aSBCCBBCaBabbBbbbBbbCbccCcc

cCc第76頁，共95頁，2022年，5月20日，18點11分，星期六77Chomsky文法體系3012第77頁，共95頁，2022年，5月20日，18點11分，星期六78文法、形式語言和自動機的對應關系遞歸可枚舉語言圖靈機0型文法上下文有關語言線性有界自動機1型文法上下文無關語言下推自動機2型文法正規(guī)語言有限自動機3型文法第78頁，共95頁，2022年，5月20日，18點11分，星期六79總結(jié)（1）自然語言是上下文有關的。但是上下文無關文法有足夠的能力描述現(xiàn)今多數(shù)程序設計語言的語法結(jié)構(gòu)算術表達式語句賦值語句條件語句讀語句……第79頁，共95頁，2022年，5月20日，18點11分，星期六80上下文無關文法描述語言語法結(jié)構(gòu)算術表達式的上下文無關文法表示文法G=({E},{+,*,i,(,)},P,E} P: E→iE→E+E E→E*EE→(E)條件語句的上下文無關文法表示

<條件語句>→if<條件表達式>then<語句>|if<條件表達式>then<語句>else<語句>第80頁，共95頁，2022年，5月20日，18點11分，星期六81總結(jié)（2）基于正規(guī)文法討論詞法分析問題，基于上下文無關文法討論語法分析問題。所以，現(xiàn)在都用上下文無關文法和正則文法描述語言語法，而其中上下文有關的問題，可通過表格處理解決。第81頁，共95頁，2022年，5月20日，18點11分，星期六82例非CFL的文法L={anbncn|n>0}的文法

SaBC|aSBCCBBCaBabbBbbbCbc可以證明不存在CFGG,使L(G)=L第82頁，共95頁，2022年，5月20日，18點11分，星期六83非CFL結(jié)構(gòu)在我們使用的程序語言中,有些語言結(jié)構(gòu)并不是總能用上下文無關文法描述的。

例1L1={wcw|w∈{a,b}+}。aabcaab就是L1的一個句子。這個語言是檢查程序中標識符的聲明應先于引用的抽象。

例2L2={anbmcndm|n,m≥0}，它是檢查過程聲明的形參個數(shù)和過程引用的參數(shù)個數(shù)是否一致問題的抽象。第83頁，共95頁，2022年，5月20日，18點11分，星期六84語法分析樹和文法的二義性語法分析樹，簡稱語法樹二義性第84頁，共95頁，2022年，5月20日，18點11分，星期六85什么是語法樹？語法樹是表示一個句型推導過程的圖，是一棵倒立的樹。結(jié)點邊根結(jié)點末端結(jié)點末端分支：A(a,b)和B(c,d)兄弟結(jié)點SBBdbaAcdc第85頁，共95頁，2022年，5月20日，18點11分，星期六86從推導構(gòu)造語法樹方法：把開始符號S做為語法樹的根結(jié)點，對每一個直接推導畫一次結(jié)點的擴展，該結(jié)點是直接推導中被替換的非終結(jié)符號