編譯原理 文法和語言.ppt

《編譯原理 文法和語言.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理 文法和語言.ppt（59頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,第三章文法和語言,語言是一個(gè)記號(hào)系統(tǒng)，完整的定義包括語法和語義兩方面。語法是一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序。文法就是闡明語法的一個(gè)重要的形式工具。語義包括靜態(tài)語義和動(dòng)態(tài)語義，闡明語義要比語法困難的多。 本章主要討論文法和語言的概念，上下文無關(guān)文法及其句型的分析。,2,本章內(nèi)容,3.1 文法的直觀概念 3.2 符號(hào)和符號(hào)串 3.3 文法和語言的形式定義 3.4 文法的類型 3.5 上下文無關(guān)文法及其語法樹 3.6 句型的分析 3.7 有關(guān)文法實(shí)用中的一些說明 3.8 典型例題及解答,3,3.1 文法的直觀概念,如何來描述一種語言？ 如果語言是有窮的(只含有有窮多個(gè)句子)，可以將

2、句子逐一列出來表示； 如果語言是無窮的，語言的有窮表示有兩個(gè)途經(jīng): 生成方式(文法):語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。 識(shí)別方式(自動(dòng)機(jī)):用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去。 參見課本句子組成的實(shí)例。,4,3.2 符號(hào)和符號(hào)串,1、字母表,字母表是符號(hào)的非空有窮集合。任何程序語言都有自己的字母表，例如: 1.計(jì)算機(jī)語言：由符號(hào)“0”和“1”組成的字母表, =0，1 2. ASCII字符集； 3. Pascal字母表為： =AZ, az, 09, +, -, *, /, ,:,

3、,, ; ，.， , (, ), , , , ,5,3.2 符號(hào)和符號(hào)串,2、符號(hào)串,一. 符號(hào)串的定義 (1)是上的一個(gè)符號(hào)串。 (2)若x是上的符號(hào)串，而a是的元素,則xa是 上的符號(hào)串。 (3)y是上的符號(hào)串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。 由字母表中的符號(hào)所組成的的任何有窮序列被稱之為該字母表上的符號(hào)串,也稱作字。,6,3.2 符號(hào)和符號(hào)串,二 術(shù)語 設(shè)s是符號(hào)串 前綴: 移走s的尾部的零個(gè)或多于零個(gè)符號(hào) 后綴: 刪去s的頭部的零個(gè)或多于零個(gè)符號(hào) 子串: 從s中刪去一個(gè)前綴和一個(gè)后綴 子序列: 從s中刪去零個(gè)或多于零個(gè)符號(hào)(這些符號(hào)不要求是連續(xù)的） 逆轉(zhuǎn): 將s中的符號(hào)按相反次序?qū)?/p>

4、出而得到的符號(hào)串。 長度: 是該符號(hào)串中的符號(hào)的數(shù)目。例|aab|=3,||=0。,7,例 ：符號(hào)串s=banana 前綴：,b,ba,ban,bana,banan,banana 后綴：banana,anana,nana,ana,na,a, 子串: banana,anana,banan,anan,, 真前綴，真后綴，真子串: xsx 子序列: baa(這些符號(hào)不要求是連續(xù)的） 逆轉(zhuǎn)：ananab 長度：banana=6,3.2 符號(hào)和符號(hào)串,8,三、符號(hào)串的運(yùn)算 1.連接：設(shè)x和y是符號(hào)串，它們的連接 xy是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串。例如，x=ba,y=nana,xy=bana

5、na. 2.方冪：x0=; x1=x; x2=xx; ; xn=xn-1x; 例: x=ba 則 x1= ba; x2=baba; x3=bababa;,3.2 符號(hào)和符號(hào)串,9,四. 符號(hào)串集合(語言）的運(yùn)算 設(shè)L和M是兩個(gè)符號(hào)串集合，則 1.合并：LMs|sL or sM 2.連接：LM st|sL and tM 3.方冪： L0=， L1L， L2LL, ..., LnLn-1L 4. 語言L的閉包，記作L*， L*Li(i=0) =L0L1L2L3 5語言L的正閉包，記作L+（L+L L*） L+Li(i =1) =L1L2L3L4,3.2 符號(hào)和符號(hào)串,10,例如：L=

6、AZ,az D=09 1LD=AZ,az ,09 2LD是由所有用一個(gè)字母后跟一個(gè)數(shù)字組成的符號(hào)串所構(gòu)成的集合。 3L4是由所有的四個(gè)字母的符號(hào)串構(gòu)的集合。 4L（LD)* 是由所有的字母打頭的字母和數(shù)字組成的符號(hào)串所構(gòu)成的集合. 5D+是由所有的長度大于等于1的數(shù)字串所構(gòu)成的集合.,3.2 符號(hào)和符號(hào)串,11,文法的定義 推導(dǎo)的概念 句型、句子和語言的定義,3. 3 文法和語言的形式定義,12,文法定義,文法G 定義為四元組(VN，VT，P，S)，其中VN :非終結(jié)符號(hào)集；VT :終結(jié)符號(hào)集；P: 規(guī)則的集合；并且VN，VT和P是非空有窮集。S:稱作開始符(識(shí)別符)，是一個(gè)非終結(jié)符，它至少

7、要在一條產(chǎn)生式中作為左部出現(xiàn)。 注：VN和VT不含公共的元素，即VN VT = ，用V表示VN VT ，稱為文法G的字母表 規(guī)則(重寫規(guī)則、產(chǎn)生式或生成式)，是形如的(,)有序?qū)?其中是字母表V的正閉包V+中的一個(gè)符號(hào)，是V*中的一個(gè)符號(hào)。 稱為規(guī)則的左部， 稱作規(guī)則的右部。,13,文法的定義,例: 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號(hào),例: 文法G=（VN，VT，P，S） VN =標(biāo)識(shí)符，字母，數(shù)字 VT =a,b,c,x,y,z,0,1,,9 P= a z 0 9 S=,15,元符號(hào)

8、: | 一般不用將文法G的四元組顯式的寫出來，只寫出產(chǎn)生式即可，并約定第一條產(chǎn)生式的左部為識(shí)別符。習(xí)慣上大寫字母表示非終結(jié)符，小寫字母表示終結(jié)符，有時(shí)也將G寫為GS,(1) G：SaAb Aab AaAb A,(2) GS：Aab AaAb A SaSb (3) GS: Aab|aAb| SaSb,文法的寫法,16,推導(dǎo)的定義,直接推導(dǎo)“” 是文法G的產(chǎn)生式,若有v,w滿足v=,w=,其中V*,V*,則稱v直接推導(dǎo)到w,記作 v w 也稱w直接歸約到v 例：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111

9、S 0S1,17,推導(dǎo)的定義,例： . ( . ) . . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A) VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A),18,推導(dǎo)的定義,若存在v =w0 w1 ... wn=w,(n0) 則記為v +w，稱作v推導(dǎo)出w，或w歸約到v 若有v =+w 或 v=w， 則記為v =* w,19,例： G： S0S1， S01 0S1 00S11

10、00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S11,20,句型、句子的定義,句型 有文法G，若S =*x，則稱x是文法G的句型。 句子 有文法G，若S =*x，且xVT*，則稱x是文法G的句子。 例： G：S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01,21,句型、句子,例：GE： EE+T|T TT*F|F F(

11、E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子：用符號(hào)a，+，*，(和)構(gòu)成的算術(shù)表達(dá)式,22,(文法生成的)語言的定義,由文法G生成的語言記為L(G),它是文法G的一切句子的集合: L(G)=x|S =* x,其中S為文法的開始符號(hào),x VT* 例：G: S0S1， S01 L(G)=0n1n|n1,例 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L(G)= anbnen | n1 G生成的每個(gè)串都在L(G)中 L(G)中的每個(gè)串確實(shí)能被G生成 分析參見課

12、本P37.,24,文法的等價(jià),若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。 例：文法G1A：A0R 與 G2S：S0S1 等價(jià) A01 S01 RA1,25,3.4 文法的類型,通過對(duì)產(chǎn)生式施加不同的限制，文法可分為以下四類： 0型文法：對(duì)任一產(chǎn)生式，都有(VNVT)+， (VNVT)*。 0型文法的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，且任何0型語言都是遞歸可枚舉的。 0型文法描述的語言為0型語言，用L0表示。 例如 ： aSbcAd,26,3.4 文法的類型,1型文法：對(duì)任一產(chǎn)生式，都有||||， 僅僅 S除外。 1型文法又稱作上下文有關(guān)文法（cont

13、ext-sensitive)： 其產(chǎn)生式的形式為1A212，即只有A出現(xiàn)在1和2的上下文中時(shí)，才允許取代A。其識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。 該文法描述的語言為1型語言或上下文有關(guān)語言,用L1表示。 例如：aUbaABBaab,27,3.4 文法的類型,2型文法：對(duì)任一產(chǎn)生式,都有VN , (VNVT)* 2型文法又稱作上下文無關(guān)文法（context-free)： 該文法相當(dāng)于對(duì)1型文法中的規(guī)則形式加以限制，即要求1和2必須為空。 2型文法描述的語言為2型語言或上下文無關(guān)語言，用L2表示。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。,28,3.4 文法的類型,例：2型（上下文無關(guān)）文法 文法GS：SAB

14、 ABS|0 BSA|1,29,3型文法：任一產(chǎn)生式的形式都為AaB或Aa，其中AVN ，BVN ，aVT* 3型文法又叫正規(guī)文法，產(chǎn)生的語言為3型語言（正規(guī)語言），是有窮自動(dòng)機(jī)所接受的集合。 高級(jí)程序設(shè)計(jì)語言的單詞符號(hào)，如標(biāo)識(shí)符、無符號(hào)整數(shù)等都是采用3型文法來描述的。,3.4 文法的類型,30,3.4 文法的類型,GS： S0A|1B|0 A0A|1B|0S B1B|1|0,GI：I lT I l T lT T dT T l T d,例： 3型文法,31,,3.4 文法的類型,0型文法,四類文法之間的逐級(jí)“包含”關(guān)系,3型文法,32,3.5 上下文無關(guān)文法及其語法樹,上下文無關(guān)文法有足夠

15、的能力描述程序設(shè)計(jì)語言的語法結(jié)構(gòu) 實(shí)例參見課本P39-40 例3.6（描述表達(dá)式及各種語句） 語法樹：是描述上下文無關(guān)文法句型推導(dǎo)的直觀工具。,33,語法樹的定義 設(shè)G=( VN,VT,P,S)為一上下文無關(guān)文法，若一棵樹滿足下列4個(gè)條件，則此樹為G的語法樹(推導(dǎo)樹)(派生樹） 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，則肯定AVN 4. 如果結(jié)點(diǎn)n的直接子孫從左到右依次為n1，n2，，nk，并且標(biāo)記分別為A1，A2，，Ak，那么AA1A2，，Ak一定是P中的一個(gè)產(chǎn)生式,3.5 上下文無關(guān)文法及其語法樹,3

16、4,語法樹的結(jié)果： 從左到右讀出葉子的標(biāo)記而構(gòu)成的符號(hào)串即為語法樹的結(jié)果,3.5 上下文無關(guān)文法及其語法樹,構(gòu)造句型aabbaa的語法樹,S a A S S b A a a b a,,,,,,,,,,,例: GS: 1) SaAS 2) ASbA 3) ASS 4) Sa 5) Aba,35,句型aabbaa的可能推導(dǎo)序列,例: GS: 1) SaAS 2) ASbA 3) ASS 4) Sa 5) Aba,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASa

17、SbAaaabAaaabbaa,3.5 上下文無關(guān)文法及其語法樹,36,規(guī)范推導(dǎo)、規(guī)范句型： 最左（最右）推導(dǎo)：在推導(dǎo)的任何一步，其中，是句型，都是對(duì)中的最左（右）非終結(jié)符進(jìn)行替換 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型 給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹(推導(dǎo)樹) 定理： G為上下文無關(guān)文法，對(duì)于，有S =* ，當(dāng)且僅當(dāng)文法G有以為結(jié)果的一棵語法樹(推導(dǎo)樹),3.5 上下文無關(guān)文法及其語法樹,37,一棵語法樹表示了一個(gè)句型的種種可能的(但未必是所有的)推導(dǎo)過程，包括最左(最右)推導(dǎo)。 一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語法樹呢? 一個(gè)句型

18、是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?,3.5 上下文無關(guān)文法及其語法樹,38,例：GE:E i E E+E E E*E E (E),E E + E E * E i i i,,,,,,,,,,E E * E i E + E i i,,,,,,,,,,句子 i*i+i 有兩種不同的最左推導(dǎo)： 推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i 推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i,3.5 上下文無關(guān)文法及其語法樹,39,若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的 或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這

19、個(gè)文法是二義的 判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無關(guān)語言，這兩個(gè)問題是遞歸不可解的，但可以為無二義性尋找一組充分條件,文法的二義性和語言的二義性,3.5 上下文無關(guān)文法及其語法樹,40,文法的二義性和語言的二義性是不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G,其中G是二義的,但有L(G)=L(G)，也就是說，這兩個(gè)文法所產(chǎn)生的語言是相同的。 如果產(chǎn)生上下文無關(guān)語言的每一個(gè)文法都是二義的，則說此語言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語言來說，常常希望它的文法是無二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語句的分析是唯一的。,文法的二義性和語言的二義性,3.5 上下文無關(guān)文法及其語

20、法樹,41,GE: E i E E+E E E*E E (E),文法的二義性和語言的二義性,3.5 上下文無關(guān)文法及其語法樹,二義文法改造為無二義文法,GE：E T|E+T T F|T*F F （E）|i,規(guī)定算符優(yōu)先性和結(jié)合性,42,3.6 （上下文無關(guān)文法）句型的分析,句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程。 在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。 從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。(以后介紹的算法均屬此類）,43,從左到右的句型分析算法分

21、類： 自上而下分析法：從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)，或者說，為輸入串尋找一個(gè)最左推導(dǎo)。 自下而上分析法：從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。,3.6 句型的分析,44,從語法樹的構(gòu)造過程來理解兩種句型分析方法 1. 自上而下方法 從文法符號(hào)開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的結(jié)果正好是輸入符號(hào)串 2.自下而上方法 從輸入符號(hào)串開始，以它做為語法樹的結(jié)果，自底向上的構(gòu)造語法樹,3.6 句型的分析,45,1. 自上而下的語法分析,例：文法G： S cAd A ab A a識(shí)別輸入串w=cabd

22、是否為該文法的句子,SSS cAdcAd a b 推導(dǎo)過程：S cAd cAd cabd,,,,,,,,,3.6 句型的分析,46,例：文法G： S cAd A ab A a識(shí)別輸入串w=cabd是否該文法的句子,S AA c a b d c a b d c a b d 歸約過程構(gòu)造的推導(dǎo)： cAd cabd S cAd,,,,,,,,1. 自下而上的語法分析,3.6 句型的分析,47,自上而下的語法分析(1)S cAd (2) A ab (3) A a 識(shí)別輸入串w=cad是否為該文法的句子,串的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符

23、號(hào)卻不能與下一葉子結(jié)點(diǎn)d匹配。宣告分析失敗(意味著，識(shí)別程序不能為串cad構(gòu)造語法樹，即cad不是句子) :: 顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。,S c A d a b,,,,,,這時(shí)應(yīng)回溯，把A為根的子樹剪掉，掃描過的輸入串中的a吐出來,再試探用產(chǎn)生式（3）,若S cAd 后選擇(2)擴(kuò)展A，S cAd cabd 那將會(huì)？,48,自下而上的語法分析(1)S cAd (2) A ab (3)A a識(shí)別輸入串w=cabd是否為該文法的句子,對(duì)串cabd的分析中，如果不用產(chǎn)生式(2的ab，而是用產(chǎn)生式(3) 將a歸約到了A，則在cAbd 中無法找到一個(gè)可歸約串

24、了，最終就達(dá)不到歸約到S的結(jié)果，因而也無從知道cabd是一個(gè)句子,c a b d c A b d a,,49,句型分析的有關(guān)問題,1）在自上而下的分析方法中選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 假定要被代換的最左非終結(jié)符號(hào)是B，且有n條規(guī)則：BA1|A2||An，那么如何確定用哪個(gè)右部去替代B？（回溯） 2）在自下而上的分析方法中如何識(shí)別可歸約的串？ 在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào)，該子串稱為“可歸約串”。在規(guī)范歸約中該可歸約串稱為句柄。,50,句柄及其相關(guān)概念,1. 短語：xuy是文法GS的一句型,如果有 S=*xUy 且U=+u ,其中UVN ,

25、uV+，則稱u是句型xuy相對(duì)于非終結(jié)符號(hào)U的短語。 短語是在句型的推導(dǎo)過程中能由某個(gè)非終結(jié)符號(hào)推導(dǎo)出的子串。 2. 直接短語（簡單短語）：若有 S=*xUy 且U=u，則稱u是句型xuy相對(duì)于非終結(jié)符號(hào)U的直接短語。 直接短語則是能由某個(gè)非終結(jié)符號(hào)直接推導(dǎo)出的子串。 3. 句柄：任一句型的最左直接短語稱為該句型句柄。,51,句柄及其相關(guān)概念,例:寫出GE中句型 i*i+i的所有短語、簡單短語和句柄。 GE: E T|E+T T F|T*F F （E）|i,解：首先構(gòu)造出句型 i1*i2+i3對(duì)應(yīng)的語法樹因?yàn)镕=i，所以i1,i2,i3分別是句型i1*i2+i3相對(duì)于規(guī)則Fi的直接

26、短語，而句柄是最左側(cè)的直接短語即i1。因?yàn)門=+i1,所以i1是句型i1*i2+i3相對(duì)于T的短語，i3也是同樣情況。,52,句柄及其相關(guān)概念,注意：并不是句型中的任意子序列都可構(gòu)成短語。如上例中的 i2+i3.,因?yàn)門=+i1*i2，所以i1*i2是句型i1*i2+i3相對(duì)于T的短語。 因?yàn)镋=+i1*i2，所以i1*i2是句型i1*i2+i3相對(duì)于E的短語。 因?yàn)镋=+ i1*i2+i3 ，所以i1*i2+i3是句型i1*i2+i3相對(duì)于E的短語。 綜上：i1，i2，i3， i1*i2， i1*i2+i3均是句型i1*i2+i3的短語，其中i1，i2，i3為直接短語， i1為句柄。,53,

27、直接短語：a2,b2a3,a4 短語：a2,b2a3,a4,a2b1b2a3,a1a2b1b2a3a4 句柄：a2,給出句型aabbaa的所有短語、直接短語和句柄,S a1 A S S b1 A a4 a2 b2 a3,,,,,,,,,,,句柄及其相關(guān)概念,例: GS: 1) SaAS 2) ASbA 3) ASS 4) Sa 5) Aba,54,3.7 有關(guān)文法實(shí)用中的一些說明,對(duì)文法進(jìn)行限制（目的是化簡文法） 文法中不含有有害規(guī)則和多余規(guī)則 有害規(guī)則：形如UU的產(chǎn)生式。會(huì)引起文法的二義性 多余規(guī)則：指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)則，

28、 它們以不可到達(dá)和不可終止兩種情況出現(xiàn) 1) 文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達(dá)。 2) 文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串，該非終結(jié)符稱為不可終止。,55,對(duì)于文法GS，為了保證任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個(gè)條件：1. A必須在某句型中出現(xiàn) 即有S =* A，其中，屬于V* 2. 必須能夠從A推出終結(jié)符號(hào)串t來 即A =* t，其中tVT*,3.7 有關(guān)文法實(shí)用中的一些說明,56,化簡文法 例：GS ： 1) SBe 2) BCe 3) BAf 4) AAe 5) Ae 6) CCf

29、7) Df,3.7 有關(guān)文法實(shí)用中的一些說明,D為不可到達(dá),C為不可終止,產(chǎn)生式 2）6）7）為多余規(guī)則應(yīng)去掉。,57,對(duì)文法的擴(kuò)充：上下文無關(guān)文法中的規(guī)則,本書所給上下文無關(guān)文法的定義中，某些規(guī)則可以具有形式A，稱這種規(guī)則為規(guī)則。有些教材對(duì)此進(jìn)行了限制，但這不牽扯到本質(zhì)的問題。 兩種定義的唯一差別是句子在不在語言中 如果語言L有一個(gè)有窮的描述，則L1=L也同樣有一個(gè)有窮的描述，并且可以證明，若L是上下文有關(guān)語言、上下文無關(guān)語言或正規(guī)語言，則L分別是上下文有關(guān)語言、上下文無關(guān)語言和正規(guī)語言。,3.7 有關(guān)文法實(shí)用中的一些說明,58,3.8 典型例題,例1：證明文法GE是二義的。P46 例2：給出下述語言的上下文無關(guān)文法 L1=anb2ncm|n,m=0 L2=anbmc2m|n,m=0 解：要產(chǎn)生形如anb2ncm的符號(hào)串，可分別產(chǎn)生形如 anb2n和cm的串，所以L1對(duì)應(yīng)的文法為： SAB A |aAbb B |cB,同理可得L1對(duì)應(yīng)的文法為： SAB A |aA B |bBcc,59,作業(yè),課本 P48: 1;2;3;5 P48-49: 6.(1)(3)(5);11;13,