編譯原理語法分析課件

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

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

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

4、 P1, P2 , Pn 相同左部的產(chǎn)生式可合并為一個: P 1| 2| n 其中, i(i=1,2,n)稱為P的候選式。例3.1 試構(gòu)造產(chǎn)生標(biāo)識符的文法。分析: 用L表示字母,D表示數(shù)字,T表示字母或數(shù)字, 則 Labz D019 TLD 用S表示字母數(shù)字串,則ST是字母數(shù)字串,即 ST | ST 標(biāo)識符I或為單個字母, 或為一字母后 跟字母數(shù)字串, 即 ILLS解: 產(chǎn)生標(biāo)識符的文法GI為： G=(a,b,z,0,9,I,S,T,L,D,I,) 其中,: ILLS STST TLD Labz D019例3.2 寫一文法, 使其語言是奇數(shù)集, 但不允 許出現(xiàn)以0打頭的奇數(shù)。解: 將奇數(shù)劃分為

5、三個部分： 最高位允許出現(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)生的語言 設(shè)G=(VT,VN,S,)且, (VTVN)*, 若存在產(chǎn)生式A, (VTVN)*， 則稱A可直接推出, 記為 A 注意與

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

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

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

9、 (對應(yīng)程序設(shè)計語言) 若文法G的每個產(chǎn)生式具有下列形式： A 其中, AVN, V* 稱文法G為2型文法或上下文無關(guān)文法, 記為CFG。 2型文法相應(yīng)的語言稱為2型語言或 上下文無關(guān)語言。 它的識別系統(tǒng)是下推自動機(jī)。4 3型文法與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 或 ABa5. 四類文法的關(guān)系與區(qū)別 從0型文法到3型文法逐步增加限制。 一般地,13型文法屬

10、于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é)符。 anbncn|n1anbncm|m,n1 ambnck|m,n,k1 這說明對文法規(guī)則定義形式的限制雖加強(qiáng)了, 但相應(yīng)的語言反而更大了。因此,不能主觀認(rèn)定文法限制越大則語言越小, 即下述結(jié)論不成立： 3型語言 2型語言 1型語言 0型語言 編譯方法中通常用3型文法描述詞法,用FA識別單詞; 利用2型文法描述語法,用下推自動

11、機(jī)PDA識別各種語法成分。例3.4 給出=a,b上具有奇數(shù)個a和奇數(shù) 個b的所有字符串集合的正規(guī)文法。解: 如圖, 由S出發(fā)經(jīng)奇數(shù)個a到達(dá)A, 或經(jīng)奇數(shù)個b到達(dá)B。再由A出發(fā)經(jīng)奇數(shù)個b到達(dá)C; 同樣, 由B出發(fā)經(jīng)奇數(shù)個a到達(dá)C。正規(guī)文法GS如下: SaA | bB AaS | bC BbS | aC CbA | aB| bbbbaaaaSAB2C3.1.3 正規(guī)式與上下文無關(guān)文法1. 正規(guī)式到上下文無關(guān)文法的轉(zhuǎn)換 由正規(guī)式構(gòu)造CFG的一種方法： (1)構(gòu)造正規(guī)式的NFA； (2)若0為初始狀態(tài), 則A0為開始符； (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)造識別(a|b)*abb的NFA M:01223ababbGA0: A0aA0bA0aA1 A1bA2 A2bA3 A3由正規(guī)式構(gòu)造CFG的另一種方法： 通過分析正規(guī)式憑經(jīng)驗直接構(gòu)造。例如, 把(a|b)*abb看作(a|b)*和abb兩部分,第一部分是由0個或若干個a和b組成的字符串,第二部分僅由abb字符串組成,由此得到CFG GA0如下： GA0: AHT HaH|bH| Tabb2. 正規(guī)式與CFG描述的對象 CFG既可描述語法,又可描述

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

14、進(jìn)行替換, 則稱這種推導(dǎo)為最右推導(dǎo)。 最左推導(dǎo): 在推導(dǎo)過程中,若每一步推導(dǎo)都是對句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換, 則稱這種推導(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)過程不唯一, 通常只考慮最左 推導(dǎo)或最右推導(dǎo)。 最右推導(dǎo)又稱為規(guī)范推導(dǎo)。 規(guī)范推導(dǎo)的逆過程稱為規(guī)范歸約。2. 短語 如果S A且A , 則稱是句型關(guān)于非終結(jié)符A的一 個短語,簡稱是的一個短語。 如果S A且A , 則稱為句型的一個直接短語或 簡單短語。注意:

15、短語的兩個條件缺一不可。 考慮i+i*i, E i+i, 但i+i不是短語 *+*+3. 句柄 句型的最左直接短語稱為句柄。 注意, 一個句型的直接短語不唯一, 但最左直接短語唯一。 例如, 對S A , 若為終結(jié)符串, 則句型中的句柄為。 將句型中的句柄用產(chǎn)生式的左部 符號代替便得到新句型A, 這是一次 規(guī)范歸約, 恰與規(guī)范推導(dǎo)相反。* 4. 素短語 含有終結(jié)符的短語,如果它不存在具有 同樣性質(zhì)的真子串,則該短語為素短語。 例如,在E E+E*i中, i、E*i、E+E*i是句型E+E*i的短語, 其中, i為素短語, E*i雖含終結(jié)符, 但其 真子串i含終結(jié)符, 故E*i不是素短語, 同樣

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

17、結(jié)點標(biāo)記為,則它必為葉結(jié)點且 是其父結(jié)點的唯一子結(jié)點。 一個句型對應(yīng)的語法樹以文法開始符S作為根結(jié)點,并隨著推導(dǎo)逐步展開。當(dāng)某非終結(jié)符被產(chǎn)生式右部的某候選式替換時,該非終結(jié)符對應(yīng)的結(jié)點產(chǎn)生出下一代結(jié)點,即候選式中從左至右的每個符號依次順序?qū)?yīng)一個新結(jié)點,且每個新結(jié)點與其父結(jié)點之間都有一連線。在一棵語法樹生長過程中的任何時刻,所有沒有后代的葉結(jié)點的自左至右排列是一個句型。 例如,句子i+i*i的語法樹如下:EEEE*Eiii第一代第二代第三代第四代 構(gòu)造語法樹時, 一個句型的最左推導(dǎo)及最右推導(dǎo)只決定先生長左子樹還是先生長右子樹, 推導(dǎo)結(jié)束時相應(yīng)的語法樹已看不出先生長的是哪個子樹。 因此, 一棵語

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

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

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

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

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

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

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

25、而下分析 實現(xiàn)確定的自上而下分析需滿足條件: (1)文法不含左遞歸。 左遞歸: AA 或 A A 左遞歸的存在可能使自上而下分析過程陷入無限循環(huán), 故使用自上而下分析法必須消除文法的左遞歸。 (2)分析過程無回溯。 回溯的存在可能使已做的大量語法和語義分析推倒重來, 這會嚴(yán)重影響效率, 故使用自上而下分析法必須消除回溯。+ 3. 左遞歸的消除直接左遞歸的消除 方法: 引入一個新的非終結(jié)符,把含有 左遞歸的產(chǎn)生式改寫為右遞歸形式。 例如: AA | , 是任意串且不以A開頭。 A的產(chǎn)生式可改寫為: 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 其中,每個都不等于 每個都不以A開頭消除A的直接左遞歸, 文法可改寫為: 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)中的某個連接切

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

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

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

30、 (2) 對非終結(jié)符的不同排序會導(dǎo)致文法形式上的不同, 但可證明它們等價。上例若排序為S,Q,R, 則得文法GS: SQc | c QRb | b RbcaR |caR |aR RbcaR | GS與GS等價的證明: 證明: 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í)行過程: 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個輸入符為a1。首先, 用1的第1終結(jié)符與輸入符a1匹配,若成功,再用1的第2終結(jié)符與下一輸入符a2匹配, 當(dāng)1的第n終結(jié)符與當(dāng)前輸入符an匹配不成功時,說明1與輸入串不匹配, 此時需把關(guān)于1的分析過程推倒,回到用1匹配前的狀態(tài)。同樣地,用2與輸入串匹配,。 可見, 回溯的存在是由于分析過程中需對產(chǎn)生式的多個候

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

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

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

35、E) | i考慮輸入串i+i #EETFTT+Ei FTi 當(dāng)A面臨輸入符a時, 若aFIRST(A)且FIRST(A), 則考慮自動匹配問題。 對于上述算術(shù)表達(dá)式文法,若輸入串為i/i, 即使讓T自動匹配, “/”仍不能與后面符號匹配, 此時沒必要讓T自動匹配。 結(jié)論: 只有在當(dāng)前輸入符能與A后的第一個終結(jié)符匹配成功時,才讓A自動得到匹配。這就要求分析前先求出緊跟在A后的終結(jié)符, 即FOLLOW(A)。 FOLLOW(A)的定義 對文法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)A面臨輸入符a時,若aFIRST(A)且FIRST(A), 則只有當(dāng)aFOLLOW(A)時,才使A自動得到匹配。缺少任一條件,均不自動匹配。 若輸入符aFIRST(A)且aFOLLOW(A), 則當(dāng)FIRST(A)時仍需進(jìn)行試探(回溯)。因此,對于存在-生成式的非終結(jié)符A,若要進(jìn)行不帶回溯的自上而下分析,則FIRST(A)與FOLLOW(A)應(yīng)互不相交。 5. 遞歸下降分析器 遞歸下降分析法是一種自上而下分析法,文法的每個非終結(jié)符對應(yīng)一個遞歸過程。分析過程從文法開始符出發(fā),執(zhí)行一組遞歸過程, 這樣向下推導(dǎo)直到推出句子。

37、若文法不含左遞歸且每個非終結(jié)符的候選式無公共左因子, 則可構(gòu)造不帶回溯的遞歸下降分析程序, 該程序由一組過程組成, 每個過程對應(yīng)文法的一個非終結(jié)符。這樣的分析程序稱為遞歸下降分析器。例如, 考慮不含左遞歸的算術(shù)表達(dá)式, 其對應(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 ();說明: 考慮E的產(chǎn)生式: E+TE | E有兩個候選式,當(dāng)E面臨輸入符+時令第一個候選工作,當(dāng)面臨其它符號時, E自動獲得匹配。遞歸函數(shù)E根據(jù)這一原則設(shè)計。 假定遞歸函數(shù)的調(diào)用以棧的形式來模擬, 下面分析輸入串 # i1*(i2+i3)# 的語法分析過程, “#”為分隔符。 進(jìn)行語法分析時,首先將“#”和文法開始符E壓入棧中,當(dāng)語法分析進(jìn)行到棧中僅?！?”而輸入串掃描指針已指向輸入串尾部的“

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

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

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

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

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

44、造文法的LL(1)分析表。構(gòu)造分析表M, 需預(yù)先定義FIRST集和FOLLOW集。 假定是文法任一符號串,(VTVN)*, FIRST()a| a, aVT 若 ,則規(guī)定 FIRST() 即FIRST()是的所有可能推出的首 終結(jié)符或可能的。*(1)FIRST集的構(gòu)造方法 對任一終結(jié)符a, FIRST(a)=a。 對每個非終結(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 對文法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)造方法 對文法每個非終結(jié)符A構(gòu)造FOLLOW(A)。 方法是連續(xù)使用下述規(guī)則,直到FOLLOW 集不再增大為止。 對文法開始符S,把#加入FOLLOW(S)。 (由語句括號“#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