第二章高級(jí)語(yǔ)言及其語(yǔ)法描述-read_第1頁(yè)
已閱讀1頁(yè),還剩52頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,本章概述高級(jí)語(yǔ)言的結(jié)構(gòu)和主要的共同特征,并介紹程序語(yǔ)言的語(yǔ)法描述方法。要學(xué)習(xí)和構(gòu)造編譯程序,理解和定義高級(jí)語(yǔ)言是必不可少的。 2.1 程序語(yǔ)言的定義 任何語(yǔ)言實(shí)現(xiàn)的基礎(chǔ)是語(yǔ)言的定義。在定義方面,編譯程序研制者與一般用戶有所不同,他們對(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ù)語(yǔ)言的定義實(shí)現(xiàn)它。

2、 程序語(yǔ)言主要由語(yǔ)法和語(yǔ)義兩方面定義。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.1.1 語(yǔ)法:任何語(yǔ)言程序都可以看成是一定字符集(稱為字母表)上的字符串(有限序列)。但是什么樣的字符串才算是一個(gè)合適的程序呢?所謂一個(gè)語(yǔ)言的語(yǔ)法是指這樣的一組規(guī)則,用它可以形成和產(chǎn)生一個(gè)合適的程序。這些規(guī)則一部分稱為詞法規(guī)則,另一部分能稱為語(yǔ)法規(guī)則(或產(chǎn)生規(guī)則)。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,注意這里提到三個(gè)概念:a.一個(gè)程序只是用一個(gè)有限字符集作

3、為字母表;b.詞法規(guī)則是指單詞符號(hào)的形成規(guī)則。單詞符號(hào)一般包括:各類型的常數(shù)、標(biāo)識(shí)符、基本字、算符和界符等。C.語(yǔ)言的語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)形成更大的結(jié)構(gòu)(即語(yǔ)法單位),換言之,語(yǔ)法規(guī)則是語(yǔ)法單位的形成規(guī)則。一般程序語(yǔ)言的語(yǔ)法單位有:表達(dá)式、語(yǔ)句、分程序、函數(shù)、過(guò)程和程序等。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.1.2 語(yǔ)義: 對(duì)于一個(gè)語(yǔ)言來(lái)說(shuō),不僅要給出它的詞法、語(yǔ)法規(guī)則,而且要定義它的單詞符號(hào)和語(yǔ)法單位的意義。這就是語(yǔ)義

4、問(wèn)題。 語(yǔ)義是指這樣的一組規(guī)則,使用它可以定義一個(gè)程序的意義。 我們采用的方法為:基于屬性文法的語(yǔ)法制導(dǎo)翻譯方法。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,一個(gè)程序語(yǔ)言的基本功能是描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序,從本質(zhì)上來(lái)說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。在現(xiàn)今的程序語(yǔ)言中,一個(gè)程序大體可以視為下面所示的層次結(jié)構(gòu),,,,,程序,,子程序,或,分程序,,語(yǔ)句,,表達(dá)式,,數(shù)據(jù)引用,算符,函數(shù)調(diào)用,,,,,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,

5、,自上而下看上述層次結(jié)構(gòu):頂端是程序本身,他是一個(gè)完整的執(zhí)行單位。一個(gè)程序通常是由若干個(gè)子程序或分程序組成的,他們常常含有自己的數(shù)據(jù)(局部名)。子程序或分程序是由于語(yǔ)句組成的。而組成語(yǔ)句的成分是個(gè)種類型的表達(dá)式。表達(dá)式是描述數(shù)據(jù)運(yùn)算的基本結(jié)構(gòu),它通常含有數(shù)據(jù)引用、算符和函數(shù)調(diào)用。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,自下而上看上述層次結(jié)構(gòu):我們希望通過(guò)對(duì)下層成分的了解掌握上層成分,從而掌握整個(gè)程序。 在學(xué)習(xí)編譯原理的過(guò)程中特別注

6、意:程序語(yǔ)言的每個(gè)組成成分都有(抽象的)邏輯和計(jì)算機(jī)實(shí)現(xiàn)兩方面的意義。當(dāng)從數(shù)學(xué)上考慮每一個(gè)組成成分時(shí),我們注重它的邏輯意義,當(dāng)從計(jì)算機(jī)這個(gè)角度來(lái)看時(shí),我們注重他在機(jī)內(nèi)的表示和實(shí)現(xiàn)的可能性與效率。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.2 高級(jí)語(yǔ)言的一般特性2.2.1 高級(jí)語(yǔ)言的分類; a.強(qiáng)制式語(yǔ)言—過(guò)程式語(yǔ)言(命令驅(qū)動(dòng)、面向語(yǔ)句,如PASCAL C等) b.應(yīng)用式語(yǔ)言—函數(shù)式語(yǔ)言( 如LISP) c.基于規(guī)

7、則的語(yǔ)言 --邏輯型設(shè)計(jì)語(yǔ)言(如PROLOG) d.面向?qū)ο笳Z(yǔ)言 --支持封裝、多態(tài)、繼承 2.2.2 幾種程序的典型結(jié)構(gòu);,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,FORTRAN MAIN  … END SUBROUTINE SUB1 … END … SUBROUTINE SUBn … END,一. FORTRAN 一個(gè)FORTRAN 程序有一個(gè)主程序段和若

8、干個(gè)(可以是0個(gè))輔助程序段組成。(如右側(cè)),第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,輔助程序段可以是子程序、函數(shù)段或數(shù)據(jù)。每程序段由一系列說(shuō)明語(yǔ)句和執(zhí)行語(yǔ)句組成。各程序段可以獨(dú)立編輯。這對(duì)模塊設(shè)計(jì)甚為方便。 一個(gè)FORTRAN 程序個(gè)程序段所定義的各種名字通常是彼此獨(dú)立的。同一個(gè)標(biāo)識(shí)符在不同的程序段中一般都可以代表不同的名字,即代表不同的存儲(chǔ)單元,個(gè)程序段對(duì)它們的引用或賦值是彼此無(wú)關(guān)的。但是,不同程序段里的同名公用塊(Common

9、Block)卻代表同一個(gè)存儲(chǔ)區(qū)域。因此,出現(xiàn)在COMMON語(yǔ)句中的名字所代表的單元在其他程序塊中也可以引用。所以說(shuō),公用區(qū)具有全局性。不出現(xiàn)在COMMON中的名字所代表的單元具有局部性。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,二. Pascal Pascal 是一個(gè)允許子程序嵌套定義的語(yǔ)言。一個(gè)Pascal程序可以看作是操作系統(tǒng)調(diào)用的一個(gè)子程序,而子程序中又可以定義別的子程序。,program main … pr

10、ocedure P1; …procedure P11; … begin … end; begin … end; procedure P2; … begin … end; begin … end .

11、,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,Pascal這種嵌套結(jié)構(gòu)中允許同一標(biāo)識(shí)符在不同的子程序段中表示不同的名字。關(guān)于名字的作用域的規(guī)定是: a.一個(gè)在子程序B1中說(shuō)明的名字X只在B1中有效(局部于B1)。 b.如果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。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.2.3

12、 數(shù)據(jù)類型與操作; 一個(gè)數(shù)據(jù)類型通常包括以下三種要素: a.用于區(qū)別這種類型的數(shù)據(jù)對(duì)象的屬性 b.這種類型的數(shù)據(jù)對(duì)象可以具有的值 c.可以作用于這種類型數(shù)據(jù)對(duì)象的操作 一、初等數(shù)據(jù)類型 常見的初等數(shù)據(jù)類型有: a.數(shù)值數(shù)據(jù) b.邏輯數(shù)據(jù) c.字符數(shù)據(jù) d.指針類型,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,指針是指這樣一種類型的數(shù)據(jù),他們的值指向另一些數(shù)據(jù)。一般意義是,假定P是一個(gè)指

13、針,P: = addr(X) 意味著P將指向X,或說(shuō)P的值將是變量X的地址。有些語(yǔ)言用P↑表示指針P的內(nèi)容。在P:=addr(X)的情況下,如令P↑:= 0.3,則意味著X的值是0.3,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,用計(jì)算機(jī)術(shù)語(yǔ)來(lái)說(shuō),名字可以看成是代表一個(gè)抽象的存儲(chǔ)單元,這個(gè)單元可包含一位、一字節(jié)、一字或相繼的許多個(gè)字。而這個(gè)單元的內(nèi)容則認(rèn)為是此名字的值。名字的值就是它所表示的對(duì)象。此外,我們還必須指出名字的屬性。

14、一個(gè)名字的屬性包括類型和作用域。名字的類型決定了它能具有什么樣的值,值在計(jì)算機(jī)內(nèi)的表示方式,以及對(duì)他能施加什么運(yùn)算。名字的作用域規(guī)定了他的值存在范圍。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,二、數(shù)據(jù)結(jié)構(gòu) 許多程序語(yǔ)言提供了一種由初級(jí)數(shù)據(jù)定義復(fù)雜數(shù)據(jù)的手段。下面我們將概述其中常見的定義方式: a. 數(shù)組 從邏輯上說(shuō),一個(gè)數(shù)組是由同一類型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)。沿著每一維的距離稱為一個(gè)下標(biāo)。數(shù)組的每個(gè)元素是矩

15、形結(jié)構(gòu)中的一個(gè)點(diǎn),它的位置可通過(guò)給出每維的下標(biāo)來(lái)確定。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,數(shù)組的每個(gè)元素 (也稱為下標(biāo)變量)是由數(shù)組名連同各維的下標(biāo)值命名的。如A(i1,i2…,in) 。根據(jù)數(shù)組的類型,每個(gè)數(shù)組元素在計(jì)算機(jī)中占有同樣大小的存儲(chǔ)空間。如果一個(gè)數(shù)組所需的存儲(chǔ)空間大小在編譯時(shí)就已知道則稱此數(shù)組是一個(gè)確定數(shù)組;否則稱為可變數(shù)組。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,數(shù)組的存儲(chǔ)表示有多種形式,最簡(jiǎn)單的一種是把整個(gè)數(shù)組按行(或按列)存放

16、在一片連續(xù)存儲(chǔ)區(qū)中。 數(shù)組元素的地址計(jì)算和數(shù)組的存儲(chǔ)方式密切相關(guān)。關(guān)于數(shù)組元素的地址計(jì)算公式,數(shù)據(jù)結(jié)構(gòu)教材中有詳細(xì)的介紹。編譯程序要做的就是實(shí)現(xiàn)地址計(jì)算公式,使數(shù)組元素得到正確的引用。 在編譯過(guò)程中,當(dāng)碰到數(shù)組說(shuō)明時(shí),必須把數(shù)組的有關(guān)的信息記錄在一個(gè)“內(nèi)情向量”之中,以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息。每個(gè)數(shù)組的內(nèi)情向量必須包括:維數(shù),各維的上下限,首地址,以及數(shù)組元素的類型等。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,b

17、.記錄 從邏輯上說(shuō),記錄結(jié)構(gòu)是由已知類型的數(shù)據(jù)組合起來(lái)的一種結(jié)構(gòu)。 記錄結(jié)構(gòu)是許多程序語(yǔ)言的一類重要的數(shù)據(jù)結(jié)構(gòu)。不同語(yǔ)言定義記錄結(jié)構(gòu)的方式也不同。如:Pascal語(yǔ)言采用下面形式定義記錄:CARD: record NAME: array[1…20] of char; AGE:integer; MARRIED:boolean end;,第二章 高級(jí)語(yǔ)言及其語(yǔ)法

18、描述,,這說(shuō)明定義了一個(gè)記錄CARD.它是一個(gè)含有三個(gè)分量的記錄結(jié)構(gòu):NAME,字符數(shù)組;AGE,整型量;MARRIED,布爾量。 記錄結(jié)構(gòu)的每個(gè)分量(域)所需占用的存儲(chǔ)單元(字節(jié))數(shù),成為該域的長(zhǎng)度。當(dāng)知道一個(gè)記錄的地址后,通過(guò)每個(gè)域的長(zhǎng)度就可算出個(gè)域的地址,因?yàn)槲覀內(nèi)菀淄瞥雒總€(gè)域相對(duì)于記錄結(jié)構(gòu)起點(diǎn)的相對(duì)數(shù)OFFSET:此域之前各域長(zhǎng)度的總和。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,如: 就CARD而言,NAME,AGE,

19、MARRIED 的相對(duì)數(shù)OFFSET分別為0、20、24。于是,假定CARD的首地址為a,那么, CARD.NAME 地址為 a CARD.AGE 地址為 a+20 CARD.MARRIED 地址為 a+24,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.2.4 語(yǔ)句與控制結(jié)構(gòu)一、表達(dá)式:一個(gè)表達(dá)式是由運(yùn)算量(亦稱操作數(shù),即數(shù)據(jù)引用或函數(shù)調(diào)用)和算符組成的。 對(duì)于大多數(shù)程序語(yǔ)言來(lái)說(shuō)

20、,表達(dá)式的形成規(guī)則可概括為:(1)變量(包括下標(biāo)變量)、常數(shù)是表達(dá)式;(2)若E1、E2為表達(dá)式,θ為二元算符,則 E1 θ E2為表達(dá)式;(3)若E為表達(dá)式, θ為一元算符,則θE為表達(dá)式;(4)若E為表達(dá)式,則(E)是表達(dá)式。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,在多數(shù)語(yǔ)言中算術(shù)算符和邏輯算符的優(yōu)先順序一般規(guī)定如下:乘冪 ( ** 或 ↑ )一元負(fù) ( - )乘、除 ( * , /, ÷ )加、

21、減 ( + , - )關(guān)系符 ( , , >= ) 非 ( ﹁, not, 或 .NOT. )與 (∧, &, and 或 .AND. )或 ( ∨,∣, or 或 .OR . )隱含 ( ? 或 imp )等值 ( ≡, ~ 或 equi ),第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,算符的代數(shù)性質(zhì)(交換率、結(jié)合率和分配率)常??捎脕?lái)優(yōu)化目標(biāo)程序的質(zhì)量。但

22、是必須注意兩點(diǎn): (1) 代數(shù)性質(zhì)引用到什么程度視具體語(yǔ)言的不同而不同。如在ALGOL中把 A*B+C*D 處理成C*D+A*B, 則至少是對(duì)ALGOL不夠忠實(shí)。 (2)數(shù)學(xué)上成立的代數(shù)性質(zhì)在計(jì)算機(jī)上未必完全成立。如:(A+B)+C=A+(B+C)在計(jì)算機(jī)上并不普遍成立。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,二、語(yǔ)句 不同程序語(yǔ)言含有不同形式和功能的各種語(yǔ)句。從功能上說(shuō)語(yǔ)句大體可分執(zhí)行性語(yǔ)句和說(shuō)明性語(yǔ)句兩大類,說(shuō)

23、明性語(yǔ)句旨在定義不同數(shù)據(jù)類型的變量或運(yùn)算。執(zhí)行性語(yǔ)句旨在描述程序的動(dòng)作。執(zhí)行性語(yǔ)句又可分賦值語(yǔ)句、控制語(yǔ)句和輸入/輸出語(yǔ)句.從形式上說(shuō),語(yǔ)句還可分為簡(jiǎn)單句、復(fù)合句和分程序等。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,1、賦值語(yǔ)句 我們知道,每個(gè)名字有兩方面的特征:一方面它代表一定的存儲(chǔ)單元,另一方面它又以該單元的內(nèi)容作為值。賦值語(yǔ)句A:=B的意義是:“把B的值送入A所代表的單元”也就是說(shuō):在賦值句中,賦值號(hào)‘:=’左右兩邊的變量名扮演著兩

24、種不同的角色。對(duì)賦值號(hào)右邊的B我們需要的是它的值;對(duì)于左邊的A我們需要的是它們的所代表的存儲(chǔ)單元(的地址)。為了區(qū)分一個(gè)名字的這兩種特征,我們把一個(gè)名字所代表的那個(gè)存儲(chǔ)單元(地址)稱為該名字的左值;把一個(gè)名字的值稱為該名字的右值。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2、控制語(yǔ)句多數(shù)語(yǔ)言中所含的控制語(yǔ)句有:無(wú)條件轉(zhuǎn)移語(yǔ)句: goto L條件語(yǔ)句: if B then S if B then S1 e

25、lse S2循環(huán)與句: 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) 重要的是我們必須了解這些語(yǔ)句在不同語(yǔ)言中的不同含義。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,3、說(shuō)明語(yǔ)句 說(shuō)明語(yǔ)句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號(hào)表

26、中,并檢查程序中名字的引用和說(shuō)明是否相一致。許多說(shuō)明語(yǔ)句沒(méi)有相應(yīng)的代碼。但有些語(yǔ)句,如過(guò)程說(shuō)明語(yǔ)句,和可變數(shù)組說(shuō)明語(yǔ)句則有相應(yīng)的目標(biāo)代碼。4、簡(jiǎn)單句和復(fù)合句 簡(jiǎn)單句是指那些不含其它語(yǔ)句成分的基本句,如賦值句、 goto句等。 復(fù)合句則指那些句中有句的語(yǔ)句。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,本節(jié)內(nèi)容是對(duì)高級(jí)語(yǔ)言中為編譯原理課程所關(guān)心特性的總結(jié),第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.3 程序語(yǔ)言的語(yǔ)法描述 對(duì)于高級(jí)程序

27、語(yǔ)言及編譯程序而言,語(yǔ)言的語(yǔ)法定義是非常重要的。本節(jié)將介紹語(yǔ)法結(jié)構(gòu)的形式描述問(wèn)題。首先引入幾個(gè)概念: 設(shè)?是一個(gè)有窮字母表,它的每個(gè)元素稱為一個(gè)符號(hào)。 ?上的一個(gè)符號(hào)串是指由?中的符號(hào)所構(gòu)成的又窮序列。不包含符號(hào)的序列稱為空字,記為?。用?*表示?上的所有符號(hào)串的全體,空字也包括在其中。如:若?={a,b}則?*={??,a,b,aa,ab,bb,aaa,…}。?表示不含任何元素的空集{}。這里要注意?、{}和{?}的區(qū)別。,

28、第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,?*的子集U和V中的(連接)積定義為: UV={??∣??U & ??V } 即集合UV中的符號(hào)串是由U和V的符號(hào)串連接而成的。注意,一般UV?VU,但(UV)W=U(VW).V自身的n次(連接)積記為: Vn = V V…V (n個(gè)V)規(guī)定 V0 = {?}. 令: V* = V0?V1?V2?… 稱 V*是V的閉包。記V+ = VV*, 稱 V+

29、是V的正則包。 閉包V*中的每個(gè)符號(hào)都是由V中的符號(hào)串經(jīng)有限次連接而成的。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.3.1 上下文無(wú)關(guān)文法: 文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則(即語(yǔ)法規(guī)則)。 所謂上下文無(wú)關(guān)文法是這樣一種文法,它所定義的語(yǔ)法范疇(或語(yǔ)法單位)是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。 請(qǐng)仔細(xì)閱讀課本P27頁(yè)的英文分析的例句,定義英文句子的規(guī)則可以說(shuō)是一個(gè)上下文無(wú)關(guān)文法。其中He, me, book,

30、 gave,a 等,稱為終結(jié)符號(hào);、、等為非終結(jié)符號(hào);這個(gè)文法最終是要定義的語(yǔ)法結(jié)構(gòu),所以在這里成為開始符號(hào);→ 這種書寫形式稱為產(chǎn)生式。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,歸納起來(lái),一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分:一組終結(jié)符號(hào),一組非終結(jié)符,一個(gè)開始符號(hào),以及一組產(chǎn)生式。所謂終結(jié)符號(hào)乃是組成語(yǔ)言的基本符號(hào),即在程序語(yǔ)言中以前屢次提到的單詞符號(hào),如基本字,標(biāo)識(shí)符,常數(shù),算符和界符等所謂非終結(jié)符號(hào)(也稱語(yǔ)法變量)用來(lái)代表語(yǔ)法范疇。

31、如“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“過(guò)程”等。一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念。因此非終結(jié)符是一個(gè)類(或集合)記號(hào),而不是個(gè)體記號(hào)。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,開始符號(hào)是一個(gè)特殊的非終結(jié)符號(hào),它代表所定義的語(yǔ)言中我們最感興趣的語(yǔ)法范疇,這個(gè)語(yǔ)法范疇通常稱為“句子”。但在程序語(yǔ)言中我們最終感興趣的是“程序”這個(gè)語(yǔ)法范疇,而其他的語(yǔ)法范疇都只不過(guò)是構(gòu)造“程序”的一塊塊磚石。產(chǎn)生式(也稱為產(chǎn)生規(guī)則或簡(jiǎn)稱規(guī)則)是定義語(yǔ)法范疇的一種書寫

32、規(guī)則。一個(gè)產(chǎn)生式的形式是 A→ α ,其中箭頭左邊的A是一個(gè)終結(jié)符,稱為產(chǎn)生式的左部符號(hào);箭頭右邊的α是終結(jié)符號(hào)或與非終結(jié)符號(hào)組成的一符號(hào)串,稱為產(chǎn)生式的右部。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,產(chǎn)生式是定義語(yǔ)法范疇的。如要定義一類含+、*的算術(shù)表達(dá)式,這個(gè)定義可以這樣給出:“變量是一個(gè)算術(shù)表達(dá)式;若E1和E2是算術(shù)表達(dá)式,則E1+E2、E1*E2和(E1)也是算術(shù)表達(dá)式。 對(duì)于這個(gè)定義,用產(chǎn)生式描述: E→i

33、 ?。拧牛拧 。?→E*E ?。拧ǎ牛┢渲校糯怼八阈g(shù)表達(dá)式”,i代表“變量”,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,形式上定義一個(gè)上下文無(wú)關(guān)文法G是一個(gè) 四元式(VT,VN,S,£)其中VT是一個(gè)非空有限集,它的每一個(gè)元素 稱為終結(jié)符號(hào);VN是一個(gè)非空有限集,它的每一個(gè)元素稱為非終結(jié)符號(hào),VT∩VN=?;S是一個(gè)非終結(jié)符號(hào),稱為開始符號(hào);£是一個(gè)產(chǎn)生式(有限)集合,每個(gè)產(chǎn)生式形式是P→? ,其中,P∈VN, 

34、  ? ∈( VT∪VN)*開始符號(hào)S至少必須在某一產(chǎn)生式的左部出現(xiàn)一次。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,假定G是一個(gè)文法,S是它的開始符號(hào)。如果S?*?(表示從S出發(fā),經(jīng)0步或若干步可推出?),則稱?是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言,將它記為L(zhǎng)(G). L(G)={?|S ?+ ? & ?∈VT }例如:終結(jié)符號(hào)串(i*i+i)是文法 E→E+E|E*E|(E)

35、|i    (2.1) 的一個(gè)句子。是因?yàn)橛?E?(E)?(E+E) ? (E*E+E) ? (i*E+E) ? (i*i+E) ? (i*i+i)從開始符號(hào)E至 (i*i+i)的一個(gè)推導(dǎo)。而E,(E),(E*E+E)等是文法的句型。,,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,下面介紹幾個(gè)簡(jiǎn)單文法的例子: 例2.1考慮一個(gè)文法G1: S→bA A→aA|a 它定義了一個(gè)什么語(yǔ)言呢?從

36、開始符S出發(fā),我們可以推出如下句子: S?bA ?ba S?bA ?baA ?baa S?bA ?baA ? … ? baa…a可以寫為:L(G1)={ban|n≥1},第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,例2.2 設(shè)有文法G S→P|aPPb P →ba|bQa Q →ab 求語(yǔ)言L(G). 解: L(G)={ba,baba,abab,ababab

37、… }例2.3 構(gòu)造一個(gè)文法G3使 L(G3)={anbn|n≥1} 解; S→aSb|ab,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,為了對(duì)句子結(jié)構(gòu)進(jìn)行確定性分析,我們往往只考慮最左推導(dǎo)或最右推導(dǎo)。所謂最左推導(dǎo)是指:任何一步???都是對(duì)?中的最左非終結(jié)符進(jìn)行替換的。同樣,可定義最右推導(dǎo)。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.3.2 語(yǔ)法分析樹與二義性 前面我們提到過(guò)可以用一張圖表示一個(gè)句型的推導(dǎo),這種表示稱

38、為語(yǔ)法分析樹,或簡(jiǎn)稱語(yǔ)法樹。 語(yǔ)法樹的根結(jié)由開始符號(hào)所標(biāo)記。隨著推導(dǎo)的展開,當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí),這個(gè)非終結(jié)符的相應(yīng)結(jié)就產(chǎn)生了下一代新結(jié)。每個(gè)新結(jié)和其父親結(jié)間都有一條連線。在一棵語(yǔ)法樹生長(zhǎng)過(guò)程中的任何時(shí)刻,所有那些沒(méi)有后代的端末結(jié)自左至右排列起來(lái)就是一個(gè)句型。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,例如對(duì)于文法(2.1)關(guān)于(i*i+i)的推導(dǎo)形成語(yǔ)法樹如圖2.2,,,,圖 2.2 語(yǔ)法樹,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描

39、述,,一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹呢?也就是說(shuō)它是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?不盡然。 如文法2.1,關(guān)于(i*i+i)就存在一個(gè)與2.2非常不同的推導(dǎo): E??(E) ?(E*E) ?(i*E) ?(i*E+E) ?(i*i+E) ?(i*i+i)其對(duì)應(yīng)語(yǔ)法樹:,,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,圖2.2與圖2.3的不同之處在于從第二代三代過(guò)渡開始。對(duì)于前者,我們選用規(guī)則E→E+E,而后者我們選用E→E*

40、E。這里不是同代兄弟生兒子的先后次序的不同而是生什么兒子的不同,后面的這個(gè)不同是本質(zhì)上的的差異。這意味著我們可以用兩種完全不同的辦法產(chǎn)生同一個(gè)句子。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹,則稱這個(gè)文法是二義的。也就是說(shuō),若一個(gè)文法存在某個(gè)句子,它有兩個(gè)不同的最左(最右)推導(dǎo),則這個(gè)文法是法是二義的。 最后,作為描述程序語(yǔ)言的上下文無(wú)關(guān)文法,我們對(duì)它有幾點(diǎn)限制。 (1)文法中不含任何

41、下面形式的產(chǎn)生式: P→P因?yàn)檫@種產(chǎn)生式除了產(chǎn)生二義性外沒(méi)有任何用處。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,(2)每個(gè)非終結(jié)符P必須有用處。這一方面意味著,必須存在含P的句型;也就是,從開始符號(hào)出發(fā),存在推導(dǎo) S?*?P?. 另一方面意味著,必須存在終結(jié)符串??VT*,使得P?+?;也就是,對(duì)于P不存在永不終結(jié)的回路。 我們以后所討論的文法均假定滿足上述兩條件。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2.3.3 形式語(yǔ)言鳥瞰:

42、 喬姆斯基把文法分為四種類型即0型、1型、2型、3型。0行強(qiáng)于1型,1行強(qiáng)于2型,2型強(qiáng)于3型。這幾文法的差別在于對(duì)產(chǎn)生式施加不同的限制。 我們說(shuō)G=(VT ,VN ,S ,?) 是一個(gè)0型文法,如果它的每個(gè)產(chǎn)生式 ???是這樣的結(jié)構(gòu) ??(VN?VT)* 且至少有一個(gè)非終結(jié)符,而??(VN?VT)* 。0型文法也稱短語(yǔ)文法。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,如果對(duì)0型文法分別施加以下的第i條限制,則我們

43、就得到第i型文法: (1)G的任何產(chǎn)生式 ??? 均滿足 |?|≤ |?|(其中|?|和|?|分別為?和?的長(zhǎng)度;僅S??例外,但S不得出現(xiàn)在任何產(chǎn)生式的右部。 (2)G的任何產(chǎn)生式為A??, A?VN , ??(VN? VT)* 。 (3) G的任何產(chǎn)生式為A??B或 A??,其中??VT*,A、B ? VN 。 其中1型文法也稱上下文有關(guān)文法。這種文法意味著,對(duì)非終結(jié)符進(jìn)行替換式務(wù)必考慮上下

44、文并且一般不允許替換成空串?。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,2型文法也稱上下文無(wú)關(guān)文法,注意其語(yǔ)言定義: G的任何產(chǎn)生式為A→β,A∈VN, β∈(VN∪VT)*   表明凡出現(xiàn)在產(chǎn)生式左邊的符號(hào)都是非終結(jié)符。 3型文法也稱右線性文法。3型文法還有另一種形式,稱左線性文法:一個(gè)文法G為左線性文法,如果G的任何產(chǎn)生式為 A→B? 或A→? ,其中?∈VT* ,

45、 A、B ∈ VN 由于3型文法等價(jià)于正規(guī)式所以也稱正規(guī)文法。,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,例題與習(xí)題解答,[例2.1]: 試構(gòu)造生成語(yǔ)言L={anbnci|n?1, i ?0}的文法 解:G(Z): Z?AB A ?aAb|ab B ?cB|?[例2.2]: 已知

46、語(yǔ)言L={anbbn| n ?1}, 寫出產(chǎn)生L的文法。,,,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,[解]: G[S]: S ?aAb A ?aAb|b[例2.3]: 已知文法G=({A,B,C},{a,b,c},A,P)其中產(chǎn)生式P由以下組成: A ?abc A ?aBbc Bb ?bB Bc ?Cbcc bC

47、?Cb aC ?aaB aC ?aa 問(wèn):此文法表式的語(yǔ)言是什么?,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,[解]:由于A為開始符。 由于A?aBbc ?abBc ?abCbcc ?aCbbcc ?aabbcc 語(yǔ)言為: {anbncn, n>0 }[例2.4]:試構(gòu)造語(yǔ)言L={anbnci | n>=1, i>=0}的文法。 [解]: G(Z):

48、 Z ?AB A ?aAb|ab B ?cB|?,第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述,,[例2.5]:試寫一文法,使其描述的語(yǔ)言L(G) 是能被5整除的整數(shù)集合。 解: G(Z): Z ?(+|- )A(0|5) A ?0|1|2|3|4|5|6|7

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論