第2章前后文無(wú)關(guān)文法和語(yǔ)言(2)

1、編譯原理第2章 前后文無(wú)關(guān)文法和語(yǔ)言計(jì)算機(jī)與軟件學(xué)院 陸克中12.1 文法及語(yǔ)言的表示2n程序設(shè)計(jì)語(yǔ)言的定義l漢語(yǔ)符合漢語(yǔ)語(yǔ)法的句子的全體l英語(yǔ)符合英語(yǔ)語(yǔ)法的句子的全體l程序設(shè)計(jì)語(yǔ)言符合該語(yǔ)言語(yǔ)法的程序的全體l如何表示或定義一種語(yǔ)言？枚舉法：當(dāng)一個(gè)語(yǔ)言?xún)H含有限個(gè)句子時(shí)，可把該語(yǔ)言中的全部句子一一列舉出來(lái)生成法(文法)：制定有限條規(guī)則，用來(lái)產(chǎn)生所要描述的語(yǔ)言之中的全部句子識(shí)別法(自動(dòng)機(jī))：建立一種裝置，此裝置以某一字母表上的所有符號(hào)串作為輸入，并檢驗(yàn)或識(shí)別這些符號(hào)串，當(dāng)一個(gè)符號(hào)串是此字母表上某給定語(yǔ)言中的句子時(shí)，就接受它，反之，則拒絕接受2.2.1 基本概念和術(shù)語(yǔ)3n字母表l由若干元素所組成的有

2、限非空集合l元素稱(chēng)為符號(hào)，字母表也稱(chēng)為符號(hào)集l通常，在一個(gè)字母表中，可用阿拉伯?dāng)?shù)字、大寫(xiě)及小寫(xiě)英文字母、各種算術(shù)運(yùn)算符、常用的標(biāo)點(diǎn)符號(hào)以及使用上認(rèn)為方便的其他符號(hào)來(lái)表示它的元素=0, 1, =a b, c, a, b, c, +, .2.2.1 基本概念和術(shù)語(yǔ)4n符號(hào)串l用字母表中的符號(hào)所組成的任何有限序列0, 1, 00, 01, 10,11, 000等都是字母表=01上的符號(hào)串a(chǎn), b, c, aa, ab, ac, ba, bb, bc, ca, cc, cb, aaa等都是=a b c上的符號(hào)串l一個(gè)字母表上全部符號(hào)串所組成的集合顯然為一無(wú)限集l在符號(hào)串中，符號(hào)是有順序的，順序不同，

3、代表不同的符號(hào)串a(chǎn)bbal空符號(hào)串: 不包含任何符號(hào)的符號(hào)串，記為l符號(hào)串長(zhǎng)度: 符號(hào)串中所含符號(hào)的個(gè)數(shù)|abc|=3, |=0l約定: 常用a, b, c, 及S, T, U, , X, Y, Z等表示符號(hào)，用t, u, , x, y, z等給符號(hào)串命名，用A, B, C等給符號(hào)串集合命名x=abc, y=11, A=a, b, c, B=00, 112.2.1 基本概念和術(shù)語(yǔ)5n符號(hào)串的前綴、后綴及子串lx的前綴: 從x的尾部刪去若干個(gè)(包括0個(gè))符號(hào)之后所余下的部分, a, ab, abc都是x=abc的前綴lx的后綴: 從x的頭部刪去若干個(gè)(包括0個(gè))符號(hào)之后所余下的部分, c, bc

4、, abc都是x=abc的后綴lx的真前綴(真后綴): x的前綴(后綴), 且不是x本身lx的子串: 從x中刪去它的一個(gè)前綴和一個(gè)后綴之后所余下的部分, a, b, c, d, ab, bc, cd, abc, bcd及abcd都是x=abcd的子串x的任何前綴和后綴都是x的子串，但其子串不一定是x的前綴或后綴和x本身既是x的前綴和后綴，也是它的子串l例: x=a+b*(c+d)的前綴、后綴和子串有哪些？2.2.1 基本概念和術(shù)語(yǔ)6n2.2.1 基本概念和術(shù)語(yǔ)7n2.2.1 基本概念和術(shù)語(yǔ)8n2.2.1 基本概念和術(shù)語(yǔ)9n例題: 定義標(biāo)識(shí)符是以小寫(xiě)字母打頭的、由小寫(xiě)字母或數(shù)字構(gòu)成的任意非空序列

5、，設(shè)A=a, b, z, B=0, 1, 9，將所有標(biāo)識(shí)符的集合表示為A和B的某種運(yùn)算形式lA(A+B)*2.2.2 文法和語(yǔ)言的形式定義10n從“產(chǎn)生語(yǔ)言”的角度出發(fā)，給出文法和語(yǔ)言的形式定義l例: 描述某些具有簡(jiǎn)單結(jié)構(gòu)的英語(yǔ)句子的語(yǔ)法規(guī)則：(1) 句子 主語(yǔ)短語(yǔ)動(dòng)詞短語(yǔ)(2) 主語(yǔ)短語(yǔ)the名詞(3) 動(dòng)詞短語(yǔ)動(dòng)詞賓語(yǔ)短語(yǔ)(4) 賓語(yǔ)短語(yǔ)冠詞名詞(5) 名詞monkey(6) 名詞banana(7) 動(dòng)詞ate(8) 動(dòng)詞has(9) 冠詞the(10)冠詞a2.2.2 文法和語(yǔ)言的形式定義11l句子the monkey ate a banana的推導(dǎo)序列：從語(yǔ)言最大的一個(gè)語(yǔ)法結(jié)構(gòu)句子出發(fā)

6、，反復(fù)用語(yǔ)法規(guī)則中右邊的符號(hào)串去替換它的左部符號(hào)推導(dǎo)步序所用的規(guī)則所得的符號(hào)串1(1)句子主語(yǔ)短語(yǔ)動(dòng)詞短語(yǔ)2(3) 主語(yǔ)短語(yǔ)動(dòng)詞賓語(yǔ)短語(yǔ)3(2) the名詞動(dòng)詞賓語(yǔ)短語(yǔ)4(4) the名詞動(dòng)詞冠詞名詞5(5) the monkey動(dòng)詞冠詞名詞6(7) the monkey ate冠詞名詞7(10) the monkey ate a名詞8(6) the monkey ate a banana2.2.2 文法和語(yǔ)言的形式定義12l文法的抽象定義一系列需要定義的語(yǔ)法結(jié)構(gòu)，稱(chēng)為非終結(jié)符號(hào)，用VN記之VN=句子,主語(yǔ)短語(yǔ),動(dòng)詞短語(yǔ),賓語(yǔ)短語(yǔ),名詞,動(dòng)詞,冠詞若干個(gè)基本符號(hào)，稱(chēng)為終結(jié)符號(hào)，用VT記之VT=

7、monkey, banana, ate, has, the, a在非終結(jié)符號(hào)中，有一個(gè)最終需定義的語(yǔ)法結(jié)構(gòu)句子，稱(chēng)為開(kāi)始符號(hào)句子一組規(guī)則，每一規(guī)則都是用符號(hào)鏈接起來(lái)的有序?qū)u，其中，U是一個(gè)非終結(jié)符號(hào)，u是一個(gè)由終結(jié)符號(hào)和(或)非終結(jié)符號(hào)所組成的符號(hào)串，稱(chēng)為產(chǎn)生式2.2.2 文法和語(yǔ)言的形式定義13n2.2.2 文法和語(yǔ)言的形式定義14l定義某文法時(shí)，習(xí)慣上只將其產(chǎn)生式寫(xiě)出，約定如下第一條產(chǎn)生式的左部是開(kāi)始符號(hào)，或用GS表示S是開(kāi)始符號(hào)用尖括號(hào)括起的符號(hào)串表示非終結(jié)符號(hào)用大寫(xiě)的拉丁字母表示非終結(jié)符號(hào)用小寫(xiě)的拉丁字母表示終結(jié)符號(hào)用希臘字母代表符號(hào)串左部相同的產(chǎn)生式A, A, 可以記為A | |

8、 ，符號(hào)“|”讀作“或”，, , 都稱(chēng)為A的侯選式2.2.2 文法和語(yǔ)言的形式定義15l例: 文法GS=(VN, VT, P, S)，其中：VN=S, VT=0, 1, P=S0S1, S01GS: S0S1 | 01l例: 文法G1S=(VN, VT, P, S), VN =標(biāo)識(shí)符, 字母, 數(shù)字, VT =a, b, c, , z, 0, 1, 2, , 9, P=標(biāo)識(shí)符字母, 標(biāo)識(shí)符標(biāo)識(shí)符字母, 標(biāo)識(shí)符標(biāo)識(shí)符數(shù)字, 字母a, , 字母z, 數(shù)字0, 數(shù)字9, S=標(biāo)識(shí)符G1S: SA | SA | SDAa | b | c | | zD0 | 1 | 2 | | 92.2.2 文法和語(yǔ)言

9、的形式定義16n2.2.2 文法和語(yǔ)言的形式定義17n2.2.2 文法和語(yǔ)言的形式定義18n2.2.2 文法和語(yǔ)言的形式定義19n2.2.2 文法和語(yǔ)言的形式定義20n2.2.2 文法和語(yǔ)言的形式定義21lL(G)中的每個(gè)符號(hào)串確實(shí)能被文法G生成有了語(yǔ)言的要求，也可以為該語(yǔ)言設(shè)計(jì)文法例: 若語(yǔ)言由0、1符號(hào)串組成，且串中0和1的個(gè)數(shù)相同，構(gòu)造其文法A: 0=1的符號(hào)串B: 0=1-1的符號(hào)串C: 0=1+1的符號(hào)串GA:A0B | 1CB1 | 1A | 0BBC0 | 0A | 1CC2.2.2 文法和語(yǔ)言的形式定義22n2.2.2 文法和語(yǔ)言的形式定義23n例題: 試分別構(gòu)造產(chǎn)生下列語(yǔ)言的

10、文法(1) an+1bn | n0=anabn | n0, G: SaSb | a(2) a2nb3n | n0=(aa)n(bbb)n | n0, G: SaaSbbb | (3) a2n+1cmb3n+2 | n0, m1=(aa)nacmbb(bbb)n | n0, m1, G: SaaSbbb | aCbb, CcC | c(4) ancmbn | n0, m1 andmbn | n0, m0 G: SaSb | C | D, CcC | c, DdD | 2.2.2 文法和語(yǔ)言的形式定義24n2.2.2 文法和語(yǔ)言的形式定義25n文法的等價(jià)l若L(G1)=L(G2)，則稱(chēng)文法G1和G

11、2是等價(jià)的l例: 文法G1A: A0R A01 RA1G2S: S0S1 S01所定義的語(yǔ)言都是0n1n，兩文法等價(jià)l引理引理2.1 G=(VN, VT, P, S)，AB，B1, B2, Bn是P中的全部B-產(chǎn)生式，又設(shè)G1=(VN, VT, P1, S)是這樣的方法，其中，P1是從P中刪去AB并添加產(chǎn)生式A1, A2, An所組成的集合，則L(G1)=L(G)2.3 句型的分析26n構(gòu)造一種算法，用以判斷所給的符號(hào)串是否為某一文法的句型(或句子)n對(duì)于一個(gè)編譯程序來(lái)說(shuō)，不論在詞法分析階段，還是在語(yǔ)法分析階段，都存在句型分析的問(wèn)題2.3.1 規(guī)范推導(dǎo)與規(guī)范歸約27n最左推導(dǎo)和最右推導(dǎo)l對(duì)于一

12、個(gè)推導(dǎo)序列中的每一直接推導(dǎo)，被替換的總是當(dāng)前符號(hào)串中的最左(右)非終結(jié)符號(hào)l常把最右推導(dǎo)稱(chēng)為規(guī)范推導(dǎo)l每一句子都必定有最左和最右推導(dǎo)，但對(duì)一句型來(lái)說(shuō)則不盡然EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iT*i+Tn左(右)句型l由最左(右)推導(dǎo)推出的句型l常把右句型稱(chēng)為規(guī)范句型2.3.1 規(guī)范推導(dǎo)與規(guī)范歸約28n自頂向下的語(yǔ)法分析l試圖為w建立一個(gè)從G的開(kāi)始符號(hào)S到w的最左推導(dǎo)l若當(dāng)前被替換的非終結(jié)符號(hào)U是由若干個(gè)候選式

13、定義的，即有U1 | 2 | | n，如何選用候選式帶回溯：逐個(gè)用這些候選式進(jìn)行試探，以期獲得正確的選擇效率很低不帶回溯：在第4章中介紹l例:EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i2.3.1 規(guī)范推導(dǎo)與規(guī)范歸約29n2.3.2 語(yǔ)法樹(shù)和二義性30n樹(shù)的性質(zhì)l有且僅有一個(gè)沒(méi)有任何前驅(qū)的結(jié)點(diǎn)，稱(chēng)之為“根”l除根之外，每一結(jié)點(diǎn)都恰好有一個(gè)直接前驅(qū)（父結(jié)點(diǎn)）l對(duì)于每一結(jié)點(diǎn)，都有唯一一條從根到此結(jié)點(diǎn)的通路l若一個(gè)結(jié)點(diǎn)有多個(gè)直接后繼（子結(jié)點(diǎn)），則按自左向右的順序進(jìn)行排序l沒(méi)有任何后繼的節(jié)點(diǎn)稱(chēng)為樹(shù)的末端節(jié)點(diǎn)（葉子）l由某個(gè)結(jié)點(diǎn)ni及其全部后繼所組成的結(jié)點(diǎn)集合Di構(gòu)成了以ni為根的

14、子樹(shù)Til若一個(gè)子樹(shù)的根只有直接后繼，則稱(chēng)為直接子樹(shù)2.3.2 語(yǔ)法樹(shù)和二義性31n設(shè)G=(VN, VT, P, S)為一文法，則G的一棵語(yǔ)法樹(shù)滿足：l每一結(jié)點(diǎn)均有一標(biāo)記，此標(biāo)記為VN VT中的一個(gè)符號(hào)l樹(shù)的根結(jié)點(diǎn)以文法的開(kāi)始符號(hào)S標(biāo)記l若一個(gè)結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號(hào)l若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有k個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為X1, X2, Xk，則AX1X2Xk必然是G的一個(gè)產(chǎn)生式EE+TTT *FFFiiiEE+TE2.3.2 語(yǔ)法樹(shù)和二義性32n由推導(dǎo)構(gòu)造語(yǔ)法樹(shù)l自頂向下的構(gòu)造：把開(kāi)始符號(hào)作為語(yǔ)法樹(shù)的根，在各步推導(dǎo)中，每當(dāng)句型中的一個(gè)

15、非終結(jié)符號(hào)被某一產(chǎn)生式的一個(gè)候選式替換時(shí)，就從此非終結(jié)符號(hào)所標(biāo)記的結(jié)點(diǎn)出發(fā)，向下建立一個(gè)直接子樹(shù)，此子樹(shù)的末端結(jié)點(diǎn)標(biāo)以該候選式中的各個(gè)符號(hào)l例: EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE + TTT * FFFiiiEE + TTT * FFFiiEE + TTT * FFFiEE + TTT * FFiEE + TTFiEE + TTFEE + TTEE + T2.3.2 語(yǔ)法樹(shù)和二義性33nE + TTT * FFFiii+*Fiii+T*FiiiE +T*FiiiE +T*FFiiiE +TT *FFiiiE +TT * FFFiiiEE + TTT * F

16、FFiii2.3.2 語(yǔ)法樹(shù)和二義性34n語(yǔ)法樹(shù)與句型l對(duì)于任一句型的推導(dǎo)序列，總能為它構(gòu)造一顆語(yǔ)法樹(shù)，此末端結(jié)點(diǎn)從左到右依次排列起來(lái)，也就組成了所給的句型l反之，當(dāng)給定一顆語(yǔ)法樹(shù)時(shí)，把它的末端結(jié)點(diǎn)從左到右排列起來(lái)所組成的符號(hào)串也必然是一個(gè)句型l語(yǔ)法樹(shù)表明了在推導(dǎo)過(guò)程中使用了哪些產(chǎn)生式和使用在哪個(gè)非終結(jié)符號(hào)上，但它并沒(méi)有表明使用產(chǎn)生式的順序l例:EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iEE+TTT *FFFiii2

17、.3.2 語(yǔ)法樹(shù)和二義性35n文法的二義性l如果一個(gè)文法存在某個(gè)句子w，與w相應(yīng)的語(yǔ)法樹(shù)不止一個(gè)，則稱(chēng)這個(gè)文法為有二義性的文法。如果一個(gè)文法所產(chǎn)生的每一個(gè)句子都僅有一顆語(yǔ)法樹(shù)，則稱(chēng)此文法為無(wú)二義性的l例: 文法G3E: EE+E | E*E | (E) | i，句子i+i*i有兩個(gè)不同的最右推導(dǎo)：EE+EE+E*EE+E*iE+i*ii+i*iEE*EE*iE+E*iE+i*ii*i+iEE+EiE *EiiEE*EiE +Eii2.3.2 語(yǔ)法樹(shù)和二義性36n文法的二義性l例: 在PASCAL語(yǔ)言中將if語(yǔ)句定義為Cif B then CCif B then C else CCS句子if B

18、1 then if B2 then S1 else S2存在兩棵不同的語(yǔ)法樹(shù)CifB1thenCifB2thenCCelseS1S2CifB1thenCifB2thenCCelseS1S22.3.2 語(yǔ)法樹(shù)和二義性37n二義性文法的問(wèn)題l當(dāng)編譯程序?qū)渥拥慕Y(jié)構(gòu)進(jìn)行語(yǔ)法分析時(shí)，就可能會(huì)產(chǎn)生兩種甚至更多種不同的理解l語(yǔ)法結(jié)構(gòu)上的不確定性，將必然會(huì)導(dǎo)致語(yǔ)義處理上的不確定性l就會(huì)出現(xiàn)對(duì)同一源程序符號(hào)串在目標(biāo)代碼生成上的不確定性l前后文無(wú)關(guān)文法的二義性是不可判定的EE+EiE *EiiEE*EiE +Eii2.3.2 語(yǔ)法樹(shù)和二義性38n二義性的消除l附加一些約定 在復(fù)合if 語(yǔ)句中，else子句總是屬

19、于最靠近的、尚無(wú)else子句的那個(gè)if語(yǔ)句l構(gòu)造一個(gè)等價(jià)的無(wú)二義性文法L(G3E: EE+E | E*E | (E) | i)=L(G2E: EE+T | T, TT*F | F, F(E) | i)n先天二義性的語(yǔ)言l用來(lái)定義該語(yǔ)言的一切文法都是二義性的l例: L=anbncmdm | n1, m1 anbmcmdn | n1, m1l前后文無(wú)關(guān)語(yǔ)言的先天二義性是不可判定的2.3.3 短語(yǔ)和句柄39n語(yǔ)法樹(shù)與短語(yǔ)和句柄l語(yǔ)法樹(shù)的句型為 ，子樹(shù)根為A，子樹(shù)的末端結(jié)點(diǎn)自左至右排列所形成的符號(hào)串為l短語(yǔ)：是句型相對(duì)A的一個(gè)短語(yǔ)l直接短語(yǔ)：若此子樹(shù)為直接子樹(shù)，則是句型相對(duì)于產(chǎn)生式A的直接短語(yǔ)l句柄：若此子樹(shù)為最左直接子樹(shù)，則是句型的句柄EE(1)+T(1)E(2)+T(2)T(3)*F(2)F(1)i2.3.3 短語(yǔ)和句柄40nEE(1)+T(1)E(2)+T(2)T(3)*F(2)F(1)i2.3.3 短語(yǔ)和句柄41nEE+TE+TT *FFiTFiiF