編譯原理語(yǔ)法分析課件

1、第3章 語(yǔ)法分析 語(yǔ)法分析是編譯過(guò)程的核心部分。 語(yǔ)法分析的基本任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析判斷程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。 語(yǔ)言的語(yǔ)法結(jié)構(gòu)用上下文無(wú)關(guān)文法來(lái)描述，因此，語(yǔ)法分析器的任務(wù)本質(zhì)上是按上下文無(wú)關(guān)文法的產(chǎn)生式，確定整個(gè)單詞串是否構(gòu)成語(yǔ)法上正確的程序。 語(yǔ)法分析的方法通常分為兩類(lèi)： 自上而下分析法和自下而上分析法3.1 文法和語(yǔ)言 3.2 推導(dǎo)與語(yǔ)法樹(shù) 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法 3.1 文法和語(yǔ)言 文法是程序語(yǔ)言的生成系統(tǒng)。 自動(dòng)機(jī)是程序語(yǔ)言的識(shí)別系統(tǒng)。 用文法可精確定義一個(gè)語(yǔ)言,并依據(jù)文法構(gòu)造出識(shí)別該語(yǔ)言的自動(dòng)機(jī)。因

2、此,文法對(duì)程序語(yǔ)言和編譯程序的構(gòu)造具有重要意義,如程序語(yǔ)言的詞法可用正規(guī)文法描述,語(yǔ)法可用上下文無(wú)關(guān)文法描述,而語(yǔ)義可借助于上下文有關(guān)文法描述。3.1.1 文法和語(yǔ)言的概念 1語(yǔ)言 通常用表示字母表。 由字母表中字符組成的有窮序列稱(chēng)為上的字符串或字。字母表上的所有字符串(包括空串)組成的集合用*表示。 對(duì)于字母表, *上的任一子集稱(chēng)為上的一個(gè)語(yǔ)言, 記為L(zhǎng), L*。語(yǔ)言L的每個(gè)字符串稱(chēng)為語(yǔ)言L的一個(gè)語(yǔ)句或句子。2. 文法 終結(jié)符是語(yǔ)言不可再分的基本符號(hào),通常為一個(gè)語(yǔ)言的字母表。終結(jié)符代表了語(yǔ)法的最小元素,是一種個(gè)體記號(hào)。 非終結(jié)符也稱(chēng)語(yǔ)法變量, 它代表語(yǔ)法實(shí)體或語(yǔ)法范疇。一個(gè)非終結(jié)符是一個(gè)類(lèi)、

3、一個(gè)集合。 例如, 變量、常量、+、* 等為終結(jié)符，而 “算術(shù)表達(dá)式”為非終結(jié)符, 它代表一定算術(shù)式組成的類(lèi),如i*(i+i)、i+i+i等,即非終結(jié)符代表由終結(jié)符組成且滿足一定規(guī)則的符號(hào)串的集合。 文法可表示為四元組G=(VT,VN,S,), 其中 (1) VT為非空終結(jié)符集; (2) VN為非空非終結(jié)符集,且VTVN=; (3) S為文法開(kāi)始符, SVN; (4)是產(chǎn)生式的非空有限集, 其中每個(gè) 產(chǎn)生式(規(guī)則)記作 或 := 左部(VTVN)+至少含一非終結(jié)符, 右部(VTVN)*。 產(chǎn)生式 (也稱(chēng)產(chǎn)生式規(guī)則或規(guī)則) 是定義語(yǔ)法實(shí)體的一種書(shū)寫(xiě)規(guī)則。一個(gè)語(yǔ)法實(shí)體的相關(guān)規(guī)則可能不止一個(gè), 如:

4、 P1, P2 , Pn 相同左部的產(chǎn)生式可合并為一個(gè): P 1| 2| n 其中, i(i=1,2,n)稱(chēng)為P的候選式。例3.1 試構(gòu)造產(chǎn)生標(biāo)識(shí)符的文法。分析: 用L表示字母,D表示數(shù)字,T表示字母或數(shù)字, 則 Labz D019 TLD 用S表示字母數(shù)字串,則ST是字母數(shù)字串,即 ST | ST 標(biāo)識(shí)符I或?yàn)閱蝹€(gè)字母, 或?yàn)橐蛔帜负?跟字母數(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 寫(xiě)一文法, 使其語(yǔ)言是奇數(shù)集, 但不允 許出現(xiàn)以0打頭的奇數(shù)。解: 將奇數(shù)劃分為

5、三個(gè)部分： 最高位允許出現(xiàn)19,用非終結(jié)符B表示; 中間部分可出現(xiàn)任意多位數(shù)字09, 每一位用非終結(jié)符D表示; 最低位只出現(xiàn)1,3,5,7,9, 用A表示。 由于中間部分可任意位,故需另引入一 非終結(jié)符M,它包括最高位和中間部分。MB最高位中間位DDDA最低位解: 奇數(shù)集文法GN為: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B3. 文法產(chǎn)生的語(yǔ)言 設(shè)G=(VT,VN,S,)且, (VTVN)*, 若存在產(chǎn)生式A, (VTVN)*， 則稱(chēng)A可直接推出, 記為 A 注意與

6、的不同: 是產(chǎn)生式中的定義記號(hào), 表示直接推導(dǎo),是對(duì)文法符號(hào)串A 中A用產(chǎn)生式A的右部替換。關(guān)于推導(dǎo)的兩點(diǎn)說(shuō)明：(1)若1可直接推出2, 2可直接推出3, 即存在一個(gè)自1至n的推導(dǎo)序列: 12 3 n (n0) 則稱(chēng)1可推導(dǎo)出n,記為1 n, 表示從1出發(fā)經(jīng)1步或若干步可推導(dǎo)出n(2)若記1 1, 則1 n表示從1出發(fā),經(jīng)過(guò) 0步或若干步可推導(dǎo)出n, 即1 n意味著或1=n, 或1 n。+0*+例如,考慮算術(shù)表達(dá)式文法GE： EE+EE*E(E)i 非終結(jié)符E代表一類(lèi)算術(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+

7、i*I注意: 在每一步推 導(dǎo)中,只能對(duì)其中一個(gè) 非終結(jié)符用其對(duì)應(yīng)的產(chǎn)生式右部的 一個(gè)候選式來(lái)替換。假定GS是一個(gè)文法, S是其開(kāi)始符號(hào),若S , (VTVN)*,則稱(chēng)是文法GS的一個(gè)句型 ;若S , VT*，則稱(chēng)是文法GS的一個(gè)句子。由上述定義知： 僅含終結(jié)符的句型是一個(gè)句子。 開(kāi)始符S是一個(gè)句型而不是一個(gè)句子。 i+i*i是一個(gè)句子, 也是一個(gè)句型, E+E*E、E+E*i和E+i*i是句型, 但不是一個(gè)句子。* 對(duì)于文法GS, 它所產(chǎn)生的句子的全體稱(chēng)為由文法GS產(chǎn)生的語(yǔ)言,記為L(zhǎng)G。 L(G)= | S 且VT*3.1.2 形式語(yǔ)言分類(lèi) Chomsky于1956年定義了四類(lèi)文法及相應(yīng)的四類(lèi)

8、形式語(yǔ)言, 它對(duì)程序語(yǔ)言的設(shè)計(jì)、編譯方法、計(jì)算復(fù)雜性等方面都產(chǎn)生了重大影響。+1 0型文法與0型語(yǔ)言 (短語(yǔ)文法) 若文法G的每個(gè)產(chǎn)生式具有下列形式: 其中至少含一個(gè)非終結(jié)符， 則稱(chēng)文法G為0型文法或短語(yǔ)文法, 記為PSG。 0型文法相應(yīng)的語(yǔ)言稱(chēng)為0型語(yǔ)言, 它的識(shí)別系統(tǒng)是圖靈機(jī)。21型文法與1型語(yǔ)言 (對(duì)應(yīng)自然語(yǔ)言) 若文法G的每個(gè)產(chǎn)生式均滿足 | | 則稱(chēng)文法G為1型文法或上下文有關(guān)文 法, 記為CSG。 1型文法相應(yīng)的語(yǔ)言稱(chēng)為1型語(yǔ)言。 1型文法的另一種定義: 文法G的每個(gè)產(chǎn)生式具有下列形式： A 其中, ,V*, AVN, V+ 它更明確地表達(dá)了上下文有關(guān)的特性。3 2型文法與2型語(yǔ)言

9、 (對(duì)應(yīng)程序設(shè)計(jì)語(yǔ)言) 若文法G的每個(gè)產(chǎn)生式具有下列形式： A 其中, AVN, V* 稱(chēng)文法G為2型文法或上下文無(wú)關(guān)文法, 記為CFG。 2型文法相應(yīng)的語(yǔ)言稱(chēng)為2型語(yǔ)言或 上下文無(wú)關(guān)語(yǔ)言。 它的識(shí)別系統(tǒng)是下推自動(dòng)機(jī)。4 3型文法與3型語(yǔ)言 (對(duì)應(yīng)有限自動(dòng)機(jī)) 若文法G的每個(gè)產(chǎn)生式具有下列形式： Aa 或 AaB 其中，A,BVN，aVT*， 則文法G稱(chēng)為3型文法或正規(guī)文法或右線 性文法，記為RG。 3型文法相應(yīng)語(yǔ)言為3型語(yǔ)言或正規(guī)語(yǔ)言。 它的識(shí)別系統(tǒng)是有限自動(dòng)機(jī)。 3型文法還可呈左線性形式： Aa 或 ABa5. 四類(lèi)文法的關(guān)系與區(qū)別 從0型文法到3型文法逐步增加限制。 一般地,13型文法屬

10、于0型文法，2,3型文法屬于1型文法,3型文法屬于2型文法。四類(lèi)文法的區(qū)別：(1)1型文法不允許有形如A的產(chǎn)生式, 2,3型文法允許形如A的產(chǎn)生式;(2)0,1型文法的產(chǎn)生式左部可以是含終結(jié) 符的符號(hào)串或兩個(gè)以上的非終結(jié)符, 2,3型文法的產(chǎn)生式左部只允許是單個(gè) 非終結(jié)符。 anbncn|n1anbncm|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ǔ)言 編譯方法中通常用3型文法描述詞法,用FA識(shí)別單詞; 利用2型文法描述語(yǔ)法,用下推自動(dòng)

11、機(jī)PDA識(shí)別各種語(yǔ)法成分。例3.4 給出=a,b上具有奇數(shù)個(gè)a和奇數(shù) 個(gè)b的所有字符串集合的正規(guī)文法。解: 如圖, 由S出發(fā)經(jīng)奇數(shù)個(gè)a到達(dá)A, 或經(jīng)奇數(shù)個(gè)b到達(dá)B。再由A出發(fā)經(jīng)奇數(shù)個(gè)b到達(dá)C; 同樣, 由B出發(fā)經(jīng)奇數(shù)個(gè)a到達(dá)C。正規(guī)文法GS如下: SaA | bB AaS | bC BbS | aC CbA | aB| bbbbaaaaSAB2C3.1.3 正規(guī)式與上下文無(wú)關(guān)文法1. 正規(guī)式到上下文無(wú)關(guān)文法的轉(zhuǎn)換 由正規(guī)式構(gòu)造CFG的一種方法： (1)構(gòu)造正規(guī)式的NFA； (2)若0為初始狀態(tài), 則A0為開(kāi)始符； (3)若存在映射關(guān)系f(i,a)=j, 則定義產(chǎn)生式Ai aAj； (4)若存在

12、映射關(guān)系f(i,)=j， 則定義產(chǎn)生式Ai Aj； (5) 若i為終態(tài), 則定義產(chǎn)生式Ai 。例3.5 用CFG描述正規(guī)式(a|b)*abb解: 先構(gòu)造識(shí)別(a|b)*abb的NFA M:01223ababbGA0: A0aA0bA0aA1 A1bA2 A2bA3 A3由正規(guī)式構(gòu)造CFG的另一種方法： 通過(guò)分析正規(guī)式憑經(jīng)驗(yàn)直接構(gòu)造。例如, 把(a|b)*abb看作(a|b)*和abb兩部分,第一部分是由0個(gè)或若干個(gè)a和b組成的字符串,第二部分僅由abb字符串組成,由此得到CFG GA0如下： GA0: AHT HaH|bH| Tabb2. 正規(guī)式與CFG描述的對(duì)象 CFG既可描述語(yǔ)法,又可描述

13、詞法。 基于下述原因,通常用正規(guī)式描述詞法: (1)詞法規(guī)則簡(jiǎn)單,用正規(guī)式已足以描述; (2)正規(guī)式的表示比CFG更簡(jiǎn)潔、直觀 和易于理解； (3) FA的構(gòu)造比PDA(下推自動(dòng)機(jī))的構(gòu) 造簡(jiǎn)單且效率高。 注意: (1)語(yǔ)言的描述和語(yǔ)言的識(shí)別是表示一種語(yǔ)言的兩個(gè)不同側(cè)面, 二者缺一不可。 (2)正規(guī)式通常適合于描述線性結(jié)構(gòu), 如標(biāo)識(shí)符、關(guān)鍵字和注釋等; 上下文無(wú)關(guān)文法通常適合于描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu), 如 if-else語(yǔ)句、while語(yǔ)句。3.2 推導(dǎo)與語(yǔ)法樹(shù)3.2.1 推導(dǎo)與短語(yǔ)1. 規(guī)范推導(dǎo) 最右推導(dǎo): 在推導(dǎo)過(guò)程中,若每一步推導(dǎo)都是對(duì)句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部

14、進(jìn)行替換, 則稱(chēng)這種推導(dǎo)為最右推導(dǎo)。 最左推導(dǎo): 在推導(dǎo)過(guò)程中,若每一步推導(dǎo)都是對(duì)句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換, 則稱(chēng)這種推導(dǎo)為最左推導(dǎo)。例如, 考慮句子 i+i*i 按文法GE的推導(dǎo) 最左推導(dǎo): EE+Ei+Ei+E*E i+i*E i+i*i 最右推導(dǎo): EE+EE+E*EE+E*i E+i*ii+i*i注意: 推導(dǎo)過(guò)程不唯一, 通常只考慮最左 推導(dǎo)或最右推導(dǎo)。 最右推導(dǎo)又稱(chēng)為規(guī)范推導(dǎo)。 規(guī)范推導(dǎo)的逆過(guò)程稱(chēng)為規(guī)范歸約。2. 短語(yǔ) 如果S A且A , 則稱(chēng)是句型關(guān)于非終結(jié)符A的一 個(gè)短語(yǔ),簡(jiǎn)稱(chēng)是的一個(gè)短語(yǔ)。 如果S A且A , 則稱(chēng)為句型的一個(gè)直接短語(yǔ)或 簡(jiǎn)單短語(yǔ)。注意:

15、短語(yǔ)的兩個(gè)條件缺一不可。 考慮i+i*i, E i+i, 但i+i不是短語(yǔ) *+*+3. 句柄 句型的最左直接短語(yǔ)稱(chēng)為句柄。 注意, 一個(gè)句型的直接短語(yǔ)不唯一, 但最左直接短語(yǔ)唯一。 例如, 對(duì)S A , 若為終結(jié)符串, 則句型中的句柄為。 將句型中的句柄用產(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的短語(yǔ), 其中, i為素短語(yǔ), E*i雖含終結(jié)符, 但其 真子串i含終結(jié)符, 故E*i不是素短語(yǔ), 同樣

16、E+E*i也不是素短語(yǔ)。+3.2.2 語(yǔ)法樹(shù)與二義性1. 語(yǔ)法樹(shù) 對(duì)于程序語(yǔ)言, 有兩個(gè)問(wèn)題需要解決: (1)判別程序在語(yǔ)法上是否正確; (2)句子的識(shí)別或分析。 為便于分析句子而引入語(yǔ)法樹(shù)。 語(yǔ)法樹(shù)以圖示化形式把句子分解成各 個(gè)組成部分,以分析句子的語(yǔ)法結(jié)構(gòu)。 語(yǔ)法樹(shù)表示法與文法規(guī)則完全一致,但 更為直觀和完整。滿足下列條件的樹(shù)稱(chēng)為文法G的語(yǔ)法樹(shù):(1)每個(gè)結(jié)點(diǎn)用G的一個(gè)終結(jié)符或非終結(jié) 符標(biāo)記;(2)根結(jié)點(diǎn)用文法開(kāi)始符S標(biāo)記;(3)內(nèi)部結(jié)點(diǎn)一定是非終結(jié)符,若某內(nèi)部結(jié) 點(diǎn)A有n個(gè)分支, 且其所有子結(jié)點(diǎn)從左 至右依次標(biāo)記為x1, x2, ,xn,則 Ax1x2xn一定是G的一條產(chǎn)生式;(4)若某

17、結(jié)點(diǎn)標(biāo)記為,則它必為葉結(jié)點(diǎn)且 是其父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。 一個(gè)句型對(duì)應(yīng)的語(yǔ)法樹(shù)以文法開(kāi)始符S作為根結(jié)點(diǎn),并隨著推導(dǎo)逐步展開(kāi)。當(dāng)某非終結(jié)符被產(chǎn)生式右部的某候選式替換時(shí),該非終結(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ǔ)法樹(shù)生長(zhǎng)過(guò)程中的任何時(shí)刻,所有沒(méi)有后代的葉結(jié)點(diǎn)的自左至右排列是一個(gè)句型。 例如,句子i+i*i的語(yǔ)法樹(shù)如下:EEEE*Eiii第一代第二代第三代第四代 構(gòu)造語(yǔ)法樹(shù)時(shí), 一個(gè)句型的最左推導(dǎo)及最右推導(dǎo)只決定先生長(zhǎng)左子樹(shù)還是先生長(zhǎng)右子樹(shù), 推導(dǎo)結(jié)束時(shí)相應(yīng)的語(yǔ)法樹(shù)已看不出先生長(zhǎng)的是哪個(gè)子樹(shù)。 因此, 一棵語(yǔ)

18、法樹(shù)表示一個(gè)句型種種可能的不同推導(dǎo)過(guò)程, 包括最左(最右)推導(dǎo)。若堅(jiān)持使用最左(最右)推導(dǎo), 則一棵語(yǔ)法樹(shù)等價(jià)于一個(gè)最左(最右)推導(dǎo), 這種等價(jià)性包括語(yǔ)法樹(shù)的每一步生長(zhǎng)和推導(dǎo)過(guò)程的每一步展開(kāi)的完全一致性。2. 子樹(shù)和短語(yǔ) 語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)連同它的所有后代組 成了一棵子樹(shù)。 只含有單層分枝的子樹(shù)稱(chēng)為簡(jiǎn)單子樹(shù)。 子樹(shù)與短語(yǔ)的關(guān)系: (1)短語(yǔ): 子樹(shù)的所有葉結(jié)點(diǎn)組成的符號(hào) 串是相對(duì)于子樹(shù)根的短語(yǔ)； (2)直接短語(yǔ): 簡(jiǎn)單子樹(shù)的所有葉結(jié)點(diǎn)組 成的符號(hào)串是直接短語(yǔ); (3)句柄: 最左簡(jiǎn)單子樹(shù)的所有葉結(jié)點(diǎn)組 成的符號(hào)串為句柄; (4)素短語(yǔ): 子樹(shù)的所有葉結(jié)點(diǎn)組成的 含終結(jié)符的符號(hào)串, 且在該子樹(shù)中

19、沒(méi)有有包含終結(jié)符的更小子樹(shù)。 顯然, 從語(yǔ)法樹(shù)出發(fā)尋找短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)直觀得多。但要注意, 子樹(shù)葉結(jié)點(diǎn)組成的符號(hào)串是指由該子樹(shù)根開(kāi)始向下生長(zhǎng)的所有葉結(jié)點(diǎn),該子樹(shù)的部分葉結(jié)點(diǎn)并不是該子樹(shù)的短語(yǔ)?？紤]句型E+E*i的語(yǔ)法樹(shù):短語(yǔ): i、E*i和E+E*i; 直接短語(yǔ): i; 句柄: i; 素短語(yǔ): iEEEE*Ei3. 文法的二義性 若文法G的一個(gè)句子能找到兩種不同的最左推導(dǎo)(最右推導(dǎo)), 即存在兩棵不同的語(yǔ)法樹(shù), 則稱(chēng)這個(gè)句子是二義性的。 若一個(gè)文法包含二義性句子, 則這個(gè)文法是二義文法, 否則是無(wú)二義文法。 例如, 對(duì)文法(3.1),句子i+i*i存在兩種最左(右)推導(dǎo):EEEE*

20、EiEEEE*Eiii(a)ii(b)再如,條件語(yǔ)句文法GS: GS: Sif B S Sif B S else S SA /A指其它語(yǔ)句 其中, VN =B,S,A, VT =if, else 文法GS的一個(gè)句型if B if B S else S對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù), 如下圖所示, 因此,文法GS是二義性文法。SifS(a)(b)BSifSelseBSBSifSelseifSB4. 文法二義性的消除 一個(gè)文法是二義性的, 并不說(shuō)明文法所描述的語(yǔ)言是二義性的。即對(duì)于一個(gè)二義文法GS, 若能找到一個(gè)非二義文法GS, 使得L(G)=L(G), 則該二義文法的二義性可以消除。若找不到這樣的GS,則

21、二義文法描述的語(yǔ)言為先天二義性的。文法二義性的消除方法:(1)不改變文法中原有的語(yǔ)法規(guī)則, 僅加進(jìn) 一些語(yǔ)法的非形式規(guī)定。 如對(duì)文法(3.1), 不改變已有產(chǎn)生式, 僅加 進(jìn)運(yùn)算符的優(yōu)先順序和結(jié)合規(guī)則, 即 *優(yōu)先于+, 且*,+都服從左結(jié)合。(2)構(gòu)造一個(gè)等價(jià)的無(wú)二義文法。即把排除 二義性的規(guī)則合并到原文法中, 改寫(xiě)原 文法。GE: EE+TT TT*FF F(E)i此時(shí),句子i+i*i只有唯一 一棵語(yǔ)法樹(shù)。 例如, 將文法(3.1)改寫(xiě)為無(wú)二義文法GE:EETFTFiiTFi*例3.6 將下述文法GS的二義性消除: GS: Sif b Sif b S else SA解: 消除GS的二義性可

22、采用兩種方法:(1)不改變已有規(guī)則, 僅加 進(jìn)一項(xiàng)非形式的語(yǔ)法規(guī) 定: else與離它最近的if 匹配, 這樣, 句子if b if b A else A對(duì)應(yīng)唯一的一 棵語(yǔ)法樹(shù)。SbSifSelseAAbifS(2)改寫(xiě)文法GS為GS: SS1| S2 S1if b S1 else S1|A S2if b S|if b S1else S2 由于引起二義性的原因是if-else語(yǔ)句的if后可以是任意if語(yǔ)句, 故改寫(xiě)文法時(shí)規(guī)定if和else之間只能是if-else語(yǔ)句或其它語(yǔ)句。S1bS1ifS1elseAAbifSS2S 編譯過(guò)程中希望一個(gè)文法是無(wú)二義性的, 這樣句子的分析可按唯一確定的方式進(jìn)

23、行。但文法的二義性是不可判定的, 即不存在一種算法能在有限步內(nèi)判定一個(gè)文法是否為二義性的。不過(guò), 二義文法有時(shí)也可帶來(lái)一定好處, 如語(yǔ)法分析中二義文法的應(yīng)用。3.3 自上而下分析方法 自上而下分析從文法開(kāi)始符出發(fā), 向下推導(dǎo), 推出句子。即尋找一個(gè)推導(dǎo)序列, 使推導(dǎo)出的句子恰為輸入串; 亦即,從根結(jié)點(diǎn)出發(fā)向下生長(zhǎng)出一棵語(yǔ)法樹(shù),其葉結(jié)點(diǎn)組成的句子恰為輸入串。 顯然, 語(yǔ)法樹(shù)的每一步生長(zhǎng)(推導(dǎo))都以能否與輸入串匹配為準(zhǔn)。1. 自上而下分析存在的不確定性 文法GS: SxAy Aaba 若輸入串為xay, 則其分析過(guò)程如下: (1)首先建立根結(jié)點(diǎn)S。 (2)文法關(guān)于S的產(chǎn)生式只有一個(gè)。yAxS 下一

24、待分析字符a與A匹配。 (3)非終結(jié)符A有兩個(gè)候選式, 先選用第一個(gè)候選式:yAxSab (4)下一待分析字符y與b匹配, 失敗。 (5)將A生成的子樹(shù)注銷(xiāo), 指針回退到輸 入串的第二個(gè)字符a。 (6) A選用第二個(gè)候選式:yAxSa 這時(shí)輸入串中a與葉結(jié)點(diǎn)a匹配。 (7) 下一個(gè)待分析字符為y, 而語(yǔ)法樹(shù)下 一個(gè)葉結(jié)點(diǎn)也為y, 匹配成功。 在上述分析過(guò)程中, 若有多個(gè)候選式可供選擇, 則逐一試探每個(gè)候選式。一次試探失敗時(shí), 必須回溯到該試探的初始現(xiàn)場(chǎng), 包括注銷(xiāo)已生長(zhǎng)子樹(shù)、指針回退到失敗前狀態(tài)。這種帶回溯的自上而下分析方法是一種窮舉法, 效率極低, 在實(shí)用編譯程序中很少使用。2. 確定的自上

25、而下分析 實(shí)現(xiàn)確定的自上而下分析需滿足條件: (1)文法不含左遞歸。 左遞歸: AA 或 A A 左遞歸的存在可能使自上而下分析過(guò)程陷入無(wú)限循環(huán), 故使用自上而下分析法必須消除文法的左遞歸。 (2)分析過(guò)程無(wú)回溯。 回溯的存在可能使已做的大量語(yǔ)法和語(yǔ)義分析推倒重來(lái), 這會(huì)嚴(yán)重影響效率, 故使用自上而下分析法必須消除回溯。+ 3. 左遞歸的消除直接左遞歸的消除 方法: 引入一個(gè)新的非終結(jié)符,把含有 左遞歸的產(chǎn)生式改寫(xiě)為右遞歸形式。 例如: AA | , 是任意串且不以A開(kāi)頭。 A的產(chǎn)生式可改寫(xiě)為: AA AA| 例如, 算術(shù)表達(dá)式文法GE為: GE: EE+T | T TT*F | F F(E)

26、 | i消去直接左遞歸后得到文法GE: GE: ETE E+TE | TFT T*FT | F(E) | i一般地, 設(shè)文法中A的產(chǎn)生式為: AA1|A2|Am| 1|2|n 其中,每個(gè)都不等于 每個(gè)都不以A開(kāi)頭消除A的直接左遞歸, 文法可改寫(xiě)為: A1A | 2A | nA A1A | 2A |mA | 例如, 試消除EE+T|ET|T的左遞歸。解: 消除左遞歸后變?yōu)?ETE E+TE | TE | 間接左遞歸的消除 例如, 文法GS: SQc | c QRb | b RSa | a 如何消除文法的間接左遞歸？ 間接左遞歸的存在是由于非終結(jié)符之間形成了循環(huán)推導(dǎo), 只要把循環(huán)推導(dǎo)中的某個(gè)連接切

27、斷, 間接左遞歸就消除了。切斷循環(huán)推導(dǎo)中的某個(gè)連接的方法：Step1. 對(duì)n個(gè)產(chǎn)生式中的某一個(gè)進(jìn)行至多 n-1次替換, 使間接左遞歸變成直 接左遞歸, 再消除之。例如, 消除上述文法GS中S,Q間的連接: S Qc|c Rbc|bc|c Sabc|abc|bc|c 改寫(xiě)為: SabcS|bcS|cS SabcS| 消除左遞歸還需消除Q,R間的連接: Q Rb|b Sab|ab|Qab|b 再消除其直接左遞歸Step2. 對(duì)其余n-1個(gè)產(chǎn)生式中的某一個(gè)進(jìn)行 至多n-2次替換,再消除直接左遞歸。 考慮上述文法的后兩個(gè)產(chǎn)生式: QRb | b RSa | a | Qa消除左遞歸算法:(1)文法的所有

28、非終結(jié)符排序?yàn)锳1,A2,An;(2)將間接左遞歸改為直接左遞歸,消除之; for (i=1; i=n; i+) for (j=1; j=i1; j+) 把AiAj| 及Aj1|k 改寫(xiě)為Ai1|k| ; 消除Ai的直接左遞歸; (3)化簡(jiǎn), 刪去那些不可達(dá)元的產(chǎn)生式。通過(guò)例子熟悉消除左遞歸算法執(zhí)行過(guò)程:例如, GS: SQc | c QRb | b RSa | a(1) 將非終結(jié)符排序?yàn)镽, Q, S;(2) 對(duì)于R (i=1, P1) 內(nèi)層循環(huán)不執(zhí)行; 消除R的直接左遞歸: RSa|a 對(duì)于Q (i=2, P2) 內(nèi)層循環(huán)改寫(xiě)P2 P1: QSab|ab|b 消除Q的直接左遞歸: QSab

29、|ab|b 對(duì)于S (i=3, P3) 內(nèi)層循環(huán)改寫(xiě)P3P1和P3P2: SSabc | abc | bc | c 消除S的直接左遞歸: SabcS | bcS | cS SabcS | 于是得文法GS: SabcS | bcS | cS SabcS | QSab | ab | b RSa | a(3) 化簡(jiǎn), 刪去關(guān)于Q和R的產(chǎn)生式。對(duì)消除左遞歸算法的兩點(diǎn)說(shuō)明: (1)消除左遞歸算法有兩個(gè)限制條件:文法中不含回路(P P)和-生成式。該限制不會(huì)影響消除左遞歸算法的使用,因?yàn)楹罄m(xù)課程形式語(yǔ)言中將學(xué)到,對(duì)任一CFG G, 存在一個(gè)不含-生成式和單一生成式的CFG G, 使得L(G)=L(G)-。

30、 (2) 對(duì)非終結(jié)符的不同排序會(huì)導(dǎo)致文法形式上的不同, 但可證明它們等價(jià)。上例若排序?yàn)镾,Q,R, 則得文法GS: SQc | c QRb | b RbcaR |caR |aR RbcaR | GS與GS等價(jià)的證明: 證明: Sabc(abc)*|bc(abc)*|c(abc)* L(G)=(abc|bc|c)(abc)i | i0 Sbca(bca)*bc|ca(bca)*bc| a(bca)*bc|bc|c L(G)=(abc|bc|c)(abc)i | i0 有興趣的同學(xué)課后以下述文法為例熟悉消除左遞歸算法的執(zhí)行過(guò)程: GS: SQc | c | Rc QRb | b | Sb RSa

31、| a | Qa GS: SQc | c | Rc | Sc QRb | b | Sb | Qb RSa | a | Qa | Ra 2. 回溯的消除 要消除回溯,首先要清楚回溯存在的原因, 根除這些原因,自然就消除了回溯。 假設(shè)輪到用A去執(zhí)行匹配任務(wù), A1| 2|n, 而A面臨的第1個(gè)輸入符為a1。首先, 用1的第1終結(jié)符與輸入符a1匹配,若成功,再用1的第2終結(jié)符與下一輸入符a2匹配, 當(dāng)1的第n終結(jié)符與當(dāng)前輸入符an匹配不成功時(shí),說(shuō)明1與輸入串不匹配, 此時(shí)需把關(guān)于1的分析過(guò)程推倒,回到用1匹配前的狀態(tài)。同樣地,用2與輸入串匹配,。 可見(jiàn), 回溯的存在是由于分析過(guò)程中需對(duì)產(chǎn)生式的多個(gè)候

32、選式進(jìn)行試探性匹配。若能根據(jù)面臨的輸入符從產(chǎn)生式的多個(gè)候選式中選出一個(gè)作為全權(quán)代表,使得若該候選式與輸入串匹配成功,則A與輸入串匹配成功, 若該候選式與輸入串匹配不成功,則A與輸入串匹配不成功, 這樣就可以消除回溯。如何從多個(gè)候選式中選出一個(gè)全權(quán)代表? 例如, AaA | bB | cC a A1| 2|n a 若A的n個(gè)候選式中只有一個(gè)推出的終結(jié)符串的首字符包含a (設(shè)為i), 則候選式i可作為A的全權(quán)代表。 這就要求匹配前先求出各個(gè)候選式所能推出的所有終結(jié)符串的首字符, 即候選式的終結(jié)首符集FIRST()。 終結(jié)首符集FIRST() 令G是一個(gè)無(wú)左遞歸文法, 對(duì)G的所有非終結(jié)符的每個(gè)候選式

33、, 定義 FIRST()a | a, aVT 若 , 則FIRST()* 即FIRST()是由所能推出的的所有 終結(jié)符串的首字符或。 A1| 2|n FIRST(A)=FIRST(1)FIRST(2) 對(duì)于A1| 2|n 若A有多個(gè)候選式的終結(jié)首符集含a, 則仍需進(jìn)行試探, 此時(shí)只是減少了回溯次數(shù), 并未消除回溯。要消除回溯, 準(zhǔn)確地指派一個(gè)候選式去執(zhí)行匹配任務(wù), 則各個(gè)候選式的終結(jié)首符集應(yīng)互不相交, 即 FIRST(i)FIRST(j)= (ij) 如何使每個(gè)非終結(jié)符的候選終結(jié)首符集互不相交? 方法是提取公共左因子。 提取公共左因子例如, AabA | aB | ab 改寫(xiě)文法: AaA A

34、bA | B | b改寫(xiě)第2式: AbA | B AA | 一般地, 假設(shè)文法中關(guān)于A的產(chǎn)生式為 A1|2|i | i+1|j提取公共左因子后, 改寫(xiě)為 AA | i+1| j A1| 2| | i 經(jīng)過(guò)反復(fù)提取公共左因子,可使每個(gè)非終結(jié)符的候選終結(jié)首符集互不相交。 消除左遞歸和提取公共左因子后, 文法不再含左遞歸且任一非終結(jié)符的候選終結(jié)首符集互不相交。此時(shí),若不屬于任一非終結(jié)符的候選終結(jié)首符集, 則可進(jìn)行有效的LL(1)分析了。然而,消除左遞歸和提取左因子后, 文法中引進(jìn)了大量-生成式, 這就引出自動(dòng)匹配問(wèn)題。3. 自動(dòng)匹配問(wèn)題對(duì)于文法GE: ETE E+TE | TFT T*FT | F(

35、E) | i考慮輸入串i+i #EETFTT+Ei FTi 當(dāng)A面臨輸入符a時(shí), 若aFIRST(A)且FIRST(A), 則考慮自動(dòng)匹配問(wèn)題。 對(duì)于上述算術(shù)表達(dá)式文法,若輸入串為i/i, 即使讓T自動(dòng)匹配, “/”仍不能與后面符號(hào)匹配, 此時(shí)沒(méi)必要讓T自動(dòng)匹配。 結(jié)論: 只有在當(dāng)前輸入符能與A后的第一個(gè)終結(jié)符匹配成功時(shí),才讓A自動(dòng)得到匹配。這就要求分析前先求出緊跟在A后的終結(jié)符, 即FOLLOW(A)。 FOLLOW(A)的定義 對(duì)文法GS的任一非終結(jié)符A, 定義 FOLLOW(A)a|S Aa,aVT 若S A, 則規(guī)定#FOLLOW(A)* 即FOLLOW(A)是所有句型中緊跟在 A之后

36、的終結(jié)符 或 # 。0 因S S, 故#FOLLOW(S)自動(dòng)匹配條件 當(dāng)A面臨輸入符a時(shí),若aFIRST(A)且FIRST(A), 則只有當(dāng)aFOLLOW(A)時(shí),才使A自動(dòng)得到匹配。缺少任一條件,均不自動(dòng)匹配。 若輸入符aFIRST(A)且aFOLLOW(A), 則當(dāng)FIRST(A)時(shí)仍需進(jìn)行試探(回溯)。因此,對(duì)于存在-生成式的非終結(jié)符A,若要進(jìn)行不帶回溯的自上而下分析,則FIRST(A)與FOLLOW(A)應(yīng)互不相交。 5. 遞歸下降分析器 遞歸下降分析法是一種自上而下分析法,文法的每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸過(guò)程。分析過(guò)程從文法開(kāi)始符出發(fā),執(zhí)行一組遞歸過(guò)程, 這樣向下推導(dǎo)直到推出句子。

37、若文法不含左遞歸且每個(gè)非終結(jié)符的候選式無(wú)公共左因子, 則可構(gòu)造不帶回溯的遞歸下降分析程序, 該程序由一組過(guò)程組成, 每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的分析程序稱(chēng)為遞歸下降分析器。例如, 考慮不含左遞歸的算術(shù)表達(dá)式, 其對(duì)應(yīng)的遞歸下降分析器: void E( ) T( ); E( ); void E( ) if (lookahead = = +) match (+); T( ); E( ); void T() F(); T(); void T() if (lookahead = =*) match (*); F(); T(); void F() if (lookahead = = i) ma

38、tch (i); else if (lookahead = =() match (); E( ); if (lookahead = =) match (); else error (); error ();說(shuō)明: 考慮E的產(chǎn)生式: E+TE | E有兩個(gè)候選式,當(dāng)E面臨輸入符+時(shí)令第一個(gè)候選工作,當(dāng)面臨其它符號(hào)時(shí), E自動(dòng)獲得匹配。遞歸函數(shù)E根據(jù)這一原則設(shè)計(jì)。 假定遞歸函數(shù)的調(diào)用以棧的形式來(lái)模擬, 下面分析輸入串 # i1*(i2+i3)# 的語(yǔ)法分析過(guò)程, “#”為分隔符。 進(jìn)行語(yǔ)法分析時(shí),首先將“#”和文法開(kāi)始符E壓入棧中,當(dāng)語(yǔ)法分析進(jìn)行到棧中僅?！?”而輸入串掃描指針已指向輸入串尾部的“

39、#”時(shí),則語(yǔ)法分析成功。分析過(guò)程如圖3-12所示。 3.3.2 LL(1)分析法 LL(1)分析法又稱(chēng)預(yù)測(cè)分析法, 是一種不帶回溯的非遞歸自上而下分析法。 LL(1)的含義: 第一個(gè)L表明自左至右掃描輸入串; 第二個(gè)L表明最左推導(dǎo); 1表明向右查看一個(gè)符號(hào)。 類(lèi)似地, 可有LL(k)文法, 即向前查看k個(gè)符號(hào)才能確定選用哪個(gè)產(chǎn)生式, 不過(guò)LL(k) (k1)在實(shí)際中極少使用。1. 表驅(qū)動(dòng)的LL(1)分析器 LL(1)分析法的基本思想: 根據(jù)輸入串的當(dāng)前輸入符確定選用某一個(gè)產(chǎn)生式進(jìn)行推導(dǎo), 當(dāng)該輸入符與推導(dǎo)的第一個(gè)符號(hào)相同時(shí)，再取輸入串的下一個(gè)符號(hào), 繼續(xù)確定下一個(gè)推導(dǎo)應(yīng)選的產(chǎn)生式, 如此下去,

40、 直到推出被分析的輸入串為止。 一個(gè)LL(1)分析器由一張LL(1)分析表(預(yù)測(cè)分析表)、一個(gè)先進(jìn)后出分析棧和一個(gè)控制程序(表驅(qū)動(dòng)程序)組成。 a1a2aian#分析表M控制程序輸入串：棧頂#x1xj輸出分析棧圖314 LL(1)分析器對(duì)圖314的LL(1)分析器說(shuō)明如下： (1)輸入串是待分析的符號(hào)串,它以“#”作為結(jié)束標(biāo)志。(注: #VT但不是文法符號(hào), 是由分析程序自動(dòng)添加的) (2)分析棧存放分析過(guò)程中的文法符號(hào)。分析開(kāi)始時(shí)棧底先放一個(gè)“#”,再壓入文法開(kāi)始符; 當(dāng)分析棧中僅?！?”且輸入串指針指向串尾的“#”時(shí), 分析成功。 (3)分析表用一個(gè)矩陣M(二維數(shù)組) 表示,它概括了文法的

41、全部信息。矩陣的每一行與文法的一個(gè)非終結(jié)符相關(guān)聯(lián),而每一列與文法的一個(gè)終結(jié)符或“#”關(guān)聯(lián)。分析表元素MA,a中的內(nèi)容為一條A的產(chǎn)生式,表明當(dāng)A面臨輸入符a時(shí)應(yīng)采用的候選式;當(dāng)元素內(nèi)容為空時(shí),表明A不應(yīng)面臨輸入符a,即輸入串含語(yǔ)法錯(cuò)誤。(4) 控制程序根據(jù)分析棧棧頂符號(hào)x和當(dāng) 前輸入符a決定分析器的動(dòng)作: 若xa“#”,則分析成功。 若xa“#”,即棧頂符號(hào)x與當(dāng)前輸入符a匹配,則將x從棧頂彈出,輸入串指針后移, 繼續(xù)對(duì)下一個(gè)字符進(jìn)行分析。 若x為非終結(jié)符A,則查分析表MA,a: i.若MA,a為一產(chǎn)生式,則A自棧頂彈出,MA,a中產(chǎn)生式的右部符號(hào)逆序壓棧;若MA,a為A,則只將A自棧頂彈出。

42、ii.若MA,a為空,則發(fā)現(xiàn)語(yǔ)法錯(cuò)誤,調(diào)用出錯(cuò)處理程序進(jìn)行處理?？刂瞥绦蛎枋鋈缦? 將“#”和文法開(kāi)始符依次入棧; 把第一個(gè)輸入符讀入a; do 把棧頂符號(hào)彈出并放入x中; if (xVT) if (xa) 將下一輸入符讀入a; else error( ); else if (Mx,a “xy1y2yk”) 把y1y2yk按逆序入棧; 輸出“xy1y2yk”; else error( ); while(x!=“#”)例3.7 一個(gè)文法的LL(1)分析表如下所示, 試給出輸入串a(chǎn)adl的分析過(guò)程。輸入串a(chǎn)adl的分析過(guò)程如下:符號(hào)棧當(dāng)前輸入符輸入串說(shuō) 明 #Aaadl#彈出棧頂符,將AaA右部反

43、序壓棧 #Aaaadl#匹配,彈出棧頂符a,讀出下一輸入符a #Aadl#彈出棧頂符,將AABl右部反序壓棧 #lBAadl# 彈出棧頂符,將AaA右部反序壓棧#lBAaadl# 匹配,彈出棧頂符a,讀出下一輸入符d #lBAdl# 由A僅彈出棧頂符號(hào)A #lBdl# 彈出棧頂符,將BdB右部反序壓棧 #lBddl#匹配,彈出棧頂符d,讀出下一輸入符l #lBl# 由B僅彈出棧頂符號(hào)B #ll # 匹配,彈出棧頂符l,讀出下一輸入符# #匹配,分析成功2. LL(1)分析表的構(gòu)造 LL(1)分析器中除分析表因文法的不同而不同外, 分析棧、控制程序都相同。因此構(gòu)造一個(gè)LL(1)分析器實(shí)際上就是構(gòu)

44、造文法的LL(1)分析表。構(gòu)造分析表M, 需預(yù)先定義FIRST集和FOLLOW集。 假定是文法任一符號(hào)串,(VTVN)*, FIRST()a| a, aVT 若 ,則規(guī)定 FIRST() 即FIRST()是的所有可能推出的首 終結(jié)符或可能的。*(1)FIRST集的構(gòu)造方法 對(duì)任一終結(jié)符a, FIRST(a)=a。 對(duì)每個(gè)非終結(jié)符X連續(xù)使用下述規(guī)則 直到FIRST集不再增大為止。 若有Xa,把a(bǔ)加入FIRST(X); 若有X,把加入FIRST(X); 若有XY,YVN,把FIRST(Y)的 所有非元素都加入FIRST(X); 若有XY1Y2Yk,而Y1Yi1都有, 則把FIRST(Yj) (j=

45、1,2,i)的所有非 元素都加入FIRST(X); 特別地,若Y1Yk均有產(chǎn)生式, 則把也加入到FIRST(X)。例1 試構(gòu)造文法GE的FIRST集。 GE: ETE E+TE | TFT T*FT | F(E)i 解: FIRST(E)=+,; FIRST(T)=*,; FIRST(F)(, i ; 由TF知,把FIRST(F)的所有非 元素加入FIRST(T),故FIRST(T)=(,i; 由ET知,把FIRST(T)的所有非 元素加入FIRST(E),故FIRST(E)=(,i 對(duì)文法GS的任何非終結(jié)符A, 定義 FOLLOW(A)a | S Aa, aVT若S A, 則規(guī)定# FOLL

46、OW(A)FOLLOW(A)是所有句型中出現(xiàn)在緊隨A 之后的終結(jié)符 或 # 。*(2) FOLLOW集構(gòu)造方法 對(duì)文法每個(gè)非終結(jié)符A構(gòu)造FOLLOW(A)。 方法是連續(xù)使用下述規(guī)則,直到FOLLOW 集不再增大為止。 對(duì)文法開(kāi)始符S,把#加入FOLLOW(S)。 (由語(yǔ)句括號(hào)“#S#”中的S#得到) 若有AB (可為空), 則將FIRST()加入FOLLOW(B)。 若有AB或AB且 , 則把 FOLLOW(A)加入到FOLLOW(B)。*例2 試構(gòu)造文法GE的FOLLOW集。 GE: ETE E+TE | TFT T*FT | F(E) | i解:1)FOLLOW(E)=#; 2)由ETE知, FIRST(E)屬于 FOLLOW(T), 即FOLLOW(T)+; 由E+TE |, FIRST(E)屬于 由TFT