1、2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄短語短語 令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有 則稱 是相對于非終結(jié)符A的, 句型的短語。SA*+且 A 2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄則稱是直接短語。 直接短語直接短語 SA*且 A 令G是一個文法，S是文法的開始符號，假定是文法G的一個句型，如果有 2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄 注意：短語和直接短語的區(qū)別在于第二個條件, 直接短語中的第二個條件表示有文法規(guī)則 A ，因此，每個直接短語都是某規(guī)則右部。 2.4 2.4 短語、直接短語和句柄短語、直接短語和

2、句柄句柄句柄 一個句型的最左直接短語稱為該句型的句柄。句柄特征： (1) 它是直接短語，即某規(guī)則右部。 (2) 它具有最左性。2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄 注意: 短語、直接短語和句柄都是針對某一句型的，都是指句型中的哪些符號串能構(gòu)成短語和直接短語，離開具體的句型來談短語、直接短語和句柄是無意義的。 2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄 例如 設(shè)有文法GS=(S,A,B,a,b,P,S) 其中P為： 求句型 baSb的全部短語、直接短語和句柄。 SABAAa | bBBa | Sb2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄對文法，首

3、先建立該句型的推導(dǎo)過程： 最左推導(dǎo):最右推導(dǎo):SABAAa | bBBa | SbSAB ASbbBSbbaSbSAB baBbaSbbBB 分析 根據(jù)短語定義，可以從句型的推導(dǎo)過程 中找出其全部短語、直接短語和句柄。 句型 baSb2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄句型baSb中的子串Sb，是(相對于非終結(jié)符B)句型baSb的短語，且為直接短語。 SAB bBBbaBbaSb(2) SbaB*B Sb (1) SS*S baSb +句型本身是(相對于非終結(jié)符S)句型baSb的短語。 根據(jù)最左推導(dǎo): S A*+ A 2.4 2.4 短語、直接短語和句柄短語、直接短語和句柄

4、句型baSb中的子串a(chǎn)，是(相對于非終結(jié)符B)句型baSb的短語，且為直接短語、句柄。 句型baSb中的子串ba，是(相對于非終結(jié)符A)句型baSb的短語。 B a(3) SbBSb*根據(jù)最右推導(dǎo):SAB ASb bBSbbaSb(4) SASb*A ba+S A*+ A 2.5 2.5 語法樹與文法的二義性語法樹與文法的二義性 推導(dǎo)和語法樹推導(dǎo)和語法樹 1. 語法樹語法樹 對句型的推導(dǎo)過程給出一種圖形表示, 這種表示稱為語法樹，也稱推導(dǎo)樹。 2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹例如 設(shè)有文法GE:構(gòu)造句型i*i+i的語法樹。首先給出句型的推導(dǎo)過程 (最左推導(dǎo)) ：EE+T | E

5、T | TTT*F | T/F | FF(E) | iEE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹根據(jù)推導(dǎo)過程構(gòu)造句型i*i+i的語法樹如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+T ii*i+Tii*i+FFi*i+ii2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 由例可知，語法樹的構(gòu)造過程是從文法的開始符號出發(fā)，構(gòu)造一個推導(dǎo)的過程。 因為文法的每一個句型 (句子) 都存在一 個推導(dǎo)，所以文法的每個句型(句子) 都存在一棵對應(yīng)的語法樹。EE+T E+F E+i T+i T*F+i T*i

6、+i F*i+i i*i+i2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 對句型i*i+i，還可給出最右推導(dǎo)： EE+TTT*FFiiFi2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 這也就是說，一棵語法樹表示了 一個句型的種種可能的(但未必是所 有的)不同推導(dǎo)過程, 包括最左(最右) 推導(dǎo)。3.5.1 3.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 2. 子樹語法樹的子樹是由某一結(jié)點連同所有分枝組成的部分。EE+TTT*FFiiFi3.5.1 3.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 3. 簡單子樹 語法樹的簡單子樹是指只有單層分枝的子樹。EE+TTT*FFiiFi2.5.1 2.5.1 推導(dǎo)和語

7、法樹推導(dǎo)和語法樹 句型的短語、直接短語和句柄的直觀解釋是： 短語：子樹的末端結(jié)點形成的符號串是 相對于子樹根的短語。 直接短語：簡單子樹的末端結(jié)點形成的 符號串是相對于簡單子樹根的直接短語。 句柄：最左簡單子樹的末端結(jié)點形成的 符號串是句柄。2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹EE+TTT*FFiiFi短語:ni*i+ini*in第一個in第二個in第三個in三個i都是直接短語n第一個i是句柄注意:i+i不是句型的短語句子 i*i+i2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 前例 對文法GS=(S,A,B,a,b,P,S)其中P為： 可用語法樹非常直觀地求出句型baSb的全

8、部短語，直接短語和句柄。SABAAa | bBBa | Sb2.5.1 2.5.1 推導(dǎo)和語法樹推導(dǎo)和語法樹 分析 首先根據(jù)句型baSb的推導(dǎo)過程畫出對 應(yīng)的語法樹如下： Sb 為句型的相對于B的短語、直接短語baSb 為句型的相對于S的短語ba 為句型的相對于A的短語a 句型的相對于B的短語、直接短語和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbB Sba由語法樹可知2.5.2 2.5.2 文法的二義性文法的二義性從前面的討論可以看出，對于文法G中 任一句型的推導(dǎo)序列, 我們總能為它構(gòu)造 一棵語法樹，現(xiàn)在我們提出一個問題： 文法的某個句型是否只對應(yīng)唯一的一棵語法樹呢？也

9、就是，它是否只有唯一的一個最左(最右)推導(dǎo)呢？ 2.5.2 2.5.2 文法的二義性文法的二義性 例如 設(shè)有文法GE： 句子 i*i+i 有兩個不同的最左推導(dǎo)，對應(yīng)兩棵不同的語法樹。E E+E | E*E | (E) | i2.5.2 2.5.2 文法的二義性文法的二義性 最左推導(dǎo)1 EE+EE*E+E i*E+Ei*i+E i*i+i 最左推導(dǎo)2 EE*Ei*E i*E+Ei*i+E i*i+i EE*EE+EiiiEE+EE*Eiii2.5.2 2.5.2 文法的二義性文法的二義性 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則說這個文法是二義性的。 或者說，若一個文法中存在某個句子，它

10、有兩個不同的最左 (最右) 推導(dǎo)，則這個文法是二義性的。 E E+E | E*E | (E) | i2.5.3 2.5.3 文法二義性的消除文法二義性的消除 1. 不改變文法中原有的語法規(guī)則, 僅加進一些非形式的語法規(guī)定。 EE+EE*Eiii2.5.3 2.5.3 文法二義性的消除文法二義性的消除2. 構(gòu)造一個等價的無二義性文法。即 把排除二義性的規(guī)則合并到原有文法中, 改寫原有的文法。例如，對于上例文法GE，將運算符的 優(yōu)先順序和結(jié)合規(guī)則：*優(yōu)先于; 、* 左結(jié)合加到原有文法中, 可構(gòu)造出無二義 性文法如下 ：2.5.3 2.5.3 文法二義性的消除文法二義性的消除則句子i*i+i只有唯一

11、一棵語法樹：EE+T | TTT*F | FF(E) | iEE+TTT*FFiiFi2.5.3 2.5.3 文法二義性的消除文法二義性的消除 例2 定義某程序語言條件語句的文法G為: 試證明該文法是二義性的并消除之。 分析 該文法的句子 if b if b A else A 對應(yīng)下面兩棵不同的語法樹： Sif b S | if b S else S | A (其它語句）2.5.3 2.5.3 文法二義性的消除文法二義性的消除 所以該文法是二義的。 SifbSbSSifAelseASbSSifAelseAifbSSif b S | if b S else S | A句子 if b if b A

12、 else A2.5.3 2.5.3 文法二義性的消除文法二義性的消除 消除文法的二義性可采用下面兩種方法： 1. 不改變已有規(guī)則，僅加進一非形式的語法規(guī)定：else與前面最接近的不帶else的 if 相對。SifbSbSSifAelseA文法G的句子 if b if b A else A只對應(yīng)唯一的一棵語法樹，消除了二義性。2.5.3 2.5.3 文法二義性的消除文法二義性的消除2. 改寫文法G為GS S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 G:Sif b S | if b S else S | A (其它語句）G

13、:2.5.3 2.5.3 文法二義性的消除文法二義性的消除 這是因為通過分析，得知引起二義性的原因是: ifelse 語句的 if 后可以是if型，因此改寫文法時規(guī)定:if else之間只能是ifelse語句或其他語句。2.5.3 2.5.3 文法二義性的消除文法二義性的消除S S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 ifbSbifAelseASS2S1S1S1對改寫后的文法，句子 if b if b A else A 只對應(yīng)唯一的一棵語法樹。通常我們只說文法的二義性, 而不說語言的二義性, 這是因為可能有兩個不同的

14、文法G和G ，而且其中一個是二義性的，另一個是無二義性的, 但卻有L(G)=L(G), 即這兩個文法所產(chǎn)生的語言是相同的。2.5.3 2.5.3 文法二義性的消除文法二義性的消除 應(yīng)該指出的是文法的二義性和語言的二義性是兩個不同的概念。2.5.3 2.5.3 文法二義性的消除文法二義性的消除 將一個語言說成是二義性的，是指對它不存在無二義性的文法，這樣的語言稱為先天二義性的語言。 例如 L= ai bj ck | i=j 或 j=k 且 i, j, k1便是這種語言。2.6 2.6 文法和語言的分類文法和語言的分類 著名的語言學(xué)家喬姆斯基(Chomsky) 將文法和語言分為四大類，即0型、1型

15、、 2型、3型。劃分的依據(jù)是對文法中的規(guī)則施加不同的限制。 2.6 2.6 文法和語言的分類文法和語言的分類 0型文法（無限制文法） 若文法G=(VN,VT, P, S)中的每條規(guī)則 是這樣一種結(jié)構(gòu)： 而且中至少含一個非終結(jié)符, 則稱G 是0型文法。(VNVT)+ , (VNVT)*0型文法描述的語言是0型語言。0型文法沒有加任何限制條件，又稱為 無限制性文法，相應(yīng)的語言稱為無限制 性語言。0型語言由圖靈機識別。2.6 2.6 文法和語言的分類文法和語言的分類 例如，有0型文法G=(VN,VT, P, S) 其中：VN=A,B,S , VT=0,1 其描述的 0 型語言為 L0(GS)= P:

16、 S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0B STOP2.6 2.6 文法和語言的分類文法和語言的分類 1型文法（上下文有關(guān)文法） 1型文法也稱為上下文有關(guān)文法， 相應(yīng) 的語言又稱為上下文有關(guān)語言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： , (VNVT)* ,AVN ,則稱G是1型文法。1型文法描述的語言是1型語言。1型語言由線性界限自動機識別。 (VNVT)+2.6 2.6 文法和語言的分類文法和語言的分類 例如，有1型文法G=(VN,VT, P, S) 其中：VN=S,A,B , VT=a,b,c P: S aSAB | a

17、bB BA BA BA AA AA AB bA bb bB bc cB cc其描述的1型語言為L1(GS)=anbncn | n1 2.6 2.6 文法和語言的分類文法和語言的分類 2型文法（上下文無關(guān)文法） 2型文法又稱上下文無關(guān)文法，其產(chǎn)生的 語言又稱為上下文無關(guān)的語言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： AVN ,(VNVT)*則稱G是2型文法。2型文法描述的語言是2型語言。2型語言由下推自動機識別。例如前面描述算術(shù)表達式的文法GE:EE+E | E*E | (E) | i2.6 2.6 文法和語言的分類文法和語言的分類 其描述的語言為 L2(

18、GS)=x | x a, b+ 且x中a和b的個數(shù)相同 例如，有2型文法G=(VN,VT, P, S) 其中：VN=S, A, B , VT=a, b P= S aB | bA A a | aS | bAA B b | bS | aBB 2.6 2.6 文法和語言的分類文法和語言的分類 2.6 2.6 文法和語言的分類文法和語言的分類 3型文法（正規(guī)文法） 右線性文法和左線性文法都稱為3型文法。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的形式 為A aB 或 A a , 其中： A , BVN, a VT*, 則稱G是右線性文法。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的

19、形式 為A Ba 或 A a , 其中： A , BVN , a VT*, 則稱G是左線性文法。3型文法描述的語言是3型語言。3型語言由有窮自動機識別。 3型文法也稱正規(guī)文法。正規(guī)文法產(chǎn)生的語言 稱為正規(guī)語言。 例如，用左線性正規(guī)文法和右線性正規(guī)文法定義標(biāo)識符 2.6 2.6 文法和語言的分類文法和語言的分類 用I代表標(biāo)識符; l代表任意一個字母; d代表任意一個數(shù)字; 則定義標(biāo)識符的文法為：左線性文法: P: I l | Il | Id右線性文法: P: I l | lT Tl | d | lT| dT 例如，用左線性正規(guī)文法和右線性正規(guī)文法定義無符號整數(shù)2.6 2.6 文法和語言的分類文法

20、和語言的分類 用N代表無符號整數(shù); d代表任意一個數(shù)字；則定義的無符號整數(shù)文法為：左線性文法: P: N Nd | d右線性文法: P: N dN | d2.6 2.6 文法和語言的分類文法和語言的分類 由上述四類文法的定義可知, 從0型文法到3型文法, 是逐漸增加對規(guī)則的限制條件而得到的，因此每一種正規(guī)文法都是上下文無關(guān)的文法，每一種上下文無關(guān)的文法都是上下文有關(guān)的文法，而每一種上下文有關(guān)的文法都是0型文法, 而由它們所定義的語言類是依次縮小的，有 L0 L1 L2 L3 。 2.7 2.7 有關(guān)文法的實用限制和變換有關(guān)文法的實用限制和變換 文法是用來描述程序設(shè)計語言的，在 實際應(yīng)用中需要對

21、文法加一些限制條件。 1. 文法中不能含有形如A A 的規(guī)則。這種規(guī)則我們稱之為有害規(guī)則。對文法的實用限制有以下兩點： 2.7 2.7 有關(guān)文法的實用限制和變換有關(guān)文法的實用限制和變換 2. 文法中不能有多余規(guī)則。所謂多余規(guī)則是指文法中出現(xiàn)以下兩種規(guī)則： (1) 某條規(guī)則 A 的左部符號A不在所屬文法的任何其他規(guī)則右部出現(xiàn)，即在推導(dǎo)文法的所有句子中始終都不可能用到的規(guī)則。 (2) 對文法中的某個非終結(jié)符A，無法從它推出任何終結(jié)符號串來。 2.7 2.7 有關(guān)文法的實用限制和變換有關(guān)文法的實用限制和變換 例如 設(shè)有文法GS: P: S Bd A Ad | dB Cd | AeC Ce D e 刪

22、除多余規(guī)則后的文法變換為: P: S Bd A Ad | dB Ae 2.7 2.7 有關(guān)文法的實用限制和變換有關(guān)文法的實用限制和變換 若程序設(shè)計語言的文法含有多余規(guī)則， 其中必定有錯誤存在，因此檢查文法中是否含有多余規(guī)則對我們來說是很重要的。 作業(yè)P26 2.1 2.2（2） 2.3 L1，L2 ，L3 2.7 2.8 2.9 2.11 2.12 本章重點介紹了語言的語法結(jié)構(gòu)的形式描 述、語法樹以及文法的二義性, 主要內(nèi)容有： 1. 設(shè)計一個文法定義一個已知的語言 (1) 文法是一個四元組 G=(VN,VT, P, S)， 文法四大要素中，關(guān)鍵是一組規(guī)則, 它定義（或描述）了一個語言的結(jié)構(gòu)。

23、 從文法定義可知, 文法對于程序設(shè)計者來 說，文法給出了語言的精確定義和描述。 本章小結(jié)本章小結(jié)本小結(jié)花時45分鐘2004/2/28 (2) 分析已知語言句子的結(jié)構(gòu)特征, 設(shè)計 出相應(yīng)的一組規(guī)則，但不唯一。 (4) 若語言是無窮集合, 設(shè)計該語言的文 法一定是遞歸的。本章小結(jié)本章小結(jié)(3) 設(shè)計的文法必須能定義已知的語言, 不能超出或縮小所定義語言的范圍。 分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計出相 應(yīng)規(guī)則例1. 給出語言 L2=an bm| mn1 的文法P2: SAB L2=ab,abb,abbb, aabb,aabbb,aabbbb, aaabbb, aabbbb，AaAb | ab BbB

24、 |本章小結(jié)本章小結(jié) 分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計出相 應(yīng)規(guī)則 例2. 給出語言 L1=a2n+1|n0 的文法P1: AaB | aP1：AaAa | a 或或L1=a, aaa, aaaaa, aaaaaaa, aaaaaaaaa，Baa | aBa本章小結(jié)本章小結(jié)本章小結(jié)本章小結(jié) 分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計出相應(yīng)規(guī)則 例3. 給出語言L3=anbmck| n,m,k0的文法P3: AaA | bB | cC |P3: AaA | B或或L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc, , ab,abb, ,bc,bcc，CcC |BbB | cC | CcC

25、|BbB | C本章小結(jié)本章小結(jié)L4=0 ,2,4,6,8,10,12,14,16,18,20,22,24,26, 例4. 寫一個 文法,使其語言是正偶數(shù)的集合,每個偶數(shù)不以0開頭。P4: NE | AE N0 | 2 | 4 | 6 | 8 |BN或或分析 不以0開頭的偶數(shù)集合中串的結(jié)構(gòu)特征:AD | AD E0 | 2 | 4 | 6 | 8 D1 | 2 | 3 | | 9 D0 | 1 | 2 | 3 | 9 B1 | 2 | 3 | | 9 |B0P4:本章小結(jié)本章小結(jié)A 0A1 | P : S 1S0 | 0A1 | 例5. 給出語言L=1n0m1m0n | n,m0的 文法。分析

26、 根據(jù)語言句子的結(jié)構(gòu)特征, 設(shè)計 出相應(yīng)規(guī)則 L=,01,0011,10,1100,1010,100110, 110100,11001100本章小結(jié)本章小結(jié)P : S a | 0S0 | 1S1例6. 給出語言L=WaWt | W0|1*,Wt 表示W(wǎng)的逆的文法。分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計 出相應(yīng)規(guī)則 L=a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001, W=,0, 1 ,01, 10, 00, 11, 101, 110, 100, 111, 本章小結(jié)本章小結(jié)2. 已知一個文法，確定該文法所定義的 語

27、言。 (2) 給定一個文法，可根據(jù)語言和推導(dǎo)定 義推導(dǎo)出文法的句子，從而確定出該文法 所定義的語言。 (1) 文法所定義的語言 L(GS)=x|S x且xVT*本章小結(jié)本章小結(jié) 自然語言描述。 例如, L=x|xa,b+且x中a,b個數(shù)相同式子描述。例如 L=a2nbb | n0。正規(guī)式描述。 (3) 語言可用本章小結(jié)本章小結(jié) 例1 文法GA=(A,a,b,AbA | a, A) 所生成的語言是什么？ 分析 AbAbbAbbbAbnAbna L(GA)= bna | n0 本章小結(jié)本章小結(jié)例2 文法GN為:N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

28、| 9(1) GN所生成的語言是什么？ (2) 給出句子0127的最左、最右推導(dǎo)。 本章小結(jié)本章小結(jié)L(GN)= | 0,1,2, 9+= | 為可帶前導(dǎo)0的正整數(shù)= | 為數(shù)字串最左推導(dǎo):NNDN7ND7N27ND27 N127D1270127最右推導(dǎo):NNDNDDNDDDDDDD 0DDD01DD012D0127N ND | DD 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9本章小結(jié)本章小結(jié) 例3. 已知文法GS=( A,B,a,b,c,d, P, S ) , 其中 P 為:分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anb

29、nc2Bd2 anbncm-1Bdm-1anbncmdm L(GS)=anbncmdm | n ,m1 該文法 所生成的語言是什么？ A aAb | ab B cBd | cd S AB本章小結(jié)本章小結(jié)3. 求句型的短語、直接短語和句柄 (1) 短語、直接短語和句柄是對某句 型而言的。 (2) 短語總是句型的某個子串，它對應(yīng) 子樹未端結(jié)點形成的符號串。 (3) 直接短語是某條規(guī)則右部，它對應(yīng) 簡單子樹未端結(jié)點形成的符號串。(4) 最左邊的直接短語是句柄。 本章小結(jié)本章小結(jié)例1 已知文法GE： 證明 E+T*F是它的一個句型,指出這個句型的短語直接短語和句柄。 EE+TE+T*F 短語: E+T*F、T*F E+T*F是它的一個句型。畫出該句型的語法樹:句柄: T*F直接短語: T*FETFT+E*EE+T | E-T | TTT*F | T/F | TT(E) | i2.9相似本章小結(jié)本章小結(jié) 例2 已知文法GS： 試找出符號串(a)和(A(SaA)(b)的短語 直接短語和句柄(如果有的話)。S(AS) | (b)A(SaA) | (a) 符號串(a)不是文法的句型，因