編譯原理教程03語法分析

1、第3章語法分析 第第3章語章語 法法 分分 析析 3.1 文法和語言文法和語言 3.2 推導與語法樹推導與語法樹 3.3 自頂向下的語法分析自頂向下的語法分析 3.4 自底向上的語法分析自底向上的語法分析 3.5 規(guī)范規(guī)約的自底向上語法分析方法規(guī)范規(guī)約的自底向上語法分析方法 習題三習題三 第3章語法分析 語法分析的基本任務：根據(jù)語言的語法規(guī)則進行語法分析語法分析的基本任務：根據(jù)語言的語法規(guī)則進行語法分析，若不存在語法錯誤則給出正確的語法結構并為語義分析，若不存在語法錯誤則給出正確的語法結構并為語義分析和代碼生成做準備。和代碼生成做準備。 描述語言的語法結構需借助描述語言的語法結構需借助上下文無

2、關文法上下文無關文法。 語法分析的方法語法分析的方法 自上而下分析法自上而下分析法 自下而上分析法自下而上分析法第3章語法分析 3.1 文法和語言文法和語言 文法和語言的概念文法和語言的概念 形式語言分類形式語言分類 正規(guī)表達式與上下文無關文法正規(guī)表達式與上下文無關文法第3章語法分析 3.1.1 文法和語言的概念文法和語言的概念語言語言文法文法文法產生的語言文法產生的語言第3章語法分析 1語言語言通常我們用通常我們用表示字母表，字母表中的每個元素稱為字符表示字母表，字母表中的每個元素稱為字符或符號。不同語言的字母表可能是不同的，程序語言的字母表或符號。不同語言的字母表可能是不同的，程序語言的字

3、母表通常是通常是ASCII字符集。由字母表字符集。由字母表中的字符所組成的有窮系列中的字符所組成的有窮系列稱為稱為上的上的字符串字符串或或字字，字母表，字母表上的所有字符串上的所有字符串(包括空串包括空串)組組成的集合用成的集合用*表示。那么，對字母表表示。那么，對字母表來說，來說，*上的任意一個上的任意一個子集都稱為子集都稱為上的一個上的一個語言語言，記為，記為L(L *)，該語言的每一個字，該語言的每一個字符串稱為語言符串稱為語言L的一個的一個語句語句或或句子句子。例如，設例如，設=a,b,c，則，則L=,a,aa,ab,aaa,aab,aba,abb,為為上的一個語言。如果上的一個語言。

4、如果a表示字母、表示字母、b表示數(shù)字、表示數(shù)字、c看作其它符號，看作其它符號，則則L即是程序語言中的標識符集，其中的每個標識符就是標識即是程序語言中的標識符集，其中的每個標識符就是標識符集中的一個句子。符集中的一個句子。第3章語法分析 2文法文法文法通常表示成文法通常表示成四元組四元組GS=(VT，VN，S，)，其中：，其中：(1) VT為為終結符終結符號集，這是一個非空有限集，它的每個元素號集，這是一個非空有限集，它的每個元素稱為終結符號；稱為終結符號；(2) VN為為非終結符非終結符集，它也是一個非空有限集，其每個元素集，它也是一個非空有限集，其每個元素稱為非終結符號，且有稱為非終結符號，

5、且有VTVN=；(3) S為一文法為一文法開始符開始符，是一個特殊的非終結符號，即，是一個特殊的非終結符號，即SVN；(4) 是是產生式產生式的非空有限集，其中每個產生式的非空有限集，其中每個產生式(或稱規(guī)則或稱規(guī)則)是是一序偶一序偶(，)，通常寫作，通常寫作 或或:=讀作讀作“是是”或或“定義定義為為”。在此，。在此，為產生式的為產生式的左部左部，而，而為為產生式的產生式的右部右部，、是由是由終結符和非終結符終結符和非終結符組成的符號串，組成的符號串，(VTVN)+且且至少至少有一個有一個非終非終結符，而結符，而(VTVN)*。第3章語法分析 產生式需要滿足下面的條件產生式需要滿足下面的條件

6、: : 1)1)可以是可以是V VN N 和和V VT T 上的任意字符串上的任意字符串, ,但其中必須至少包含但其中必須至少包含一個非終結符一個非終結符, ,并且不能是空字符串（空字）并且不能是空字符串（空字）; ; 2)2)可以是可以是V VN N 和和V VT T 上的任意字符串上的任意字符串, ,也可以是空字也可以是空字; ; 3)3)中至少有一個產生式中的中至少有一個產生式中的得由得由S S 來充當來充當; ;第3章語法分析 終結符號終結符號是指語言是指語言不可再分不可再分的基本符號，通常是一個語言的基本符號，通常是一個語言的字母表；終結符代表了語法的最小元素，是一種個體記號。的字母

7、表；終結符代表了語法的最小元素，是一種個體記號。非終結符號非終結符號也稱也稱語法變量語法變量，它代表語法，它代表語法實體實體或語法或語法范疇范疇；非終；非終結符代表一個一定的結符代表一個一定的語法概念語法概念，因此，一個非終結符是一個類、，因此，一個非終結符是一個類、一個集合。例如，在程序語言中，可以把變量、常數(shù)、一個集合。例如，在程序語言中，可以把變量、常數(shù)、“+”、“*”等看作是等看作是終結符終結符，而像，而像“算術表達式算術表達式”這個這個非終結符則非終結符則代代表著一定表著一定算術式組成算術式組成的類，如的類，如i*(i+i)、i+i+i等；也即每個非終結等；也即每個非終結符代表著由符

8、代表著由一些終結符和非終結符且滿足一些終結符和非終結符且滿足一定規(guī)則的符號串組一定規(guī)則的符號串組成的集合。成的集合。文法文法開始符號開始符號是一個特殊的是一個特殊的非終結符非終結符，它代表文法所定義，它代表文法所定義的語言中我們的語言中我們最終感興趣最終感興趣的語法實體，即的語法實體，即語言的目標語言的目標，而其它，而其它語法實體只是構造語言目標的語法實體只是構造語言目標的中間變量中間變量。如。如表達式文法表達式文法的語言的語言目標是表達式，而目標是表達式，而程序語言的目標程序語言的目標通常為程序。通常為程序。 第3章語法分析 產生式產生式(也稱產生也稱產生規(guī)則或規(guī)則規(guī)則或規(guī)則)是定義語法實體

9、的一種是定義語法實體的一種書寫規(guī)書寫規(guī)則則。一個語法實體的。一個語法實體的相關規(guī)則相關規(guī)則可能不止一個。例如，有：可能不止一個。例如，有：P1P2Pn為書寫方便，可將這些有相同左部的產生式合并為一個，即縮為書寫方便，可將這些有相同左部的產生式合并為一個，即縮寫成寫成P1 2 n其中，每個其中，每個i (i=1,2,n) 稱為稱為P的一個候選式，直豎的一個候選式，直豎“ ”讀為讀為“或或”，它與，它與“”一樣是用來描述文法的一樣是用來描述文法的元語言符號元語言符號(即不屬即不屬于于的字符的字符)。第3章語法分析 例例3.1 試構造產生試構造產生標識符標識符的文法。的文法。解答解答 首先，標識符是

10、以字母開頭的字母數(shù)字串，我們用首先，標識符是以字母開頭的字母數(shù)字串，我們用L表示表示“字母字母”類非終結符，用類非終結符，用D表示表示“數(shù)字數(shù)字”類非終結符，而用類非終結符，而用T表示表示“字母或數(shù)字字母或數(shù)字”類非終結符，則有：類非終結符，則有： La b zD0 1 9TL D其次，如果用其次，如果用S表示表示“字母數(shù)字串字母數(shù)字串”類，則類，則T是一字母或數(shù)字，是一字母或數(shù)字，ST也是也是字母數(shù)字串字母數(shù)字串，即有，即有 ST ST其中，產生式其中，產生式ST ST是一種左遞歸形式，由它可以產生一串是一種左遞歸形式，由它可以產生一串T。第3章語法分析 最后，作為最后，作為“標識符標識符”

11、的非終結符的非終結符I，它或者是一單個字母，它或者是一單個字母，或者為一字母后跟字母數(shù)字串，即或者為一字母后跟字母數(shù)字串，即 IL LS 因此，產生標識符的文法因此，產生標識符的文法GI為：為：GI=(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.2 寫一文法，使其語言是寫一文法，使其語言是奇數(shù)奇數(shù)集合，但不允許出現(xiàn)以集合，但不允許出現(xiàn)以0打頭的奇數(shù)。打頭的奇數(shù)。解答解答 根據(jù)題意，我們可以將奇數(shù)劃分為如圖根據(jù)題意，我們可以將奇數(shù)劃分為如圖31所示的三所示的三個部分，即最高位允許出現(xiàn)個部分，即最高位允許

12、出現(xiàn)19，用非終結符，用非終結符B表示；中間部分表示；中間部分可以出現(xiàn)任意多位數(shù)字可以出現(xiàn)任意多位數(shù)字09，每一位用非終結符，每一位用非終結符D表示；最低位表示；最低位只允許出現(xiàn)只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用等奇數(shù)，用A表示。表示。第3章語法分析 圖31 奇數(shù)劃分示意第3章語法分析 由于中間部分可出現(xiàn)任意位，所以另引入了一個非終結符由于中間部分可出現(xiàn)任意位，所以另引入了一個非終結符M，它包括最高位和中間位部分。假定開始符為，它包括最高位和中間位部分。假定開始符為N，則可得到文，則可得到文法法GN為為GN=(0,1,9,N,A,M,B,D,N, ) : NA MA /*一位數(shù)字一位數(shù)字多

13、位數(shù)字多位數(shù)字*/ MB MD /*僅兩位數(shù)字僅兩位數(shù)字(無中間位無中間位)多于兩位數(shù)字多于兩位數(shù)字*/ A1 3 5 7 9 B1 2 3 4 5 6 7 8 9 D0 B第3章語法分析 第3章語法分析 注意：在每一步推導過程中，注意：在每一步推導過程中，只能只能對其中的對其中的一個一個非終結符用非終結符用其對應的其對應的產生式右部產生式右部的一個候選式來替換。的一個候選式來替換。第3章語法分析 第3章語法分析 第3章語法分析 第3章語法分析 3.1.2 形式語言分類形式語言分類語言學家語言學家Noam Chomsky于于1956年首先建立了年首先建立了形式語言的描形式語言的描述述，定義了，

14、定義了四類文法四類文法及及相應相應的形式語言，并的形式語言，并分別分別與相應的識別系與相應的識別系統(tǒng)相聯(lián)系，它對程序語言的設計、編譯方法、計算復雜性等方面統(tǒng)相聯(lián)系，它對程序語言的設計、編譯方法、計算復雜性等方面都都產生了產生了重大影響。重大影響。0型文法與型文法與0型語言型語言(對應圖靈機對應圖靈機) 1型文法與型文法與1型語言型語言(對應對應線性界限自動機，自然語言線性界限自動機，自然語言) 2型文法與型文法與2型語言型語言(對應對應下推自動機，程序設計語言下推自動機，程序設計語言) 3型文法與型文法與3型語言型語言(對應有限自動機對應有限自動機)第3章語法分析 10型文法與型文法與0型語言

15、型語言(對應圖靈機對應圖靈機)如果文法如果文法GS的每一個產生式具有的每一個產生式具有下列下列形式：形式：其中，其中，V*VNV* (注：注：V=VNVT)，即，即至少至少含有一個含有一個非終結符非終結符；V*；則稱文法；則稱文法GS為為0型文法或短語文法型文法或短語文法，記為，記為PSG。 0型文法相應的語言稱為型文法相應的語言稱為0型語言型語言或稱或稱遞歸可枚舉集遞歸可枚舉集，它的識，它的識別系統(tǒng)是別系統(tǒng)是圖靈圖靈(Turing)機。機。第3章語法分析 21型文法與型文法與1型語言型語言(對應對應線性界限自動機，自然語言線性界限自動機，自然語言)文法文法GS的每一個產生式的每一個產生式，均

16、在，均在0型文法的基礎型文法的基礎上上增加增加了字符長度上了字符長度上滿足滿足 的限制，則稱文法的限制，則稱文法GS為為1型文法型文法或上下文或上下文有關有關文法，記為文法，記為CSG。 1型文法相應的語言稱為型文法相應的語言稱為1型語言型語言或上下文或上下文有關有關語言，它的識語言，它的識別系統(tǒng)是別系統(tǒng)是線性界限自線性界限自動機。動機。1型文法的另一種定義方法是文法型文法的另一種定義方法是文法GS的每一個產生式具有的每一個產生式具有下列下列形式形式：A其中其中，、V*，AVN ，V+。顯然，它滿足前述定義的長。顯然，它滿足前述定義的長度限制，但它更度限制，但它更明確明確地表達了地表達了上下文

17、有關上下文有關的特性，即的特性，即A必須必須在在、的上下文環(huán)境中才能被的上下文環(huán)境中才能被所替換。所替換。第3章語法分析 32型文法與型文法與2型語言型語言(對應對應下推自動機，程序設計語言下推自動機，程序設計語言)文法文法GS的每一個產生式具有下列形式：的每一個產生式具有下列形式：A其中，其中，AVN，V*，則稱文法，則稱文法GS為為2型型文法或上下文文法或上下文無關無關文法，記為文法，記為CFG。 2型文法相應的語言稱為型文法相應的語言稱為2型語言或上下文無關語型語言或上下文無關語言，它的識言，它的識別系統(tǒng)是別系統(tǒng)是下推自動機下推自動機。第3章語法分析 43型文法與型文法與3型語言型語言(

18、對應有限自動機對應有限自動機)文法文法GS的每個產生式的每個產生式具有下列具有下列形式：形式：Aa或或AaB其中，其中，A、BVN ，aVT*，則文法，則文法GS稱為稱為3型型文法、文法、正規(guī)正規(guī)文文法或法或右線右線性文法，記為性文法，記為RG。 3型文法相應的語言為型文法相應的語言為3型語言型語言或或正規(guī)語言正規(guī)語言，它的識別系統(tǒng)，它的識別系統(tǒng)是是有限自動機有限自動機。 3型文法還可以型文法還可以呈左線呈左線性形式：性形式：Aa或或ABa第3章語法分析 5四類文法的關系與區(qū)別四類文法的關系與區(qū)別由四類文法的定義可知，從由四類文法的定義可知，從0型文法到型文法到3型文法型文法逐漸逐漸增加限制。

19、增加限制。13型文法都屬于型文法都屬于0型文法，型文法， 2、3型文法型文法不一定屬于不一定屬于1型文法型文法(如果存在形如如果存在形如A的產生式，的產生式，則不屬于則不屬于1型文法型文法)，3型文法屬于型文法屬于2型文法。型文法。 四類文法的四類文法的區(qū)別區(qū)別如下：如下：(1) 1型文法中型文法中不允許有不允許有形如形如“A”的產生式存在，而的產生式存在，而2、3型文法則允型文法則允許形如許形如“A”的產生式存在；的產生式存在；(2) 0、1型文法的型文法的產生式產生式左部存在含有左部存在含有終結符號的符號串或兩個以上的終結符號的符號串或兩個以上的非終結符非終結符，而，而2型和型和3型文法的

20、產生式型文法的產生式左部只允許左部只允許是單個的非終結符號。是單個的非終結符號。第3章語法分析 例例3.3 試判斷下列產生式集所對應的文法和產生的語言：試判斷下列產生式集所對應的文法和產生的語言：(1) SACaB (2) SaSBC (3)SAc (4) SaS CaaaC SaBC SSc SaA CBDB CBDB Aab AbA CBE DBDC AaAb AbB aDDa DCBC BcB ADAC aBab Bc aEEa bBbb AE bCbc cCcc第3章語法分析 解答 由四類文法的定義與區(qū)別可知，(1)(4)分別為03 型文法。 (1) 該 0 型文法產生的 0 型語言為

21、 L0(G)=a2nn0。 例如：當 n=2 時，句子 a22= aaaa ,是通過下列推導得到的： S (1) ACaB (2) AaaCB (3) AaaDB (5) AaDaB (5) ADaaB (6) ACaaB (2) AaaCaB (2) AaaaaCB (4) AaaaaE (7) AaaaEa (7) AaaEaa (7) AaEaaa (7) AEaaaa (8) aaaa 第3章語法分析 (2) 該1型文法產生的1型語言為L1(G)=anbncnn1。 例如，當 n=2 時，句子 a2b2c2=aabbcc 是通過下列推導得到的： S (1) aSBC (2) aaBCB

22、C (6) aabCBC (3) aabDBC (4) aabDCC (5) aabBCC (7) aabbCC (8) aabbcC (9) aabbcc 第3章語法分析 (3) 該2型文法產生的2型語言為L2(G)=anbncmm、n1。例如當 n=2、m=3 時，句子 a2 b2 c3=aabbccc 是通過下列推導得到的： S (2) Sc (2) Scc (1) Accc (4) aAbccc (3) aabbccc 第3章語法分析 (4) 該 3 型文法產生的 3 型語言為 L3(G)=ambnckm、n、k1。例如當 m=2、n=3、k=4 時，句子 a2b3c4=aabbbcc

23、cc 是通過下列推導得到的： S (1) aS (2) aaA (3) aabA (3) aabbA (4) aabbbB (5) aabbbcB (5) aabbbccB (5) aabbbcccB (6) aabbbcccc 第3章語法分析 第3章語法分析 例例3.4 給出字母表給出字母表=a,b上的上的同時同時只有奇數(shù)個只有奇數(shù)個a和奇數(shù)個和奇數(shù)個b的的所有字符串集合的正規(guī)文法。所有字符串集合的正規(guī)文法。解答解答 為了構造字母表為了構造字母表=a,b上同時只有奇數(shù)個上同時只有奇數(shù)個a和奇數(shù)個和奇數(shù)個b的所有字符串的正規(guī)表達式，我們畫出如圖的所有字符串的正規(guī)表達式，我們畫出如圖32所示的所

24、示的DFA，即，即由開始符由開始符S出發(fā)，經過奇數(shù)個出發(fā)，經過奇數(shù)個a到達狀態(tài)到達狀態(tài)A，或經過奇數(shù)個，或經過奇數(shù)個b到達狀到達狀態(tài)態(tài)B。再由狀態(tài)。再由狀態(tài)A出發(fā)，經過奇數(shù)個出發(fā)，經過奇數(shù)個b到達狀態(tài)到達狀態(tài)C(終態(tài)終態(tài))；同樣，由；同樣，由狀態(tài)狀態(tài)B出發(fā)，經過奇數(shù)個出發(fā)，經過奇數(shù)個a到達終態(tài)到達終態(tài)C。第3章語法分析 圖32 例3.4的DFA第3章語法分析 由圖由圖32可直接得到正規(guī)文法可直接得到正規(guī)文法GS如下：如下： GS: SaA bBAaS bC bBbS aC aCbA aB 第3章語法分析 3.1.3 正規(guī)表達式與上下文無關文法正規(guī)表達式與上下文無關文法1正規(guī)表達式到上下文無關文

25、法的轉換正規(guī)表達式到上下文無關文法的轉換2正規(guī)表達式與上下文無關文法描述的對象正規(guī)表達式與上下文無關文法描述的對象第3章語法分析 1正規(guī)表達式到上下文無關文法的轉換正規(guī)表達式到上下文無關文法的轉換正規(guī)表達式所描述的正規(guī)表達式所描述的語言結構語言結構均均可以可以用用上下文無關文法上下文無關文法描述，描述，反之則不反之則不一定。由正規(guī)表達式構造上下文無關文法的一種方法如一定。由正規(guī)表達式構造上下文無關文法的一種方法如下：下：(1) 構造構造正規(guī)表達式的正規(guī)表達式的NFA；(2) 若若0為初始狀態(tài)，則為初始狀態(tài)，則A0為開始符號；為開始符號；(3) 如果存在映射關系如果存在映射關系f(i, a)=

26、j，則定義產生式，則定義產生式Ai aAj；(4) 如果存在映射關系如果存在映射關系f(i, )= j，則定義產生式，則定義產生式Ai Aj；(5) 若若i為終態(tài)，則定義產生式為終態(tài)，則定義產生式Ai 。第3章語法分析 例例3.5 用上下文無關文法描述正規(guī)表達式用上下文無關文法描述正規(guī)表達式(a b)*abb。解答解答 首先構造識別正規(guī)表達式首先構造識別正規(guī)表達式(a b)*abb的的NFA M如圖如圖33所示。所示。由構造上下文無關文法的方法得到上下文無關文法由構造上下文無關文法的方法得到上下文無關文法GA0如如下：下：GA0: A0aA0 bA0 aA1A1bA2A2bA3 A3第3章語法

27、分析 圖33 例3.5的NFA M第3章語法分析 事實上，由正規(guī)表達式構造上下文無關文法還可以采用事實上，由正規(guī)表達式構造上下文無關文法還可以采用另另一種一種方法，即通過方法，即通過分析分析正規(guī)表達式的特性憑經驗直接構造。正規(guī)表達式的特性憑經驗直接構造。 如如可把可把(a b)*abb看作由看作由(a b)*和和abb兩部分組成，兩部分組成， 第一部分第一部分是由是由0個或若干個個或若干個a和和b組成的字符串，組成的字符串， 而而第二部分第二部分則僅由則僅由abb字符串組成，由此得到上下文無關文法字符串組成，由此得到上下文無關文法GA如下：如下： GA: AHT HaH bH Tabb第3章語

28、法分析 2正規(guī)表達式與上下文無關文法描述的對象正規(guī)表達式與上下文無關文法描述的對象上下文無關文法上下文無關文法既既可以可以描述程序語言的語法，描述程序語言的語法，又可以又可以描述程描述程序語言的詞法，但基于下述原因，應采用正規(guī)表達式描述詞法：序語言的詞法，但基于下述原因，應采用正規(guī)表達式描述詞法：(1) 詞法詞法規(guī)則簡單規(guī)則簡單，采用正規(guī)表達式已足以描述；，采用正規(guī)表達式已足以描述；(2) 正規(guī)表達式的表示正規(guī)表達式的表示比比上下文無關文法更加上下文無關文法更加簡潔、直觀和簡潔、直觀和易于理解易于理解；(3) 有限自動機的構造有限自動機的構造比下推自動機簡單且分析效率高。比下推自動機簡單且分析

29、效率高。第3章語法分析 貫穿詞法分析和語法分析始終如一的思想是：貫穿詞法分析和語法分析始終如一的思想是： 語言的語言的描述描述和語言的和語言的識別識別是表示一個語言的是表示一個語言的兩個不同兩個不同的側面，的側面，二者缺一不可。用二者缺一不可。用正規(guī)表達式正規(guī)表達式和和上下文無關文法描述語言上下文無關文法描述語言時的識時的識別方法別方法(即自動機即自動機)不同。不同。 通常，通常，正規(guī)表達正規(guī)表達式適合于描述線性結構，如標識符、關鍵字和式適合于描述線性結構，如標識符、關鍵字和注釋等；注釋等； 而而上下文無關文法上下文無關文法則適合于描述具有嵌套則適合于描述具有嵌套(層次層次)性質的非線性性質的

30、非線性結構，如不同結構的語句結構，如不同結構的語句if-else、while等。等。第3章語法分析 3.2 推導與語法樹推導與語法樹推導與短語推導與短語語法樹與二義性語法樹與二義性第3章語法分析 在此后的討論中，我們用在此后的討論中，我們用大寫字母大寫字母A、B、S、E等表示非終等表示非終結符，結符， 用用小寫字小寫字母母a、b、i、j等表示終結符，等表示終結符， 并用并用希臘字母等希臘字母等表示文法符號串，即表示文法符號串，即、等均屬于等均屬于(VTVN)*。第3章語法分析 3.2.1 推導與短語推導與短語1. 規(guī)范推導規(guī)范推導2. 短語短語3. 句柄句柄4. 素短語素短語第3章語法分析 1

31、規(guī)范推導規(guī)范推導推導序列中的推導序列中的每一步每一步推導都是對句型中的推導都是對句型中的最右最右非終結符用相非終結符用相應產生式的右部進行替換，這樣的推導稱為應產生式的右部進行替換，這樣的推導稱為最右推導最右推導。 如果每一步推導都是對句型中的如果每一步推導都是對句型中的最左最左非終結符用相應產生式非終結符用相應產生式的右部進行替換，則稱為的右部進行替換，則稱為最左推導最左推導。例如句子。例如句子i+i*i按文法按文法(3. .1)的最左推導是的最左推導是 從從一個句型一個句型到到另一個句型另一個句型的推導過程并不的推導過程并不是惟一的是惟一的，為了對句子的結構進，為了對句子的結構進行確定性分

32、析，我們行確定性分析，我們往往往往只考慮只考慮最左最左推導或推導或最右最右推導，并且稱推導，并且稱最右推導最右推導為為規(guī)規(guī)范范推導。規(guī)范推導的推導。規(guī)范推導的逆逆過程便是過程便是規(guī)范歸約規(guī)范歸約。E E + E i+ E i+ E * E i+ i* E i+ i* i 第3章語法分析 第3章語法分析 第3章語法分析 第3章語法分析 第3章語法分析 3.2.2 語法樹與二義性語法樹與二義性1. 語法樹語法樹2. 子樹和短語子樹和短語3. 文法的二義性文法的二義性第3章語法分析 1語法樹語法樹對程序語言來說，有對程序語言來說，有兩個問題需要兩個問題需要解決：解決： 其一其一是判別程序在語法上是否

33、正確；是判別程序在語法上是否正確； 其二其二是句子的識別或分析。是句子的識別或分析。 在在編譯方法編譯方法中，為了便于中，為了便于識別或分析句子識別或分析句子而引入了而引入了語法樹語法樹這一重要的輔助工具。這一重要的輔助工具。 語法樹語法樹以以圖示化圖示化的形式把的形式把句子句子分解成各個組成部分來描述分解成各個組成部分來描述或分析句子的語法結構，這種圖示化的表示與所定義的或分析句子的語法結構，這種圖示化的表示與所定義的文法文法規(guī)規(guī)則完全一致，但更為則完全一致，但更為直觀和完整直觀和完整。第3章語法分析 對文法對文法GS=(VT,VN,S,) ，滿足滿足下列條件的下列條件的樹樹稱為稱為GS的的

34、語法樹：語法樹：(1) 每個結點每個結點用用GS的一個的一個終結終結符或符或非終結符非終結符標記；標記；(2) 根結點根結點用文法開始符用文法開始符S標記；標記；(3) 內部結點內部結點(指非樹葉結點指非樹葉結點)一定是非終結符，如果某一定是非終結符，如果某內部內部結點結點A有有n個分支個分支，它的所有，它的所有子結點子結點從左至右依次標記為從左至右依次標記為x1、x2、xn，則則Ax1x2xn一定是文法一定是文法GS的的一條一條產生式；產生式；(4) 如果如果某結點某結點標記為標記為，則它必為葉結點且是其父結點的，則它必為葉結點且是其父結點的惟一子惟一子結點。結點。第3章語法分析 相應于一個

35、相應于一個句型句型的語法樹是以文法的的語法樹是以文法的開始符開始符S作為根結點的，作為根結點的，并并隨著隨著推導逐步展開；推導逐步展開； 當當某個某個非終結符被它對應的產生式右部的某個候選式所非終結符被它對應的產生式右部的某個候選式所替換替換時，這個時，這個非終結符非終結符所對應的結點就所對應的結點就產生出下產生出下一代新結點，即候選一代新結點，即候選式中式中從左至右從左至右的每一個符號都依次順序對應一個新結點，且每個的每一個符號都依次順序對應一個新結點，且每個新結點與其父結點之間都有一條連線新結點與其父結點之間都有一條連線(樹枝樹枝)。 在一棵語法樹生長過程中的在一棵語法樹生長過程中的任何任

36、何時刻，所有時刻，所有那些沒有那些沒有后代的后代的樹葉結點樹葉結點自左至右自左至右排列排列起來就是一個起來就是一個句型句型。例如，與文法例如，與文法(3.1)的句子的句子i+i*i相應的相應的語法樹語法樹如圖如圖34所示。所示。第3章語法分析 圖3-4 句子i+i*i的語法樹第3章語法分析 在構造語法樹時可以發(fā)現(xiàn)，一個句型的在構造語法樹時可以發(fā)現(xiàn)，一個句型的最左最左推導及推導及最右最右推導推導只決定只決定先先生長左子樹生長左子樹還是還是先生長右子樹，句型推導結束時相應的先生長右子樹，句型推導結束時相應的語法樹也隨之完成，這時已不能看出是先生長左子樹還是先生長語法樹也隨之完成，這時已不能看出是先

37、生長左子樹還是先生長右子樹，所呈現(xiàn)的僅僅是已經長成的這個句子或句型的語法樹。右子樹，所呈現(xiàn)的僅僅是已經長成的這個句子或句型的語法樹。 這與這與使用文法規(guī)則使用文法規(guī)則進行推導是有差異的，即使用文法規(guī)則的進行推導是有差異的，即使用文法規(guī)則的推導過程是有先后之分的。因此，一棵推導過程是有先后之分的。因此，一棵語法樹語法樹表示了一個表示了一個句型種句型種種可能的種可能的(但未必是所有的但未必是所有的見下面文法的二義性見下面文法的二義性)不同推導過不同推導過程，包括最左程，包括最左(最右最右)推導。推導。 如果我們堅持使用如果我們堅持使用最左最左(或最右或最右)推導推導，那么一棵語法樹就完全，那么一棵

38、語法樹就完全等價于一個最左等價于一個最左(或最右或最右)推導，這種等價性也包括語法樹的每一推導，這種等價性也包括語法樹的每一步生長和推導的每一步展開的這種完全一致性。步生長和推導的每一步展開的這種完全一致性。第3章語法分析 2子樹和短語子樹和短語語法樹的語法樹的某個結點連同某個結點連同它的它的所有后代所有后代組成了一棵組成了一棵子樹子樹。只。只含有單層含有單層分枝分枝的子樹稱為簡單子樹。的子樹稱為簡單子樹。子樹子樹與與短語短語的關系的關系十分十分密切，根據(jù)子樹的概念，句型的短密切，根據(jù)子樹的概念，句型的短語、直接短語、句柄和素短語的直觀解釋如下：語、直接短語、句柄和素短語的直觀解釋如下：(1)

39、 短語短語：子樹的末端結點：子樹的末端結點(即樹葉即樹葉)組成的符號串是相對于組成的符號串是相對于子樹根的短語；子樹根的短語；(2) 直接短語直接短語：簡單子樹的末端結點組成的符號串是相對于：簡單子樹的末端結點組成的符號串是相對于簡單子樹根的直接短語；簡單子樹根的直接短語；(3) 句柄句柄：最左簡最左簡單子樹的末端結點組成的符號串為句柄；單子樹的末端結點組成的符號串為句柄；(4) 素短語素短語：子樹的末端結點組成的：子樹的末端結點組成的含含終結符的符號串，且終結符的符號串，且在該子樹中不再有在該子樹中不再有包含包含含有含有終結符終結符的更小子樹。的更小子樹。第3章語法分析 顯然顯然，從語法樹出

40、發(fā)，從語法樹出發(fā)尋找尋找短語、直接短語、句柄和素短語要短語、直接短語、句柄和素短語要直觀得多。直觀得多。 此外，此外，要注意的是子樹末端結點組成的符號串是指由該子樹要注意的是子樹末端結點組成的符號串是指由該子樹根開始向下生長的根開始向下生長的所有所有末端結點末端結點(即樹葉即樹葉)，該子樹的，該子樹的部分末端結部分末端結點并不是該子樹的短語。點并不是該子樹的短語。對圖對圖35所示的關于句型所示的關于句型E+E*i的的語法樹語法樹來說，它有來說，它有3棵子樹，棵子樹，即即3個個短語，分別為短語，分別為i、E*i和和E+E*i；而直接短語、句柄和素短語；而直接短語、句柄和素短語均為均為i；而；而E

41、+E由于在句型由于在句型E+E*i的限制下只是樹根的限制下只是樹根E的部分末端的部分末端結點，因而不是短語。結點，因而不是短語。但是但是，在圖，在圖36中給出的中給出的E+E+E*i的句型的句型下，下，E+E卻是子結點卻是子結點E的一個直接短語。的一個直接短語。第3章語法分析 圖35 E+E*i的語法樹 第3章語法分析 圖36 E+E+E*i的語法樹 第3章語法分析 3文法的二義性文法的二義性文法文法GS的一個的一個句子句子如果如果能能找到找到兩種兩種不同的不同的最左最左推導推導(或或最最右右推導推導)，或者存在，或者存在兩棵不同兩棵不同的語法樹，則稱這個的語法樹，則稱這個句子句子是是二義性二

42、義性的的。 一個文法如果一個文法如果包含包含二義性的句子，則這個文法是二義性的句子，則這個文法是二義二義文法，文法，否則是無二義文法。否則是無二義文法。例如，對文法例如，對文法(3.1)，句子，句子i+i*i存在著兩種最左推導或最右推存在著兩種最左推導或最右推導，所形成的兩棵不同的語法樹如圖導，所形成的兩棵不同的語法樹如圖37所示。所示。第3章語法分析 圖37 句子i+i*i的兩棵不同的語法樹第3章語法分析 再如，條件語句的再如，條件語句的文法文法GS為為 GS: Sif B S Sif B S else S SA /*A指其它語句指其它語句*/其中，其中，VN = B,S,A，VT = if

43、 , else，則，則句型句型if B if B S else S所所對應的兩棵不同語法樹見圖對應的兩棵不同語法樹見圖38。因此，文法。因此，文法GS是二義性文法。是二義性文法。第3章語法分析 圖38 句型 if B if B S else S 的兩棵不同語法樹第3章語法分析 顯然，二義性文法將給編譯程序的執(zhí)行帶來顯然，二義性文法將給編譯程序的執(zhí)行帶來麻煩麻煩。對于二義。對于二義性文法的句子，當編譯程序對它的結構進行語法分析時，就會產性文法的句子，當編譯程序對它的結構進行語法分析時，就會產生生兩種甚至多種不兩種甚至多種不同的解釋；由于語法結構的這種不確定性，因同的解釋；由于語法結構的這種不確定

44、性，因而必將導致語義處理上的不確定性。而必將導致語義處理上的不確定性。第3章語法分析 4文法二義性的消除文法二義性的消除一個文法是二義性的，并不說明該文法所描述的語言也是二一個文法是二義性的，并不說明該文法所描述的語言也是二義性的。也即，對于一個二義性文法義性的。也即，對于一個二義性文法GS，如果能如果能找到找到一個非二一個非二義性義性文法文法GS，使得使得L(G)=L(G)，則該二義性文法的二義性是，則該二義性文法的二義性是可以消除的?？梢韵?。 如果找不到如果找不到這樣的這樣的GS，則二義性文法描述的語言為，則二義性文法描述的語言為先天先天二二義性的。義性的。第3章語法分析 文法二義性文

45、法二義性消除的方法消除的方法如下：如下：(1) 不改變文法中原有的語法規(guī)則，僅加進一些語法的不改變文法中原有的語法規(guī)則，僅加進一些語法的非形非形式規(guī)定式規(guī)定。 如對文法如對文法(3.1)，不改變已有的四條規(guī)則，不改變已有的四條規(guī)則(即四個產生式即四個產生式)，僅加，僅加進進運算符的優(yōu)先順序和結合運算符的優(yōu)先順序和結合規(guī)則，即規(guī)則，即*優(yōu)先于優(yōu)先于+，且，且*、+都服從左都服從左結合。這樣，對文法結合。這樣，對文法(3.1)中的句子中的句子i+i*i就只有如圖就只有如圖37(a)所示的所示的惟一一棵語法樹。惟一一棵語法樹。第3章語法分析 (2) 構造一個構造一個等價等價的無二義性文法，即把的無二

46、義性文法，即把排除排除二義性的規(guī)則二義性的規(guī)則合并到原有文法中，改寫原有的文法。合并到原有文法中，改寫原有的文法。例如，我們可以將文法例如，我們可以將文法(3.1)改寫為改寫為無二義性無二義性的文法的文法GE如如下：下：GE: EE+T TTT*F F F(E) i此時，此時，句子句子i+i*i就只有如圖就只有如圖39所示的惟一一棵語法樹。所示的惟一一棵語法樹。第3章語法分析 圖39 句子i+i*i的語法樹第3章語法分析 例例3.6 試將如下的二義性文法試將如下的二義性文法GS的的二義二義性消除性消除:GS: Sif b S if b S else S A解答解答 消除消除GS的二義性可采用如

47、下兩種方法：的二義性可采用如下兩種方法：(1) 不改變已有規(guī)則，僅加進一項不改變已有規(guī)則，僅加進一項非形式非形式的語法規(guī)定：的語法規(guī)定：else與與離它最近的離它最近的if匹配匹配(即最近匹配原則即最近匹配原則)， 這樣，這樣，文法文法GS的句子的句子if b if b A else A只對應只對應惟一的一棵語惟一的一棵語法樹法樹(見圖見圖310)。 第3章語法分析 圖310 復合if語句的語法樹 第3章語法分析 (2) 改寫改寫文法文法GS為為GS: SS1 S2 S1if b S1 else S1 A S2if b S if b S1 else S2這是因為引起二義性的原因是這是因為引起二

48、義性的原因是if-else語句的語句的if后可以是任意后可以是任意if型語句，所以型語句，所以改寫改寫文法時規(guī)定文法時規(guī)定if和和else之間只能是之間只能是if-else語句或其語句或其它語句。這樣，改寫后文法它語句。這樣，改寫后文法GS的句子的句子if b if b A else A只對應惟只對應惟一的一棵語法樹一的一棵語法樹(如圖如圖311所示所示)。第3章語法分析 圖311 GS的復合if語句的語法樹 第3章語法分析 我們我們總希望總希望一個文法是無二義性的，這樣，句子的分析可一個文法是無二義性的，這樣，句子的分析可以按以按惟一確定惟一確定的方式進行。但是，文法的的方式進行。但是，文法

49、的二義性是不可判定二義性是不可判定的，的， 即即不存在不存在一種算法，能夠在一種算法，能夠在有限步內有限步內判定一個文法是否為判定一個文法是否為二義性的。二義性的。 有時候，二義性文法也可帶來一定的有時候，二義性文法也可帶來一定的好處好處，如語法分析，如語法分析中二義性文法的應用。中二義性文法的應用。第3章語法分析 3.3 自上而下分析方法自上而下分析方法遞歸下降分析法遞歸下降分析法LL(1)分析法分析法第3章語法分析 自上而下分析自上而下分析就是從文法的就是從文法的開始符出發(fā)開始符出發(fā)并尋找出這樣一個并尋找出這樣一個推導序列：推導序列： 推導出的推導出的句子句子恰為恰為輸入符號輸入符號串；串

50、； 或者說或者說，能否從，能否從根結根結點出發(fā)向下生長出一棵語法樹，其葉點出發(fā)向下生長出一棵語法樹，其葉結點組成的句子結點組成的句子恰為恰為輸入符號串。輸入符號串。 顯然，顯然，語法樹語法樹的的每一步每一步生長生長(每一步推導每一步推導)都以都以能否與輸入能否與輸入符符號串匹配號串匹配為準為準，如果，如果最終句子最終句子得到識別，則證明輸入符號串為得到識別，則證明輸入符號串為該文法的一個句子；該文法的一個句子； 否則，否則，輸入符號串不是該文法的句子。輸入符號串不是該文法的句子。第3章語法分析 3.3.1 遞歸下降分析法遞歸下降分析法1.1.自上而下分析存在的不確定性自上而下分析存在的不確定性

51、 2. 2.確定的自上而下分析確定的自上而下分析 3.3.消除左遞歸消除左遞歸 4.4.消除回溯消除回溯 5.5.遞歸下降分析器遞歸下降分析器第3章語法分析 遞歸下降分析法是一種遞歸下降分析法是一種自上而下自上而下的分析方法，文法的每個的分析方法，文法的每個非終結符對應一個遞歸過程。非終結符對應一個遞歸過程。 分析過程分析過程就是從文法就是從文法開始符出開始符出發(fā)執(zhí)行一組遞歸過程，這樣發(fā)執(zhí)行一組遞歸過程，這樣向下推導向下推導直到直到推出句子；推出句子； 或者說從或者說從根結根結點出發(fā)，點出發(fā)，自上而下自上而下為輸入串尋找一個最左匹為輸入串尋找一個最左匹配序列，建立一棵語法樹。配序列，建立一棵語

52、法樹。第3章語法分析 1自上而下分析存在的不確定性自上而下分析存在的不確定性假定假定文法文法GS為為 SxAy Aab a若輸入串為若輸入串為xay，則其分析過程如下：，則其分析過程如下：(1) 首先首先建立根結點建立根結點S。(2) 文法關于文法關于S的產生式只有一個，也即由的產生式只有一個，也即由S生長的語法樹如生長的語法樹如圖圖312(a)所示，它的第一個終結符所示，它的第一個終結符x與輸入串待分析的字符與輸入串待分析的字符x匹匹配。此時，配。此時，下一個待下一個待分析的字符為分析的字符為a，期待著與語法樹中在，期待著與語法樹中在x右右側且與側且與x相鄰的葉結點相鄰的葉結點A匹配。匹配。

53、第3章語法分析 圖312 試探分析對應的語法樹第3章語法分析 (3) 非終結非終結符符A有兩個候選式，先選用第一個候選式生長的有兩個候選式，先選用第一個候選式生長的語法樹語法樹(如圖如圖312(b)所示所示)；這時語法樹的第二個葉結點；這時語法樹的第二個葉結點a恰與待恰與待分析的字符分析的字符a匹配。匹配。(4) 輸入串輸入串中下一個待分析的字符為中下一個待分析的字符為y，它期待與第三個葉，它期待與第三個葉結點結點b匹配，但匹配時發(fā)現(xiàn)這兩個字符是不同的，即匹配失敗，匹配，但匹配時發(fā)現(xiàn)這兩個字符是不同的，即匹配失敗，這是因為生成這是因為生成A的子樹時所選用的是其第一個候選式。的子樹時所選用的是其

54、第一個候選式。(5) 因不匹配因不匹配而將而將A所生成的這棵子樹注銷，即把匹配指針所生成的這棵子樹注銷，即把匹配指針回退到輸入串的第二個字符回退到輸入串的第二個字符a，也就是恢復與，也就是恢復與A匹配時的現(xiàn)場，匹配時的現(xiàn)場，即即(3)之前。之前。(6) 此時此時A選用選用第二個候選第二個候選式并生長語法樹如圖式并生長語法樹如圖312(c)所示，所示，這時第二個葉結點這時第二個葉結點a與輸入串的第二個葉結點與輸入串的第二個葉結點a匹配。匹配。第3章語法分析 (7) 此時輸入串的下一個待分析字符指向此時輸入串的下一個待分析字符指向y，而語法樹的下一，而語法樹的下一個未匹配的葉結點也為個未匹配的葉結

55、點也為y，兩者兩者恰好匹配。因此，圖恰好匹配。因此，圖312(c)所示所示的語法樹即為輸入串的語法樹即為輸入串xay的語法樹。的語法樹。顯然，這種自上而下的分析是一個顯然，這種自上而下的分析是一個不斷試探不斷試探的過程；的過程； 也即，在分析過程中，如果出現(xiàn)也即，在分析過程中，如果出現(xiàn)多個產生式多個產生式(即候選式即候選式)可供可供選擇，則逐一試探每一候選式進行匹配，每當一次試探失敗，選擇，則逐一試探每一候選式進行匹配，每當一次試探失敗，就選取下一候選式再進行試探；就選取下一候選式再進行試探； 此時，必須此時，必須回溯回溯到這一次試探的初始現(xiàn)場，包括到這一次試探的初始現(xiàn)場，包括注銷注銷已生長已

56、生長的子樹及將的子樹及將匹配指針調回匹配指針調回到失敗前的狀態(tài)。這種帶回溯的自上到失敗前的狀態(tài)。這種帶回溯的自上而下分析方法實際上是而下分析方法實際上是一種窮舉一種窮舉的的試探試探方法，其分析方法，其分析效率極低效率極低，在實用的編譯程序中很少使用。在實用的編譯程序中很少使用。第3章語法分析 2確定的自上而下分析確定的自上而下分析為了實現(xiàn)確定的為了實現(xiàn)確定的(即無回溯的即無回溯的)自上而下分析，則要求文法滿自上而下分析，則要求文法滿足下述兩個條件：足下述兩個條件：(1) 文法不文法不含左遞歸含左遞歸，即不存在這樣的非終結符號，即不存在這樣的非終結符號A：有：有AA存在或者有存在或者有A ；(2

57、) 無回溯無回溯，對文法的任一非終結符號，當其產生式右部有，對文法的任一非終結符號，當其產生式右部有多個候選多個候選式可供選擇時，各候選式所推出的終結符號串的首字式可供選擇時，各候選式所推出的終結符號串的首字符集合要兩兩不相交。符集合要兩兩不相交。左遞歸是程序語言的語法規(guī)則中并不少見的形式，例如前左遞歸是程序語言的語法規(guī)則中并不少見的形式，例如前述消除了二義性的算術表達式文法的一個規(guī)則：述消除了二義性的算術表達式文法的一個規(guī)則： EE+T /* 簡單表達式簡單表達式簡單表達式簡單表達式+項項 */第3章語法分析 對于回溯，對于回溯， 由上述不確定的自上而下分析示例可知，由于回溯的存在，由上述不

58、確定的自上而下分析示例可知，由于回溯的存在，可能可能在已經做了在已經做了大量大量的語法分析工作之后，的語法分析工作之后，才發(fā)現(xiàn)走才發(fā)現(xiàn)走了一大段了一大段錯路而錯路而必須回頭必須回頭，要把已經做的一大堆語義工作，要把已經做的一大堆語義工作(指中間代碼產指中間代碼產生工作和各種表格的簿記工作生工作和各種表格的簿記工作)推倒重來推倒重來。 回溯回溯使得自上而下語法分析只具有使得自上而下語法分析只具有理論理論意義而無意義而無實際使用實際使用的的價值。價值。 因此，要使自上而下語法分析具有因此，要使自上而下語法分析具有實用性實用性，就必須要，就必須要消除消除回回溯。溯。第3章語法分析 如果對該如果對該左

59、遞歸文法左遞歸文法采用采用自上而下自上而下分析法，分析法， 即首先以即首先以“E+T”中的中的E為目標對為目標對“E+T”進行試探，進而又進行試探，進而又以其中的以其中的E為目標再對選擇為目標再對選擇“E+T”進行試探；進行試探； 也即也即E+TE+T+T E+T+T+T ，這種左遞歸的文法使，這種左遞歸的文法使自上而下分析工作自上而下分析工作陷入無限循環(huán)陷入無限循環(huán)。 也就是說，當試圖用也就是說，當試圖用E去匹配去匹配輸入符號串時會發(fā)現(xiàn)：在沒有輸入符號串時會發(fā)現(xiàn)：在沒有吃吃進進任何輸入符號的情況下，又得任何輸入符號的情況下，又得重新重新要求要求E去進行新的匹配。去進行新的匹配。 因此，使用自

60、上而下分析法因此，使用自上而下分析法首先首先要消除文法的要消除文法的左遞左遞歸性。歸性。第3章語法分析 第3章語法分析 例如，含有例如，含有直接左遞歸直接左遞歸的表達式文法的表達式文法GE為為GE: EE+T TTT*F FF(E) i經過消去直接左遞歸后得到文法經過消去直接左遞歸后得到文法GE為為GE: ETEE+TE TFTT*FT F(E) i (3.2)第3章語法分析 第3章語法分析 第3章語法分析 第3章語法分析 第3章語法分析 (3) 化簡化簡由由(2)所得的文法，即去掉那些從開始符號所得的文法，即去掉那些從開始符號S出發(fā)，出發(fā)，在推導中無法出現(xiàn)的非終結符的產生式在推導中無法出現(xiàn)的