編譯原理語法分析課件

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

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

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

4、 P1, P2 , Pn 相同左部的產生式可合并為一個: P 1| 2| n 其中, i(i=1,2,n)稱為P的候選式。例3.1 試構造產生標識符的文法。分析: 用L表示字母,D表示數(shù)字,T表示字母或數(shù)字, 則 Labz D019 TLD 用S表示字母數(shù)字串,則ST是字母數(shù)字串,即 ST | ST 標識符I或為單個字母, 或為一字母后 跟字母數(shù)字串, 即 ILLS解: 產生標識符的文法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,用非終結符B表示; 中間部分可出現(xiàn)任意多位數(shù)字09, 每一位用非終結符D表示; 最低位只出現(xiàn)1,3,5,7,9, 用A表示。 由于中間部分可任意位,故需另引入一 非終結符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. 文法產生的語言 設G=(VT,VN,S,)且, (VTVN)*, 若存在產生式A, (VTVN)*， 則稱A可直接推出, 記為 A 注意與

6、的不同: 是產生式中的定義記號, 表示直接推導,是對文法符號串A 中A用產生式A的右部替換。關于推導的兩點說明：(1)若1可直接推出2, 2可直接推出3, 即存在一個自1至n的推導序列: 12 3 n (n0) 則稱1可推導出n,記為1 n, 表示從1出發(fā)經1步或若干步可推導出n(2)若記1 1, 則1 n表示從1出發(fā),經過 0步或若干步可推導出n, 即1 n意味著或1=n, 或1 n。+0*+例如,考慮算術表達式文法GE： EE+EE*E(E)i 非終結符E代表一類算術表達式, 從E出發(fā)可進行一系列推導, 表達式 i+i*i 的推導如下： E E+E E+E*E E+E*i E+i*i i+

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

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

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

10、于0型文法，2,3型文法屬于1型文法,3型文法屬于2型文法。四類文法的區(qū)別：(1)1型文法不允許有形如A的產生式, 2,3型文法允許形如A的產生式;(2)0,1型文法的產生式左部可以是含終結 符的符號串或兩個以上的非終結符, 2,3型文法的產生式左部只允許是單個 非終結符。 anbncn|n1anbncm|m,n1 ambnck|m,n,k1 這說明對文法規(guī)則定義形式的限制雖加強了, 但相應的語言反而更大了。因此,不能主觀認定文法限制越大則語言越小, 即下述結論不成立： 3型語言 2型語言 1型語言 0型語言 編譯方法中通常用3型文法描述詞法,用FA識別單詞; 利用2型文法描述語法,用下推自動

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

12、映射關系f(i,)=j， 則定義產生式Ai Aj； (5) 若i為終態(tài), 則定義產生式Ai 。例3.5 用CFG描述正規(guī)式(a|b)*abb解: 先構造識別(a|b)*abb的NFA M:01223ababbGA0: A0aA0bA0aA1 A1bA2 A2bA3 A3由正規(guī)式構造CFG的另一種方法： 通過分析正規(guī)式憑經驗直接構造。例如, 把(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的構造比PDA(下推自動機)的構 造簡單且效率高。 注意: (1)語言的描述和語言的識別是表示一種語言的兩個不同側面, 二者缺一不可。 (2)正規(guī)式通常適合于描述線性結構, 如標識符、關鍵字和注釋等; 上下文無關文法通常適合于描述具有嵌套(層次)性質的非線性結構, 如 if-else語句、while語句。3.2 推導與語法樹3.2.1 推導與短語1. 規(guī)范推導 最右推導: 在推導過程中,若每一步推導都是對句型中的最右非終結符用相應產生式的右部

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

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

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

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

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

19、沒有有包含終結符的更小子樹。 顯然, 從語法樹出發(fā)尋找短語、直接短語、句柄和素短語直觀得多。但要注意, 子樹葉結點組成的符號串是指由該子樹根開始向下生長的所有葉結點,該子樹的部分葉結點并不是該子樹的短語。考慮句型E+E*i的語法樹:短語: i、E*i和E+E*i; 直接短語: i; 句柄: i; 素短語: iEEEE*Ei3. 文法的二義性 若文法G的一個句子能找到兩種不同的最左推導(最右推導), 即存在兩棵不同的語法樹, 則稱這個句子是二義性的。 若一個文法包含二義性句子, 則這個文法是二義文法, 否則是無二義文法。 例如, 對文法(3.1),句子i+i*i存在兩種最左(右)推導: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對應兩棵不同的語法樹, 如下圖所示, 因此,文法GS是二義性文法。SifS(a)(b)BSifSelseBSBSifSelseifSB4. 文法二義性的消除 一個文法是二義性的, 并不說明文法所描述的語言是二義性的。即對于一個二義文法GS, 若能找到一個非二義文法GS, 使得L(G)=L(G), 則該二義文法的二義性可以消除。若找不到這樣的GS,則

21、二義文法描述的語言為先天二義性的。文法二義性的消除方法:(1)不改變文法中原有的語法規(guī)則, 僅加進 一些語法的非形式規(guī)定。 如對文法(3.1), 不改變已有產生式, 僅加 進運算符的優(yōu)先順序和結合規(guī)則, 即 *優(yōu)先于+, 且*,+都服從左結合。(2)構造一個等價的無二義文法。即把排除 二義性的規(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ī)則, 僅加 進一項非形式的語法規(guī) 定: else與離它最近的if 匹配, 這樣, 句子if b if b A else A對應唯一的一 棵語法樹。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 編譯過程中希望一個文法是無二義性的, 這樣句子的分析可按唯一確定的方式進

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

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

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

26、 | i消去直接左遞歸后得到文法GE: GE: ETE E+TE | TFT T*FT | F(E) | i一般地, 設文法中A的產生式為: 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 如何消除文法的間接左遞歸？ 間接左遞歸的存在是由于非終結符之間形成了循環(huán)推導, 只要把循環(huán)推導中的某個連接切

27、斷, 間接左遞歸就消除了。切斷循環(huán)推導中的某個連接的方法：Step1. 對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個產生式中的某一個進行 至多n-2次替換,再消除直接左遞歸。 考慮上述文法的后兩個產生式: QRb | b RSa | a | Qa消除左遞歸算法:(1)文法的所有

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

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

30、 (2) 對非終結符的不同排序會導致文法形式上的不同, 但可證明它們等價。上例若排序為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 有興趣的同學課后以下述文法為例熟悉消除左遞歸算法的執(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. 回溯的消除 要消除回溯,首先要清楚回溯存在的原因, 根除這些原因,自然就消除了回溯。 假設輪到用A去執(zhí)行匹配任務, A1| 2|n, 而A面臨的第1個輸入符為a1。首先, 用1的第1終結符與輸入符a1匹配,若成功,再用1的第2終結符與下一輸入符a2匹配, 當1的第n終結符與當前輸入符an匹配不成功時,說明1與輸入串不匹配, 此時需把關于1的分析過程推倒,回到用1匹配前的狀態(tài)。同樣地,用2與輸入串匹配,。 可見, 回溯的存在是由于分析過程中需對產生式的多個候

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

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

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

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

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

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

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

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

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

42、ii.若MA,a為空,則發(fā)現(xià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)分析表如下所示, 試給出輸入串aadl的分析過程。輸入串aadl的分析過程如下:符號棧當前輸入符輸入串說 明 #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)分析表的構造 LL(1)分析器中除分析表因文法的不同而不同外, 分析棧、控制程序都相同。因此構造一個LL(1)分析器實際上就是構

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

45、1,2,i)的所有非 元素都加入FIRST(X); 特別地,若Y1Yk均有產生式, 則把也加入到FIRST(X)。例1 試構造文法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的任何非終結符A, 定義 FOLLOW(A)a | S Aa, aVT若S A, 則規(guī)定# FOLL

46、OW(A)FOLLOW(A)是所有句型中出現(xiàn)在緊隨A 之后的終結符 或 # 。*(2) FOLLOW集構造方法 對文法每個非終結符A構造FOLLOW(A)。 方法是連續(xù)使用下述規(guī)則,直到FOLLOW 集不再增大為止。 對文法開始符S,把#加入FOLLOW(S)。 (由語句括號“#S#”中的S#得到) 若有AB (可為空), 則將FIRST()加入FOLLOW(B)。 若有AB或AB且 , 則把 FOLLOW(A)加入到FOLLOW(B)。*例2 試構造文法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