《形式語言與文法》PPT課件.ppt

《《形式語言與文法》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《形式語言與文法》PPT課件.ppt（93頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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