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

1、第3章上 形式語(yǔ)言簡(jiǎn)介,3.1 文法和語(yǔ)言 3.2 推導(dǎo)與語(yǔ)法樹,3.1 文法和語(yǔ)言,文法是程序語(yǔ)言的生成系統(tǒng)，而自動(dòng)機(jī)則是程序語(yǔ)言的識(shí)別系統(tǒng)；用文法可以精確地定義一個(gè)語(yǔ)言，并依據(jù)該文法構(gòu)造出識(shí)別這個(gè)語(yǔ)言的自動(dòng)機(jī)。因此，文法對(duì)程序語(yǔ)言和編譯程序的構(gòu)造具有重要意義，如程序語(yǔ)言的詞法可用正規(guī)文法描述，語(yǔ)法可用上下文無(wú)關(guān)文法描述，而語(yǔ)義則要借助于上下文有關(guān)文法描述。,3.1.1 文法和語(yǔ)言的概念 1語(yǔ)言 通常我們用表示字母表，字母表中的每個(gè)元素稱為字符或符號(hào)。不同語(yǔ)言的字母表可能是不同的，程序語(yǔ)言的字母表通常是ASCII字符集。由字母表中的字符所組成的有窮系列稱為上的字符串或字，字母表上的所有

2、字符串(包括空串)組成的集合用*表示。那么，對(duì)字母表來(lái)說(shuō)，*上的任意一個(gè)子集都稱為上的一個(gè)語(yǔ)言，記為L(zhǎng)(L*)，該語(yǔ)言的每一個(gè)字符串稱為語(yǔ)言L的一個(gè)語(yǔ)句或句子。,每一個(gè)形式語(yǔ)言都是某字母表上符號(hào)串的一個(gè)集合，反之字母表上符號(hào)串的一個(gè)集合可定義為一個(gè)形式語(yǔ)言。例如，C語(yǔ)言是其基本符號(hào)字母表上符號(hào)串的集合，而每個(gè)C語(yǔ)言程序是基本符號(hào)的符號(hào)串。再如，假定=a,b,c，則 L1=a,b,c L2=a,aa,ab L3=c,cc 均可表示字母表=a,b,c上的一個(gè)形式語(yǔ)言。,當(dāng)一語(yǔ)言是有窮集合時(shí)，可用上述枚舉方法來(lái)表示語(yǔ)言。但如果語(yǔ)言是無(wú)窮集合，那就無(wú)法用這種枚舉方法。我們要設(shè)計(jì)出表示

3、無(wú)窮集合的強(qiáng)有力的工具。文法就是這樣一種工具。 設(shè)=a,b，則根據(jù)定義+表示a和b的所有可能的符號(hào)串的集合。下面用A表示+則A可表示成： A a A b A Aa A Ab 其中，符號(hào)“”讀作“生成”。,顯然，由A生成的符號(hào)串都屬于+，另一方面，可用歸納法證明+ A，因此有A= +。 考慮=a上的符號(hào)串集合：A=a2n|n1 顯然aa A；如果yaa A，因此，A可按下法構(gòu)造： A aa A Aaa 考慮=a,b上的符號(hào)串集合：A=abna|n 1 顯然A可表示為 A=

4、aBa B=bn|n 1 其中B是我們會(huì)構(gòu)造的，于是可以寫出：, A aBa B b B Bb 在這里A是所要構(gòu)造的，B是輔助集合。這樣A aBa可理解為A可生成aBa。若用“ ”表示“推出”，則我們有 A aBa aBa aBba aBba aBbba aBbba abbba 于是得出：A推出符號(hào)串a(chǎn)bbba，即abbba A。,,,,,,2文法 文法通常表示成四元組G=(VT，VN，S，)，其中： (1)VT為終結(jié)符號(hào)集，這是一個(gè)非空有限集，它的每個(gè)元素

5、稱為終結(jié)符號(hào)； (2)VN為非終結(jié)符集，它也是一個(gè)非空有限集，其每個(gè)元素稱為非終結(jié)符號(hào)，且有VTVN=； (3)S為一文法開始符，是一個(gè)特殊的非終結(jié)符號(hào)，即SVN；,(4)是產(chǎn)生式的非空有限集，其中每個(gè)產(chǎn)生式(或稱規(guī)則)是一序偶(，)，通常寫作 或::= 讀作“是”或“定義為”。在此，為產(chǎn)生式的左部，而為產(chǎn)生式的右部，、是由終結(jié)符和非終結(jié)符組成的符號(hào)串，(VTVN)+且至少有一個(gè)非終結(jié)符，而(VTVN)*。,終結(jié)符號(hào)是指語(yǔ)言不可再分的基本符號(hào)，通常是一個(gè)語(yǔ)言的字母表；終結(jié)符代表了語(yǔ)法的最小元素，是一種個(gè)體記號(hào)。非終結(jié)符號(hào)也稱語(yǔ)法變量，它代表語(yǔ)法實(shí)體或語(yǔ)法范疇；非終結(jié)符代表一

6、個(gè)一定的語(yǔ)法概念，因此，一個(gè)非終結(jié)符是一個(gè)類、一個(gè)集合。例如，在程序語(yǔ)言中，可以把變量、常數(shù)、“+”、“*”等看作是終結(jié)符，而像“算術(shù)表達(dá)式”這個(gè)非終結(jié)符則代表著一定算術(shù)式組成的類，如i*(i+i)、i+i+i等；也即每個(gè)非終結(jié)符代表著由一些終結(jié)符和非終結(jié)符且滿足一定規(guī)則的符號(hào)串組成的集合。,文法開始符號(hào)是一個(gè)特殊的非終結(jié)符，它代表文法所定義的語(yǔ)言中我們最終感興趣的語(yǔ)法實(shí)體，即語(yǔ)言的目標(biāo)，而其它語(yǔ)法實(shí)體只是構(gòu)造語(yǔ)言目標(biāo)的中間變量；如表達(dá)式文法的語(yǔ)言目標(biāo)是表達(dá)式，而程序語(yǔ)言的目標(biāo)通常為程序。 產(chǎn)生式(也稱產(chǎn)生規(guī)則或規(guī)則)是定義語(yǔ)法實(shí)體的一種書寫規(guī)則。一個(gè)語(yǔ)法實(shí)體的相關(guān)規(guī)則可能不止一個(gè)。例如

7、，有： P1 P2 Pn,為書寫方便，可將這些有相同左部的產(chǎn)生式合并為一個(gè)，即縮寫成 P12n 其中，每個(gè)i(i=1,2,,n)稱為P的一個(gè)候選式，直豎“”讀為“或”，它與“”一樣是用來(lái)描述文法的元語(yǔ)言符號(hào)(即不屬于的字符),例3.1試構(gòu)造產(chǎn)生標(biāo)識(shí)符的文法。 解答首先，標(biāo)識(shí)符是以字母開頭的字母數(shù)字串，我們用L表示“字母”類非終結(jié)符，用D表示“數(shù)字”類非終結(jié)符，而用T表示“字母或數(shù)字”類非終結(jié)符，則有： Labz D019 TLD 其次，如果用S表示“字母數(shù)字串”類，則T是一字母或數(shù)字，ST也是字母數(shù)字串，即有 STST 其中，產(chǎn)生式STST是一種左遞歸形式，由它可以產(chǎn)生一串T。,最后，作

8、為“標(biāo)識(shí)符”的非終結(jié)符I，它或者是一單個(gè)字母，或者為一字母后跟字母數(shù)字串，即 ILLS 因此，產(chǎn)生標(biāo)識(shí)符的文法GI為： G=(a,b,,z,0,,9,I,S,T,L,D,I,) :ILLS STST TLD Labz D019,例3.2寫一文法，使其語(yǔ)言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。 解答根據(jù)題意，我們可以將奇數(shù)劃分為如圖31所示的三個(gè)部分，即最高位允許出現(xiàn)19，用非終結(jié)符B表示；中間部分可以出現(xiàn)任意多位數(shù)字09，每一位用非終結(jié)符D表示；最低位只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用A表示。,圖31奇數(shù)劃分示意,由于中間部分可出現(xiàn)任意位，所以另引入了一個(gè)非終結(jié)符M，它包括最高位和中

9、間位部分。假定開始符為N，則可得到文法GN為： G=(0,1,,9,N,A,M,B,D,N,) :NAMA/*一位數(shù)字多位數(shù)字*/ MBMD/*僅兩位數(shù)字(無(wú)中間位)多于兩位數(shù)字*/ A13579 B123456789 D0B,3文法產(chǎn)生的語(yǔ)言 設(shè)文法G=(VT,VN,S,)且、(VTVN)*，如果存在產(chǎn)生式A((VTVN)*)，則稱A可直接推出，即 A 其中“ ”表示直接推導(dǎo)出，是應(yīng)用產(chǎn)生規(guī)則進(jìn)行推導(dǎo)的記號(hào)。注意“ ”與“”不同，“”是產(chǎn)生式中的定義記號(hào)。直接推導(dǎo)是對(duì)文法符號(hào)串A中的非終結(jié)符A用相應(yīng)的產(chǎn)生式A的右部來(lái)替換，從而得到。我們給出推導(dǎo)的說(shuō)明如下：

10、,,,,(1)如果1可直接推出2，2可直接推出3，，n-1可直接推出n，即存在一個(gè)自1至n的推導(dǎo)序列：1 2 3 n(n0)，則我們稱1可推導(dǎo)出n，記為1 n，它表示從1出發(fā)經(jīng)過(guò)一步或若干步可推導(dǎo)出n。 (2)如果記1 1，則1 n表示從1出發(fā)，經(jīng)過(guò)0步或若干步可推導(dǎo)出n；也即1 n意味著或者1=n，或者1 n。,,,,,例如，對(duì)下面的文法GE： EE+EE*E(E)i (3.1) 其中，惟一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式。我們可以從E出發(fā)進(jìn)行一系列的推導(dǎo)，如表達(dá)式i+i*i的推導(dǎo)如下： E E+E E+E*E E+E*i

11、 E+i*i i+i*i,,,,,,假定GS是一個(gè)文法，S是它的開始符號(hào)，如果S ，(VTVN)*，則稱是文法GS的一個(gè)句型；如果VT*，則稱是文法GS的一個(gè)句子。僅含終結(jié)符的句型是一個(gè)句子。 由定義可知，開始符S本身只能是文法的一個(gè)句型而不可能是一個(gè)句子；此外，上面推導(dǎo)出的i+i*i是文法GE的一個(gè)句子(當(dāng)然也是一個(gè)句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。 對(duì)于文法GS，它所產(chǎn)生的句子的全體稱為由文法GS產(chǎn)生的語(yǔ)言，記為L(zhǎng)G，即有 L(G)=S且VT*,3.1.2形式語(yǔ)言分類 語(yǔ)言學(xué)家Noam Chomsky于

12、1956年首先建立了形式語(yǔ)言的描述，定義了四類文法及相應(yīng)的形式語(yǔ)言，并分別與相應(yīng)的識(shí)別系統(tǒng)相聯(lián)系，它對(duì)程序語(yǔ)言的設(shè)計(jì)、編譯方法、計(jì)算復(fù)雜性等方面都產(chǎn)生了重大影響。 在四類文法中，我們主要用到2型和3型文法。,10型文法與0型語(yǔ)言(對(duì)應(yīng)圖靈機(jī)) 如果文法G的每一個(gè)產(chǎn)生式具有下列形式： 其中，V*VNV*(注：V=VNVT)，即至少含有一個(gè)非終結(jié)符；V*；則稱文法G為0型文法或短語(yǔ)文法，記為PSG。0型文法相應(yīng)的語(yǔ)言稱為0型語(yǔ)言或稱遞歸可枚舉集，它的識(shí)別系統(tǒng)是圖靈(Turing)機(jī)，0型語(yǔ)言是不可判定的。 換句話說(shuō)， 和都是符號(hào)串，對(duì)它們沒(méi)有任何限制。這種文法，對(duì)計(jì)算機(jī)語(yǔ)言

13、來(lái)說(shuō)，太一般化了。,21型文法與1型語(yǔ)言(對(duì)應(yīng)線性界限自動(dòng)機(jī),自然語(yǔ)言) 文法G的每一個(gè)產(chǎn)生式，均在0型文法的基礎(chǔ)上增加了字符長(zhǎng)度上滿足的限制，則稱文法G為1型文法或上下文有關(guān)文法，記為CSG。1型文法相應(yīng)的語(yǔ)言稱為1型語(yǔ)言或上下文有關(guān)語(yǔ)言，它的識(shí)別系統(tǒng)是線性界限自動(dòng)機(jī)。 1型語(yǔ)言是可以判定的，但是現(xiàn)在還沒(méi)有找到有效的方法。 1型文法的另一種定義方法是文法G的每一個(gè)產(chǎn)生式具有下列形式： A 其中，、V*，AVN，V+（ 是非空串）；顯然|A|| ，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在、的上下文環(huán)境中才能被所替換。,32型文法與2型語(yǔ)言(對(duì)應(yīng)下推自動(dòng)機(jī),程序設(shè)計(jì)

14、語(yǔ)言) 文法G的每一個(gè)產(chǎn)生式具有下列形式： A 其中，AVN，V*，則稱文法G為2型文法或上下文無(wú)關(guān)文法，記為CFG。2型文法相應(yīng)的語(yǔ)言稱為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言，它的識(shí)別系統(tǒng)是下推自動(dòng)機(jī)。2型文法是可判定的，而且有有效的判定方法。 大部分程序設(shè)計(jì)語(yǔ)言的文法近似于2型文法，因此2型文法是我們的主要研究對(duì)象。,43型文法與3型語(yǔ)言(對(duì)應(yīng)有限自動(dòng)機(jī)) 文法G的每個(gè)產(chǎn)生式具有下列形式： Aa或AaB 其中，A、BVN，aVT*，則文法G稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語(yǔ)言為3型語(yǔ)言或正規(guī)語(yǔ)言，它的識(shí)別系統(tǒng)是有限自動(dòng)機(jī)。 程序設(shè)計(jì)語(yǔ)

15、言的單詞通常都可寫成3型文法的形式，因此3型文法（或自動(dòng)機(jī)）與詞法分析有密切關(guān)系。 3型文法還可以呈左線性形式： Aa或ABa,5四類文法的關(guān)系與區(qū)別 由四類文法的定義可知，從0型文法到3型文法逐漸增加限制。13型文法都屬于0型文法，2、3型文法均屬于1型文法，3型文法屬于2型文法。四類文法的區(qū)別如下： (1)1型文法中不允許有形如“A”的產(chǎn)生式存在，而2、3型文法則允許形如“A”的產(chǎn)生式存在； (2)0、1型文法的產(chǎn)生式左部存在含有終結(jié)符號(hào)的符號(hào)串或兩個(gè)以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個(gè)的非終結(jié)符號(hào)。,給定一個(gè)文法，如何判斷其屬于何種文法？通常我們判斷

16、是按照3型文法、2型文法、1型文法、0型文法從高到低的順序來(lái)判斷。 例如：一旦判斷給定文法屬于3型文法之后，就沒(méi)有必要再判斷是否屬于2型文法了，因?yàn)樗囟▽儆?型文法。我們應(yīng)該以最高規(guī)則來(lái)判定一個(gè)文法屬于的文法類型，其他情況依次類推。只有當(dāng)我們不屬于3型文法時(shí)，我們才向下判斷，它是否屬于2型文法，若不屬于2型文法，則依次類推向下判斷。最終的結(jié)果如果不屬于3型文法、 2型文法以及1型文法，那就只有屬于0型文法了。,例3.3試判斷下列產(chǎn)生式集所對(duì)應(yīng)的文法和產(chǎn)生的語(yǔ)言： (1)SACaB (2)SaSBC (3)SAc (4) SaS CaaaC SaBC SSc SaA CBDB

17、 CBDB Aab AbA CBE DBDC AaAb AbB aDDa DCBC BcB ADAC aBab Bc aEEa bBbb AE bCbc cCcc,解答 由四類文法的定義與區(qū)別可知，14分別為03型文法。 (1) 該0型文法產(chǎn)生的0型語(yǔ)言為L(zhǎng)0(G)=a2nn0。例如：當(dāng)n=2時(shí)，句子a22= aaaa是通過(guò)下列推導(dǎo)得到的：,(2) 該1型文法產(chǎn)生的1型語(yǔ)言為 L1(G)=anbncnn1。 例如，當(dāng)n=2時(shí)，句子a2b2c2=aabbcc是通過(guò)下列推導(dǎo)得到的：,(3) 該2型文法產(chǎn)生的2型語(yǔ)言為 L2(G)=anbncm

18、m、n1。 例如當(dāng)n=2、m=3時(shí)，句子a2 b2 c3=aabbccc是通過(guò)下列推導(dǎo)得到的：,(4) 該3型文法產(chǎn)生的3型語(yǔ)言為 L3(G)=ambnckm、n、k1。 例如當(dāng)m=2、n=3、k=4時(shí)，句子a2b3c4=aabbbcccc是通過(guò)下列推導(dǎo)得到的：,由例3.3可知：anbncnn1 anbncmm、n1 ambnckm、n、k1，這說(shuō)明對(duì)文法規(guī)則定義形式的限制雖然加強(qiáng)了，但相應(yīng)的語(yǔ)言反而更大了。因此，不能主觀認(rèn)定文法限制越大則語(yǔ)言越小，也即下述結(jié)論是不成立的： 3型語(yǔ)言 2型語(yǔ)言 1型語(yǔ)言 0型語(yǔ)言 在編譯方法中，通常用3型文法來(lái)描述高級(jí)程序語(yǔ)言的詞法部分，然

19、后用有限自動(dòng)機(jī)FA來(lái)識(shí)別高級(jí)語(yǔ)言的單詞；利用2型文法來(lái)描述高級(jí)語(yǔ)言的語(yǔ)法部分，然后用下推自動(dòng)機(jī)PDA來(lái)識(shí)別高級(jí)語(yǔ)言的各種語(yǔ)法成分。,例3.4 給出字母表=a,b上的同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有字符串集合的正規(guī)文法。 解答 為了構(gòu)造字母表=a,b上同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有字符串的正規(guī)表達(dá)式，我們畫出如圖32所示的DFA，即由開始符S出發(fā)，經(jīng)過(guò)奇數(shù)個(gè)a到達(dá)狀態(tài)A，或經(jīng)過(guò)奇數(shù)個(gè)b到達(dá)狀態(tài)B。再由狀態(tài)A出發(fā)，經(jīng)過(guò)奇數(shù)個(gè)b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)，經(jīng)過(guò)奇數(shù)個(gè)a到達(dá)終態(tài)C。,圖32 例3.4的DFA,由圖32可直接得到正規(guī)文法GS如下： GS: SaAbB

20、 AaSbCb BbSaCa CbAaB,3.1.3 正規(guī)表達(dá)式與上下文無(wú)關(guān)文法 1正規(guī)表達(dá)式到上下文無(wú)關(guān)文法的轉(zhuǎn)換 正規(guī)表達(dá)式所描述的語(yǔ)言結(jié)構(gòu)均可以用上下文無(wú)關(guān)文法描述，反之則不一定。由正規(guī)表達(dá)式構(gòu)造上下文無(wú)關(guān)文法的一種方法如下： (1) 構(gòu)造正規(guī)表達(dá)式的NFA； (2) 若0為初始狀態(tài)，則A0為開始符號(hào)； (3) 如果存在映射關(guān)系f(i, a)= j，則定義產(chǎn)生式 Ai aAj； (4) 如果存在映射關(guān)系f(i, )= j，則定義產(chǎn)生式 Ai Aj； (5) 若i為終態(tài)，則定義產(chǎn)生式 Ai 。,例3.5 用上下文無(wú)關(guān)

21、文法描述正規(guī)表達(dá)式(ab)*abb。 解答 首先構(gòu)造識(shí)別正規(guī)表達(dá)式(ab)*abb的NFA M如圖33所示。 由構(gòu)造上下文無(wú)關(guān)文法的方法得到上下文無(wú)關(guān)文法GA0如下： GA0: A0aA0bA0aA1 A1bA2 A2bA3 A3,事實(shí)上，由正規(guī)表達(dá)式構(gòu)造上下文無(wú)關(guān)文法還可以采用另一種方法，即通過(guò)分析正規(guī)表達(dá)式的特性憑經(jīng)驗(yàn)直接構(gòu)造。如可把(ab)*abb看作由(ab)*和abb兩部分組成，第一部分是由0個(gè)或若干個(gè)a和b組成的字符串，而第二部分則僅由abb字符串組成，由此得到上下文無(wú)關(guān)文法GA0如下： GA0: AHT HaHbH

22、 Tabb,圖33 例3.5的NFA M,2正規(guī)表達(dá)式與上下文無(wú)關(guān)文法描述的對(duì)象 上下文無(wú)關(guān)文法既可以描述程序語(yǔ)言的語(yǔ)法，又可以描述程序語(yǔ)言的詞法，但基于下述原因，應(yīng)采用正規(guī)表達(dá)式描述詞法： (1) 詞法規(guī)則簡(jiǎn)單，采用正規(guī)表達(dá)式已足以描述； (2) 正規(guī)表達(dá)式的表示比上下文無(wú)關(guān)文法更加簡(jiǎn)潔、直觀和易于理解； (3) 有限自動(dòng)機(jī)的構(gòu)造比下推自動(dòng)機(jī)簡(jiǎn)單且分析效率高。,貫穿詞法分析和語(yǔ)法分析始終如一的思想是：語(yǔ)言的描述和語(yǔ)言的識(shí)別是表示一個(gè)語(yǔ)言的兩個(gè)不同的側(cè)面，二者缺一不可。用正規(guī)表達(dá)式和上下文無(wú)關(guān)文法描述語(yǔ)言時(shí)的識(shí)別方法(即自動(dòng)機(jī))不同。通常，正規(guī)表達(dá)式適合于描述線性結(jié)構(gòu)，

23、如標(biāo)識(shí)符、關(guān)鍵字和注釋等；而上下文無(wú)關(guān)文法則適合于描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的語(yǔ)句if-else、while等。,3.2 推導(dǎo)與語(yǔ)法樹,3.2.1 推導(dǎo)與短語(yǔ) 1規(guī)范推導(dǎo) 在3.1.1節(jié)中，所給句子i+i*i推導(dǎo)序列中的每一步推導(dǎo)都是對(duì)句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換，這樣的推導(dǎo)稱為最右推導(dǎo)。如果每一步推導(dǎo)都是對(duì)句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換，則稱為最左推導(dǎo)。,從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程并不是惟一的，為了對(duì)句子的結(jié)構(gòu)進(jìn)行確定性分析，我們往往只考慮最左推導(dǎo)或最右推導(dǎo)，并且稱最右推導(dǎo)為規(guī)范推導(dǎo)。規(guī)范推導(dǎo)的逆過(guò)程便是規(guī)范歸約。,例如句

24、子i+i*i按文法(3.1)的最左推導(dǎo)是,例如,假定有文法 G:N D|ND D 0|1|2 則下面的推導(dǎo)都是規(guī)范推導(dǎo): N D N ND N ND N2 D2 22 而下面的推導(dǎo)都不是規(guī)范推導(dǎo): N ND NDD N ND DD D2 22,,,,,,,,,,,,,每個(gè)句子都有規(guī)范推導(dǎo)，而且通常是唯一的。例如，對(duì)上例來(lái)說(shuō)，33這個(gè)句子只有下面一種規(guī)范推導(dǎo)： N ND N3 D3 33 但對(duì)句型來(lái)說(shuō)，也可能沒(méi)有規(guī)范推導(dǎo)。例

25、如，對(duì)上例的句型2D和2DD，我們只有下面一種推導(dǎo)，但它們都不是規(guī)范的： N ND DD 2D N ND NDD DDD 2DD 我們所感興趣的是句子，而每個(gè)句子都有規(guī)范推導(dǎo)，因此可以只考慮規(guī)范推導(dǎo)。,,,,,,,,,,,,2短語(yǔ) 設(shè)是文法GS的一個(gè)句型，如果有： S A 且 A 則稱是句型關(guān)于非終結(jié)符A的一個(gè)短語(yǔ)，或稱是的一個(gè)短語(yǔ)。特別是有A產(chǎn)生式時(shí)，為句型的一個(gè)直接短語(yǔ)或簡(jiǎn)單短語(yǔ)。 短語(yǔ)的兩個(gè)條件缺一不可。僅有A 未必意味著就是句型的一個(gè)短語(yǔ)，還需要有S A這一條件加以限制；也即短語(yǔ)屬于該句型的組成部分，不能

26、破壞這種句型結(jié)構(gòu)的限制。,3句柄 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。注意，一個(gè)句型的直接短語(yǔ)可能不只一個(gè)，但最左直接短語(yǔ)則是惟一的。如對(duì)S A 來(lái)說(shuō)，將句型中的句柄用產(chǎn)生式的左部符號(hào)代替便得到新句型A，這是一次規(guī)范歸約，恰好與規(guī)范推導(dǎo)相反。,4素短語(yǔ) 含有終結(jié)符的短語(yǔ)，如果它不存在也具有同樣性質(zhì)的真子串，則該短語(yǔ)為素短語(yǔ)。 例如，在E E+E*i中，i、E*i和E+E*i是句型E+E*i的三個(gè)短語(yǔ)；其中，i為素短語(yǔ)；E*i雖為短語(yǔ)且含有終結(jié)符，但它的真子串i是素短語(yǔ)，故E*i不是素短語(yǔ)；同樣E+E*i也不是素短語(yǔ)。,下面考慮定義表達(dá)式的一個(gè)文法。 G:E E+T | E-

27、T | T T T*F | T/F | F F i | (E) 符號(hào)串(T+i)*i-F是文法G的一個(gè)句型。對(duì)此我們有： 短語(yǔ)8個(gè)： 1. (T+i)*i-F 2. (T+i)*i 3. (T+i) 4. T+i 5. T 6. 第一個(gè)i 7. 第二個(gè)i 8. F,下面考慮定義表達(dá)式的一個(gè)文法。 G:E E+T | E-T | T T T*F | T/F | F F i | (E) 符號(hào)串(T+i)*i-F是文法G的一個(gè)句型。對(duì)此我們有： 簡(jiǎn)單短語(yǔ)4個(gè)： 1. T 2. 第一個(gè)i

28、 3. 第二個(gè)i 4. F 句柄1個(gè)： T,3.2.2 語(yǔ)法樹與二義性 1語(yǔ)法樹 對(duì)程序語(yǔ)言來(lái)說(shuō)，有兩個(gè)問(wèn)題需要解決：其一是判別程序在語(yǔ)法上是否正確；其二是句子的識(shí)別或分析。在編譯方法中，為了便于識(shí)別或分析句子而引入了語(yǔ)法樹這一重要的輔助工具。語(yǔ)法樹以圖示化的形式把句子分解成各個(gè)組成部分來(lái)描述或分析句子的語(yǔ)法結(jié)構(gòu)，這種圖示化的表示與所定義的文法規(guī)則完全一致，但更為直觀和完整。,對(duì)文法G=(VT,VN,S,) ，滿足下列條件的樹稱為GS的語(yǔ)法樹： (1) 每個(gè)結(jié)點(diǎn)用GS的一個(gè)終結(jié)符或非終結(jié)符標(biāo)記； (2) 根結(jié)點(diǎn)用文法開始符S標(biāo)記； (3) 內(nèi)部結(jié)點(diǎn)(指非

29、樹葉結(jié)點(diǎn))一定是非終結(jié)符，如果某內(nèi)部結(jié)點(diǎn)A有n個(gè)分支，它的所有子結(jié)點(diǎn)從左至右依次標(biāo)記為x1、x2、、xn，則Ax1x2xn一定是文法GS的一條產(chǎn)生式； (4) 如果某結(jié)點(diǎn)標(biāo)記為，則它必為葉結(jié)點(diǎn)且是其父結(jié)點(diǎn)的惟一子結(jié)點(diǎn)。,相應(yīng)于一個(gè)句型的語(yǔ)法樹是以文法的開始符S作為根結(jié)點(diǎn)的，并隨著推導(dǎo)逐步展開；當(dāng)某個(gè)非終結(jié)符被它對(duì)應(yīng)的產(chǎn)生式右部的某個(gè)候選式所替換時(shí)，這個(gè)非終結(jié)符所對(duì)應(yīng)的結(jié)點(diǎn)就產(chǎn)生出下一代新結(jié)點(diǎn)，即候選式中從左至右的每一個(gè)符號(hào)都依次順序?qū)?yīng)一個(gè)新結(jié)點(diǎn)，且每個(gè)新結(jié)點(diǎn)與其父結(jié)點(diǎn)之間都有一條連線(樹枝)。在一棵語(yǔ)法樹生長(zhǎng)過(guò)程中的任何時(shí)刻，所有那些沒(méi)有后代的樹葉結(jié)點(diǎn)自左至右排列起來(lái)就是一個(gè)句型。,圖3

30、-4 句子i+i*i的語(yǔ)法樹 例如，對(duì)下面的文法GE： EE+EE*E(E)i (3.1) 與文法(3.1)的句子i+i*i相應(yīng)的語(yǔ)法樹如圖34所示。,在構(gòu)造語(yǔ)法樹時(shí)可以發(fā)現(xiàn)，一個(gè)句型的最左推導(dǎo)及最右推導(dǎo)只是決定先生長(zhǎng)左子樹還是先生長(zhǎng)右子樹，句型推導(dǎo)結(jié)束時(shí)相應(yīng)的語(yǔ)法樹也隨之完成，這時(shí)已不能看出是先生長(zhǎng)左子樹還是先生長(zhǎng)右子樹，所呈現(xiàn)的只是已經(jīng)長(zhǎng)成的這個(gè)句子或句型的語(yǔ)法樹，這與使用文法規(guī)則進(jìn)行推導(dǎo)是有差異的，即使用文法規(guī)則的推導(dǎo)過(guò)程是有先后之分的。,因此，一棵語(yǔ)法樹表示了一個(gè)句型種種可能的(但未必是所有的見(jiàn)下面文法的二義性)不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。如果我們堅(jiān)持使用最左(

31、或最右)推導(dǎo)，那么一棵語(yǔ)法樹就完全等價(jià)于一個(gè)最左(或最右)推導(dǎo)，這種等價(jià)性也包括語(yǔ)法樹的每一步生長(zhǎng)和推導(dǎo)的每一步展開的這種完全一致性。,2子樹和短語(yǔ) 語(yǔ)法樹的某個(gè)結(jié)點(diǎn)連同它的所有后代組成了一棵子樹，只含有單層分枝的子樹稱為簡(jiǎn)單子樹。 子樹與短語(yǔ)的關(guān)系十分密切，根據(jù)子樹的概念，句型的短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)的直觀解釋如下： (1) 短語(yǔ)：子樹的末端結(jié)點(diǎn)(即樹葉)組成的符號(hào)串是相對(duì)于子樹根的短語(yǔ)； (2) 直接短語(yǔ)：簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于簡(jiǎn)單子樹根的直接短語(yǔ)；,(3) 句柄：最左簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串為句柄； (4) 素短語(yǔ)：子樹的末端結(jié)點(diǎn)組成的符號(hào)

32、串含終結(jié)符，且在該子樹中不再有包含含有終結(jié)符的更小子樹。顯然，從語(yǔ)法樹出發(fā)尋找短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)要直觀得多。此外，要注意的是子樹末端結(jié)點(diǎn)組成的符號(hào)串是指由該子樹根開始向下生長(zhǎng)的所有末端結(jié)點(diǎn)(即樹葉)，該子樹的部分末端結(jié)點(diǎn)并不是該子樹的短語(yǔ)。,圖35 E+E*i的語(yǔ)法樹,對(duì)圖35所示的關(guān)于句型E+E*i的語(yǔ)法樹來(lái)說(shuō)，它有3棵子樹，即3個(gè)短語(yǔ)，分別為i、E*i和E+E*i；而直接短語(yǔ)、句柄和素短語(yǔ)均為i。 3文法的二義性 文法GS的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語(yǔ)法樹，則稱這個(gè)句子是二義性的。一個(gè)文法如果包含二義性的句子，則這個(gè)文法是二義

33、文法，否則是無(wú)二義文法。 例如，對(duì)文法(3.1)，句子i+i*i存在著兩種最左推導(dǎo)或最右推導(dǎo)，所形成的兩棵不同的語(yǔ)法樹如圖36所示。,圖36 句子i+i*i的兩棵不同語(yǔ)法樹,再如，條件語(yǔ)句的文法GS為： GS: Sif B S Sif B S else S SA /*A指其它語(yǔ)句*/ 其中，VN = B,S,A，VT = if , else，則句型 if B if B S else S 所對(duì)應(yīng)的兩棵不同語(yǔ)法樹見(jiàn)圖37。 因此，文法GS是二義性文法。,圖37 句型 if B if B S else S 的兩棵不同語(yǔ)法樹,4

34、文法二義性的消除 一個(gè)文法是二義性的，并不說(shuō)明該文法所描述的語(yǔ)言也是二義性的。也即，對(duì)于一個(gè)二義性文法GS，如果能找到一個(gè)非二義性文法GS，使得L(G)=L(G)，則該二義性文法的二義性是可以消除的。如果找不到這樣的GS，則二義性文法描述的語(yǔ)言為先天二義性的。,文法二義性消除的方法如下： (1) 不改變文法中原有的語(yǔ)法規(guī)則，僅加進(jìn)一些語(yǔ)法的非形式規(guī)定。如對(duì)文法(3.1)，不改變已有的四條規(guī)則(即四個(gè)產(chǎn)生式)，僅加進(jìn)運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則，即*優(yōu)先于+，且*、+都服從左結(jié)合。這樣，對(duì)文法(3.1)中的句子i+i*i就只有如圖36(a)的惟一一棵語(yǔ)法樹。,(2) 構(gòu)造一個(gè)等價(jià)的無(wú)二義

35、性文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。 例如，我們可以將文法(3.1)改寫為無(wú)二義性的文法G E如下： GE: EE+TT TT*FF F(E)i 此時(shí)，句子i+i*i就只有如圖38所示的惟一一棵語(yǔ)法樹。,圖38 句子i+i*i的語(yǔ)法樹,例3.6 試將如下的二義性文法GS的二義性消除: GS: Sif b Sif b S else SA 解答 消除GS的二義性可采用如下兩種方法： (1) 不改變已有規(guī)則，僅加進(jìn)一項(xiàng)非形式的語(yǔ)法規(guī)定：else與離它最近的if匹配(即最近匹配原則)，這樣，文法GS的句子if b if b A el

36、se A只對(duì)應(yīng)惟一的一棵語(yǔ)法樹(見(jiàn)圖39)。,(2) 改寫文法GS為GS: SS1S2 S1if b S1 else S1A S2if b Sif b S1 else S2 這是因?yàn)橐鸲x性的原因是if-else語(yǔ)句的if后可以是任意if型語(yǔ)句，所以改寫文法時(shí)規(guī)定if和else之間只能是if-else語(yǔ)句或其它語(yǔ)句。這樣，改寫后文法GS的句子if b if b A else A只對(duì)應(yīng)惟一的一棵語(yǔ)法樹(如圖310所示)。,圖39 復(fù)合if語(yǔ)句的語(yǔ)法樹,圖310 GS的復(fù)合if語(yǔ)句的語(yǔ)法樹,我們總希望一個(gè)文法是無(wú)二義性的，這樣，句子的分析可以按惟一確定的方式進(jìn)行。但是，文法的二義性是不可判定的，即不存在一種算法，能夠在有限步內(nèi)判定一個(gè)文法是否為二義性的。有時(shí)候，二義性文法也可帶來(lái)一定的好處，如語(yǔ)法分析中二義性文法的應(yīng)用。,