第二章高級語言及其語法描述-read

1、第二章 高級語言及其語法描述,第二章 高級語言及其語法描述,本章概述高級語言的結(jié)構(gòu)和主要的共同特征，并介紹程序語言的語法描述方法。要學習和構(gòu)造編譯程序，理解和定義高級語言是必不可少的。 2.1 程序語言的定義 任何語言實現(xiàn)的基礎是語言的定義。在定義方面，編譯程序研制者與一般用戶有所不同，他們對那些構(gòu)造允許出現(xiàn)更感興趣。即使一時不能看出某種構(gòu)造的實際應用，或者判斷實現(xiàn)該結(jié)構(gòu)會導致嚴重的困難，但仍必須嚴格根據(jù)語言的定義實現(xiàn)它。

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

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

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

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

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

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

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

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

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

11、,第二章 高級語言及其語法描述,,Pascal這種嵌套結(jié)構(gòu)中允許同一標識符在不同的子程序段中表示不同的名字。關(guān)于名字的作用域的規(guī)定是： a.一個在子程序B1中說明的名字X只在B1中有效（局部于B1）。 b.如果B2是B1的一個內(nèi)層子程序，且B2中對標識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2中對X的任何引用都是指重新說明過的這個X。,第二章 高級語言及其語法描述,,2.2.3

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

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

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

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

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

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

18、描述,,這說明定義了一個記錄CARD.它是一個含有三個分量的記錄結(jié)構(gòu)：NAME,字符數(shù)組；AGE,整型量；MARRIED,布爾量。 記錄結(jié)構(gòu)的每個分量（域）所需占用的存儲單元（字節(jié)）數(shù)，成為該域的長度。當知道一個記錄的地址后，通過每個域的長度就可算出個域的地址，因為我們?nèi)菀淄瞥雒總€域相對于記錄結(jié)構(gòu)起點的相對數(shù)OFFSET：此域之前各域長度的總和。,第二章 高級語言及其語法描述,,如： 就CARD而言，NAME,AGE,

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

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

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

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

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

24、種不同的角色。對賦值號右邊的B我們需要的是它的值；對于左邊的A我們需要的是它們的所代表的存儲單元（的地址）。為了區(qū)分一個名字的這兩種特征，我們把一個名字所代表的那個存儲單元（地址）稱為該名字的左值；把一個名字的值稱為該名字的右值。,第二章 高級語言及其語法描述,,2、控制語句多數(shù)語言中所含的控制語句有：無條件轉(zhuǎn)移語句: goto L條件語句： 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過程調(diào)用語句： call P( X1,X2,…,Xn)返回語句： return(E) 重要的是我們必須了解這些語句在不同語言中的不同含義。,第二章 高級語言及其語法描述,,3、說明語句 說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表

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

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

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

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

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

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

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

33、　?。拧牛拧　。?→Ｅ＊Ｅ　?。拧ǎ牛┢渲校糯怼八阈g(shù)表達式”，ｉ代表“變量”,第二章 高級語言及其語法描述,,形式上定義一個上下文無關(guān)文法Ｇ是一個 四元式（ＶＴ，ＶＮ，Ｓ，￡）其中ＶＴ是一個非空有限集，它的每一個元素 稱為終結(jié)符號；ＶＮ是一個非空有限集，它的每一個元素稱為非終結(jié)符號，ＶＴ∩ＶＮ＝?；Ｓ是一個非終結(jié)符號，稱為開始符號；￡是一個產(chǎn)生式（有限）集合，每個產(chǎn)生式形式是Ｐ→?　，其中，Ｐ∈ＶＮ，　

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

35、|ｉ　　　 (2.1) 的一個句子。是因為有 E?(E)?(E+E) ? (E*E+E) ? (i*E+E) ? (i*i+E) ? (i*i+i)從開始符號E至 （i*i+i)的一個推導。而E,(E),(E*E+E)等是文法的句型。,,第二章 高級語言及其語法描述,,下面介紹幾個簡單文法的例子： 例2.1考慮一個文法G1: S→bA A→aA|a 它定義了一個什么語言呢？從

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

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

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

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

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

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

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

43、就得到第i型文法: (1)G的任何產(chǎn)生式 ??? 均滿足 |?|≤ |?|（其中|?|和|?|分別為?和?的長度；僅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)文法。這種文法意味著，對非終結(jié)符進行替換式務必考慮上下

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

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

46、語言L={anbbn| n ?1}, 寫出產(chǎn)生L的文法。,,,第二章 高級語言及其語法描述,,[解]： 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 問：此文法表式的語言是什么？,第二章 高級語言及其語法描述,,[解]：由于A為開始符。 由于A?aBbc ?abBc ?abCbcc ?aCbbcc ?aabbcc 語言為： {anbncn, n>0 }[例2.4]：試構(gòu)造語言L={anbnci | n>=1, i>=0}的文法。 [解]： G(Z):

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