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

第二章 形式語(yǔ)言與文法,主要內(nèi)容: 1 語(yǔ)言的形式描述. 2 語(yǔ)言與文法的形式定義. 3 文法的分類. 4 語(yǔ)法樹(shù)及句型分析.,主要問(wèn)題： 已知給定的文法求該文法表示的語(yǔ)言 已知語(yǔ)言求描述該語(yǔ)言的文法 求給定語(yǔ)句的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄, 1.符號(hào)串,符號(hào)串是形式語(yǔ)言中最基本的名詞. 一, 字母表與符號(hào)串 1,字母表∑ 定義:元素的非空有窮集合 例:∑={a, b, c} (a, b, c字母表) ∑={0, 1} (二進(jìn)制數(shù)字字母表) ∑={漢字,數(shù)字,標(biāo)點(diǎn)符號(hào), …} (漢字組成的字母表) 注:元素可是字母、數(shù)字或其他符號(hào). 字母表中至少有一個(gè)元素.,2. 符號(hào)(字符),定義：字母表中的元素. 注:符號(hào)是字母表中不可再分解的最小單位. 3. 符號(hào)串 定義：字母表中的符號(hào)組成的有窮序列. 例:∑={a, b, c} 符 號(hào):a, b, c 符號(hào)串:a, b, c, ab, ac, aa, ba, ca, abc, … 例;設(shè)字母表A={0, 1} A中的符號(hào):0, 1 A中的符串:0,1,01,10,00,11,001,010, …,01000, …,顯然:字母表上的符號(hào)串可形成一個(gè)集合(可數(shù)無(wú)窮) 注: 1.符號(hào)串的組成與符號(hào)串組成的順序有關(guān).如01≠10,ab≠ba 2.空符號(hào)串為不包含任何符號(hào)的符號(hào)串,記為: ε 3.符號(hào)串的長(zhǎng)度:符號(hào)串所含符號(hào)的個(gè)數(shù).設(shè)符號(hào)串為x,則x的 長(zhǎng)度為∣x∣。 例:∣a∣=1 ∣abc∣=3 特別：|ε |＝0 即空符號(hào)串的長(zhǎng)度為零． 二．符號(hào)串的運(yùn)算 １．連接運(yùn)算 定義：設(shè)x和y為符號(hào)串，則xy被稱為x與y的連接． 設(shè)x＝abc，y＝10a 則xy＝abc10a；yx＝10aabc,２．符號(hào)串的方冪 設(shè)有符號(hào)串x，則x的n次連接稱為x的n次方冪，記為:x 例：x ＝ ε （注:x ≠１） x＝x x ＝xx x ＝x x＝xx ＝xxx …… x＝x x＝xx ＝xx…x n次連接 例:x＝abc 則x＝ ε ，x ＝abc，x ＝abcabc 即︱x︱＝０，︱x︱＝３，︱x︱＝６,n,,0,0,1,2,3,2,2,n,n－1,n－1,0,1,1,0,2,2,３．符號(hào)串集合的乘積 設(shè)AB＝｛xy︱x∈Ａ，y∈Ｂ｝ 即:AB是x∈Ａ,且y∈Ｂ的所有符號(hào)串xy構(gòu)成的集合． 例:設(shè)A＝｛a，b｝，B＝｛c，d｝ 則AB＝｛ac，ad，bc，bd｝ 注：{ε }A=A{ε}=A A=A =A (其中 為空集) ={ } 注: ε 不屬于 ， 即空符號(hào)串并不屬于空集,4.符號(hào)串集合的方冪 設(shè)A為符號(hào)串集合,則定義 A={ε} A=A A=AA A=AA=AA=AAA …… A=A A=AA =AA……A (n個(gè)) 例:設(shè)A={a,b} A={ε} A={a,b} A={aa,ab,ba,bb} (A共有2 =4個(gè)長(zhǎng)度為2的元素) A=AA={aa,ab,ba,bb}{a,b} ={aaa,aba,baa,bba,aab,abb,bab,bbb} (A共有2 =8個(gè)長(zhǎng)度為3的元素),0,1,2,3,2,2,n,n－1,n－1,0,1,2,3,2,2,3,3,5.符號(hào)串集合的正閉包A和閉包A ⑴.符號(hào)串集合的正閉包A 設(shè)A為符號(hào)串集合,則A定義為: A=A UA UA U……UA U…… 例 設(shè)A={a,b}則 A ={a,b} U {aa,ab,ba,bb} U…… ={a,b,aa,ab,ba,bb,aaa,…,bbb,……}={a,b} 即:A包括了由A上的元素a,b構(gòu)成的所有符號(hào)串. ⑵.符號(hào)串集合A的閉包A. A =A U A U A U…U A U…… (A =A U A ) 即A ={ε} U A = A U {ε} (A = A－{ε}),＋,＊,＋,＋,＋,1,2,3,n,＋,＋,＊,＊,0,1,2,n,＊,0,＋,＊,＋,＋,＋,＊,+,例 設(shè)A ={a,b} 則 A ={ε,a,b,aa,ab,ba,bb,aaa,…,bbb,……} ={a,b} 顯然:對(duì)于所有的A,有ε ∈A,＊,＊,＊,2.文法和語(yǔ)言的形式定義,一.文法與語(yǔ)言的關(guān)系 ●語(yǔ)言:由定義在該語(yǔ)言字母表上,且按一定組成規(guī)則所構(gòu)成的句子的集合. 即:字母表 {字符串(句子)} (語(yǔ)言) ●語(yǔ)言的描述 ⑴.當(dāng)語(yǔ)言為有窮個(gè)句子的集合時(shí),可用枚舉的方法表示語(yǔ)言. ⑵.當(dāng)語(yǔ)言為無(wú)窮個(gè)句子的集合時(shí),則用有無(wú)窮的語(yǔ)法規(guī)則(文法)描述無(wú)窮的句子的結(jié)構(gòu).,,語(yǔ)法規(guī)則,例:漢語(yǔ):人們無(wú)法列出全部的句子.但人們可以給出一些規(guī)則,用這些規(guī)則來(lái)說(shuō)明(或定義)句子的組成結(jié)構(gòu). 如:漢語(yǔ)句子結(jié)構(gòu): =+ =+ =︱ ………… 用擴(kuò)充BNF來(lái)表示這種句子的結(jié)構(gòu): ∷= (∷=表示“定義為”，“產(chǎn)生”，“生成”) ∷=︱ (︱表示“或者”) ∷=我︱你︱他 (表示非終結(jié)符) ∷=王明︱大學(xué)生︱工人︱英語(yǔ) ∷= (不加表示終結(jié)符),∷=是∣學(xué)習(xí) ∷=∣ 利用以上規(guī)則(文法)推導(dǎo)句子:我是大學(xué)生. 我 我 我是 我是 我是大學(xué)生 利用上列文法:可以產(chǎn)生的句子:我學(xué)習(xí)英語(yǔ),他學(xué)習(xí),語(yǔ),他是工人,….(很多句子),,,,,,,,利用上列文法不可產(chǎn)生“我大學(xué)生是”.它不符合以上規(guī)則. 文法的作用:不僅嚴(yán)格定義句子的結(jié)構(gòu),也是為了用有限的規(guī)則把語(yǔ)言的全部句子描述出來(lái)。它是用有窮的集合刻畫(huà)無(wú)窮集合的工具. 文法:語(yǔ)言的語(yǔ)法規(guī)則的有窮表示.(文法又稱元語(yǔ)言) 注: 1.有窮的文法通過(guò)推導(dǎo)的方法,可以推導(dǎo)出給定字母表上的所有句子. 2.描述文法的所有字符構(gòu)成了語(yǔ)言的字母表. 3.通過(guò)文法在推導(dǎo)合法句子過(guò)程中會(huì)有多個(gè)句型產(chǎn)生. 4.合法的句型和句子是用字符串表示的.,二. 文法的形式定義,1. 規(guī)則(產(chǎn)生式,生成式,重寫規(guī)則)是一個(gè)符號(hào)與一個(gè)符號(hào)串的有序?qū)?A, β) 常寫成:A∷= β 或 A → β 其中:A是規(guī)則的左部.它是某個(gè)字母表∑的正閉包∑中的一個(gè)符號(hào).即A∈∑. β是規(guī)則的右部.它是∑中一個(gè)符號(hào)串.(包括ε) 2. 文法的形式定義 定義:文法G是一個(gè)四元組,它是規(guī)則的非空有窮集合. G=(V ,V ,P,S) 其中:V 是文法規(guī)則式中的非終結(jié)符號(hào)集. V 是文法規(guī)則式中的終結(jié)符號(hào)集.,＋,＋,N,T,N,T,﹡,V ∩V =Ф P是文法的規(guī)則式集。 S是文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）。S∈V 非終結(jié)符號(hào)：出現(xiàn)在產(chǎn)生是左邊 ，能派生出符號(hào)和符號(hào)串的符號(hào),常用大寫字母表示，即，每一個(gè)非終結(jié)符號(hào)表示一定的符號(hào)串。它至少要在產(chǎn)生式左邊出現(xiàn)一次。 終結(jié)符號(hào)：不能派生出符號(hào)串的符號(hào)，它是組成語(yǔ)言不可再分的基本符號(hào)，一般用小寫字母表示。,N,T,N,例：文法G = (V ,V ,P,S),其中 VN={S} VT ={0,1} P ={S→0S1,S →01} 一般約定: 1.只寫出文法的產(chǎn)生式 2.第一條產(chǎn)生式的左部是開(kāi)始符號(hào)，且習(xí)慣用G（開(kāi)始符號(hào)）表示。 上例文法可寫成： G[S]: S::=0S1 S::=01,N,T,例：G[]: ::=| | ::= a|b|c|…|z ::= 0|1|2|…|9,其中：VN={ ， ， } S = { } VT ={a,b,c,…,z, 0,1,2,…,9 } 字母表：V=VN∪ VT ={ , , ,a,b,c,…,z, 0,1,2,…,9 },3.推導(dǎo),有了文法，怎樣由文法推導(dǎo)出與該文法相應(yīng)的語(yǔ)言？為此引入了“推導(dǎo)”等概念。 直接推導(dǎo) 設(shè)x,y是V*中任意符號(hào)串，若用一次規(guī)則式可以從x推出y，則稱y是x的直接推導(dǎo)，記為：x y。（或稱符號(hào)串x直接產(chǎn)生了符號(hào)串y，或稱y直接歸約到x）,,例：設(shè)G[S]: S::=0S1|01 則有如下一些直接推導(dǎo)：,S 01 （利用S::=01 ） S 0S1 （利用S::=0S1 ） 0S1 0011 （利用S::=01 ） 0S1 00S11 （利用S::=0S1 ） 說(shuō)明：每利用文法中的一條規(guī)則U::=u一次，均可得到一次直接推導(dǎo)： U u,,,,,,推導(dǎo)（＋推導(dǎo)） 若使用若干次規(guī)則式可以從x推出y，則稱y為x的推導(dǎo)，記為：x ＋y（或稱x產(chǎn)生y，或稱y規(guī)約到x），或記為：x y 例：上例： 0S1 00S11 000S111 00001111 ∴ 0S1 + 00001111 （推導(dǎo)長(zhǎng)度為3）,,,,,,,,,＋,廣義推導(dǎo)（＊推導(dǎo)） 若x ＋y或者x＝y(tǒng)（表示0步推導(dǎo)），則寫為x ＊y （反之亦然，即：x ＊y，當(dāng)且僅當(dāng)x ＋y或者x＝y(tǒng) ） 例，上例中： 0S1 +00001111也可記為：0S1 *00001111 注：直接推導(dǎo)、推導(dǎo)、廣義推導(dǎo)的區(qū)別： 推導(dǎo)長(zhǎng)度n不同： 直接推導(dǎo)：n＝1 推導(dǎo)：n≥ 1 廣義推導(dǎo)：n≥ 0 (0步推導(dǎo)：如S＝s),,,,,,,,,,,,,＊包涵 ＋ 包涵,,,,,,4.句型和句子,設(shè)有文法G[S],若有S ＊x,則稱符號(hào)串x為文法G[S]的句型。 換句話說(shuō)：凡是由識(shí)別符號(hào)推導(dǎo)出來(lái)的任意符號(hào)串稱為句型。 句子：僅有終結(jié)符號(hào)組成的句型稱為句子。 區(qū)別：符號(hào)串x∈(VN∪VT)*;x稱為句型， 符號(hào)串x∈VT*;x稱為句子。,,例：G[S]: S::=01|0S1 S 01 S 0S1 00S11 000111 可見(jiàn)：01,0S1,00S11,000111均為文法G[S]的句型。 其中：01，000111為句子（說(shuō)明句型包含了句子，句子是特殊的句型） 但是：符號(hào)串000S11,0000111都不是文法G[S]的句型。,,,,,例：已知文法G[E]： E::=E+E|E*E|(E)|i (其中:VN={E} VT={+,*,i,(,)}) 試證明:符號(hào)串(i*i+i)是文法G[E]的一個(gè)句子。 證明：只要證明(i*i+i)是文法G[E]的一個(gè)存在的推導(dǎo)）(需從開(kāi)始符號(hào)出發(fā) ) E=(E) =(E+E) =(E*E+E) =(i*E+E) =(i*i+E) =(i*i+i) 即：E=＊ (i*i+ i) 所以,符號(hào)串(i*i+i)是文法G[E]的一個(gè)句子。,三、語(yǔ)言的形式定義：,定義：由文法G[S]產(chǎn)生的所有句子的集合。即： L(G[S]) = {x|S=+x,且x∈V*} 注： 一旦文法給定，語(yǔ)言就確定。 語(yǔ)言L(G)是V*的子集。（語(yǔ)言是字母表中終結(jié)符號(hào)串閉包的子集） 即：屬于L(G)的句子屬于V* 反之,屬于V*的符號(hào)串x不一定屬于L(G)。,T,T,T,T,例：已知文法G[S]： S::=0S1|01 求:L(G)=? 解：分析：S=0S1 =00S11 =000S111 … =0n-1S1n-1 =0n1n 即：S=＊0n1n ∴G描述的語(yǔ)言：L(G[S]) = {0n1n | n≥1 } 但： VT’＝{0,1,00,01,10,11,000,…,111,0000,…,0011,…,1111,…}， 可見(jiàn)L(G)僅是VT‘的真子集。,＋,＋,例：已知文法：G[S]: S∷=0S|1S|ε,求L(G)=? 解：L(G[S]) = {ε,0,1,01,11,00,10,…} = {x | x∈{0,1}* },例：已知： S∷=aB|bA A∷=a|aS|bAA B∷=b|bS|aBB 求：L＝？ 解： S=aB=ab S=aB=abS=abaB=abab S=aB=aaBB=aabB=aabb 又∵S=bA=ba S=bA=baS=babA=baba S=bA=bbAA=bbaA=bbaa ∴L(G[S]) = {x|x∈{a,b},且x中a，b個(gè)數(shù)相同} 反過(guò)來(lái)，給定語(yǔ)言L(G)后，若要寫出能正確描述此語(yǔ)言的文法，是有一定難度的。,+,例：試對(duì)語(yǔ)言L(G) = {(n)n|n=0,1,2,…}構(gòu)造相應(yīng)的文法G。 解：（1）首先分析L是由怎樣的符號(hào)串x組成的。 當(dāng)n=0時(shí)，x=ε 當(dāng)n=1時(shí)，x=() 當(dāng)n=2時(shí)，x=(()) 當(dāng)n=3時(shí)，x=((())) … ∴L(G) = {ε,(),(()),((())),…},(2) 歸納集合L(G)的組成特點(diǎn)： L(G)中每個(gè)符號(hào)串呈對(duì)稱形式，即 ( 和 )成對(duì)出現(xiàn)。 L(G)為無(wú)窮集合，因此描述出的規(guī)則中必然含有遞歸定義。 L(G)中的終結(jié)符號(hào)只有兩個(gè):( 和 )。 (3) 寫出規(guī)則：S∷=(S)| ε 即，定義此語(yǔ)言L(G)的文法： G: VT = {(,)}, VN = {S},S為開(kāi)始符號(hào)，產(chǎn)生式： P： S∷=(S)| ε,例：給出語(yǔ)言L(G) ＝ {anbncm|n≥1,m≥0}的對(duì)應(yīng)文法 解：分析： 將anbn看成一個(gè)整體用一個(gè)非終結(jié)符號(hào)A來(lái)表示，cm看成另一個(gè)整體用非終結(jié)符B來(lái)表示。 設(shè)S為G的識(shí)別符號(hào)，則有S∷=AB，而由A推出anbn，B推出cm 。 保證anbn成立，即a,b個(gè)數(shù)相等，且大于等于1。 所以可以用產(chǎn)生式：A∷=aAb|ab 又因?yàn)閙可以為0 ,所以 S::=AB改寫為S::=AB|A; 又由于A∷=aAb|ab，則對(duì)B容易看出B∷=cB|c ∴ S∷=AB|A S∷=AB A∷=aAb|ab 或者： A∷=aAb|ab B∷=cB|c B∷=cB|c|ε,例：設(shè)字母表∑＝{a,b},試設(shè)計(jì)一個(gè)文法，描述語(yǔ)言L＝{a ,b | n≥1} 解：分析語(yǔ)言由怎樣的符號(hào)串組成。 當(dāng)n=1時(shí)，L={aa,bb} 當(dāng)n=2時(shí)，L={aaaa,bbbb} 當(dāng)n=3時(shí)，L={aaaaaa,bbbbbb} … L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…} 即：語(yǔ)言由偶數(shù)個(gè)a和偶數(shù)個(gè)b的符號(hào)串組成。所以，描述語(yǔ)言的文法： G[A]: A∷=aa|aaB|bb|bbD B∷=aa|aaB D∷=bb|bbD,2n,,2n,可以寫出另一個(gè)文法： G1[A]: A∷=B|D B∷=aa|aBa D∷=bb|bDb 可見(jiàn)，對(duì)于給定語(yǔ)言，描述該語(yǔ)言的文法不是唯一的。 注： ①描述一個(gè)語(yǔ)言的文法不是唯一的 ②若不同的文法產(chǎn)生相同的語(yǔ)言，則稱這些文法是等價(jià)的。,例：設(shè)有文法 G1={VN,VT,P,A} 其中： VN={A} VT={a,b} P={A::=ab} 顯然： L(G1)={ab} 文法 G2={VN,VT,P,A} 其中： VN ={A,B} VT ={a,b} P={A::=Bb,B::=a} 顯然： L(G2,)={ab} 即：L(G1)=L(G2)，且G1= G2 ③若語(yǔ)言在語(yǔ)法上等價(jià)，并不一定意味著語(yǔ)義上等價(jià)。,例：G3[S]和G4[S]它們的VN和VT相同： VN ={S,A}, VT ={a,b,c} 而, G3[S]的P為： S::=A|S-A A::=a|b|c G4[S]的P為： S::=A|A-S A::=a|b|c 顯然：G3 [S]和G4 [S]等價(jià)（語(yǔ)法），因?yàn)樗鼈兌籍a(chǎn)生相同的句子： {a,b,c,a-b-c,a-b-b-c,…} 但：句子的含義（語(yǔ)義）不一定相同： 例如：由G3[S]推導(dǎo)出的句子：a-b-c其含義為(a-b)-c 由G4[S]推導(dǎo)出的句子：a-b-c其含義為a-(b-c),④文法應(yīng)該能準(zhǔn)確地描述語(yǔ)言，不能擴(kuò)大或縮小。 例：設(shè)計(jì)一個(gè)表示所有標(biāo)識(shí)符的文法。 解：分析：標(biāo)識(shí)符：字母|字母開(kāi)頭的字母數(shù)字串,用B表示標(biāo)識(shí)符；L-字母；D-數(shù)字： 則G[B]的產(chǎn)生式P: B::=L|BL|BD L::=a|b|c|…|x|y|z D::=0|1|2|…|9 ……可以表示a1b2c3,若將產(chǎn)生式設(shè)計(jì)成P1： B::=L|BD L::=a|b|c|…|x|y|z D::=0|1|2|…|9 表示：字母開(kāi)頭，后面全是數(shù)字：abc1， 不能表示a1b2c3 顯然：P1 縮小了標(biāo)識(shí)符的表示，比P描述的范圍縮小了 若將產(chǎn)生式設(shè)計(jì)成P2： B::=L|BL|BD|D L::=a|b|c|…|x|y|z D::=0|1|2|…|9 顯然: P2也不能準(zhǔn)確地描述，擴(kuò)大了P的描述范圍,3 與語(yǔ)法分析有關(guān)的概念,一、短語(yǔ)、簡(jiǎn)單短語(yǔ)與句柄 短語(yǔ)：設(shè)有文法G[S]，W=αβδ是G的一個(gè)句型。若有識(shí)別符號(hào)S=＊αAδ,且A=+β,則稱β是相對(duì)非終結(jié)符A的句型w的短語(yǔ)。 特別，如果上式A=+β為： A=β 則稱β為句型w的簡(jiǎn)單短語(yǔ)（直接短語(yǔ)）,例：設(shè)有文法G=({S,A,B},{a,b},P,S)其中P為： 1. S::=AB 2. A::=Aa 3. A::=bB 4. B::=a 5. B::=Sb 試求句型baSb,bBABb和baabaab全部短語(yǔ)，簡(jiǎn)單短語(yǔ)。 解：先討論句型w=baSb,其中子串b,a,S,ba,aS,Sb,baS,aSb. 是句型w的短語(yǔ)嗎？ 根據(jù)短語(yǔ)定義，可由句型的推導(dǎo)中找到全部短語(yǔ)及簡(jiǎn) 單短語(yǔ)。 最左推導(dǎo)：,,由此可見(jiàn)，下式成立： ①∵S=*S,且S=+baSb ∴baSb是短語(yǔ)(句型 本身是短語(yǔ))(注意:主要求異于句型本身的短語(yǔ)). ②又∵ S=*AB,且B=Sb ∴句型baSb中子串Sb也該句型（相對(duì)于B）的短語(yǔ),且是簡(jiǎn)單短語(yǔ)。 ③又∵ S=*bBSb,且B=a ∴句型baSb中子串a(chǎn)也該句型（相對(duì)于B）的短語(yǔ),且是簡(jiǎn)單短語(yǔ)。 ④ 又∵ S=*ASb,且A=+ba ∴句型baSb中子串ba也該句型（相對(duì)于A）的短語(yǔ). 注:短語(yǔ)是句型中的子串,在推導(dǎo)中不是句型中的子串不能作短語(yǔ)。 如:S=*ASb ,A=bB;則由于bB不是句型baSb中子串,所以他不是該句型的短語(yǔ).,,∴sb，a，ba是句型baSb異于自身的短語(yǔ)(句型本身是短語(yǔ)),其中Sb,a是簡(jiǎn)單短語(yǔ)。 最右推導(dǎo)： 同樣可求出同上的該句型的短語(yǔ),同學(xué)們可自求. 可用同樣的方法分析句型bBABb和baabaab的全部短語(yǔ)和簡(jiǎn)單短語(yǔ)（略）同學(xué)們也可自求。 句柄：句型的最左簡(jiǎn)單短語(yǔ) 特征：句柄至少是簡(jiǎn)單短語(yǔ)（某規(guī)則的右部），且為最左簡(jiǎn)單短語(yǔ)（具有最左性）。 例如：上例中a是最左簡(jiǎn)單短語(yǔ)――句柄。,注:短語(yǔ)、簡(jiǎn)單短語(yǔ)與句柄的關(guān)系: ●它們都是針對(duì)某個(gè)句型而言的,離開(kāi)了句型來(lái)談短語(yǔ)、簡(jiǎn)單短語(yǔ)與句柄,是毫無(wú)意義的. ●句柄一定是簡(jiǎn)單短語(yǔ)和短語(yǔ),反之不成立. ●簡(jiǎn)單短語(yǔ)和句柄一定是某個(gè)產(chǎn)生式的右部符號(hào)串,短語(yǔ)不是(他作為我們尋找和判斷句型的簡(jiǎn)單短語(yǔ)的依據(jù));但文法中產(chǎn)生式的右部符號(hào)串不見(jiàn)得都是簡(jiǎn)單短語(yǔ)或句柄. 二、最右（左）推導(dǎo)，規(guī)范推導(dǎo)和規(guī)范規(guī)約，規(guī)范句型 (1) 最右（左）推導(dǎo)：在推導(dǎo)過(guò)程中，任何一步α=β都是對(duì)α中最右（左）非終結(jié)符進(jìn)行替換。稱為最右（左）推導(dǎo)。 特別：最右推導(dǎo)稱為規(guī)范推導(dǎo)。得到的句型稱為規(guī)范句型。,例：設(shè)有文法G的規(guī)則集P為： S::=AB A::=Aa|bB B::=a|Sb 給出babaab的最右（左）推導(dǎo) 解：最右推導(dǎo)： S=AB=ASb=AABb=AAab=AbBab=Abaab=bBbaab=babaab規(guī)范推導(dǎo)。 最左推導(dǎo)：S=AB=bBB=baB=baSb=baABb=babBBb=babaBb=babaab 忽左忽右推導(dǎo)：,,歸約：將句型中某一個(gè)子串用一個(gè)非終結(jié)符替換的過(guò)程。 若有A::= α,則xAy=xαy，有： xαy=xAy……規(guī)約 (2) 規(guī)范歸約（又稱最左規(guī)約） ：規(guī)范推導(dǎo)（最右推導(dǎo)）的逆過(guò)程。 例：G[N1]: N1::=N N::=ND|D D::=0|1|2 最右推導(dǎo)：N1=N=ND=N2=D2=12 最左規(guī)約： 12=D2=N2=ND=N= N1,三、文法的遞歸 1．遞歸規(guī)則 若文法中有形如規(guī)則:A::=A…，稱為規(guī)則左遞歸。 若文法中有形如規(guī)則:A::=…A，稱為規(guī)則右遞歸 。 若文法中有形如規(guī)則:A::=…A…，稱為規(guī)則遞歸。（規(guī)則遞歸稱為直接遞歸） ２．文法的遞歸性 如果有推導(dǎo)A=+A…，稱文法左遞歸 如果有推導(dǎo)A=+…A，稱文法右遞歸 如果有推導(dǎo)A=+…A…，稱文法遞歸 （文法遞歸稱為間接遞歸）,例：G[N1]: N1::=N N::=ND （規(guī)則左遞歸：直接遞歸） 例：G[U]: U::=Vx V::= U y|a ∵U=Vx= U yx (左遞歸文法:間接遞歸) G[U]的規(guī)則中無(wú)規(guī)則左遞歸，但在推導(dǎo)過(guò)程中存在左 遞歸，所以G[U]是左遞歸文法。 作用：用遞歸規(guī)則可以定義無(wú)窮集合的語(yǔ)言。 例：G[A]: A::=B B::=D|DD|DDD…， D::=0|1|2|… 結(jié)論：若語(yǔ)言為無(wú)窮集合，描述語(yǔ)言的文法一定是遞歸的。,可用 A::=AD替代,,四、語(yǔ)法樹(shù)與文法的二義性 句型的語(yǔ)法樹(shù) (1) 作用： 直觀地求出一個(gè)句型的短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄。 直觀地表示一個(gè)句型（或句子）的推導(dǎo)或歸約過(guò)程，即它是語(yǔ)法分析的工具。 可以判斷一個(gè)文法的二義性問(wèn)題。,(2) 句型推導(dǎo)的語(yǔ)法樹(shù)表示 用樹(shù)型結(jié)構(gòu)直觀地表示一個(gè)句型的推導(dǎo)過(guò)程，稱為該句型的一棵語(yǔ)法樹(shù)（又稱推導(dǎo)樹(shù)） 語(yǔ)法樹(shù)的構(gòu)成： 樹(shù)的根為文法的識(shí)別符號(hào)； 樹(shù)的中間結(jié)點(diǎn)是文法的非終結(jié)符； 葉子結(jié)點(diǎn)為文法的終結(jié)符號(hào)或非終結(jié)符號(hào)。 若一個(gè)標(biāo)記為U的結(jié)點(diǎn)，它有標(biāo)記依次為 x1x2x3……xn 的直接后繼結(jié)點(diǎn)，即U::=x1x2x3……xn 必定是文法G的一條規(guī)則。 一個(gè)句型的推導(dǎo)過(guò)程用語(yǔ)法樹(shù)表示：,例：設(shè)有文法G[E]： E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i 根據(jù)推導(dǎo)，畫(huà)出句型（T+I)＊i-F的語(yǔ)法樹(shù)： 最右推導(dǎo)： E=E-T=E-F=T-F =T*F-F=T*i-F=F*i-F=(E)*i-F =(E+T)*i-F =(E+F)*i-F =(E+i)*i-F =(T+i)*i-F,,,最左推導(dǎo)：從左向右畫(huà)子樹(shù)。 子樹(shù)：由某一結(jié)點(diǎn)連同所有分支組成的部分。 簡(jiǎn)單子樹(shù)：包括葉子在內(nèi)的單層子樹(shù)。 (3) 語(yǔ)法樹(shù)中的短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄的概念 短語(yǔ)：子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串是相對(duì)子樹(shù)根的短語(yǔ)。 簡(jiǎn)單短語(yǔ)：簡(jiǎn)單子樹(shù)末端結(jié)點(diǎn)形成的符號(hào)串是相對(duì)于簡(jiǎn)單子樹(shù)根的簡(jiǎn)單短語(yǔ)。 句柄：最左簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串是句柄。,例：設(shè)有文法G[E]： E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i 求 (T+i)*i –F的短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄。 (T+i)*i –F為句型的相對(duì)根E的短語(yǔ)。 (T+i)*i 為句型的相對(duì)于以T為根的子樹(shù)的短語(yǔ)。 (T+i)為句型的相對(duì)于以F為根的子樹(shù)的短語(yǔ)。 T+i為句型的相對(duì)于以E為根的子樹(shù)的短語(yǔ)。 T為句型的相對(duì)于以E為根的子樹(shù)的短語(yǔ)，且為簡(jiǎn)單短語(yǔ)。 第一個(gè)i為句型的相對(duì)于以F為根的子樹(shù)的短語(yǔ)，且為簡(jiǎn)單短語(yǔ)。 第二個(gè)i為句型的相對(duì)于以F為根的子樹(shù)的短語(yǔ)，且為簡(jiǎn)單短語(yǔ)。 F為句型的相對(duì)于以T為根的子樹(shù)的短語(yǔ)，且為簡(jiǎn)單短語(yǔ)。 在四個(gè)簡(jiǎn)單短語(yǔ)T，i，i，F(xiàn)中，T為句型的句柄,例：設(shè)有文法G[S]： S::=(T)|a|ε T::=T,S|S 求句子（a,(a,a)）最右推導(dǎo)的逆過(guò)程（最左規(guī)約）每 一步的句柄。 ——最右推導(dǎo)：S =(T) 句柄:（T） =(T,S) 句柄:T,S =(T,(T)) 句柄:(T) =(T,(T,S)) 句柄:T,S =(T,(T,a)) 句柄:第三個(gè)a =(T,(S,a)) 句柄:S =(T,(a,a)) 句柄:第二個(gè)a =(S,(a,a)) 句柄:S =(a,(a,a)) 句柄:第一個(gè)a,,文法的二義性 所謂文法的二義性是指文法存在的某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)（或說(shuō)存在兩個(gè)不同的最左（右）推導(dǎo)）。 例：文法G[E]：E::=E+E|E*E|(E)|i 句子i*i+i有兩個(gè)不同的語(yǔ)法樹(shù)（最左推導(dǎo)） E =E+E=E*E+E =i*E+E =i*i+E =i*i+i,E=E*E=i*E =i*E+E =i*i+E =i*i+i ∴G[E]具有二義性 文法的二義性會(huì)導(dǎo)致對(duì)二義性文法的句子結(jié)構(gòu)產(chǎn)生多種不同的理解，造成語(yǔ)法分析和語(yǔ)義理解的不確定性。希望描述語(yǔ)言的文法是無(wú)二義性的。,文法二義性的消除 (1) 不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一些語(yǔ)法的非形式規(guī)定。 例如，對(duì)于上例文法G[E],不改變已有的4條規(guī)則，僅加入運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則；即*優(yōu)先于+；+,*服從左結(jié)合。這樣，句子i*i+i只有唯一的一棵語(yǔ)法樹(shù)（如上例的第一個(gè)圖）。 (2) 改寫文法。把排除二義性的規(guī)則合并到原文法中，構(gòu)造一個(gè)等價(jià)的無(wú)二義性的文法。,例如，對(duì)于上例文法G[E],將運(yùn)算符的優(yōu)先順序及結(jié)合規(guī)則（*優(yōu)先于+；+,*服從左結(jié)合）加到原文法中： E::=E+T|T T::=T*F|F F::=(E)|i 則句子i*i+i只有唯一的語(yǔ)法樹(shù) 可見(jiàn)：對(duì)于有二義性文法描述的語(yǔ)言，有時(shí)可以找到等價(jià)的無(wú)二義性文法來(lái)描述它。,例：某語(yǔ)言的條件語(yǔ)句的文法G為： S::=if b S|if b S else S |A (A為其它語(yǔ)句) 證明G具有二義性，并消除之。 分析：該文法的句子if b if b A else A對(duì)應(yīng)的兩棵不同的語(yǔ)法樹(shù),所以G是具有二義性的文法。 消除二義性： (1).不改變已有規(guī)則，僅加入一項(xiàng)非形式語(yǔ)法規(guī)定： else與前面最接近的if配對(duì)。這時(shí)句子if b if b A else A 只唯一對(duì)應(yīng)語(yǔ)法樹(shù)(a). (2).改造文法G為G’: S::=S1|S2 S1::=if b S1else S1 |A S2::=if b S|if b S1 else S2,注： 文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。通常只說(shuō)文法的二義性，而且不說(shuō)語(yǔ)言的二義性，因?yàn)槊枋稣Z(yǔ)言的文法不唯一，可能存在一個(gè)文法G有二義性，一個(gè)文法G’無(wú)二義性：使L(G)=L(G’) 如果語(yǔ)言是二義性的，則它不存在無(wú)二義性的文法，這樣的語(yǔ)言稱為先天二義性語(yǔ)言。 如：L={a b c | i=j或j＝k,i,j,k≥1}便是這種語(yǔ)言。 已證明，不存在一個(gè)算法，它能在有限步驟內(nèi)確切地判定任意給定一個(gè)上下文無(wú)關(guān)文法是否為二義性文法，或它是否會(huì)產(chǎn)生一個(gè)先天二義性的上下文無(wú)關(guān)語(yǔ)言。,i,j,k,4 文法與語(yǔ)言的分類,分類的依據(jù)：將文法中的規(guī)則施加不同的限制。 文法被劃分為4類：0～3型文法 一、0型文法（短語(yǔ)文法） 若文法G的規(guī)則式具有形式：α::=β(其中 α∈(VN∪VT)+,β∈(VN∪VT)*)即α，β都是符號(hào)串 對(duì)它們沒(méi)有作任何限制。（也可以|α||β|） 由0型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言 0型文法的能力相當(dāng)于圖靈機(jī)。,例：有產(chǎn)生式P： S::=0AB 1B::=0 B::=SA|01 A1::=SB1 A0::=S0B |α||β|為0型文法 該文法推不出任何句子：L={ },二、1型文法（上下文有關(guān)文法） 若文法G中規(guī)則呈現(xiàn)下列的形式： αAβ::= αuβ 其中：A∈VN，u ∈(VN∪VT)+, α, β∈(VN∪VT)* 則稱G為1型文法，所產(chǎn)生的語(yǔ)言為1型語(yǔ)言。 由于利用規(guī)則將A替換為u時(shí)，必須考慮A在上下 文α…β中出現(xiàn)的情況，即與上下文有關(guān)，故又稱為 下文有關(guān)文法。 特點(diǎn)：每個(gè)規(guī)則式：|左邊|≤|右邊|；規(guī)則右部符號(hào)個(gè)數(shù)至少與左部符號(hào)個(gè)數(shù)一樣多。,例：設(shè)有G=(VN ， VT ，P，S) VN={S,B,C} VT={a,b,c} P: S::=aSBC S::=aBC CB::=BC aB::=ab bB::=bb bC::=bc cC::=cc 這是一個(gè)1型文法，它描述了如下語(yǔ)言 L(G)={an bn cn |n≥1},三、2型文法（上下文無(wú)關(guān)文法） 若文法G中規(guī)則呈現(xiàn)如下形式： A::= β 其中，A∈VN， β ∈（VN∪VT）* 則稱G為2型文法，由它產(chǎn)生的語(yǔ)言稱2型語(yǔ)言。 由于利用規(guī)則將A替換成β時(shí)與其上下文無(wú)關(guān)，即與A在 上下文出現(xiàn)的情況無(wú)關(guān)，所以又稱這種文法為上下文無(wú)關(guān)文 法。 例：文法G的產(chǎn)生式P： E::=E+E|E*E|(E)|i 屬于2型文法。 特點(diǎn)：2型文法產(chǎn)生式的左部是單個(gè)的非終結(jié)符，右部為終結(jié)符和非終結(jié)符組成的符號(hào)串。 注：上下文無(wú)關(guān)文法可以描述當(dāng)今的程序語(yǔ)言,四、3型文法（正規(guī)文法） 如果對(duì)2型文法的產(chǎn)生式作進(jìn)一步的限制，限制 產(chǎn)生式的右部是單一終結(jié)符或單一終結(jié)符和單一非 終結(jié)符組成。 若文法G中的規(guī)則式，呈現(xiàn)如下形式： 右線性文法 A::= aB A::= a 或左線性文法 A::= Ba A::= a 其中：A，B∈VN，a∈VT 稱G為3型文法?；蚍Q正規(guī)（正則）文法，由它 產(chǎn)生的語(yǔ)言為3型語(yǔ)言或正規(guī)語(yǔ)言。,＊,+,例：設(shè)有G=( V ,V ,P,S) P: S::=A0|B1 A::=0|1 B::=0|1 左線性文法 注：①文法類型是由產(chǎn)生式的形式來(lái)劃分：,N,T,即：G0 G1 G2 G3,表格：文法類型與產(chǎn)生式,,,,,,②文法的分類對(duì)于程序設(shè)計(jì)語(yǔ)言的編譯程序有重要的意義。 程序語(yǔ)言的詞法規(guī)則屬于正則文法?編譯程序詞法掃描器采用正則文法識(shí)別技術(shù)。 程序語(yǔ)言的語(yǔ)法和語(yǔ)義部分的規(guī)則屬于上下文有關(guān)文法。但考慮高功效而采用上下文無(wú)關(guān)文法定義語(yǔ)法?編譯程序語(yǔ)法分析器采用上下文文法識(shí)別技術(shù)。 程序語(yǔ)言的詞法由正則文法描述。,程序語(yǔ)言中與局部語(yǔ)法有關(guān)的規(guī)則屬于上下文無(wú)關(guān)文法。 程序語(yǔ)言中全局的語(yǔ)法與語(yǔ)義有關(guān)的部分屬于上下文有關(guān)文法。（如標(biāo)識(shí)符類型匹配問(wèn)題（說(shuō)明部分與語(yǔ)句部分）。過(guò)程調(diào)用中實(shí)參與形參要求一致的問(wèn)題等等）,5文法的實(shí)用限制,在實(shí)際使用中，對(duì)文法要作一些假定或限制。 例如限制文法不含有有害規(guī)則或多余的規(guī)則。 一、文法中不能含有有害規(guī)則U::=U 這樣的規(guī)則顯然沒(méi)有必要，而且會(huì)引起二義性。 例如，文法G[S]: S::=0S1|01是無(wú)二義性的，若將規(guī)則寫成：S::=0S1|01|S則文法G不再是無(wú)二義性的。就句子0011而言，可畫(huà)出多棵語(yǔ)法樹(shù)。,二、文法中不能含有多余的規(guī)則 文法的規(guī)則中不含有無(wú)用的非終結(jié)符和不可到達(dá)的符號(hào)。 1.無(wú)用的非終結(jié)符號(hào)（不可終止符號(hào)） 如果從文法中某個(gè)非終結(jié)符推不出終結(jié)符號(hào)串，則稱該非終結(jié)符號(hào)為無(wú)用的非終結(jié)符 2.不可到達(dá)的符號(hào) 如果文法規(guī)則中的一個(gè)非終結(jié)符（不是識(shí)別符號(hào)），不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱該非終結(jié)符為不可到達(dá)的符號(hào).,例：已知文法G=( VN，VT，P，Z) 其中， VN={Z,A,B,C,D},VT={e,f} P: Z::=Be A::=Ae|e B::=Ce|Af C::=Cf D::=f C為無(wú)用的非終結(jié)符，因?yàn)镃在推導(dǎo)中沒(méi)有終結(jié)符號(hào)替換。 ∴C::=cf 和B::=Ce多余應(yīng)該刪去。,D為不可到達(dá)的符號(hào)，即D::=f在推導(dǎo)中不 起作用，應(yīng)該刪去。 刪除多余的規(guī)則后的文法為： Z::=Be A::=Ae|e B::=Af,文法中不含多余規(guī)則的充要條件： U(U∈VN)必須出現(xiàn)在某個(gè)推導(dǎo)的句型中，即：Z=＊x∪y。（U為文法的非終結(jié)符） 能從U推出終結(jié)符號(hào)串，即：U=+t(t∈VT) 滿足上述條件的文法稱為壓縮過(guò)的或化簡(jiǎn)了 的。 對(duì)文法的限制還有： 文法中不含有左遞歸規(guī)則U::=U…。（消除左遞歸在后面會(huì)講到） 對(duì)于上下文無(wú)關(guān)文法，限制U::= ε，即不含有空規(guī)則。（可以變換消除）等等,6小結(jié),本章主要解決的問(wèn)題： 已知文法，確定該文法描述的語(yǔ)言 已知語(yǔ)言，設(shè)計(jì)描述該語(yǔ)言的文法 求句型的短語(yǔ)，簡(jiǎn)單短語(yǔ)及句柄 文法二義性的判斷,一、已知文法，確定該文法描述的語(yǔ)言 1.語(yǔ)言的定義：文法G產(chǎn)生句子的全體。即L(G[S])={x|S=+x,且x∈VT*} 2.語(yǔ)言的描述： 用自然語(yǔ)言：L={x|x∈{a,b}+,且x中a，b個(gè)數(shù)相同} 用式子：L={a2nbb|n≥0} 用正規(guī)式：L={bna| n≥0}，可用：L=b*a來(lái)描述。 3.求法：根據(jù)給定文法，從文法的識(shí)別符號(hào)開(kāi)始，推導(dǎo)出所有的句子，然后歸納寫出語(yǔ)言描述的三種形式之一。,例：有如下文法G[S]： S::=AB A::=aAb|ab B::=BC|ε 求：L(G[S])=? 解：S=AB=abB=ab S=AB=abB=abBc=abc S=AB=aAbB=aabbB=aabb S=AB=aAbB=aabbB=aabbBC=aabbc …… ∴L(G[S])={anbnc | n≥1, m≥0},m,例：已知文法G[S]為： S::=dAB A::=aA|a B::=Bb|ε G[S]產(chǎn)生的語(yǔ)言是什么？G[S]能否改寫為等價(jià)的正規(guī) 文法？ 解：首先分析G[S]產(chǎn)生的語(yǔ)言： 語(yǔ)言的句子都是d開(kāi)頭，后跟a或b，且a，b個(gè)數(shù)不等。 L(G[S])={danbm| n≥1, m≥0} 根據(jù)語(yǔ)言的特點(diǎn)：a,b的個(gè)數(shù)n與m沒(méi)有相互制約 的關(guān)系，所以將an與bm分別構(gòu)造，得到正規(guī)文法： G[S]：S::=dA A::=aA|aB|a B::=bB|b,二、已知語(yǔ)言，設(shè)計(jì)描述該語(yǔ)言的文法 文法的形式定義：四元組G[S]=( VN,VT,P,S)，主要求產(chǎn)生式P。 分析已知語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)相應(yīng)的產(chǎn)生式，但求出的文法不唯一。 設(shè)計(jì)出的文法必須能準(zhǔn)確地定義已知的語(yǔ)言，不能超出或縮小所定義的語(yǔ)言范圍。 若語(yǔ)言是句子的無(wú)窮集合，則設(shè)計(jì)的文法一定是遞歸的。,例：已知L={x| x∈{a,b,c}*, 且x中符號(hào)的排列是對(duì)稱的。（例如：aabcbaa或aabbaa等）} 試寫出產(chǎn)生該語(yǔ)言的文法。 解：句子x中符號(hào)有多個(gè)，所以有遞歸產(chǎn)生式存在。 又因?yàn)榫渥觴中符號(hào)是對(duì)稱的，保證對(duì)稱的推導(dǎo)出每個(gè) 符號(hào)就可以了。 G[Z]: Z::=aZa|bZb|cZc|a|b|c|ε 例：給出描述：L={a2m+1bm+1|m≥0}∪{a2mbm+2|m≥0}的文法。 解：將句子的描述變形： a2mabbm和a2mbbbm 發(fā)現(xiàn)句子中前后的a和b的個(gè)數(shù)有倍數(shù)關(guān)系 于是：G[Z]: Z::=aaZb|ab|bb,例：寫一文法，使其語(yǔ)言是偶整數(shù)的集合（不允許0開(kāi)頭，且不考慮帶符號(hào)數(shù)） 解：根據(jù)題意，將偶整數(shù)結(jié)構(gòu)劃分如圖所示的三個(gè)部分： 最高位允許1～9，用非終結(jié)符B表示 中間位允許任意多位數(shù)字0～9，每位用非終結(jié)符D表示 最低位只允許出現(xiàn)0，2，4，6，8偶數(shù)，用A表示。,由于中間部分可以出現(xiàn)任意位，所以引入一個(gè) 非終結(jié)符M，它包括最高位和中間位。 所求文法G[N]: N::=A|MA M::=B|MD A::=0|2|4|6|8 B::=1|2||3|4|5|6|7|8|9 D::=0|B 類似問(wèn)題： 寫出帶符號(hào)奇整數(shù)集合的文法 寫出不能被5整除的無(wú)符號(hào)偶整數(shù)集合的文法 寫出能被5整除的帶符號(hào)偶整數(shù)集合的文法 ……,三、求句型的短語(yǔ)，簡(jiǎn)單短語(yǔ)及句柄以及判斷文法二義性的問(wèn)題 用語(yǔ)法樹(shù)作為分析的工具。 1. 求句型的短語(yǔ)，簡(jiǎn)單短語(yǔ)及句柄 句型的定義：對(duì)文法G[S]，若S=＊x，x∈(VN∪VT )*，則稱x為句型。 短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄總是針對(duì)某個(gè)句型而言的。 短語(yǔ)總是句型的某個(gè)子串，它對(duì)應(yīng)該句型語(yǔ)法樹(shù)中，子樹(shù)末端結(jié)點(diǎn)形成的符號(hào)串。 簡(jiǎn)單短語(yǔ)總是某個(gè)產(chǎn)生式右部，它對(duì)應(yīng)該句型語(yǔ)法樹(shù)中，簡(jiǎn)單子樹(shù)末端結(jié)點(diǎn)形成的符號(hào)串。 語(yǔ)法樹(shù)中最左邊的簡(jiǎn)單短語(yǔ)就是句柄。,例：有文法G[E]: E::=E+T|E-T|T T::=T*F|T/F|F F::=(E)|i 求句型(F+i)-T*(E-T)的短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄。 解：畫(huà)句型(F+i)-T*(E-T)的語(yǔ)法樹(shù)：,,E,,,,E,-,T,,T,,F,,,,(,+,E,T,F,),,,,E,T,F,,,,i,,,,,T,F,*,,,,(,),E,,,,E,－,T,短語(yǔ)：F, i, F+i , (F+i) , E-T, (E-T), T*(E-T), (F+i)－T*(E-T).。 簡(jiǎn)單短語(yǔ)：F, i , E-T 。文法中某產(chǎn)生式的右部 句柄：F,2. 文法二義性的判斷及消除 判斷：找出正確的句子，使之對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)。 例：已知文法G[N]： N::=SE|E S::=SD|D E::=0|2|4|6|8|10 D::=0|1|2|3|4|5|6|7|8|9 ⑴ 證明此文法具有二義性。 ⑵ 求此文法描述的語(yǔ)言 ⑶ 找出等價(jià)的無(wú)二義性文法,解： （1）證明： 如：句子10 所以G具有二義性。,（2）L是所有偶整數(shù)的集合 （3）等價(jià)無(wú)二義性文法 去掉E::=10 假定除0外，偶整數(shù)均不以0開(kāi)頭： G[N]： N::=SE|E S::=SD|D E::=0|2|4|6|8 D::=0|1|2|3|4|5|6|7|8|9,第2章 練習(xí)題,一，單選題 1.給定文法：A→bA|cc,下面的符號(hào)串為該文法句子的是（ ）。 ① cc ② bcbcc ③ bccbcc ④ bbbcc A. ①④ B. ①②③ C. ①③ D. ②③④ 2.文法G[Z]和語(yǔ)言L（ G[Z ]）存在如下關(guān)系（ ）。 A.一一對(duì)應(yīng)：一個(gè)文法對(duì)應(yīng)唯一的語(yǔ)言；并且反過(guò)來(lái)，一 個(gè)語(yǔ)言對(duì)應(yīng)唯一的文法。 B.一個(gè)語(yǔ)言對(duì)應(yīng)唯一的文法，反之則不然。 C.一個(gè)文法對(duì)應(yīng)唯一的語(yǔ)言，反之則不然。 D.若G為非二義性文法，則C是正確的；若G為二義性文法 ，則一個(gè)文法不對(duì)應(yīng)唯一的語(yǔ)言。,3. 有文法G[E]：E→－EE， E→－E，E →a|b|c 則文法的句子－－a－bc的所有可能的語(yǔ)法樹(shù)有（ ）棵。 A. 1 B. 2 C. 4 D. 3 4.有文法G[S]，如果S x，( x∈V )，則x是（ ）。 A. 句型 B. 句子 C. A和B D. 非A和B 二.構(gòu)造一個(gè)上下文無(wú)關(guān)文法G，使得： L(G)={ a b |m0},,*,T,2m,m,三.已知文法G[E]：E→ET+ | T T→TF* | F F→FP↑| P P→(E) | i 有句型TF*PP↑+，問(wèn)此句型的短語(yǔ)，簡(jiǎn)單短語(yǔ)和句柄是什么？（畫(huà)語(yǔ)法樹(shù)說(shuō)明）,四.請(qǐng)用語(yǔ)法樹(shù)證明文法G[s]是二義性的， G[s]： S→SS | (S) | ( )。 五.已知文法G[Z]：Z→AB A→aAb |ab B→Bc | ε 則，L(G[Z] )＝？,