《《形式語(yǔ)言概述》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《形式語(yǔ)言概述》PPT課件.ppt（81頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第二章形式語(yǔ)言概述,本章學(xué)習(xí)目標(biāo),形式語(yǔ)言由Chomsky于1956年提出，主要討論語(yǔ)言和文法的數(shù)學(xué)機(jī)制以及語(yǔ)言和文法的分類。形式語(yǔ)言 的形成和發(fā)展，對(duì)編譯原理和技術(shù)產(chǎn)生了重要的影響。本章主要內(nèi)容是: 文法和語(yǔ)言的形式定義 文法的分類 句型的分析和語(yǔ)法樹,字母表,字母表 是元素的非空有窮集合，字母表中的元素稱為符號(hào)，因此字母表也稱為符號(hào)表。高級(jí)語(yǔ)言如C語(yǔ)言的字母表是由字母、數(shù)字、特殊符號(hào)和一些專用符號(hào)構(gòu)成。 字母表可以用表示 例：=a,b， =0,1， =0,1，2，3，4，5，6，7，8，9， =a,b,c,z,if,then,else,main,1,2,3,4,,9,0,=,==,,<,;

2、（，）,2.1.2 符號(hào)串,（1）符號(hào) 語(yǔ)言中最基本的不可再分的單位 （2）符號(hào)串 符號(hào)串是由字母表中的符號(hào)所組成的有窮序列。符號(hào)串由小寫x,y,z表示 例 ：某個(gè)字母表=a,b,c,z,if,then,else,main,1,2,3,4,,9,0,=,==,,<,;，則建立在上的符號(hào)串有：if (2+3==5) then a=6 else b=8; 空串是不含任何符號(hào)的串，記作 （3）符號(hào)串的長(zhǎng)度 符號(hào)串x中所包含的符號(hào)的個(gè)數(shù)稱為符號(hào)串x的長(zhǎng)度，記為|x| 。 例：字母表0，1，則|010110|=6。空串的長(zhǎng)度為0。,（4）子字符串 設(shè)有非空符號(hào)串u=xvy，其中x、v、y是符號(hào)串，且v，

3、則稱v為符號(hào)串u的子符號(hào)串。 例：設(shè)字母表=a，b，c，d，+，-，*，/，(，)上有符號(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 （5）符號(hào)串的頭和尾 如果z=xy是一個(gè)符號(hào)串，則x是z的頭,而y是z的尾。如果y非空，則x是z的固有頭，又稱為真前綴；若x非空，則y是z的固有尾，又稱為真后綴。 例 假設(shè)字母表=a,b,c上的符號(hào)串z=abc，則、a、ab、abc都是z的頭，且除abc外都是z的固有頭；、c、bc、abc都是z 的尾，且除abc外都是z的固有尾。,若只對(duì)符號(hào)串的頭部感興趣，記做z=x。若只對(duì)尾部感興

4、趣，則記為z=x。,符號(hào)串的運(yùn)算,連接（乘積）運(yùn)算 設(shè) x與y是同一個(gè)字母表上的兩個(gè)符號(hào)串，把y的各個(gè)符號(hào)相繼寫在x的符號(hào)后所得到的符號(hào)串稱為x與y的連接，記為xy。 例：設(shè)在字母表a,b,c上有符號(hào)串 x=ab與y=cba，則z=xy=abcba。這里x=2, y=3, z=5。 對(duì)于字母表上的任何符號(hào)串x，都有x=x=x 注：xy!=yx 符號(hào)串的方冪 設(shè)x是某個(gè)字母表上的符號(hào)串，把x自身連接n次，即z=xxx（n個(gè)x），稱為符號(hào)串x的n次方冪，記為z=xn。 例: x=ab x3=ababab,2.1.3 符號(hào)串集合,符號(hào)串集合 集合A中一切元素都是某字母表上的符號(hào)串，則稱A是該字母

5、表上的符號(hào)串的集合。 字母表上的符號(hào)串的集合通常用大寫字母來A、B、C、表示。 例： 設(shè)某個(gè)字母表a,b,c,d, 符號(hào)串集合A，B A=a,bc, B=abc,cd,ab,乘積 兩個(gè)符號(hào)串集合A和B的乘積AB定義為AB=xyxA ，且yB 例: 設(shè)A=a,b，B=c,d,e 則AB=ac,ad,ae,bc,bd,be 對(duì)于任何空集合，都有A=A=A 方冪 類似于符號(hào)串的方冪，可以定義符號(hào)串集合的方冪，特別地定義字母表A的方冪為： A0=，A1=A，An=An-1A (n0),符號(hào)串集合的運(yùn)算,字母表的閉包與正閉包的運(yùn)算 閉包 設(shè)有字母表A，A的閉包定義如下： A*=A0A1 A2 An

6、,其中，An （n=0，1，2，3，）中所有的符號(hào)串的長(zhǎng)度為n，因此字母表A的閉包 A*為字母表上一切長(zhǎng)度為n的符號(hào)串所組成的集合。 注：閉包可以看作由A上符號(hào)組成的所有串的集合（包括空串） 正閉包 如果不允許包含空串，則得到字母表A的正閉包。 A的正閉包 A+=A1 A2 An 注：正閉包可以看作由A上符號(hào)組成的所有串的集合（不包括空串） 語(yǔ)言 字母表上按照某種規(guī)則形成的某個(gè)符號(hào)串的集合，所以，語(yǔ)言是該字母表上正閉包的子集,例：設(shè)字母表=a,b,c,依次寫出長(zhǎng)度為1、2、3的符號(hào)串，可得到 的正閉包 + ：+=a,b,c,aa,ab,ac,bb,bc,aaa,aab,aac,abb,abc,

7、baa, 在+上添入空串即得*。,2.2 文法的定義及其分類,什么是文法? 描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則，嚴(yán)格地定義句子的結(jié)構(gòu)，用適當(dāng)條數(shù)的規(guī)則把語(yǔ)言的全部句子描述出來，是以有窮的集合刻劃無窮的集合的工具。, ::= ::= | ::= 我|你|他 ::= ::= 是|學(xué)習(xí) ::= |,我是大學(xué)生的推導(dǎo)過程： = = = 我 =我 =我是 =我是 =我是大學(xué)生,2.2.2 文法的形式定義(1),非終結(jié)符 出現(xiàn)在規(guī)則的左部，用括起來，表示一定語(yǔ)法概念的詞， 用VN表示 終結(jié)符 語(yǔ)言中不可再分割的字符串（包括單個(gè)字符組成的串） 用VT表示 V= VN U VT 開始

8、符號(hào) 表示所定義的語(yǔ)法范疇的非終結(jié)符又稱為識(shí)別符號(hào) 開始符號(hào)用S表示,2.2.2 文法的形式定義(2),重寫規(guī)則 也叫產(chǎn)生式規(guī)則，或稱為生成式，是形如或::=的(,)有序?qū)?其中, 是某個(gè)字母表V+中的一個(gè)元素，是V* 中的一個(gè)元素。稱為規(guī)則的左部，稱為規(guī)則的右部。 例： AB讀作“A定義為B”，也就是說它是一條關(guān)于A的規(guī)則（產(chǎn)生式）。 文法 文法G是一個(gè)四元組，G=（VN，VT，P，S），其中，VN、VT分別是非空有限的非終結(jié)符號(hào)集和終結(jié)符號(hào)集，VNVT=，P是產(chǎn)生式的集合，SVN 為文法的識(shí)別符號(hào)或開始符號(hào)。,例： 在程序設(shè)計(jì)語(yǔ)言中，假設(shè)我們定義標(biāo)識(shí)符的命名規(guī)則為字母a、b、c開頭的，字母

9、a、b、c和數(shù)字1、2、3的序列。命名規(guī)則為： a b c 1 2 3,我們一般用大寫字母代表左邊的非終結(jié)符，設(shè)N 代表，D代表，L代表，則定義標(biāo)識(shí)符的文法是： G=(VN，VT，P，S)其中，VN=N，L，D ,VT=a,b,c,1,2,3 P為產(chǎn)生式的規(guī)則： NL， NNL ，NND ，La ，Lb ，Lc ，D1 ，D2，D3 S 是開始符號(hào), 為N 注：產(chǎn)生式的規(guī)則說明一點(diǎn)，即若A，A，A可寫成A|| 。“|” 讀做 “或者”。 上面的產(chǎn)生式規(guī)則可以改寫為： NL|NL|ND La|b| c D1|2|3,2.2.3 文法的分類,喬姆斯基（Chomsky）于1956年建立形式語(yǔ)言的

10、描述以來，把文法分成四種類型，即0型、1型、2型和3型文法。 0型文法(短語(yǔ)文法) 設(shè)G=（VN，VT，P，S），如果它的每個(gè)產(chǎn)生式是這樣一種結(jié)構(gòu)：(VNVT )+ ，且至少含有一個(gè)非終結(jié)符，而（VNVT ）*，則稱G是一個(gè)0型文法。0型文法又稱短語(yǔ)文法，它的能力相當(dāng)于一個(gè)圖靈機(jī)。 例如，A 圖靈機(jī)是識(shí)別0型文法的識(shí)別裝置 0型文法是對(duì)產(chǎn)生式限制最少的文法； 對(duì)0型文法產(chǎn)生式的形式作某些限制，可得到其他類型文法的定義。,1型文法（上下文有關(guān)文法） 設(shè)G=（VN，VT，P，S）為一文法，若P中的每一個(gè)產(chǎn)生式均滿足，僅僅S除外，則文法G是1型文法或上下文有關(guān)文法。 所謂上下文有關(guān)文法即：=1A2，

11、=1B2，符號(hào)串1 和2可以認(rèn)為是上下文，A只有出現(xiàn)在上下文之間中，才可以被符號(hào)串B替代，成為=1A2=1B2因此，1型文法又稱為上下文有關(guān)文法。 能夠識(shí)別上下文無關(guān)語(yǔ)言的自動(dòng)機(jī)稱為線性界限自動(dòng)機(jī)?？s寫為L(zhǎng)BA 注：1型文法意味著，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文，并且，一般不允許替換成 ，除非是開始符號(hào)產(chǎn)生,2型文法（上下文無關(guān)文法） 設(shè)G=(VN，VT，P，S)，若P中的每個(gè)產(chǎn)生式滿足: 是一個(gè)非終結(jié)符, (VNVT ) *，則此文法稱為2 型文法或上下文無關(guān)文法。有時(shí)將2型文法的產(chǎn)生式表示為形如：A，其中AVN 。 也就是當(dāng)用取代非終結(jié)符A時(shí)，與A所在的上下文無關(guān)。上下文無關(guān)文法有足夠

12、的能力描述現(xiàn)今的程序設(shè)計(jì)語(yǔ)言。 識(shí)別上下文無關(guān)語(yǔ)言的自動(dòng)機(jī)稱為下推自動(dòng)機(jī)。它是?？s寫為PDA。 例: 2 型文法 G=（VN，VT，P，N） 其中，VN=N，D VT=0，1，2，3，4，5，6，7，8，9 P=NNDD，D0123456789 注：該文法描述的符號(hào)串的集合是整數(shù)。,3型文法（右線性文法或正規(guī)文法） 對(duì)2型文法的產(chǎn)生式做進(jìn)一步的限制，限制產(chǎn)生式右部是單一終結(jié)符或單一終結(jié)符跟著單一非終結(jié)符，即：Aa ,AaB 則稱該文法為3型文法，又稱為右線性文法或正規(guī)文法，其中A、BVN，aVT. 識(shí)別3型語(yǔ)言或正則語(yǔ)言的自動(dòng)機(jī)稱為有窮自動(dòng)機(jī)?？s寫為FA。 例: 3型文法 G=（VN，VT，P

13、，S） 其中，VN=S，A，B VT=0，1 P=S011A0B，A1A0B，B010B 注：該文法產(chǎn)生的是二進(jìn)制整數(shù)。,2.2.4 文法舉例,例：1型文法 G=（VN，VT，P，A） VN=S,X,Y,Z VT=x,y,z P= S xSYZxYZ xYxy yYyy yZ yz ZY YZ zZ zz ,例：2型文法 G=（VN，VT，P，E） VN=E，T，F(xiàn)， VT=+，*，（，），i P= EE+T|T, TT*F|T, F(E)|i 注：該文法能推出具有乘和加運(yùn)算的算術(shù)表達(dá)式。,例：正規(guī)文法 G=（VN，VT，P，S）其中VN=S，A，B，G，H， VT=d，，+， P= SdB

14、 | +A | A | .G AdB | .G BdB | .H |d GdH HdH | d 其中，d代表十進(jìn)制數(shù)字。 根據(jù)以上我們對(duì)文法的定義我們不難發(fā)現(xiàn)3型文法類是2型文法類的特殊情況，2型文法類是1型文法類的特殊情況。每一類文法都是在前一類文法的基礎(chǔ)上加上一些限定規(guī)則而產(chǎn)生的。因此，四類文法產(chǎn)生的語(yǔ)言就會(huì)有如下關(guān)系： 3型語(yǔ)言2型語(yǔ)言1型語(yǔ)言0型語(yǔ)言,2.2.6 文法分類的意義,一個(gè)文法實(shí)際上是某種語(yǔ)言的一個(gè)簡(jiǎn)明、確切的描述，它表示了該語(yǔ)言中所允許的一類語(yǔ)法結(jié)構(gòu)。從一個(gè)文法能推導(dǎo)出多個(gè)終結(jié)符的句子。但是知道了如何去構(gòu)造屬于某一個(gè)語(yǔ)言的一個(gè)合法串只是問題的一個(gè)方面。同時(shí)我們還要有

15、能力判定一個(gè)串是否合法。也就是說，我們需要確定這個(gè)給定串的推導(dǎo)序列。如果從文法出發(fā)找不到這個(gè)推導(dǎo)序列，則該串就是非法的。 程序設(shè)計(jì)語(yǔ)言的詞法分析屬于正規(guī)文法，與局部語(yǔ)法相關(guān)的部分屬于上下文無關(guān)文法，與全局語(yǔ)法和語(yǔ)義有關(guān)的部分屬于上下文有關(guān)文法。,2.3 文法產(chǎn)生的語(yǔ)言和句型的語(yǔ)法樹,推導(dǎo) 推導(dǎo)是從開始符號(hào)開始，通過使用產(chǎn)生式的右部取代左部，最終能產(chǎn)生語(yǔ)言的一個(gè)句子的過程。 最左（右）推導(dǎo)：每次使用一個(gè)規(guī)則，以其右部取代符號(hào)串的最左（右）非終結(jié)符。 注：最左推導(dǎo)和最右推導(dǎo)稱為規(guī)范推導(dǎo)： 歸約 歸約是推導(dǎo)的逆過程，即，從給定的源語(yǔ)言的句子開始，通過規(guī)則的左部取代右部，最終達(dá)到開始符號(hào)的過程。 最左

16、(右)歸約是最右(左)推導(dǎo)的逆過程。 注：最左歸約和最右歸約稱為規(guī)范歸約。,文法產(chǎn)生的語(yǔ)言和句型的語(yǔ)法樹（續(xù)）,推導(dǎo)和規(guī)范推導(dǎo) 推導(dǎo)分為三大類：直接推導(dǎo)、，長(zhǎng)度為n(n1)的推導(dǎo)+和長(zhǎng)度為n（ n0）的推導(dǎo) *。 直接推導(dǎo) 如是文法G=(VN,VT,P,S)的規(guī)則（或說是P中的一產(chǎn)生式），,(VNVT)*，則稱符號(hào)串為符號(hào)串應(yīng)用產(chǎn)生式所得到的直接推導(dǎo)。記為。,推導(dǎo)長(zhǎng)度大于0的推導(dǎo) 如果對(duì)于符號(hào)串v 與w存在一個(gè)直接推導(dǎo)序列 u0 u1u2u3un (n0) 其中u0=v與un =w,則稱符號(hào)串v推導(dǎo)出w或稱w歸約到v，記作v +w，稱這個(gè)直接推導(dǎo)序列是長(zhǎng)度為n的推導(dǎo)。 推導(dǎo)長(zhǎng)度大于等于0的推

17、導(dǎo) 如果對(duì)于符號(hào)串v和w，v=w或v=w，則記作v *w，稱符號(hào)串v廣義推導(dǎo)到符號(hào)串w，或稱w廣義歸約到v。,例： 根據(jù)文法，考慮以C語(yǔ)言中的無正負(fù)號(hào)整數(shù)作為識(shí)別符號(hào)的文法。 | 0|1|2|3|4|5|6|7|8|9 VT =0,1,2,3,4,5,6,7,8,9 VN = , , 判斷數(shù)據(jù)2634是否是C語(yǔ)言合法的數(shù)據(jù)? 給出數(shù)據(jù)2634的推導(dǎo)。 4 43434 6342634 由此可見，2634是C 語(yǔ)言的合法數(shù)據(jù)。每一步推導(dǎo)都是直接推導(dǎo)。可以表示為=2634,最左推導(dǎo) 如果在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最左非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最左推導(dǎo)。 最右推導(dǎo) 如

18、果在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最右非終結(jié)符進(jìn)行替換，則稱這種推導(dǎo)為最右推導(dǎo)。 規(guī)范推導(dǎo) 在形式語(yǔ)言中，最右推導(dǎo)常稱為規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。,例： 給出了下列文法G: | 0|1|2|3|4|5|6|7|8|9 VT =0,1,2,3,4,5,6,7,8,9 VN = , , 判斷數(shù)據(jù)2634是否是C語(yǔ)言合法的數(shù)據(jù)? （1）用最右推導(dǎo)，每次用產(chǎn)生式的規(guī)則替換最右邊的非終結(jié)符，推導(dǎo)過程如下： 4434346342634,（2）用最左推導(dǎo)，每次直接推導(dǎo)都替換最左邊的非終結(jié)符，推導(dǎo)過程如下： 2 26 263 2634,2.3.2 句型、句子和語(yǔ)言,句型 設(shè)G

19、S是一個(gè)文法，如果符號(hào)串x是從開始符號(hào)S推導(dǎo)得到的，即有S=*x，xV+，則稱符號(hào)串x是該文法G的一個(gè)句型。 句子 GS是一個(gè)文法，如果符號(hào)串x是從開始符號(hào)S推導(dǎo)得到的，即有S=+x，并且xVT，則稱該符號(hào)串為該文法的一個(gè)句子。 注：實(shí)質(zhì)上，句子是句型的特殊情況，句子是由終結(jié)符組成，而句型是有終結(jié)符和非終結(jié)符組成。 語(yǔ)言: GS是一個(gè)文法，文法G產(chǎn)生的語(yǔ)言L(G)=x|S=*x，并且xVT，即文法的語(yǔ)言是文法所有句子的集合。,句型、句子和語(yǔ)言（續(xù)）,文法規(guī)則的遞歸定義 非終結(jié)符的定義中包含了非終結(jié)符自身。 注：使用文法的遞歸定義要謹(jǐn)慎，要有遞歸出口，否則，可能永遠(yuǎn)產(chǎn)生不出句子。,例：字母表A=

20、0,1 文法： | 0|1 再如：字母表A=0,1 0|1,,,2.3.3 語(yǔ)法樹,在自然語(yǔ)言中，句子結(jié)構(gòu)可以借助一種樹形表示進(jìn)行分析。如下面的句子： They are students and teachers of the Physics Department。 對(duì)該句子的結(jié)構(gòu)進(jìn)行分析，其樹型結(jié)構(gòu)如圖2-3所示，由此可以看出，該句子是由主語(yǔ)、系詞和表語(yǔ)組成，是一個(gè)語(yǔ)法正確的句子。,在自然語(yǔ)言中，可以通過樹型表示直觀地分析句子的結(jié)構(gòu)；在形式語(yǔ)言中，我們提到了句型、推導(dǎo)的概念，在證明某個(gè)符號(hào)串是否是某個(gè)文法的句型時(shí)，采用從文法開始符號(hào)推導(dǎo)的方法，這個(gè)推導(dǎo)過程可以用語(yǔ)法樹直觀的表示出

21、來。語(yǔ)法樹也稱為推導(dǎo)樹，其定義如下：,給定文法G=(VN,VT,P,S) ，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹，這棵樹滿足下列四個(gè)條件： （1）每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。 （2）根的標(biāo)記是S。 （3）若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有 標(biāo)記A，則A肯定在VN中。 （4）如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,n3.nk，其標(biāo)記分別為A1，A2，A3，AK。那么AA1A2A3AK一定是P中的一個(gè)產(chǎn)生式。,例: 設(shè)文法GS ： EE+T|T TT*F|F F(E)|i 證明符號(hào)串E+(E+T)*i是文法的句型?,2.3.4 二義性文法及其他,二義性文

22、法 一個(gè)文法，如果它的一個(gè)句子或句型有兩棵或兩棵以上的語(yǔ)法樹，則稱此句子具有二義性。如果一個(gè)文法含有二義性的句子，則稱該文法具有二義性。 例: 設(shè)文法GS： Sif B then S|if B then S else S|i：=E 給出符號(hào)串if B then if B then S else S的語(yǔ)法樹。 語(yǔ)法樹的結(jié)構(gòu)如圖2-5所示。 從上面的語(yǔ)法圖我們可以看出，字符串if B then if B then S else S能夠畫出兩棵語(yǔ)法樹，所以該文法是一個(gè)二義性文法。,在語(yǔ)言中，為了避免二義性的文法，往往對(duì)文法加以一定的限制， 限制條件語(yǔ)句then之后不允許再是條件語(yǔ)句 從語(yǔ)義解釋方面限

23、制條件語(yǔ)句中的else只能與其前面的、還沒有和其他else配對(duì)的then配對(duì)。,Sif B then S|if B then S else S|i：=E 符號(hào)串if B then if B then S else S,2二義性文法的證明,要判定一個(gè)文法是否是二義性文法，或它是否產(chǎn)生一個(gè)先天二義性的上下文無關(guān)語(yǔ)言，是個(gè)遞歸不可解的。即不存在一個(gè)算法，它能在有限的步驟內(nèi)，確切的判斷出某個(gè)給定的文法是否是一個(gè)二義性文法。 我們要證明一個(gè)文法是否是一個(gè)二義性文法，就是找到該文法的一個(gè)句型特例，能夠畫出這個(gè)句型的兩棵語(yǔ)法樹，該文法就是二義性文法。,例2.25 文法G=（E，+，*，I,(,)，P，E）其

24、中P為： Ei EE+E EE*E E(E) 證明該文法是二義性文法，并將該文法改為等價(jià)的非二義性文法（等價(jià)的文法是指產(chǎn)生的語(yǔ)言相等的文法）?,【證明】取句型i*i+i，寫出該句型的兩個(gè)不同的推導(dǎo)。畫出推導(dǎo)的兩棵不同的語(yǔ)法樹。 推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i 推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i 推導(dǎo)的兩棵語(yǔ)法樹如圖2-6所示。 將文法改為非二義性文法為： ET |E+T TF |T*F F（E）|i,2.3.5 文法產(chǎn)生的語(yǔ)言,例2.26 設(shè)G=（VN，VT，P，S），VN=S,B,E，VT=a,b,c，P由下列產(chǎn)生式組成： SaSBE SaBE E

25、BBE aBab bBbb bEbe eEee （1）問該文法是Chomsky哪一類型的文法？ （2）它生成的語(yǔ)言是什么？,（1）答根據(jù)文法分類定義，由于文法中存在產(chǎn)生式，其左部由長(zhǎng)度大于1的符號(hào)串構(gòu)成，如產(chǎn)生式“EBBE”，顯然不符合Chomsky 的2型和3型文法的定義。該文法產(chǎn)生式左部串的長(zhǎng)度均小于等于右部串的長(zhǎng)度，符合1型文法的定義，所以該文法是上下文有關(guān)文法。,（2）根據(jù)如下推導(dǎo)：對(duì)于每一個(gè)n1，我們將號(hào)產(chǎn)生式使用n-1次，得到推導(dǎo)序列：S an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S an(BE)n，然后從an(BE)n.繼續(xù)推導(dǎo)，總是對(duì)EB使用產(chǎn)生式的右部進(jìn)行替換

26、，而最終在得到的串中，所有的B都限于所有的E。設(shè)n=3，aaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S anBnEn.接著，使用產(chǎn)生式(4)一次,得到SanbBn-1En，然后使用產(chǎn)生式n-1 次得到：S anbnEn，然后使用產(chǎn)生式一次，使用產(chǎn)生式n-1次，得到：S anbnen 因此該文法產(chǎn)生的語(yǔ)言是L(G)=anbnen|n1。,例 ：設(shè)有上下文無關(guān)文法如下： GS： SAB AUT Ua|aU Tb|bT Bc|cC 將文法的產(chǎn)生式代入產(chǎn)生如下文法： GS： SUTB Ua| aU Tb|bT Bc|cC,考察文法，用L(S)，L(U)，L(T)和L(

27、B)分別表示從終結(jié)符S，U，T和B出發(fā)推導(dǎo)出的符號(hào)串的集合，不難發(fā)現(xiàn)： L（U）=ai|i1=a+ L（T）=bj|j1=a+ L（B）=ck|k1=a+ 由于有SUTB，則有： L（S）=L(U)L(T)L(B) =(aibjck|i1,j1, k1) =a+b+c+,語(yǔ)言產(chǎn)生文法 (1),例：設(shè)L1=a2nbn|n=1 且a,b VT試構(gòu)造生成L1的文法G1 設(shè) n=1， L1 =aab n=2， L1 =aaaabb n=3， L1 =aaaaaabbb 所以得：S aaSb S aab,例：構(gòu)造一個(gè)上下文無關(guān)文法G，使其描述的語(yǔ)言L(G)是能夠被5整除的無符號(hào)整數(shù)集合。 能夠被

28、5整除的整數(shù)其結(jié)構(gòu)特點(diǎn)是，末位數(shù)一定是0或5。所以，只要保證生成的整數(shù)末位數(shù)字是0或5即可。據(jù)此，構(gòu)造描述能被5整除的無符號(hào)整數(shù)集合的文法如下： GS： SN0|N5 NDN| D0|1|2|3|4|5|6|7|8|9,語(yǔ)言產(chǎn)生文法 (3),例: 寫出一個(gè)上下文無關(guān)文法G，使得L(G)=anbmcmdn|n0，m1 分析該語(yǔ)言的特點(diǎn)，可以看出，a和d的個(gè)數(shù)是一樣的，b和c的個(gè)數(shù)是一樣的。m的取值范圍從1開始，所以至少有一個(gè)bc，n的最小值為0。寫出文法為： SaSd|A AbAc|bc,2.4 句型分析與句柄,對(duì)于上下文無關(guān)文法，語(yǔ)法樹是句型推導(dǎo)過程的幾何表示；是進(jìn)行句型分析極好的工具。所謂句

29、型分析就是識(shí)別一個(gè)符號(hào)串是否是某一個(gè)文法的句型。進(jìn)一步說就是給定一個(gè)符號(hào)串時(shí)，按照某文法的規(guī)則為該符號(hào)串構(gòu)造推導(dǎo)或語(yǔ)法樹，以此來識(shí)別它是文法的一個(gè)句型。對(duì)于上下文無關(guān)文法，其句型分析方法有兩大類，一類是自上而下的分析方法（又稱自頂向下），另一類是自下而上（自底向上）的分析方法。,2.4.1 自上向下的分析方法,基本思想 自上而下的分析方法就是從識(shí)別符號(hào)出發(fā)，看是否能推導(dǎo)出待檢查的符號(hào)串，如果能推導(dǎo)出這個(gè)符號(hào)串，則表明此符號(hào)串是該文法的句型或句子，否則就不是。 或者說，以文法的識(shí)別符號(hào)作為根結(jié)點(diǎn)，看是否能構(gòu)造出一個(gè)語(yǔ)法樹，而且此語(yǔ)法樹所有葉子結(jié)點(diǎn)從左到右所構(gòu)成的符號(hào)串恰好是待檢查的符號(hào)串。如果能

30、生成這樣的語(yǔ)法樹，則表明待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則就不是。,例 設(shè)文法GS： SaAbc| aB Aba BbeB|d 輸入串：abed，識(shí)別該串是否是該文法的一個(gè)句子? 方法：從文法的識(shí)別符號(hào)S開始出發(fā)，選擇它的一個(gè)產(chǎn)生式SaAbc 得到直接推導(dǎo) S aAbc以識(shí)別符S作為根結(jié)點(diǎn)，構(gòu)造語(yǔ)法樹，如下圖2-7所示,SaAbc| aB Aba BbeB|d,,abed??,2分析過程,符號(hào)串a(chǎn)Abc與待檢查的符號(hào)串a(chǎn)bed的第一個(gè)符號(hào)相匹配。由于符號(hào)串a(chǎn)Abc的第2個(gè)符號(hào)是非終結(jié)符，因此需要對(duì)它進(jìn)行替換。A只有一個(gè)產(chǎn)生式Aba。以其右部替換A，得推導(dǎo)SaAbcababc得到語(yǔ)法樹

31、，如圖2-7（b）所示。 符號(hào)串a(chǎn)babc與待查符號(hào)串a(chǎn)bed的第2個(gè)符號(hào)相匹配，但與第3個(gè)符號(hào)不相匹配，匹配失敗。此時(shí)，需要退回到非終結(jié)符 A，重新選擇S另外的產(chǎn)生式，再做試探。這種選擇的過程稱之為回溯。,選擇S的另外一條產(chǎn)生式的規(guī)則SaB，得到直接推導(dǎo)SaB，得到語(yǔ)法樹2-7（c），再選取其中的一條產(chǎn)生式BbeB，得到推導(dǎo)SaBabeB，得到語(yǔ)法樹如圖（d），將Bd代入即可得到該字符串a(chǎn)bed。,3存在問題,自上而下分析方法是從文法的識(shí)別符號(hào)開始，選擇相應(yīng)的產(chǎn)生式規(guī)則進(jìn)行推導(dǎo)。但在推導(dǎo)過程中會(huì)出現(xiàn)回溯現(xiàn)象。我們把出現(xiàn)回溯的分析稱為不確定的自頂上下分析方法。這種方法花費(fèi)時(shí)間多，效率低，編程實(shí)

32、現(xiàn)時(shí)復(fù)雜，如果對(duì)文法加以限制，就可以避免回溯，這就出現(xiàn)了我們后面要提到的LL(1)分析方法,2.4.2 確定的自上而下的分析方法,例: 設(shè)文法GS SaBc|bCd BeB|f CdC|c 試檢查符號(hào)串a(chǎn)efc是不是該文法的句子?,識(shí)別符S有兩條產(chǎn)生式，它們的右部首符號(hào)分別是終結(jié)符a和b。待檢查符號(hào)串a(chǎn)efc的首符號(hào)是a，所以從識(shí)別符S出發(fā)，只能選擇其產(chǎn)生式SaBc得到直接推導(dǎo)SaBc得到語(yǔ)法樹如圖2-8（a）所示。其中，非終結(jié)符B有兩條產(chǎn)生式，它們右部首符號(hào)分別是終結(jié)符e與f，而待檢查的符號(hào)串a(chǎn)efc的第2個(gè)符號(hào)是終結(jié)符e，所以選擇B的產(chǎn)生式BeB 得到推導(dǎo)SaBcaeBc，得到語(yǔ)法樹如圖2

33、-8（b）所示。,由于待檢查的符號(hào)串a(chǎn)efc的第3個(gè)符號(hào)是終結(jié)符f，因而對(duì)句型aeBc中的非終結(jié)符B選擇其產(chǎn)生式Bf的推導(dǎo)SaBcaeBcaefc得到語(yǔ)法樹如圖2-8（c）所示。 如此推導(dǎo)出的符號(hào)串a(chǎn)efc，語(yǔ)法樹的葉子結(jié)點(diǎn)序列是aefc，與待檢查的符號(hào)串a(chǎn)efc相匹配。,SaBc|bCd BeB|f CdC|c,aefc?,例: 若有文法GS SAp|Bq Aa AcA Bb BdB 當(dāng)輸入串W=ccap，那么試圖推出輸入串的推導(dǎo)過程為： SApcApccApccap 很容易構(gòu)造相應(yīng)語(yǔ)法樹，如圖2-9所示。,2.4.3 自下而上的分析方法,基本思想 自下而上的分析方法的基本思想是從待檢查的符

34、號(hào)串出發(fā)，看最終是否能歸約到文法的識(shí)別符號(hào)。如果能歸約到文法的開始的識(shí)別符號(hào)，則表明此待檢查的符號(hào)串是該文法的一個(gè)句型或句子，否則便不是。,例2.33 若有文法GS ScAd Aab Aa 識(shí)別輸入串w=cabd是否是該文法的句子。 首先從輸入串開始，掃描cabd，從中尋找一個(gè)子串，該子串與某一產(chǎn)生式的右端相匹配。子串a(chǎn)和子串a(chǎn)b都是合格的，假若我們選用了ab，用產(chǎn)生式的左端A去替代它，即把a(bǔ)b歸約到A，得到串cAd。 構(gòu)造一個(gè)直接推導(dǎo)cAdcabd，即從cabd葉子開始向上構(gòu)造語(yǔ)法樹，接下去在得到的串cAd中又找到了子串cAd與產(chǎn)生式的右端相匹配，則用S替代cAd，或稱將cAd歸約到S，得到

35、了又一直接推導(dǎo)ScAd，形成了最終的語(yǔ)法樹。分析過程如圖2-10所示。,2存在問題,在自上向下的分析中，假定要被代換的最左非終結(jié)符的符號(hào)是V，且有n條規(guī)則：V1|2|3||n，那么如何確定用哪個(gè)右部去替換V？有一種解決方法是從各種可能的選擇中挑選一種，并希望它是正確的。如果發(fā)現(xiàn)它是錯(cuò)誤的，我們必須退回，再試著進(jìn)行另外的選擇，這種方式稱為回溯。,在自下向上的分析方法中，在分析程序工作的每一步中，都從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，我們暫且把這個(gè)子串稱為“可歸約串”。出現(xiàn)的問題是如何確定這個(gè)“可歸約串”？比如在上例中，我們?cè)趯?duì)輸入串cabd 的分析中，如果不是選擇ab，用產(chǎn)生式，而

36、是選擇a，用產(chǎn)生式將a歸約到A，那么最終就達(dá)不到S的結(jié)果，也就不知道cabd是一個(gè)句子。因此在歸約時(shí)，ab是“可歸約串”而不是a。如何求“可歸約串”成為自下而上進(jìn)行分析的關(guān)鍵。下面我們用“句柄”的概念來描述“可歸約串”。,3句柄的概念,（1）形式化定義 令G是一文法，S是文法的開始符號(hào)， 是文法的一個(gè)句型。如果有：S=*A且A=+則稱是句型相對(duì)于非終結(jié)符A的短語(yǔ)。特別地，如有A則稱是句型相對(duì)于規(guī)則A的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。 （2）求一個(gè)句型的句柄 給定某個(gè)句型，要求出該句型的句柄，比較直觀的方法就是畫出該句型的語(yǔ)法樹。該語(yǔ)法樹的一棵子樹的葉子結(jié)點(diǎn)（從左到右）組成的符

37、號(hào)串便是這個(gè)句型關(guān)于子樹根結(jié)點(diǎn)的一個(gè)短語(yǔ)。,語(yǔ)法樹的一棵簡(jiǎn)單子樹（只有單層子樹）的葉子結(jié)點(diǎn)組成的符號(hào)串是這個(gè)句型關(guān)于簡(jiǎn)單子樹根結(jié)點(diǎn)的一個(gè)直接短語(yǔ)。語(yǔ)法樹的最左的簡(jiǎn)單子樹葉子結(jié)點(diǎn)組成的符號(hào)串就是這個(gè)句型的句柄。,例: 已知文法GS： S(R)|a| RT TS,T|S 求句型=(a,(T),(S,T))的短語(yǔ)，直接短語(yǔ)和句柄？,【解答】觀察該語(yǔ)法樹，共有10個(gè)非葉子結(jié)點(diǎn)，10棵子樹。 因此有短語(yǔ) a T (T) S,T (S,T) (T), (S,T) a, (T), (S,T) (a, (T), (S,T)),2.4.4 文法的存儲(chǔ),一個(gè)文法的語(yǔ)法圖由該文法所有非終結(jié)符的定義圖組成。每個(gè)非終結(jié)

38、符號(hào)的定義圖是一個(gè)結(jié)構(gòu)型數(shù)據(jù)。 寫成高級(jí)語(yǔ)言的結(jié)構(gòu)型數(shù)據(jù)形式，則為： type struc= boxes boxes=record name:array110 of char; def:struc; nextp:struc; 、 rights:struc; end;,,“名字”是用某種內(nèi)部形式表示的終結(jié)符號(hào)或非終結(jié)符號(hào)的名字。 “定義”是一個(gè)指針，對(duì)于非終結(jié)符號(hào)，它指向其第一個(gè)侯選式結(jié)構(gòu)圖的開始位置。對(duì)于終結(jié)符號(hào)，它為0 “下一個(gè)侯選式”是一個(gè)指針，指向相同左部的下一個(gè)侯選式的開始位置。若無侯選式，則它為0； “右部后繼”是一個(gè)指針，指向同一個(gè)右部的下

39、一個(gè)符號(hào)。 另用一個(gè)一維數(shù)組記錄所有的非終結(jié)符號(hào)定義圖的開始地址。 也就是說，這個(gè)數(shù)組的每個(gè)元素都是一個(gè)指針，分別指向相應(yīng)的非終結(jié)符號(hào)的第一個(gè)候選式的定義圖。 例2.35（p31）,例2.35文法 EEAT|T TTMF|F F（E）|i A+| M*|/ 按照上面的存儲(chǔ)結(jié)構(gòu)，畫出文法的存儲(chǔ)結(jié)構(gòu)如圖2-12所示：,小 結(jié),文法是形式語(yǔ)言的一個(gè)十分重要的基本概念。文法可定義為一個(gè)四元組，文法G=（VN，VT，P，S），其中，VN是一個(gè)非終結(jié)符集，VT是一個(gè)終結(jié)符集，P是一個(gè)產(chǎn)生式集，S是文法的開始符號(hào)。 Chomsky 將文法分為0 型，1型，2型和3型文法。程序設(shè)計(jì)語(yǔ)言的詞法規(guī)則屬于3型文法（正規(guī)文法），程序設(shè)計(jì)語(yǔ)言的語(yǔ)法和語(yǔ)義部分一般是采用2型文法來描述。,對(duì)于一個(gè)文法，我們需要研究它的句型，句子和語(yǔ)言。要識(shí)別一個(gè)符號(hào)串是不是一個(gè)文法的句子，需要對(duì)它進(jìn)行語(yǔ)法分析。分析方法有兩類，一類是自上而下分析法，另一類是自下而上的分析方法。 為了進(jìn)行語(yǔ)法分析，需要事先將產(chǎn)生式存儲(chǔ)在計(jì)算機(jī)中?？梢詾槲姆ń⒁粋€(gè)產(chǎn)生式表，把文法的所有的產(chǎn)生式都放在這個(gè)產(chǎn)生式表中。為了在分析過程中能迅速查找到相應(yīng)的產(chǎn)生式，還可以建立一個(gè)目錄表。,作業(yè),P36 3,4,5,6,7,10 ftp://219.222.171.9 user: chenqians 無密碼,