高級(jí)語(yǔ)言及其語(yǔ)法描述

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

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

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

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

[α]≡α|ε……第12頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六13語(yǔ)義對(duì)于一個(gè)語(yǔ)言來(lái)說(shuō)，不僅要給出它的詞法、語(yǔ)法規(guī)則，而且要定義它的單詞符號(hào)和語(yǔ)法單位的意義。這就是語(yǔ)義問(wèn)題。語(yǔ)義是指這樣的一組規(guī)則，使用它可以定義一個(gè)程序的意義。我們采用的方法為：基于屬性文法的語(yǔ)法制導(dǎo)翻譯方法。第13頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六14程序語(yǔ)言的功能一個(gè)程序語(yǔ)言的基本功能是描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序，從本質(zhì)上來(lái)說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。在現(xiàn)今的程序語(yǔ)言中，一個(gè)程序大體可以視為如圖所示的層次結(jié)構(gòu)第14頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六15內(nèi)容線(xiàn)索程序設(shè)計(jì)語(yǔ)言的定義高級(jí)語(yǔ)言的一般特性程序語(yǔ)言的語(yǔ)法描述第15頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六16高級(jí)語(yǔ)言的分類(lèi)(1)強(qiáng)制式：ImperativeLanguage形式：語(yǔ)句序列舉例：Fortran、C、Pascal(2)應(yīng)用式：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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六17高級(jí)語(yǔ)言的一般特性程序結(jié)構(gòu)數(shù)據(jù)類(lèi)型與操作語(yǔ)句與控制結(jié)構(gòu)第17頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六18程序結(jié)構(gòu)——單層結(jié)構(gòu)Fortran程序結(jié)構(gòu)主程序＋若干個(gè)輔程序段（子程序、函數(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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六20作用域：一個(gè)名字能被使用的區(qū)域范圍稱(chēng)作這個(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。第20頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六21programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

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

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

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

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

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

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

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

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

，使得x=x1…xn

，且xi∈A*

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

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

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

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

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

?！辏盒问綖镻→α的產(chǎn)生式的有限集合，且P∈(VN∪VT)*VN(VN∪VT)*，α∈(VN∪VT)*第51頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六53文法的解釋?zhuān)?）非終結(jié)符號(hào)：需要進(jìn)一步定義的符號(hào)，不會(huì)出現(xiàn)在程序中。用來(lái)代表語(yǔ)法范疇。如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過(guò)程”等。一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念，因此非終結(jié)符是一個(gè)類(lèi)（或集合）記號(hào)，而不是個(gè)體記號(hào)。終結(jié)符號(hào)：不需要再定義，會(huì)出現(xiàn)在程序中。組成語(yǔ)言的基本符號(hào)，即在程序語(yǔ)言中的單詞符號(hào)，如標(biāo)識(shí)符，常數(shù)，算符和界符等開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次.第53頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六54文法的解釋?zhuān)?）產(chǎn)生式（規(guī)則）：定義語(yǔ)法單位的一種書(shū)寫(xiě)規(guī)則它的形式為：P→α（或P::=α）其中“→”讀作“定義為”，P，α為符號(hào)串，箭頭左邊稱(chēng)為產(chǎn)生式左部，箭頭右邊稱(chēng)為產(chǎn)生式右部。

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

可合并成一個(gè),縮寫(xiě)為

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

其中,每個(gè)αi

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

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

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

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

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

α1

α2

…αn

則稱(chēng)這個(gè)序列是從α1到αn的一個(gè)推導(dǎo)。若存在一個(gè)α1到αn的推導(dǎo)，則稱(chēng)α1可推導(dǎo)出αn。

α1

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

α1

αn

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

SAB

AS1AAB1

AA01

A1B01

A1001

1B1001

101001最左推導(dǎo)：

SAB1BB10B10S110AB1

101BB11010B1101001第61頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六62句型、句子和語(yǔ)言句型：假定G是一個(gè)文法，E是它的開(kāi)始符號(hào)，如果Eα，則稱(chēng)α是文法G的一個(gè)句型。

例

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

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

試求此文法所描述的語(yǔ)言。解：因?yàn)閺拈_(kāi)始符號(hào)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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六64例.設(shè)文法G2[S]：S→AB A→aA|a B→bB|b 該文法所描述的語(yǔ)言是什么？解：從文法開(kāi)始符號(hào)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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六65例.試對(duì)如下語(yǔ)言L(G3)={anbn|n>=1}構(gòu)造文法G3。解：L(G3)由以下一些符號(hào)串x組成： n=1,x=abn=2,x=aabbn=3,x=aaabbb…L(G3)={ab,aabb,aaabbb,… 由此可見(jiàn)，集合L（G3）有如下特點(diǎn)：每個(gè)符號(hào)串呈對(duì)稱(chēng)形式，即a,b成對(duì)出現(xiàn)；L(G3)為無(wú)窮集合，描述它的規(guī)則中含遞歸定義；文法中終結(jié)符只有a,b。因此可用以下兩條產(chǎn)生式定義語(yǔ)言L(G3)

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

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

語(yǔ)言L(G)為非負(fù)整數(shù)。非負(fù)整數(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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六67例.寫(xiě)一文法G3，使其描述的語(yǔ)言為正奇數(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

思考：如果要求開(kāi)頭元素非零，如何改造？第67頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)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頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六69同一句型有不同的推導(dǎo)序列設(shè)有文法G[N1]:N1→NN→ND|DD→0|1|2

則句子12可由若干種不同的推導(dǎo)序列推導(dǎo)出來(lái)：

(1)N1

NNDN2D212(2)

N1

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

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

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

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

P∈VN

，且α∈(VN∪VT)*對(duì)應(yīng)的語(yǔ)言：上下文無(wú)關(guān)語(yǔ)言（CFL：Context-freeLanguage)對(duì)應(yīng)的自動(dòng)機(jī)：下推自動(dòng)機(jī)（PDA：PushdownAutomaton)。第72頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六732型文法示例例.上下文無(wú)關(guān)文法

S01S0S1

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

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

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

，P∈(VN∪VT)*VN(VN∪VT)*對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（CSL：Context-sensitiveLanguage)若不考慮ε，與線(xiàn)性有界自動(dòng)機(jī)（LBA,LinearBoundedAutomaton）等價(jià)。第74頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六751型文法示例例.下列文法是1型文法

SaBC|aSBCCBBCaBabbBbbbCbccCcc第75頁(yè)，共95頁(yè)，2022年，5月20日，18點(diǎn)11分，星期六760型文法0型文法：無(wú)限制文法，短語(yǔ)文法對(duì)應(yīng)的語(yǔ)言：遞歸可枚舉語(yǔ)言與圖靈機(jī)等價(jià)。例.下列文法是0型文法

SaBC|aSBCCBBCaBabbBbbbBbbCbccCcc

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

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

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

例1L1={wcw|w∈{a,b}+}。aabcaab就是L1的一個(gè)句子。這個(gè)語(yǔ)言是檢查程序中標(biāo)識(shí)符的聲明應(yīng)先于引用的抽象。

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