第2章 形式語(yǔ)言基礎(chǔ)

1、第第2章章 形式語(yǔ)言基礎(chǔ)形式語(yǔ)言基礎(chǔ) 計(jì)算機(jī)處理語(yǔ)言，首先應(yīng)考慮語(yǔ)言的形式化、規(guī)范化，使其具有可計(jì)算性和可操作性；這就是形式語(yǔ)言理論研究的問(wèn)題。 形式語(yǔ)言誕生于1956年，由Chomsky創(chuàng)立。通常，語(yǔ)言研究至少涉及三個(gè)方面：語(yǔ)法、語(yǔ)義和語(yǔ)用； 形式語(yǔ)言的基本觀點(diǎn)是 ： 語(yǔ)言是符號(hào)串之集合！ 形式語(yǔ)言理論研究的形式語(yǔ)言理論研究的基本問(wèn)題基本問(wèn)題是：是： 研究符號(hào)串集合的表示方法、結(jié)構(gòu)特性研究符號(hào)串集合的表示方法、結(jié)構(gòu)特性 以及運(yùn)算規(guī)律。以及運(yùn)算規(guī)律。因此：因此：【內(nèi)容提要】 2.1 形式語(yǔ)言是符號(hào)串集合 2.2 形式語(yǔ)言是由文法定義的 2.3 各種語(yǔ)法成分的定義 2.4 兩類特性文法 2.5

2、文法變換方法 2.6 形式語(yǔ)言的分類第第2章章 形式語(yǔ)言基礎(chǔ)形式語(yǔ)言基礎(chǔ) 字母表 - 元素(符號(hào))的非空有限集合； 符號(hào)串 - 符號(hào)的有限序列； 符號(hào)串集合 - 有限個(gè)或者無(wú)限個(gè)符號(hào)串組成的集合； 規(guī) 則 - 以某種形式表達(dá)的在一定范圍內(nèi)共同遵守的章程和制度；這里，指符號(hào)串的組成規(guī)則。2.1 形式語(yǔ)言是符號(hào)串集合形式語(yǔ)言是符號(hào)串集合 【形式語(yǔ)言】是字母表上的符號(hào)按一定的規(guī)則組成的所有符號(hào)串集合；其中的每個(gè)符號(hào)串稱為一個(gè)句子?！久~解釋】：【名詞解釋】：三要素！三要素！【例【例2.1】 L1= 00,01,10,11 ; 字母表字母表1= 0,1, 句子有：句子有：00,01,10,11【注【注

3、】 (1) b0= （空符號(hào)串）（空符號(hào)串）,b1=b,b2=bb,b3=bbb, (2) L1 為有限語(yǔ)言為有限語(yǔ)言; L2 為無(wú)限語(yǔ)言。為無(wú)限語(yǔ)言。 形式語(yǔ)言概念示例：形式語(yǔ)言概念示例：【例【例2.2】 L2= abmc,bn | m0,n0 字母表字母表2= a,b,c,句型句型1: abmc 有句子：有句子：abc, abbc, abbbc, 句型句型2: bn 有句子：有句子： , b, bb, bbb, 兩個(gè)語(yǔ)言兩個(gè)語(yǔ)言!1.1.連接連接：. = 如：a.b=ab符號(hào)串符號(hào)串(集合集合)的運(yùn)算的運(yùn)算3.3.方冪方冪： n n = = = = n-1n-1 = = n-1n-1 4.

4、4.閉包：閉包：n n個(gè)個(gè).符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算 設(shè)設(shè) , , 為兩個(gè)符號(hào)串，則為兩個(gè)符號(hào)串，則： 的正閉包：的正閉包： + + = = 1 1| | 2 2| | | n n| | 的星閉包：的星閉包： * * = = 0 0| | 1 1| | 2 2| | | n n| | 0 0 = = ( (空符號(hào)串空符號(hào)串) ) 什么符號(hào)也沒(méi)有的符號(hào)串什么符號(hào)也沒(méi)有的符號(hào)串 ！ 1 1= = ； 2 2 = = ；2.2. 或或： | | = = 或者或者 這是一種這是一種泛指泛指！5.5.固有頭，固有尾固有頭，固有尾 對(duì)于每個(gè)符號(hào)串對(duì)于每個(gè)符號(hào)串s s， s s和和兩者兩者都都是符號(hào)串是符號(hào)

5、串s s的前綴，的前綴，后綴和子串。后綴和子串。 符號(hào)串符號(hào)串s s的固有頭，固有尾：的固有頭，固有尾： z=xy,xz=xy,x是是z z的頭，的頭，y y是是z z的尾，如果的尾，如果x x非空則非空則y y是固是固有尾，如果有尾，如果y y非空則非空則x x是固有頭。是固有頭。例：在例：在Z=abcZ=abc Z Z的頭的頭:,a,ab,abc:,a,ab,abc；其中固有頭：；其中固有頭：,a,ab,a,ab Z Z的尾的尾:,c,bc,abc:,c,bc,abc；其中固有尾：；其中固有尾：,c,bc,c,bc【例【例2.3】：】：(2) abc. = . abc=abc(1) abc

6、.de= abcde(4) (a|b)1 =(a|b)= a|b (a|b)* =(a|b)0 |(a|b)1 |(a|b)2 |(a|b)2 =(a|b)(a|b)=aa|ab|ba|bb 即：即：(a|b)* = (a|b)n , n0同理：同理：(a|b)+ = (a|b)n , n0 符號(hào)串運(yùn)算示例符號(hào)串運(yùn)算示例泛指：泛指：由由a，b組成的組成的任意符號(hào)串！任意符號(hào)串?。ò沾ò沾?3) ab|cd = ab或者或者cd1. 乘積乘積： AB = xy | x A 且且 y B4.閉包閉包：A的正閉包的正閉包：A+ = A1A2AnA的星閉包的星閉包：A* = A0A1A2

7、An 設(shè)設(shè) A 和和 B 為兩個(gè)符號(hào)串集合，則：為兩個(gè)符號(hào)串集合，則：2. 和和： AB = A+B = x | x A 或或 x B 3.方冪方冪： An = AAA = AAn-1 = An-1An個(gè)個(gè) A0 = ; A1 =A ; A2 =AA ; A3 =AAA ; .符號(hào)串集合的運(yùn)算符號(hào)串集合的運(yùn)算 符號(hào)串符號(hào)串(集合集合)的運(yùn)算的運(yùn)算 符號(hào)串集合運(yùn)算示例符號(hào)串集合運(yùn)算示例【例【例2.4】 設(shè)設(shè) A=a,b,B=c,d 則則 A+B=a,b,c,d 則則 AB=xy|x A,y B=ac,ad,bc,bd【例【例2.5】 設(shè)設(shè) A=a 則則 A* = A0A1A2An = +a+aa

8、+aaa+ = ,a,aa,aaa, =an|n0 【例【例2.6】 設(shè)設(shè) A=a, b， A* = ? A* = A0A1A2An A0 = ; A1 = A =a, b; A2 = AA=a, ba, b=aa,ab,ba,bb; A3 = AA2=a, baa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbb; A* = x | x=(a|b)n , n0 符號(hào)串集合運(yùn)算示例符號(hào)串集合運(yùn)算示例( (續(xù)續(xù)) )： 推論推論：若：若 A 為任一字母表，則為任一字母表，則 A* 就是該字母就是該字母表表 上上的所有符號(hào)串的所有符號(hào)串(包括空串包括空串)的集合。

9、的集合。2.2 形式語(yǔ)言是由文法定義的形式語(yǔ)言是由文法定義的 形式語(yǔ)言是符號(hào)串的集合，對(duì)形式語(yǔ)言的描述形式語(yǔ)言是符號(hào)串的集合，對(duì)形式語(yǔ)言的描述有兩種方式：有兩種方式：(1) 枚舉方式枚舉方式：語(yǔ)言為有窮集合時(shí)：語(yǔ)言為有窮集合時(shí) 設(shè)有字母表設(shè)有字母表A=a,b,c, 有有 L1=a,aa,ab,ac, L2=c,cc(2) 使用文法使用文法：語(yǔ)言為無(wú)窮集合時(shí)，無(wú)法枚舉：語(yǔ)言為無(wú)窮集合時(shí)，無(wú)法枚舉 設(shè)有字母表設(shè)有字母表B=0,1, B+=0,1,00,10,11,01,000, 用用 A 表示表示B+，可以表示為，可以表示為A-0 A-1 A-A0 A-A1文法：用有窮的集合刻畫無(wú)窮的集合的工具。

10、文法：用有窮的集合刻畫無(wú)窮的集合的工具。 【定義】【定義】 文法文法(grammar)是是規(guī)則規(guī)則的有限集，通?？傻挠邢藜ǔ？梢员硎緸樗脑M：以表示為四元組： G(Z)=(VN, VT, Z, P) VN : 非終結(jié)符集非終結(jié)符集 ( 定義的對(duì)象集，如：語(yǔ)法成分等定義的對(duì)象集，如：語(yǔ)法成分等 ) ； VT : 終結(jié)符集終結(jié)符集 ( 字母表字母表 ) ； Z : 開始符號(hào)開始符號(hào) ( 研究范疇中最大的定義對(duì)象研究范疇中最大的定義對(duì)象 ) ； P : 規(guī)則集規(guī)則集 ( 又稱產(chǎn)生式集又稱產(chǎn)生式集 ) ；2.2 形式語(yǔ)言是由文法定義的形式語(yǔ)言是由文法定義的每個(gè)元素每個(gè)元素2.2.1 什么是文法什么

11、是文法 ？ Z - 或者或者 A - | 注：此文法實(shí)際稱為上下文無(wú)關(guān)文法注：此文法實(shí)際稱為上下文無(wú)關(guān)文法 描述符號(hào)描述符號(hào) ： -(定義為定義為/生成生成)，|(或者是或者是) 文法符號(hào)文法符號(hào) ： Z , AVN， , (VN+VT)* 每個(gè)規(guī)則每個(gè)規(guī)則 【注意】提供了規(guī)則集，就相當(dāng)給出了一個(gè)文法： S - aAc A - bA | G(S):VT= a,b,c ; Z = S ; P :VN= S,A ;G(Z)=(VN, VT, Z, P)2.2.1 什么是文法什么是文法 ？【例【例2.7】 L = abnc | n0 ，字母表：，字母表：= a,b,c； 展開：展開：L =ac,ab

12、c,abbc,abbbc, 可以用右圖給出的可以用右圖給出的 S - aAc A - bA | 文法規(guī)則文法規(guī)則來(lái)表示來(lái)表示：2.2.2 文法是怎樣定義語(yǔ)言的？文法是怎樣定義語(yǔ)言的？ 則則 L(G) = x | Z x, x VT* 即：一個(gè)文法所定義的即：一個(gè)文法所定義的語(yǔ)言語(yǔ)言，就是由該文法，就是由該文法開始開始設(shè)有文法設(shè)有文法G(Z)，L(G)為為G所定義的語(yǔ)言；所定義的語(yǔ)言；利用利用推導(dǎo)算符推導(dǎo)算符 = 進(jìn)行連續(xù)推導(dǎo)進(jìn)行連續(xù)推導(dǎo)符號(hào)推導(dǎo)出符號(hào)推導(dǎo)出的所有的所有僅含終結(jié)符僅含終結(jié)符的所有的所有符號(hào)串符號(hào)串之之集合集合。其中的每個(gè)符號(hào)串皆稱為其中的每個(gè)符號(hào)串皆稱為句子句子。 = + +2.

13、1使用文法的使用文法的規(guī)則進(jìn)行規(guī)則進(jìn)行 形式語(yǔ)言是字母表上的符號(hào)按一定的形式語(yǔ)言是字母表上的符號(hào)按一定的規(guī)則規(guī)則組成的組成的 所有符號(hào)串集合。所有符號(hào)串集合。 從從開始符號(hào)出發(fā)，對(duì)符號(hào)串中的出發(fā)，對(duì)符號(hào)串中的定義對(duì)象定義對(duì)象，采，采用用推導(dǎo)的方法（的方法（用其規(guī)則右部替換左部用其規(guī)則右部替換左部）產(chǎn)生新的）產(chǎn)生新的符號(hào)串，如此進(jìn)行，直到新符號(hào)串中不再出現(xiàn)定義符號(hào)串，如此進(jìn)行，直到新符號(hào)串中不再出現(xiàn)定義的對(duì)象為止，則最終的符號(hào)串就是一個(gè)的對(duì)象為止，則最終的符號(hào)串就是一個(gè)句子。 S - aAc A - bA | 利用利用文法規(guī)則文法規(guī)則表示語(yǔ)言表示語(yǔ)言 【句子產(chǎn)生過(guò)程】( (= 推導(dǎo)算符) S S

14、= = aAcaAc = ac= ac = ac= ac S S= aAc= aAc = abAc= abAc = abc= abc = abc= abc S S= aAc= aAc = abAc= abAc= abbAc= abbAc = abbc= abbc 一個(gè)句子一個(gè)句子! !又一個(gè)句子又一個(gè)句子! ! S abS abn nc c ,n0 ,n0 = + +再一個(gè)句子再一個(gè)句子! !非終結(jié)符號(hào)非終結(jié)符號(hào)練習(xí)練習(xí)1.=a,b上的字符串集上的字符串集A=abna|n=1則該集合的文法是：則該集合的文法是：(1) A-aBa B-b|Bb|bB(2) Z-ABC A-a C-a B-bB|

15、Bb|b(3) A-aB B-ba|bB練習(xí)練習(xí)2. =a,b,c上的字符串集上的字符串集A=ancbn|n=0 該集合的文法是：該集合的文法是：A-aAb|c【例【例2.8】標(biāo)識(shí)符標(biāo)識(shí)符的文法的文法 【標(biāo)識(shí)符標(biāo)識(shí)符】指字母開頭的字母、數(shù)字序列?！恐缸帜搁_頭的字母、數(shù)字序列。令令G(Z)=(VN, VT, Z, P)則則 VN = I(標(biāo)識(shí)符標(biāo)識(shí)符) , A(標(biāo)識(shí)符尾標(biāo)識(shí)符尾) ； VT = (字母字母) , d(數(shù)字?jǐn)?shù)字) ； Z = I ; P : I - A | A - A | d A | 同理，同理，【無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)】文法可寫成：】文法可寫成：G(N): N - d N | d其

16、其四元組四元組也可寫成：也可寫成：G(N)=( N, d, N, P ) 得：得： I = (|d)n , n0 令：令： I = A | A = A | d A | 求解求解文法文法所定義的語(yǔ)言所定義的語(yǔ)言(1)上面構(gòu)造的標(biāo)識(shí)符文法 屬于正規(guī)文法I - A | A - A | d A | 先求解先求解 A: A=(|d) A , A=(|d)2 A , , A=(|d)n A 代入代入 A= 得：得： A= (|d)n , n0 I= A | 代入代入 A= (|d)n , n0正規(guī)方程式正規(guī)方程式標(biāo)識(shí)符：字母開頭的字母、數(shù)字序列標(biāo)識(shí)符：字母開頭的字母、數(shù)字序列 求解求解文法文法所定義的語(yǔ)言

17、所定義的語(yǔ)言(2)則則 L(G)的求解過(guò)程的求解過(guò)程 代入法代入法 ： Z - aAc A - bA | 【例【例2.9】 G(Z):所以所以： L(G)= abnc | n0 A = bA = bbA = = bn ,n0 Z = a A c a bn c , n0 = + +A b bn n = + + 即：即： A bn = + +，n0即：即： Z abnc ，n0 = + +則則 VN = E(算術(shù)表達(dá)式算術(shù)表達(dá)式),T(項(xiàng)項(xiàng)),F(因式因式)； VT = i(變量或常數(shù)變量或常數(shù)), + , - , * , / , ( , ) ； Z = E ; P : 【例【例2.10】簡(jiǎn)單算術(shù)

18、表達(dá)式文法】簡(jiǎn)單算術(shù)表達(dá)式文法【注】此文法定義了算術(shù)表達(dá)式的層次嵌套結(jié)構(gòu)【注】此文法定義了算術(shù)表達(dá)式的層次嵌套結(jié)構(gòu): : E - T | E + T | E - T T - F | T * F | T / F F - i | ( E )令令 G(Z)= (VN, VT, Z, P) ( ( 表達(dá)式表達(dá)式 ) )表達(dá)式表達(dá)式項(xiàng)項(xiàng)因式因式文法文法E - E + E | E E | E * E | E / E | i | (E) ? 算術(shù)表達(dá)式文法應(yīng)用示例：算術(shù)表達(dá)式文法應(yīng)用示例： 根據(jù)根據(jù) 語(yǔ)言定義式語(yǔ)言定義式2.1， G(E): E-T |E+T |E-T T-F |T* F |T/F F-i

19、|(E)證明證明 i*(i+i-i)是文法是文法G(E)的一個(gè)的一個(gè)句子句子(即合法的即合法的算術(shù)表達(dá)式算術(shù)表達(dá)式): = + +E i*(i+i-i) 成立嗎？成立嗎？ E = + +E i*(i+i-i) =T =T*F =T*(E) =T*(E-T)=T*(E+T-T) =F*(E+T-T)=i*(E+T-T)= 觀察推導(dǎo)過(guò)程，可以看觀察推導(dǎo)過(guò)程，可以看到：一旦產(chǎn)生式選擇錯(cuò)到：一旦產(chǎn)生式選擇錯(cuò)了，會(huì)導(dǎo)致失敗！了，會(huì)導(dǎo)致失?。?i*(i+i-i)L(G) = x | Z x , x VT* = + +合法的算術(shù)表達(dá)式是指：合法的算術(shù)表達(dá)式是指： 文法有兩種基本運(yùn)算：文法有兩種基本運(yùn)算：推導(dǎo)

20、推導(dǎo)和和歸約歸約v星推導(dǎo)星推導(dǎo)( ): 2.3 各種語(yǔ)法成分的定義各種語(yǔ)法成分的定義1. 直接推導(dǎo)直接推導(dǎo)( = ) : xAy = x y即：指用產(chǎn)生式的右部符號(hào)串即：指用產(chǎn)生式的右部符號(hào)串替換替換左部非終結(jié)符。左部非終結(jié)符。 加推導(dǎo)加推導(dǎo)算符算符v 加推導(dǎo)( ): 設(shè)設(shè) x, y(VN+VT)*，A - P = * = *（當(dāng)且僅當(dāng)（當(dāng)且僅當(dāng) = 1 = 2 = = ） 即：指一步或一步以上的直接推導(dǎo)運(yùn)算。即：指一步或一步以上的直接推導(dǎo)運(yùn)算。 （當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) =或或 = 1= 2=) 即：指零步或零步以上的直接推導(dǎo)運(yùn)算。即：指零步或零步以上的直接推導(dǎo)運(yùn)算。直接推導(dǎo)直接推導(dǎo)算符算符星推導(dǎo)

21、星推導(dǎo)算符算符 = + + = + +2.3.1 文法的運(yùn)算文法的運(yùn)算 =. .+ + =. .+ +2. 直接歸約直接歸約( ) : x y xAy =. . =. .（當(dāng)且僅當(dāng)（當(dāng)且僅當(dāng) 1 1 2 2 ） =. . =. . =. . =. .v 星歸約星歸約( ): =. .* =. .* （當(dāng)且僅當(dāng)（當(dāng)且僅當(dāng) =或或 1 1 2 2 ) ) =. . =. . = . . =. .即：直接歸約是直接推導(dǎo)的即：直接歸約是直接推導(dǎo)的逆運(yùn)算逆運(yùn)算，用產(chǎn)生式的左，用產(chǎn)生式的左 部非終結(jié)符替換右部符號(hào)串。部非終結(jié)符替換右部符號(hào)串。即：指零步或零步以上的直接歸約運(yùn)算。即：指零步或零步以上的直接歸

22、約運(yùn)算。即：指一步或一步以上的直接歸約運(yùn)算。即：指一步或一步以上的直接歸約運(yùn)算。直接歸約直接歸約算符算符加歸約加歸約算符算符星歸約星歸約算符算符v 加歸約加歸約( ): 2.3.1 文法的運(yùn)算文法的運(yùn)算 規(guī)范推導(dǎo)和規(guī)范歸約規(guī)范推導(dǎo)和規(guī)范歸約 實(shí)用中最常見的兩種運(yùn)算：l 最左推導(dǎo)( )每次推導(dǎo)皆最左非終結(jié)符優(yōu)先；l 最左歸約( )每次歸約皆最左可歸約串優(yōu)先。 =+ + =. .+ +l 最右推導(dǎo)也稱為規(guī)范推導(dǎo)l 最左歸約也稱為規(guī)范歸約同一個(gè)句子可以通過(guò)不同的推導(dǎo)序列推導(dǎo)出來(lái)同一個(gè)句子可以通過(guò)不同的推導(dǎo)序列推導(dǎo)出來(lái)通常只考慮兩種特殊推導(dǎo)，即通常只考慮兩種特殊推導(dǎo)，即最左推導(dǎo)和最右推導(dǎo)最左推導(dǎo)和最右

23、推導(dǎo)N1=N=ND=N2=D2=1212 D2 N2 ND N N1N1 - N N - ND|D D - 0|1|2 =. =. =. =. =.最左歸約是最右推導(dǎo)的逆過(guò)程！最左歸約是最右推導(dǎo)的逆過(guò)程！i + i*il 給定一個(gè)符號(hào)串給定一個(gè)符號(hào)串 i+i*i ： T-F|T*F|T/F F-i |( E )G(E): E-T|E+T|E-T文法運(yùn)算示例：文法運(yùn)算示例： 【例【例 2.11】 算術(shù)表達(dá)式文法：算術(shù)表達(dá)式文法： =. =. =. =. =. =. =. =.2. 最左歸約最左歸約(從從符號(hào)串出發(fā)符號(hào)串出發(fā))過(guò)程：過(guò)程：E = E +T= T +T= F+T= i+ T = i+

24、T*F= i+ F *F = i+i*F = i+i*i E =+ +i + i * iF+i*iT+i*iE+ i *iE+F*iE+T*iE+T*FE+TE i + i * i =. .+ +E1. 最左推導(dǎo)最左推導(dǎo)(從從開始符號(hào)出發(fā)開始符號(hào)出發(fā))過(guò)程：過(guò)程：最左非終結(jié)符最左非終結(jié)符最左可歸約串最左可歸約串練習(xí)：練習(xí)：G=(S,A,a,b,P,S)S-aAS A-SbA A-SS S-a A-ba請(qǐng)寫出句子請(qǐng)寫出句子aabbaa的最右推導(dǎo)和最左推導(dǎo)。的最右推導(dǎo)和最左推導(dǎo)。最右推導(dǎo)最右推導(dǎo):S=aAS=aAa=aSbAa=aSbbaa=aabbaa最左推導(dǎo)：最左推導(dǎo)：S=aAS=aSbAS=

25、aabAS=aabbaS=aabbaa1,4,2,5,41,2,4,5,4即：句型是由文法開始符號(hào)加推導(dǎo)出的任一符號(hào)串。即：句型是由文法開始符號(hào)加推導(dǎo)出的任一符號(hào)串。 2.3.2 句句型、句子和語(yǔ)法樹型、句子和語(yǔ)法樹若有若有 且且 VT*，則，則 是句子是句子； Z =+若有若有 , 則則 是句型；是句型； Z =+2. 句子句子即：句子是由開始符號(hào)加推導(dǎo)出的任一即：句子是由開始符號(hào)加推導(dǎo)出的任一終結(jié)終結(jié)符號(hào)串。符號(hào)串。 1. 句型句型設(shè)有文法設(shè)有文法 G(Z)=(VN, VT, Z, P)，則：，則：3.語(yǔ)法樹語(yǔ)法樹 句型句型(句子句子)產(chǎn)生過(guò)程的一種樹結(jié)構(gòu)表示；產(chǎn)生過(guò)程的一種樹結(jié)構(gòu)表示；樹

26、根樹根開始符號(hào)開始符號(hào)；樹葉樹葉給定的給定的句型句型(句子句子)。 A x1 x2 xn 重復(fù)步驟重復(fù)步驟，直到推導(dǎo)過(guò)程結(jié)束為止。，直到推導(dǎo)過(guò)程結(jié)束為止。 置樹根為開始符號(hào)；置樹根為開始符號(hào)； 【語(yǔ)法樹的構(gòu)造算法【語(yǔ)法樹的構(gòu)造算法】 若若推導(dǎo)推導(dǎo)采用了采用了產(chǎn)生式產(chǎn)生式：A - x1x2xn，則有，則有子樹：子樹： 如此構(gòu)造的語(yǔ)法樹，其如此構(gòu)造的語(yǔ)法樹，其全體樹葉全體樹葉( (自左至右自左至右) ) 恰好是給定的句型恰好是給定的句型( (句子句子) )。 E = T = T*F =F*F =(E)*F =(E+T)*F=(T+T)*F =(T/F+T)*F =(T/F+F)*F =(T/F+F

27、)*i 句型、句子和語(yǔ)法樹示例句型、句子和語(yǔ)法樹示例【例2.12】算術(shù)表達(dá)式文法：(1) 證明證明 (T/F+F)*i 是一個(gè)句型是一個(gè)句型(表達(dá)式型表達(dá)式型)；(2) 畫出該句型的語(yǔ)法樹。畫出該句型的語(yǔ)法樹。 E - T | E + T | E - T T - F | T * F | T / F F - i | ( E )【證【證】即：即：E (T/F+F)*i = + + 句型句型(T/F+F)*i的語(yǔ)法樹構(gòu)造：的語(yǔ)法樹構(gòu)造：ETT * FF ( E )E + TT T / FFiE - T | E+T | E-T T - F | T*F | T/F F - i | ( E )【注】關(guān)于語(yǔ)

28、法樹：【注】關(guān)于語(yǔ)法樹： 子樹：由某一結(jié)點(diǎn)子樹：由某一結(jié)點(diǎn)連同連同所有分支所有分支組成組成的部分。的部分。 簡(jiǎn)單子樹簡(jiǎn)單子樹 ：僅具有：僅具有單層分支單層分支的子樹。的子樹。 3. 句柄句柄 - - 一個(gè)句型的一個(gè)句型的最左簡(jiǎn)單短語(yǔ)最左簡(jiǎn)單短語(yǔ)稱為該句型的稱為該句型的句柄句柄。2.3.3 短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄 設(shè)文法設(shè)文法G(Z),x y是一個(gè)句型，則是一個(gè)句型，則: 則則 是句型是句型 x y 關(guān)于關(guān)于A的短語(yǔ)的短語(yǔ)(A是是 的名字的名字)； = + + = + +1.1.短語(yǔ)短語(yǔ) 若若 Z xAy xZ xAy x y y Z x A y 任一任一子樹子樹的的樹葉全體樹葉全體( (具有共同

29、具有共同祖先祖先的葉節(jié)點(diǎn)符號(hào)串的葉節(jié)點(diǎn)符號(hào)串) )皆為皆為短語(yǔ)短語(yǔ)； = + +2. 簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ) 若若 Z xAyZ xAy = x x y y 則則 是句型是句型 x y 關(guān)于關(guān)于A的簡(jiǎn)單短語(yǔ)的簡(jiǎn)單短語(yǔ)(A是是 的名字的名字) ； 任一任一簡(jiǎn)單子樹簡(jiǎn)單子樹的的樹葉全體樹葉全體( (具有共同具有共同父親父親的葉節(jié)點(diǎn)符的葉節(jié)點(diǎn)符號(hào)串號(hào)串) )皆為皆為簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ)； (他他) (哥哥哥哥)(喜歡喜歡) (看看) 圖圖2.2 他哥哥喜歡看書他哥哥喜歡看書的的語(yǔ)法樹語(yǔ)法樹(書書) 2.3.3 短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄 【例2.13】圖2.2為一個(gè)中文句型的語(yǔ)法樹： 短 語(yǔ) - 他哥哥,喜歡看,書

30、， 喜歡看書，他哥哥喜歡看書 簡(jiǎn)單短語(yǔ) - 他哥哥，喜歡看，書 句 柄 - 他哥哥（最左邊的簡(jiǎn)單短語(yǔ)!）【例2.14】圖2.3為一個(gè)算術(shù)表達(dá)式(型)的語(yǔ)法樹： 句型： E+F-T/F*i 短語(yǔ): E+F-T/F*i，E+F，F(xiàn)，T/F*i，T/F，i 簡(jiǎn)單短語(yǔ): F，T/F，i 句柄: F E E - T E + T T * F F T / F i 圖圖2.3 E+F-T/F*i 的語(yǔ)法樹的語(yǔ)法樹 2.3.3 短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄 一類典型的綜合例題：一類典型的綜合例題：【例【例2.15】G(S): S-aAcBe ; A-Ab|b ; B-d 給定符號(hào)串給定符號(hào)串 ：aAbcde 證明證明

31、= aAbcde 是一個(gè)句型；是一個(gè)句型； 畫出句型畫出句型 的語(yǔ)法樹；的語(yǔ)法樹； 指出指出 中的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。中的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。【題解【題解】 S=aAcBe=aAbcBe= aAbcde 語(yǔ)法樹如右圖：語(yǔ)法樹如右圖： 短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄: : S S a A c B e a A c B e A b d A b d 短語(yǔ)短語(yǔ): aAbcde ,Ab , d 簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ): Ab , d 句柄：句柄：Ab練習(xí)：練習(xí)：G=(E,T,F,+,*,i,(,),P,E)P為為E-T|E+T , T-F|T*F , F-(E)|i句型句型(T+i)*i+F的語(yǔ)法

32、樹的語(yǔ)法樹EET+TFT*FFi(E)+ETTFi短語(yǔ)短語(yǔ): (T+i)*i+F T+i (T+i) (T+i)*i i F T i簡(jiǎn)單短語(yǔ)簡(jiǎn)單短語(yǔ): i，F(xiàn)，T，i句柄：句柄：TG2(S): S - b S | a - 直接右遞歸直接右遞歸文法。文法。2.4 兩種特性文法兩種特性文法 2.4.1 遞歸文法 設(shè)有文法：設(shè)有文法：G(Z)=(VN,VT,Z,P)【定義】【定義】 設(shè)設(shè) AVN，x, y(VN+VT)*，則，則; 若若 A xAy，稱文法具有，稱文法具有遞歸性遞歸性; = + +特別地特別地： 若若 A - A ，稱文法具有，稱文法具有直接左遞歸性直接左遞歸性； A - A ，稱文

33、法具有，稱文法具有直接右遞歸性直接右遞歸性。 遞歸文法是定義無(wú)限語(yǔ)言的工具遞歸文法是定義無(wú)限語(yǔ)言的工具 遞歸文法定義的語(yǔ)言有無(wú)限個(gè)句子遞歸文法定義的語(yǔ)言有無(wú)限個(gè)句子如：如：G1(S): S - S b | a - 直接左遞歸直接左遞歸文法；文法； 遞歸文法示例遞歸文法示例【例【例2.16】G(Z)： Z - aAbB | cZ A - bBc | B - BbAc |a Z - cZ 直接右遞歸性直接右遞歸性； B - BbAc 直接左遞歸性直接左遞歸性； A =bBc = bBbAcc 即即 A A 具有遞歸性具有遞歸性 ( 且且 又稱為又稱為A具有自嵌套性具有自嵌套性) 可以統(tǒng)稱文法可以統(tǒng)

34、稱文法G(Z)具有遞歸性。具有遞歸性。 = + +2.4.2 二義性文法【定義】【定義】 若文法中存在這樣的句型，它具有若文法中存在這樣的句型，它具有兩棵兩棵不同的語(yǔ)法樹不同的語(yǔ)法樹，則稱該文法是，則稱該文法是二義性二義性文法。文法?！纠纠?.17】 算術(shù)表達(dá)式的另一種文法：算術(shù)表達(dá)式的另一種文法： 句型句型 i+i*i 有兩棵不有兩棵不 同的語(yǔ)法樹同的語(yǔ)法樹(右圖右圖)： G(E) 是二義性文法。是二義性文法。G(E)：E - E+E | E*E | (E) | i ;i (變量或常數(shù)變量或常數(shù)) E E E E E + E E E + E E * * E E i E i E * * E

35、E + E i E E + E i i i i i i i i i 二義性文法會(huì)引起歧義，二義性文法會(huì)引起歧義，應(yīng)盡量避免之！應(yīng)盡量避免之！文法二義性的消除文法二義性的消除【方法【方法1 1】不改變文法的原有規(guī)則】不改變文法的原有規(guī)則, ,加進(jìn)一些非形加進(jìn)一些非形 式的規(guī)定。式的規(guī)定?！痉椒ā痉椒? 2】構(gòu)造一個(gè)】構(gòu)造一個(gè)等價(jià)的無(wú)二義性文法等價(jià)的無(wú)二義性文法，將排除，將排除 二義性的規(guī)則合并到文法中二義性的規(guī)則合并到文法中 加進(jìn)運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則加進(jìn)運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則 對(duì)對(duì)G(E)，規(guī)定，規(guī)定*優(yōu)于優(yōu)于+，*和和+服從左結(jié)合服從左結(jié)合G(E) - G (E) : E - E+T

36、 | T T - T*F | F F - (E) | i ;練習(xí)：判斷下面的文法是否具有二義性？練習(xí)：判斷下面的文法是否具有二義性？S-aB|bAB-bS|aBB|bA-aS|bAA|aaabbab最左推導(dǎo)最左推導(dǎo)S=aB=aaBB=aabB=aabbS=aabbaB=aabbabS=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab所以該文法有二義性！所以該文法有二義性！2.5.1 文法的等價(jià)性 2.5 文法的等價(jià)變換文法的等價(jià)變換即：即：文法的等價(jià)性是指它們所定義的語(yǔ)言是一樣的。文法的等價(jià)性是指它們所定義的語(yǔ)言是一樣的。【定義【定義】 設(shè)設(shè)G1、G2是兩個(gè)文法，若是兩個(gè)文

37、法，若L(G1)=L(G2)， 則稱則稱G1與與G2等價(jià)，記作等價(jià)，記作G1G2?！纠纠?.18】 G1：S - aS|a G2：S - Sa|a L(G1)=a, aa, aaa, =an | n1 L(G2)=a, aa, aaa, =an | n1 L(G1)=L(G2) 即即 G1G2 【結(jié)論【結(jié)論】一個(gè)語(yǔ)言，其描述文法并不唯一。一個(gè)語(yǔ)言，其描述文法并不唯一。練習(xí)：下面兩個(gè)文法是否等價(jià)？練習(xí)：下面兩個(gè)文法是否等價(jià)？G1: S-0S1 , S-01G2: A-0R , A-01 , R-A1 L1=0n1n|n=1;L2=0n1n|n=1;所以等價(jià)！所以等價(jià)！2.5.2 文法變換方法文

38、法變換方法 在實(shí)際工作中，人們總是希望定義一種語(yǔ)言的文法盡可能地簡(jiǎn)單。 另外，某些常用的語(yǔ)法分析技術(shù)也會(huì)對(duì)文法提出一定的要求或限制。 因此，有時(shí)需要對(duì)文法進(jìn)行必要的改寫。改寫后的文法要與原文法等價(jià)通常稱為文法變換。 這里重點(diǎn)介紹三類變換： BNF（巴科斯范式）表示法：（巴科斯范式）表示法： 刪除刪除產(chǎn)生式；產(chǎn)生式； 必選項(xiàng)法；必選項(xiàng)法； 可選項(xiàng)法；可選項(xiàng)法； 重復(fù)可選項(xiàng)法。重復(fù)可選項(xiàng)法。 刪除無(wú)用的產(chǎn)生式（文法的化簡(jiǎn)）；刪除無(wú)用的產(chǎn)生式（文法的化簡(jiǎn)）； 文法的化簡(jiǎn)是指消除如下文法的化簡(jiǎn)是指消除如下無(wú)用產(chǎn)生式無(wú)用產(chǎn)生式： 1. A-A 形式的產(chǎn)生式形式的產(chǎn)生式(自定己自定己)； 2. 不能從其推

39、導(dǎo)出終結(jié)符號(hào)串的產(chǎn)生式不能從其推導(dǎo)出終結(jié)符號(hào)串的產(chǎn)生式(不終結(jié)不終結(jié))； 3. 在推導(dǎo)中永不使用的產(chǎn)生式在推導(dǎo)中永不使用的產(chǎn)生式(不可用不可用)。 文法的化簡(jiǎn)文法的化簡(jiǎn) 刪除刪除不終結(jié)不終結(jié)產(chǎn)生式算法：產(chǎn)生式算法：(1) 構(gòu)造構(gòu)造能能推導(dǎo)出終結(jié)符號(hào)串的非終結(jié)符集推導(dǎo)出終結(jié)符號(hào)串的非終結(jié)符集VVT: 若有若有 A- 且且 VT* ;則令則令 AVVT ； 若有若有 B- 且且 (VT+ VVT)* ;則令則令 BVVT ; 重復(fù)步驟重復(fù)步驟，直到，直到VVT不再擴(kuò)大為止。不再擴(kuò)大為止。(2) 刪除不在刪除不在VVT中的所有非終結(jié)符中的所有非終結(jié)符( (連同其產(chǎn)生式連同其產(chǎn)生式) )。例題：例題：

40、對(duì)文法化簡(jiǎn)：對(duì)文法化簡(jiǎn)：S-Bab|cCB-b|bSC-DaD-Cb|CDaVVT=B,SS-BabB-b|bSC,D為什么沒(méi)有入選？為什么沒(méi)有入選？因?yàn)樗鼈儾荒芡瞥鼋K極符因?yàn)樗鼈儾荒芡瞥鼋K極符 刪除刪除不可用不可用產(chǎn)生式算法：產(chǎn)生式算法：(1) 構(gòu)造可用構(gòu)造可用的非終結(jié)符集的非終結(jié)符集 VUS: 首先令首先令 ZVUS ; (Z 為文法為文法開始符號(hào)開始符號(hào)) = + +(2) 刪除不在刪除不在VUS中的所有非終結(jié)符中的所有非終結(jié)符(連同其產(chǎn)生式連同其產(chǎn)生式)?！纠纠?.19】化簡(jiǎn)下述文法：】化簡(jiǎn)下述文法： G(S): S - Be | Ec A - Ae | e | A B - C e

41、| AfC - Cf ; D - f ; G - b 若有若有 Z A ，則，則 令令 AVUS ; 重復(fù)步驟重復(fù)步驟，直到，直到VUS不再擴(kuò)大為止。不再擴(kuò)大為止。 = + +文法的化簡(jiǎn)文法的化簡(jiǎn)例題：化簡(jiǎn)文法例題：化簡(jiǎn)文法S-aSab|bABA-bB|aB-aA|bC-abB|baAD-Cbc|abcVVT=A,B,C,D,SVUS=S,A,BS-aSab|bABA-bB|aB-aA|b 文法化簡(jiǎn)示例文法化簡(jiǎn)示例l 化簡(jiǎn)步驟：G(S): S - Be | EcG(S): S - Be | Ec A - AeA - Ae | e | A | e | A B - C e | AfB - C e

42、| AfC - CfC - Cf ; D - f ; G - b ; D - f ; G - b 刪除刪除 A - A ;2. 刪除刪除不終結(jié)不終結(jié)產(chǎn)生式產(chǎn)生式: VVT= A,D,G,B,S ; 應(yīng)刪除應(yīng)刪除 C,E(連同其產(chǎn)生式連同其產(chǎn)生式)得：得： G(S): S - Be ; A - Ae | e ; B - Af ;D - f ; G - b ;3. 刪除刪除不可用不可用產(chǎn)生式產(chǎn)生式: VUS= S,B,A ; 應(yīng)刪除應(yīng)刪除 D,G(連同其產(chǎn)生式連同其產(chǎn)生式) 整理后得：整理后得：G(S):A - Ae | eB - AfS - Be 刪除刪除 產(chǎn)生式產(chǎn)生式【算法【算法】1. 首先構(gòu)

43、造可以推出空串的非終結(jié)符集：首先構(gòu)造可以推出空串的非終結(jié)符集：V 若有若有 A- ; 則則 令令 AV ; 若有若有 B-A1 An 且全部且全部 AiV ;則令則令 BV ; 重復(fù)步驟重復(fù)步驟，直到，直到V 不再擴(kuò)大為止。不再擴(kuò)大為止。2. 刪除刪除 G(Z)中的中的 A - 形式的產(chǎn)生式；形式的產(chǎn)生式； 假定文法假定文法G(Z); L(G)3. 依次改寫依次改寫G(Z)中的產(chǎn)生式中的產(chǎn)生式 B - X1 X2 Xn :若有若有 Xi V 則用則用 (Xi| ) 替換之替換之(一個(gè)分裂為兩個(gè)一個(gè)分裂為兩個(gè))； 若有若有 j 個(gè)個(gè) Xi V ，則一個(gè)產(chǎn)生式將分裂為則一個(gè)產(chǎn)生式將分裂為2j個(gè)個(gè)!

44、 刪除刪除 產(chǎn)生式示例：產(chǎn)生式示例：(1) 求解求解 V = A,B (2) 刪除刪除 產(chǎn)生式產(chǎn)生式 得：得：S-aAbc|bS ；A-dABe ； B-A|b(3) 改寫改寫 右部含有右部含有 V 中元素的產(chǎn)生式：中元素的產(chǎn)生式： S-a(A| )bc S-aAbc|abc A-d(A| )(B| )e A-dABe|dBe|dAe|de B-(A| ) B-A含有含有V 元素元素的產(chǎn)生式的產(chǎn)生式 綜合綜合 G(S) ： S-aAbc|abc|bS A-dABe|dBe|dAe|de B-A|b【例【例2.20】G(S): S-aAbc|bS A-dABe| ; B-A|b練習(xí)：消空串練習(xí)：

45、消空串S-aBSS-bB-cSB-=S-a(B| )S S-b B-cS=S-aBS|aS S-b B-cS令令 ( | ) = 或者或者 1.必選項(xiàng)法（圓括號(hào)法） BNF（巴科斯范式）表示法（巴科斯范式）表示法必選其中之一！必選其中之一！例如：有例如：有 A - a |a 也可寫成：也可寫成： A - aA；A- | 【注】此法又稱【注】此法又稱提公因子法，提公因子法，利用此法可以解決：利用此法可以解決： 具有相同左部的各產(chǎn)生式首符號(hào)不同！具有相同左部的各產(chǎn)生式首符號(hào)不同！ 基本思想基本思想：擴(kuò)展文法，引進(jìn)新的：擴(kuò)展文法，引進(jìn)新的描述符號(hào)描述符號(hào)： ( ) 圓括號(hào)；圓括號(hào)； 方括號(hào)；方括號(hào)；

46、 花括號(hào)花括號(hào)可變換成可變換成: A - a( | ) 也可寫成：也可寫成： S - S; S - |令令 = 或者或者 2. 可選項(xiàng)法（方括號(hào)法） 例如：例如： S - | 可選也可不選！可選也可不選！例如例如 條件語(yǔ)句文法：條件語(yǔ)句文法： S - if (B) S 可變換成：可變換成： S - S - if (B) S else S可變換成：可變換成： S - if (B) S else S S(語(yǔ)句語(yǔ)句)，B(布布爾表達(dá)式爾表達(dá)式)或：或： S - if (B) S S ; S- else S| BNF（巴科斯范式）表示法（巴科斯范式）表示法3. 重復(fù)可選項(xiàng)法（花括號(hào)法） 例如：例如：

47、A - A| 令令 = 或或 或或 或或 可變換為：可變換為： A - 通過(guò)遞推方法，可得：通過(guò)遞推方法，可得： A= A= A= A= * 有有 A - 或或 A A ; A -A| 也可寫成：也可寫成： A A ; A -A| 驗(yàn)證：驗(yàn)證：【注】此方法常用來(lái)消除文法的【注】此方法常用來(lái)消除文法的直接左遞歸直接左遞歸！ BNF（巴科斯范式）表示法（巴科斯范式）表示法 產(chǎn)生式形式為：產(chǎn)生式形式為： A - u 2.6 形式語(yǔ)言的分類形式語(yǔ)言的分類 Chomsky 把形式語(yǔ)言分為把形式語(yǔ)言分為四類四類，分別由四類文，分別由四類文法定義；四類文法的區(qū)別在于法定義；四類文法的區(qū)別在于產(chǎn)生式的形式不同產(chǎn)生式的形式不同：(2) 1 型語(yǔ)言型語(yǔ)言 由由 1型文法型文法定義定義(1) 0 型語(yǔ)言型語(yǔ)言 由由 0型文法型文法定義定義又稱又稱 無(wú)限制文法無(wú)限制文法！ 產(chǎn)生式形式為：產(chǎn)生式形式為： - (VNVT)* 且至少有一個(gè)非終結(jié)符且至少有一個(gè)非終結(jié)符(VNVT)* 又稱又稱 上下文有關(guān)文法上下文有關(guān)文法！A VN, , (VNVT)* , u (VNVT)+A只有在只有在 和和 這樣的上下文環(huán)境中才能換成這樣的上下文環(huán)境中才能換成u2.6 形式語(yǔ)言的分類形