第七講語(yǔ)法分析1

1、第第3 3章章 語(yǔ)法分析語(yǔ)法分析 第第3章章 語(yǔ)法分析語(yǔ)法分析 3.1 文法和語(yǔ)言文法和語(yǔ)言 第第3 3章章 語(yǔ)法分析語(yǔ)法分析 3.1 文法和語(yǔ)言文法和語(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 3章章 語(yǔ)法分析語(yǔ)法分析 3.1.1 文法和語(yǔ)言的概念1語(yǔ)言 通常我們用表示字母表，字母表中的每個(gè)元素稱為字符或符號(hào)。不同語(yǔ)言的字母表可能是不同的，程序語(yǔ)言的

2、字母表通常是ASCII字符集。由字母表中的字符所組成的有窮系列稱為上的字符串或字，字母表上的所有字符串(包括空串)組成的集合用*表示。那么，對(duì)字母表來(lái)說(shuō)，*上的任意一個(gè)子集都稱為上的一個(gè)語(yǔ)言，記為L(zhǎng)(L*)，該語(yǔ)言的每一個(gè)字符串稱為語(yǔ)言L的一個(gè)語(yǔ)句或句子。 第第3 3章章 語(yǔ)法分析語(yǔ)法分析 2文法 文法通常表示成四元組G=(VT，VN，S，)，其中： (1)VT為終結(jié)符號(hào)集，這是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)； (2)VN為非終結(jié)符集，它也是一個(gè)非空有限集，其每個(gè)元素稱為非終結(jié)符號(hào)，且有VTVN=； (3)S為一文法開(kāi)始符，是一個(gè)特殊的非終結(jié)符號(hào)，即SVN；第第3 3章章 語(yǔ)法分析語(yǔ)

3、法分析 (4)是產(chǎn)生式的非空有限集，其中每個(gè)產(chǎn)生式(或稱規(guī)則)是一序偶(，)，通常寫(xiě)作 或:= 讀作“是”或“定義為”。在此，為產(chǎn)生式的左部，而為產(chǎn)生式的右部，、是由終結(jié)符和非終結(jié)符組成的符號(hào)串，(VTVN)+且至少有一個(gè)非終結(jié)符，而(VTVN)*。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 終結(jié)符號(hào)是指語(yǔ)言不可再分的基本符號(hào)，通常是一個(gè)語(yǔ)言的字母表；終結(jié)符代表了語(yǔ)法的最小元素，是一種個(gè)體記號(hào)。非終結(jié)符號(hào)也稱語(yǔ)法變量，它代表語(yǔ)法實(shí)體或語(yǔ)法范疇；非終結(jié)符代表一個(gè)一定的語(yǔ)法概念，因此，一個(gè)非終結(jié)符是一個(gè)類、一個(gè)集合。例如，在程序語(yǔ)言中，可以把變量、常數(shù)、“+”、“*”等看作是終結(jié)符，而像“算術(shù)表達(dá)式”這個(gè)非

4、終結(jié)符則代表著一定算術(shù)式組成的類，如i*(i+i)、i+i+i等；也即每個(gè)非終結(jié)符代表著由一些終結(jié)符和非終結(jié)符且滿足一定規(guī)則的符號(hào)串組成的集合。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 文法開(kāi)始符號(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í)體的一種書(shū)寫(xiě)規(guī)則。一個(gè)語(yǔ)法實(shí)體的相關(guān)規(guī)則可能不止一個(gè)。例如，有： P1 P2 Pn第第3 3章章 語(yǔ)法分析語(yǔ)法分析 為書(shū)寫(xiě)方便，可將這些有相同左部的產(chǎn)生式合并為一個(gè)，即縮寫(xiě)成 P1

5、 2 n 其中，每個(gè)i(i=1,2,n)稱為P的一個(gè)候選式，直豎“ ”讀為“或”，它與“”一樣是用來(lái)描述文法的元語(yǔ)言符號(hào)(即不屬于的字符)。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 例3.1試構(gòu)造產(chǎn)生標(biāo)識(shí)符的文法。解答首先，標(biāo)識(shí)符是以字母開(kāi)頭的字母數(shù)字串，我們用L表示“字母”類非終結(jié)符，用D表示“數(shù)字”類非終結(jié)符，而用T表示“字母或數(shù)字”類非終結(jié)符，則有： La b z D0 1 9 TL D 其次，如果用S表示“字母數(shù)字串”類，則T是一字母或數(shù)字，ST也是字母數(shù)字串，即有 ST ST 其中，產(chǎn)生式ST ST是一種左遞歸形式，由它可以產(chǎn)生一串T。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 最后，作為“標(biāo)識(shí)符”的

6、非終結(jié)符I，它或者是一單個(gè)字母，或者為一字母后跟字母數(shù)字串，即 IL LS 因此，產(chǎn)生標(biāo)識(shí)符的文法GI為： G=(a,b,z,0,9,I,S,T,L,D,I,) :IL LS ST ST TL D La b z D0 1 9第第3 3章章 語(yǔ)法分析語(yǔ)法分析 例3.2寫(xiě)一文法，使其語(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表示。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 圖31 奇數(shù)劃分示意MB最高位中

7、間 位DDDA最低位第第3 3章章 語(yǔ)法分析語(yǔ)法分析 由于中間部分可出現(xiàn)任意位，所以另引入了一個(gè)非終結(jié)符M，它包括最高位和中間位部分。假定開(kāi)始符為N，則可得到文法GN為：G=(0,1,9,N,A,M,B,D,N,):NA MA/*一位數(shù)字多位數(shù)字*/ MB MD/*僅兩位數(shù)字(無(wú)中間位)多于兩位數(shù)字*/ A1 3 5 7 9 B1 2 3 4 5 6 7 8 9 D0 B第第3 3章章 語(yǔ)法分析語(yǔ)法分析 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)。注意“

8、”與“”不同，“”是產(chǎn)生式中的定義記號(hào)。直接推導(dǎo)是對(duì)文法符號(hào)串A中的非終結(jié)符A用相應(yīng)的產(chǎn)生式A的右部來(lái)替換，從而得到。我們給出推導(dǎo)的說(shuō)明如下：第第3 3章章 語(yǔ)法分析語(yǔ)法分析 (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。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 例如，對(duì)下面的文法GE： EE+E E*E (E)i (3.1) 其中，惟一的非終結(jié)符E

9、可以看成是代表一類算術(shù)表達(dá)式。我們可以從E出發(fā)進(jìn)行一系列的推導(dǎo)，如表達(dá)式i+i*i的推導(dǎo)如下： E E+E E+E*E E+E*i E+i*i i+i*i第第3 3章章 語(yǔ)法分析語(yǔ)法分析 假定GS是一個(gè)文法，S是它的開(kāi)始符號(hào)，如果S ，(VTVN)*，則稱是文法GS的一個(gè)句型；如果VT*，則稱是文法GS的一個(gè)句子。僅含終結(jié)符的句型是一個(gè)句子。 由定義可知，開(kāi)始符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)生的

10、語(yǔ)言，記為L(zhǎng)G，即有 L(G)= S 且VT*第第3 3章章 語(yǔ)法分析語(yǔ)法分析 3.1.2形式語(yǔ)言分類 語(yǔ)言學(xué)家Noam Chomsky于1956年首先建立了形式語(yǔ)言的描述，定義了四類文法及相應(yīng)的形式語(yǔ)言，并分別與相應(yīng)的識(shí)別系統(tǒng)相聯(lián)系，它對(duì)程序語(yǔ)言的設(shè)計(jì)、編譯方法、計(jì)算復(fù)雜性等方面都產(chǎn)生了重大影響。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 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)是圖靈(Turi

11、ng)機(jī)。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 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型文法的另一種定義方法是文法G的每一個(gè)產(chǎn)生式具有下列形式： A 其中，、V*，AVN，V+；顯然它滿足前述定義的長(zhǎng)度限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在、的上下文環(huán)境中才能被所替換。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 32型文法與2型語(yǔ)言(對(duì)應(yīng)下推自動(dòng)機(jī)，程序設(shè)計(jì)語(yǔ)言) 文法G的每一

12、個(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ī)。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 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ī)。3型文法還可以呈左線性形式： Aa或ABa第第3 3章章 語(yǔ)法分析語(yǔ)法分析 5四類文法的關(guān)系與區(qū)別 由四類文法的定義可知，從0型文法到3型文法逐漸增加限制。1

13、3型文法都屬于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)。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 例3.3試判斷下列產(chǎn)生式集所對(duì)應(yīng)的文法和產(chǎn)生的語(yǔ)言： (1)SACaB (2) SaSBC (3)SAc (4) SaSCaaaCSaBCSSc SaACBDBCBDBAabAbACBEDBDCAaAbAbBaDDaDCBC BcBADACaBab

14、BcaEEabBbbAEbCbc cCcc第第3 3章章 語(yǔ)法分析語(yǔ)法分析 解答 由四類文法的定義與區(qū)別可知，14分別為03型文法。 (1) 該0型文法產(chǎn)生的0型語(yǔ)言為L(zhǎng)0(G)=a2n n0。例如：當(dāng)n=2時(shí)，句子a22= aaaa , (1)(2)(3)(5)(6)(2)(2)(2)(1)(4)(7)(7)(7)(8)S ACaB AaaCB AaaDB AaDaB ADaaB ACaaB AaaCaB AaaaaCB AaaaaE AaaaEa AaaEaa AaEaaa AEaaaa aaaa 第第3 3章章 語(yǔ)法分析語(yǔ)法分析 (2) 該1型文法產(chǎn)生的1型語(yǔ)言為L(zhǎng)1(G)=anbncn

15、 n1。例如，當(dāng)n=2時(shí)，句子a2b2c2=aabbcc是通過(guò)下列推導(dǎo)得到的：(1)(2)(6)(3)(4)(5)(7)(8)(9)S aSBC aaBCBC aabCBC aabDBC aabDCC aabBCC aabbCC aabbcC aabbcc 第第3 3章章 語(yǔ)法分析語(yǔ)法分析 (3) 該2型文法產(chǎn)生的2型語(yǔ)言為L(zhǎng)2(G)=anbncm m、n1。例如當(dāng)n=2、m=3時(shí)，句子a2 b2 c3=aabbccc是通過(guò)下列推導(dǎo)得到的：(2)(2)(1)(4)(3)S Sc Scc Accc aAbccc aabbccc第第3 3章章 語(yǔ)法分析語(yǔ)法分析 (4) 該3型文法產(chǎn)生的3型語(yǔ)言為L(zhǎng)

16、3(G)=ambnck m、n、k1。例如當(dāng)m=2、n=3、k=4時(shí)，句子a2b3c4=aabbbcccc是通過(guò)下列推導(dǎo)得到的：(1)(2)(3)(3)(4)(5)(5)(5)(6)SaS aaA aabA aabbA aabbbB aabbbcB aabbbccB aabbbcccB aabbbcccc 第第3 3章章 語(yǔ)法分析語(yǔ)法分析 由例3.3可知：anbncn n1 anbncm m、n1 ambnck m、n、k1，這說(shuō)明對(duì)文法規(guī)則定義形式的限制雖然加強(qiáng)了，但相應(yīng)的語(yǔ)言反而更大了。因此，不能主觀認(rèn)定文法限制越大則語(yǔ)言越小，也即下述結(jié)論是不成立的：3型語(yǔ)言 2型語(yǔ)言 1型語(yǔ)言 0型語(yǔ)言

17、 在編譯方法中，通常用3型文法來(lái)描述高級(jí)程序語(yǔ)言的詞法部分，然后用有限自動(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 3章章 語(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á)式，我們畫(huà)出如圖32所示的DFA，即由開(kāi)始符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。第第3 3章章 語(yǔ)法分析語(yǔ)法分析 圖32 例3.4的DFAbbbbaaaaSAB2 C第