第七講語法分析1

1、第第3 3章章 語法分析語法分析 第第3章章 語法分析語法分析 3.1 文法和語言文法和語言 第第3 3章章 語法分析語法分析 3.1 文法和語言文法和語言 文法是程序語言的生成系統(tǒng)，而自動機(jī)則是程序語言的識別系統(tǒng)；用文法可以精確地定義一個語言，并依據(jù)該文法構(gòu)造出識別這個語言的自動機(jī)。因此，文法對程序語言和編譯程序的構(gòu)造具有重要意義，如程序語言的詞法可用正規(guī)文法描述，語法可用上下文無關(guān)文法描述，而語義則要借助于上下文有關(guān)文法描述。第第3 3章章 語法分析語法分析 3.1.1 文法和語言的概念1語言 通常我們用表示字母表，字母表中的每個元素稱為字符或符號。不同語言的字母表可能是不同的，程序語言的

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

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

4、終結(jié)符則代表著一定算術(shù)式組成的類，如i*(i+i)、i+i+i等；也即每個非終結(jié)符代表著由一些終結(jié)符和非終結(jié)符且滿足一定規(guī)則的符號串組成的集合。第第3 3章章 語法分析語法分析 文法開始符號是一個特殊的非終結(jié)符，它代表文法所定義的語言中我們最終感興趣的語法實體，即語言的目標(biāo)，而其它語法實體只是構(gòu)造語言目標(biāo)的中間變量；如表達(dá)式文法的語言目標(biāo)是表達(dá)式，而程序語言的目標(biāo)通常為程序。 產(chǎn)生式(也稱產(chǎn)生規(guī)則或規(guī)則)是定義語法實體的一種書寫規(guī)則。一個語法實體的相關(guān)規(guī)則可能不止一個。例如，有： P1 P2 Pn第第3 3章章 語法分析語法分析 為書寫方便，可將這些有相同左部的產(chǎn)生式合并為一個，即縮寫成 P1

5、 2 n 其中，每個i(i=1,2,n)稱為P的一個候選式，直豎“ ”讀為“或”，它與“”一樣是用來描述文法的元語言符號(即不屬于的字符)。第第3 3章章 語法分析語法分析 例3.1試構(gòu)造產(chǎn)生標(biāo)識符的文法。解答首先，標(biāo)識符是以字母開頭的字母數(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章章 語法分析語法分析 最后，作為“標(biāo)識符”的

6、非終結(jié)符I，它或者是一單個字母，或者為一字母后跟字母數(shù)字串，即 IL LS 因此，產(chǎn)生標(biāo)識符的文法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章章 語法分析語法分析 例3.2寫一文法，使其語言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。解答根據(jù)題意，我們可以將奇數(shù)劃分為如圖31所示的三個部分，即最高位允許出現(xiàn)19，用非終結(jié)符B表示；中間部分可以出現(xiàn)任意多位數(shù)字09，每一位用非終結(jié)符D表示；最低位只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用A表示。第第3 3章章 語法分析語法分析 圖31 奇數(shù)劃分示意MB最高位中

7、間 位DDDA最低位第第3 3章章 語法分析語法分析 由于中間部分可出現(xiàn)任意位，所以另引入了一個非終結(jié)符M，它包括最高位和中間位部分。假定開始符為N，則可得到文法GN為：G=(0,1,9,N,A,M,B,D,N,):NA MA/*一位數(shù)字多位數(shù)字*/ MB MD/*僅兩位數(shù)字(無中間位)多于兩位數(shù)字*/ A1 3 5 7 9 B1 2 3 4 5 6 7 8 9 D0 B第第3 3章章 語法分析語法分析 3文法產(chǎn)生的語言設(shè)文法G=(VT,VN,S,)且、(VTVN)*，如果存在產(chǎn)生式A(VTVN)*)，則稱A可直接推出，即 A 其中“ ”表示直接推導(dǎo)出， 是應(yīng)用產(chǎn)生規(guī)則進(jìn)行推導(dǎo)的記號。注意“

8、”與“”不同，“”是產(chǎn)生式中的定義記號。直接推導(dǎo)是對文法符號串A中的非終結(jié)符A用相應(yīng)的產(chǎn)生式A的右部來替換，從而得到。我們給出推導(dǎo)的說明如下：第第3 3章章 語法分析語法分析 (1)如果1可直接推出2，2可直接推出3，n-1可直接推出n，即存在一個自1至n的推導(dǎo)序列：1 2 3 n(n0)，則我們稱1可推導(dǎo)出n，記為1 n，它表示從1出發(fā)經(jīng)過一步或若干步可推導(dǎo)出n。(2)如果記1 1，則1 n表示從1出發(fā)，經(jīng)過0步或若干步可推導(dǎo)出n；也即1 n意味著或者1=n，或者1 n。第第3 3章章 語法分析語法分析 例如，對下面的文法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章章 語法分析語法分析 假定GS是一個文法，S是它的開始符號，如果S ，(VTVN)*，則稱是文法GS的一個句型；如果VT*，則稱是文法GS的一個句子。僅含終結(jié)符的句型是一個句子。 由定義可知，開始符S本身只能是文法的一個句型而不可能是一個句子；此外，上面推導(dǎo)出的i+i*i是文法GE的一個句子(當(dāng)然也是一個句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。 對于文法GS，它所產(chǎn)生的句子的全體稱為由文法GS產(chǎn)生的

10、語言，記為LG，即有 L(G)= S 且VT*第第3 3章章 語法分析語法分析 3.1.2形式語言分類 語言學(xué)家Noam Chomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應(yīng)的形式語言，并分別與相應(yīng)的識別系統(tǒng)相聯(lián)系，它對程序語言的設(shè)計、編譯方法、計算復(fù)雜性等方面都產(chǎn)生了重大影響。第第3 3章章 語法分析語法分析 10型文法與0型語言(對應(yīng)圖靈機(jī)) 如果文法G的每一個產(chǎn)生式具有下列形式： 其中，V*VNV*(注：V=VNVT)，即至少含有一個非終結(jié)符；V*；則稱文法G為0型文法或短語文法，記為PSG。0型文法相應(yīng)的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turi

11、ng)機(jī)。第第3 3章章 語法分析語法分析 21型文法與1型語言(對應(yīng)線性界限自動機(jī)，自然語言) 文法G的每一個產(chǎn)生式，均在0型文法的基礎(chǔ)上增加了字符長度上滿足 的限制，則稱文法G為1型文法或上下文有關(guān)文法，記為CSG。1型文法相應(yīng)的語言稱為1型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性界限自動機(jī)。 1型文法的另一種定義方法是文法G的每一個產(chǎn)生式具有下列形式： A 其中，、V*，AVN，V+；顯然它滿足前述定義的長度限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在、的上下文環(huán)境中才能被所替換。第第3 3章章 語法分析語法分析 32型文法與2型語言(對應(yīng)下推自動機(jī)，程序設(shè)計語言) 文法G的每一

12、個產(chǎn)生式具有下列形式： A 其中，AVN，V*，則稱文法G為2型文法或上下文無關(guān)文法，記為CFG。2型文法相應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識別系統(tǒng)是下推自動機(jī)。第第3 3章章 語法分析語法分析 43型文法與3型語言(對應(yīng)有限自動機(jī)) 文法G的每個產(chǎn)生式具有下列形式： Aa或AaB 其中，A、BVN，aVT*，則文法G稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機(jī)。3型文法還可以呈左線性形式： Aa或ABa第第3 3章章 語法分析語法分析 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é)符號的符號串或兩個以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個的非終結(jié)符號。第第3 3章章 語法分析語法分析 例3.3試判斷下列產(chǎn)生式集所對應(yīng)的文法和產(chǎn)生的語言： (1)SACaB (2) SaSBC (3)SAc (4) SaSCaaaCSaBCSSc SaACBDBCBDBAabAbACBEDBDCAaAbAbBaDDaDCBC BcBADACaBab

14、BcaEEabBbbAEbCbc cCcc第第3 3章章 語法分析語法分析 解答 由四類文法的定義與區(qū)別可知，14分別為03型文法。 (1) 該0型文法產(chǎn)生的0型語言為L0(G)=a2n n0。例如：當(dāng)n=2時，句子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章章 語法分析語法分析 (2) 該1型文法產(chǎn)生的1型語言為L1(G)=anbncn

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

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

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