編譯原理語法分析

1、第3章 語法分析,語法分析是編譯過程的核心部分。 語法分析的基本任務是在詞法分析識別出單詞符號串的基礎上，分析判斷程序的語法結構是否符合語法規(guī)則。 語言的語法結構用上下文無關文法來描述，因此，語法分析器的任務本質上是按上下文無關文法的產生式，確定整個單詞串是否構成語法上正確的程序。 語法分析的方法通常分為兩類： 自上而下分析法和自下而上分析法,3.1 文法和語言 3.

2、2 推導與語法樹 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法,3.1 文法和語言,文法是程序語言的生成系統(tǒng)。 自動機是程序語言的識別系統(tǒng)。 用文法可精確定義一個語言,并依據文法構造出識別該語言的自動機。因此,文法對程序語言和編譯程序的構造具有重要意義,如程序語言的詞法可用正規(guī)文法描述,語法可用上下文無關文法描述,而語義可借助于上下文有關文法描述。,3.1.1

3、文法和語言的概念 1．語言 通常用Σ表示字母表。 由字母表Σ中字符組成的有窮序列稱為Σ上的字符串或字。字母表Σ上的所有字符串(包括空串)組成的集合用Σ*表示。 對于字母表Σ, Σ*上的任一子集稱為Σ上的一個語言, 記為L, L?Σ*。語言L的每個字符串稱為語言L的一個語句或句子。,2. 文法 終結符是語言不可再分的基本符號,通常為一個語言的字母表。終結符代表

4、了語法的最小元素,是一種個體記號。 非終結符也稱語法變量, 它代表語法實體或語法范疇。一個非終結符是一個類、一個集合。 例如, 變量、常量、+、* 等為終結符，而 “算術表達式”為非終結符, 它代表一定算術式組成的類,如i*(i+i)、i+i+i等,即非終結符代表由終結符組成且滿足一定規(guī)則的符號串的集合。,文法可表示為四元組G=(VT,VN,S,ξ), 其中 (1) VT為非空終結符集;

5、 (2) VN為非空非終結符集,且VT∩VN=Φ; (3) S為文法開始符, S∈VN; (4)ξ是產生式的非空有限集, 其中每個 產生式(規(guī)則)記作 ?→? 或 ?::= ? 左部?∈(VT∪VN)+至少含一非終結符, 右部?∈(VT∪VN)*。,產生式 (也稱產生式規(guī)則或規(guī)則) 是定義語法實體的一種書寫規(guī)則。一個語法實體的相關規(guī)則可能不止一個, 如:

6、 P→?1, P→?2 , P→?n 相同左部的產生式可合并為一個: P→ ? 1| ? 2|…| ? n 其中, ? i(i=1,2,…,n)稱為P的候選式。,例3.1 試構造產生標識符的文法。分析: 用L表示字母,D表示數字,T表示字母或數字, 則 L→a∣b∣…∣z

7、D→0∣1∣…∣9 T→L∣D 用S表示字母數字串,則ST是字母數字串,即 S→T | ST 標識符I或為單個字母, 或為一字母后 跟字母數字串, 即 I→L∣LS,解: 產生標識符的文法G[I]為： G=({a,b,…,z,0,…,9},{I,S,T,

8、L,D},I,ξ) 其中,ξ: I→L∣LS S→T∣ST T→L∣D L→a∣b∣…∣z D→0∣1∣…∣9,例3.2 寫一文法, 使其語言是奇數集, 但不允 許出現以0打頭的奇數。解: 將奇數劃分為三個部分： 最高位允許出

9、現1～9,用非終結符B表示; 中間部分可出現任意多位數字0～9, 每一位用非終結符D表示; 最低位只出現1,3,5,7,9, 用A表示。 由于中間部分可任意位,故需另引入一 非終結符M,它包括最高位和中間部分。,解: 奇數集文法G[N]為: G=({0,1,…,9},{N,A,M,B,D},N,ξ) ξ: N→A | MA

10、 M→B | MD A→1 | 3 | 5 | 7 | 9 B→1|2|3|4|5|6|7|8|9 D→0 | B,3. 文法產生的語言 設G=(VT,VN,S,ξ)且?,? ∈(VT∪VN)*, 若存在產生式A→δ, δ∈(VT∪VN)*， 則稱?A?可直接推出?δ?,

11、記為 ?A? ? ?δ? 注意?與→的不同: →是產生式中的定義記號, ?表示直接推導,是對文法符號串?A? 中A用產生式A→δ的右部δ替換。,關于推導的兩點說明：(1)若?1可直接推出?2, ?2可直接推出?3,…, 即存在一個自?1至?n的推導序列: ?1??2 ??3 ?…??n (n>0)

12、則稱?1可推導出?n,記為?1 ?n, 表示從?1出發(fā)經1步或若干步可推導出?n(2)若記?1 ?1, 則?1 ?n表示從?1出發(fā),經過 0步或若干步可推導出?n, 即?1 ?n意味著或?1=?n, 或?1 ?n。,例如,考慮算術表達式文法G[E]： E→E+E∣E*E∣(E)│i 非終結符E代表一類

13、算術表達式, 從E出發(fā)可進行一系列推導, 表達式 i+i*i 的推導如下： E ?E+E ?E+E*E ?E+E*i ?E+i*i ?i+i*I注意: 在每一步推 導中,只能對其中一個 非終結符用其對應的產生式右部的 一個候選式來替換。,假定G[S]是一個文法, S是其開始符號,若S ?, ?∈(V

14、T∪VN)*,則稱?是文法G[S]的一個句型 ;若S ?, ?∈VT*，則稱?是文法G[S]的一個句子。由上述定義知： 僅含終結符的句型是一個句子。 開始符S是一個句型而不是一個句子。 i+i*i是一個句子, 也是一個句型, E+E*E、E+E*i和E+i*i是句型, 但不是一個句子。,對于文法G[S], 它所產

15、生的句子的全體稱為由文法G[S]產生的語言,記為L[G]。 L(G)={? | S ?且?∈VT*}3.1.2 形式語言分類 Chomsky于1956年定義了四類文法及相應的四類形式語言, 它對程序語言的設計、編譯方法、計算復雜性等方面都產生了重大影響。,1> 0型文法與0型語言 (短語文法) 若文法G的每個產生式具有下列形式: α→

16、β 其中α至少含一個非終結符， 則稱文法G為0型文法或短語文法, 記為PSG。 0型文法相應的語言稱為0型語言, 它的識別系統(tǒng)是圖靈機。,2>1型文法與1型語言 (對應自然語言) 若文法G的每個產生式?→?均滿足 |?| ≤ |?| 則稱文法G為1型文法或上下文有關文

17、 法, 記為CSG。 1型文法相應的語言稱為1型語言。 1型文法的另一種定義: 文法G的每個產生式具有下列形式： ?Aδ→??δ 其中, ?,δ∈V*, A∈VN, ?∈V+ 它更明確地表達了上下文有關的特性。,3> 2型文法與2型語言 (對應程序設計語言) 若文法G的每個產生式具有下列形式：

18、 A→α 其中, A∈VN, α∈V* 稱文法G為2型文法或上下文無關文法, 記為CFG。 2型文法相應的語言稱為2型語言或 上下文無關語言。 它的識別系統(tǒng)是下推自動機。,4> 3型文法與3型語言 (對應有限自動機) 若文法G的每個產生式具有下列形式： A→a 或 A→aB

19、 其中，A,B∈VN，a∈VT*， 則文法G稱為3型文法或正規(guī)文法或右線 性文法，記為RG。 3型文法相應語言為3型語言或正規(guī)語言。 它的識別系統(tǒng)是有限自動機。 3型文法還可呈左線性形式： A→a 或 A→Ba,5. 四類文法的關系與區(qū)別 從0型文法到3型文法逐步增加限制。 一般地,1～3型文法屬于0型文法，2,3型

20、文法屬于1型文法,3型文法屬于2型文法。四類文法的區(qū)別：(1)1型文法不允許有形如A→ε的產生式, 2,3型文法允許形如A→ε的產生式;(2)0,1型文法的產生式左部可以是含終結 符的符號串或兩個以上的非終結符, 2,3型文法的產生式左部只允許是單個 非終結符。,{anbncn|n≥1}?{anbncm|m,n≥1} ?{ambnck|m,n,k≥1} 這說明對文法規(guī)則定義形式的

21、限制雖加強了, 但相應的語言反而更大了。因此,不能主觀認定文法限制越大則語言越小, 即下述結論不成立： 3型語言? 2型語言? 1型語言? 0型語言 編譯方法中通常用3型文法描述詞法,用FA識別單詞; 利用2型文法描述語法,用下推自動機PDA識別各種語法成分。,例3.4 給出Σ={a,b}上具有奇數個a和奇數 個b的所有字符串集合的正規(guī)文法。解: 如圖, 由S出發(fā)經奇數個a到達A, 或

22、經奇數個b到達B。再由A出發(fā)經奇數個b到達C; 同樣, 由B出發(fā)經奇數個a到達C。,正規(guī)文法G[S]如下: S→aA | bB A→aS | bC B→bS | aC C→bA | aB|ε,3.1.3 正規(guī)式與上下文無關文法1. 正規(guī)式到上下文無關文法的轉換 由正規(guī)式構造CFG的一種方法： (1)構造正規(guī)式的NFA； (2)若0為初始狀態(tài), 則A0為開始符；

23、(3)若存在映射關系f(i,a)=j, 則定義產生式Ai →aAj； (4)若存在映射關系f(i,ε)=j， 則定義產生式Ai →Aj； (5) 若i為終態(tài), 則定義產生式Ai →ε。,例3.5 用CFG描述正規(guī)式(a|b)*abb解: 先構造識別(a|b)*abb的NFA M:,G[A0]: A0→aA0∣bA0∣aA1 A1→bA2

24、 A2→bA3 A3→ε,由正規(guī)式構造CFG的另一種方法： 通過分析正規(guī)式憑經驗直接構造。例如, 把(a|b)*abb看作(a|b)*和abb兩部分,第一部分是由0個或若干個a和b組成的字符串,第二部分僅由abb字符串組成,由此得到CFG G[A0]如下： G[A0]: A→HT H→aH|bH|ε

25、 T→abb,2. 正規(guī)式與CFG描述的對象 CFG既可描述語法,又可描述詞法。 基于下述原因,通常用正規(guī)式描述詞法: (1)詞法規(guī)則簡單,用正規(guī)式已足以描述; (2)正規(guī)式的表示比CFG更簡潔、直觀 和易于理解； (3) FA的構造比PDA(下推自動機)的構 造簡單且效率高。,注意: (1)語言的描述和語言的識別是表示一種語言的兩個不同

26、側面, 二者缺一不可。 (2)正規(guī)式通常適合于描述線性結構, 如標識符、關鍵字和注釋等; 上下文無關文法通常適合于描述具有嵌套(層次)性質的非線性結構, 如 if-else語句、while語句。,3.2 推導與語法樹,3.2.1 推導與短語1. 規(guī)范推導 最右推導: 在推導過程中,若每一步推導都是對句型中的最右非終結符用相應產生式的右部進行替換, 則稱這種推導為最右推導。 最左推導: 在

27、推導過程中,若每一步推導都是對句型中的最左非終結符用相應產生式的右部進行替換, 則稱這種推導為最左推導。,例如, 考慮句子 i+i*i 按文法G[E]的推導 最左推導: E?E+E?i+E?i+E*E ?i+i*E ?i+i*i 最右推導: E?E+E?E+E*E?E+E*i ?E+i*i

28、?i+i*i注意: 推導過程不唯一, 通常只考慮最左 推導或最右推導。 最右推導又稱為規(guī)范推導。 規(guī)范推導的逆過程稱為規(guī)范歸約。,2. 短語 如果S ?Aδ且A ?, 則稱?是句型??δ關于非終結符A的一 個短語,簡稱?是??δ的一個短語。 如果S ?Aδ且A ?, 則稱?為句型??δ的一個直接短

29、語或 簡單短語。注意: 短語的兩個條件缺一不可。 考慮i+i*i, E i+i, 但i+i不是短語,3. 句柄 句型的最左直接短語稱為句柄。 注意, 一個句型的直接短語不唯一, 但最左直接短語唯一。 例如, 對S ?Aδ ??δ, 若?為終結符串, 則句型??δ中的句柄為?。

30、將句型??δ中的句柄?用產生式的左部 符號代替便得到新句型?Aδ, 這是一次 規(guī)范歸約, 恰與規(guī)范推導相反。,4. 素短語 含有終結符的短語,如果它不存在具有 同樣性質的真子串,則該短語為素短語。 例如,在E E+E*i中, i、E*i、E+E*i是句型E+E*i的短語, 其中, i為素短語, E*i雖含終結符, 但其 真子串i含終結符, 故E*i不是素短

31、語, 同樣E+E*i也不是素短語。,3.2.2 語法樹與二義性1. 語法樹 對于程序語言, 有兩個問題需要解決: (1)判別程序在語法上是否正確; (2)句子的識別或分析。 為便于分析句子而引入語法樹。 語法樹以圖示化形式把句子分解成各 個組成部分,以分析句子的語法結構。 語法樹表示法與文法規(guī)則完全一致,但 更為直觀和完整。,滿足下列條件的樹稱為文法G的語法樹

32、:(1)每個結點用G的一個終結符或非終結 符標記;(2)根結點用文法開始符S標記;(3)內部結點一定是非終結符,若某內部結 點A有n個分支, 且其所有子結點從左 至右依次標記為x1, x2, …,xn,則 A→x1x2…xn一定是G的一條產生式;(4)若某結點標記為ε,則它必為葉結點且 是其父結點的唯一子結點。,一個句型對應的語法樹以文法開始符S作為根結點,并隨著推導逐步展開。當

33、某非終結符被產生式右部的某候選式替換時,該非終結符對應的結點產生出下一代結點,即候選式中從左至右的每個符號依次順序對應一個新結點,且每個新結點與其父結點之間都有一連線。在一棵語法樹生長過程中的任何時刻,所有沒有后代的葉結點的自左至右排列是一個句型。,例如,句子i+i*i的語法樹如下:,構造語法樹時, 一個句型的最左推導及最右推導只決定先生長左子樹還是先生長右子樹, 推導結束時相應的語法樹已看不出先生長的是哪個子樹。 因此

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

35、 串是相對于子樹根的短語； (2)直接短語: 簡單子樹的所有葉結點組 成的符號串是直接短語; (3)句柄: 最左簡單子樹的所有葉結點組 成的符號串為句柄;,(4)素短語: 子樹的所有葉結點組成的 含終結符的符號串, 且在該子樹中 沒有有包含終結符的更小子樹。 顯然, 從語法樹出發(fā)尋找短語、直接短語、句柄和素短語直觀得多。但要注意,

36、 子樹葉結點組成的符號串是指由該子樹根開始向下生長的所有葉結點,該子樹的部分葉結點并不是該子樹的短語。,考慮句型E+E*i的語法樹:短語: i、E*i和E+E*i; 直接短語: i; 句柄: i; 素短語: i,3. 文法的二義性 若文法G的一個句子能找到兩種不同的最左推導(最右推導), 即存在兩棵不同的語法樹, 則稱這個句子是二義性的。 若一個文法包含二義性句子, 則這個文法

37、是二義文法, 否則是無二義文法。,例如, 對文法(3.1),句子i+i*i存在兩種最左(右)推導:,再如,條件語句文法G[S]: G[S]: S→if B S S→if B S else S S→A //A指其它語句 其中, VN ={B,S,A}, VT ={if, else}

38、 文法G[S]的一個句型if B if B S else S對應兩棵不同的語法樹, 如下圖所示, 因此,文法G[S]是二義性文法。,4. 文法二義性的消除 一個文法是二義性的, 并不說明文法所描述的語言是二義性的。即對于一個二義文法G[S], 若能找到一個非二義文法G‘[S], 使得L(G’)=L(G), 則該二義文法的二義性可以消除。若找不到這樣的G'[S],則二義文法描述的語言為先天二義性的。,文法二義性的

39、消除方法:(1)不改變文法中原有的語法規(guī)則, 僅加進 一些語法的非形式規(guī)定。 如對文法(3.1), 不改變已有產生式, 僅加 進運算符的優(yōu)先順序和結合規(guī)則, 即 *優(yōu)先于+, 且*,+都服從左結合。(2)構造一個等價的無二義文法。即把排除 二義性的規(guī)則合并到原文法中, 改寫原 文法。,G'[E]: E→E+T∣T T→T*F∣F

40、 F→(E)∣i此時,句子i+i*i只有唯一 一棵語法樹。,例如, 將文法(3.1)改寫為無二義文法G'[E]:,例3.6 將下述文法G[S]的二義性消除: G[S]: S→if b S∣if b S else S∣A解: 消除G[S]的二義性可采用兩種方法:,(1)不改變已有規(guī)則, 僅加 進一項非形式的語法規(guī) 定: else與離它最近的if 匹配, 這樣, 句子if b

41、 if b A else A對應唯一的一 棵語法樹。,(2)改寫文法G[S]為G'[S]: S→S1| S2 S1→if b S1 else S1|A S2→if b S|if b S1else S2 由于引起二義性的原因是if-else語句的if后可以是任意if語句, 故改寫文法時規(guī)定if和else之間只能是if-else語句或其它語句。,編譯過

42、程中希望一個文法是無二義性的, 這樣句子的分析可按唯一確定的方式進行。但文法的二義性是不可判定的, 即不存在一種算法能在有限步內判定一個文法是否為二義性的。不過, 二義文法有時也可帶來一定好處, 如語法分析中二義文法的應用。,3.3 自上而下分析方法,自上而下分析從文法開始符出發(fā), 向下推導, 推出句子。即尋找一個推導序列, 使推導出的句子恰為輸入串; 亦即,從根結點出發(fā)向下生長出一棵語法樹,其葉結點組成的句子恰為輸入串。

43、 顯然, 語法樹的每一步生長(推導)都以能否與輸入串匹配為準。,1. 自上而下分析存在的不確定性 文法G[S]: S→xAy ? A→ab∣a 若輸入串為xay, 則其分析過程如下: (1)首先建立根結點S。 (2)文法關于S的產生式只有一個。,下一待分析字符a與A匹配。,(3)非終結符A有兩個候選式, 先選用第一個候選式:,y,A,x,,,,S

44、,,,a,b,(4)下一待分析字符y與b匹配, 失敗。 (5)將A生成的子樹注銷, 指針回退到輸 入串的第二個字符a。,(6) A選用第二個候選式:,這時輸入串中a與葉結點a匹配。 (7) 下一個待分析字符為y, 而語法樹下 一個葉結點也為y, 匹配成功。,在上述分析過程中, 若有多個候選式可供選擇, 則逐一試探每個候選式。一次試探失敗時, 必須回溯到該試探的初始現場, 包括注銷已

45、生長子樹、指針回退到失敗前狀態(tài)。這種帶回溯的自上而下分析方法是一種窮舉法, 效率極低, 在實用編譯程序中很少使用。,2. 確定的自上而下分析 實現確定的自上而下分析需滿足條件: (1)文法不含左遞歸。 左遞歸: A→A? 或 A A? 左遞歸的存在可能使自上而下分析過程陷入無限循環(huán), 故使用自上而下分析法必須消除文法的左遞歸。 (2)分析過程無回溯。

46、 回溯的存在可能使已做的大量語法和語義分析推倒重來, 這會嚴重影響效率, 故使用自上而下分析法必須消除回溯。,3. 左遞歸的消除直接左遞歸的消除 方法: 引入一個新的非終結符,把含有 左遞歸的產生式改寫為右遞歸形式。 例如: A→A? | ? ?, ?是任意串且?不以A開頭。 A的產生式可改寫為: A→

47、?A' A'→?A'| ?,,例如, 算術表達式文法G[E]為: G[E]: E→E+T | T T→T*F | F F→(E) | i,消去直接左遞歸后得到文法G'[E]: G'[E]: E→TE'???

48、 E'→+TE' |ε??? T→FT'??? T'→*FT' |ε??? F→(E) | i,一般地, 設文法中A的產生式為: A→A?1|A?2|…|A?m| ?1|?2|…|?n 其中,每個?都不等于ε

49、 每個?都不以A開頭,消除A的直接左遞歸, 文法可改寫為: A→?1A' | ?2A' |…| ?nA' A→?1A' | ?2A' |…|?mA' | ?,例如, 試消除E→E+T|E?T|T的左遞歸。解: 消除左遞歸后變?yōu)?E→TE' E'→+TE' | ?TE

50、9; |ε, 間接左遞歸的消除 例如, 文法G[S]: S→Qc | c Q→Rb | b R→Sa | a,如何消除文法的間接左遞歸？ 間接左遞歸的存在是由于非終結符之間形成了循環(huán)推導, 只要把循環(huán)推導中的某個連接切斷, 間接左遞歸就消除了。,切斷循環(huán)推導中的某個連接的方法：Step1.

51、 對n個產生式中的某一個進行至多 n-1次替換, 使間接左遞歸變成直 接左遞歸, 再消除之。,例如, 消除上述文法G[S]中S,Q間的連接: S? Qc|c? Rbc|bc|c? Sabc|abc|bc|c 改寫為: S→abcS'|bcS'|cS' S'→abcS

52、'|ε,消除左遞歸還需消除Q,R間的連接: Q? Rb|b? Sab|ab|Qab|b 再消除其直接左遞歸…,Step2. 對其余n-1個產生式中的某一個進行 至多n-2次替換,再消除直接左遞歸。 …,考慮上述文法的后兩個產生式: Q→Rb | b R→Sa | a | Qa,消除左遞歸

53、算法:(1)文法的所有非終結符排序為A1,A2,…,An;(2)將間接左遞歸改為直接左遞歸,消除之; for (i=1; i<=n; i++) {for (j=1; j<=i?1; j++) 把Ai→Ajγ| ?及Aj→δ1|…|δk 改寫為Ai→δ1γ|…|δkγ| ? ; 消除Ai的直接左遞歸; }

54、(3)化簡, 刪去那些不可達元的產生式。,通過例子熟悉消除左遞歸算法執(zhí)行過程:例如, G[S]: S→Qc | c Q→Rb | b R→Sa | a,(1) 將非終結符排序為R, Q, S;(2) 對于R (i=1, P1) 內層循環(huán)不執(zhí)行; 消除R的直接左遞歸: R→Sa|a 對于Q

55、(i=2, P2) 內層循環(huán)改寫P2→ P1γ: Q→Sab|ab|b 消除Q的直接左遞歸: Q→Sab|ab|b,對于S (i=3, P3) 內層循環(huán)改寫P3→P1γ和P3→P2γ: S→Sabc | abc | bc | c 消除S的直接左遞歸:

56、 S→abcS' | bcS' | cS' S'→abcS' |ε,于是得文法G'[S]: S→abcS' | bcS' | cS' S'→abcS' |ε Q→Sab | ab | b R

57、→Sa | a,(3) 化簡, 刪去關于Q和R的產生式。,對消除左遞歸算法的兩點說明: (1)消除左遞歸算法有兩個限制條件:文法中不含回路(P P)和ε-生成式。該限制不會影響消除左遞歸算法的使用,因為后續(xù)課程《形式語言》中將學到,對任一CFG G, 存在一個不含ε-生成式和單一生成式的CFG G', 使得L(G')=L(G)-{ε}。 (2) 對非終結符的不同排序會導致文法形式上

58、的不同, 但可證明它們等價。,上例若排序為S,Q,R, 則得文法G'''[S]: S→Qc | c Q→Rb | b R→bcaR' |caR' |aR' R'→bcaR' |ε,G''[S

59、]與G'''[S]等價的證明: 證明: S?…?abc(abc)*|bc(abc)*|c(abc)* L(G'')={(abc|bc|c)(abc)i | i≥0} S?…?bca(bca)*bc|ca(bca)*bc| a(bca)*bc|bc|c L(G''

60、;')={(abc|bc|c)(abc)i | i≥0},有興趣的同學課后以下述文法為例熟悉消除左遞歸算法的執(zhí)行過程: G[S]: S→Qc | c | Rc Q→Rb | b | Sb R→Sa | a | Qa G[S]: S→Qc | c | Rc | Sc Q→Rb | b

61、| Sb | Qb R→Sa | a | Qa | Ra,2. 回溯的消除 要消除回溯,首先要清楚回溯存在的原因, 根除這些原因,自然就消除了回溯。 假設輪到用A去執(zhí)行匹配任務, A→?1| ?2|…|?n, 而A面臨的第1個輸入符為a1。首先, 用?1的第1終結符與輸入符a1匹配,若成功,再用?1的第2終結符與下一輸入符a2匹配,…, 當?1的第n終結符與當前輸入符a

62、n匹配不成功時,說明?1與輸入串不匹配, 此時需把關于?1的分析過程推倒,回到用?1匹配前的狀態(tài)。同樣地,用?2與輸入串匹配,…。,可見, 回溯的存在是由于分析過程中需對產生式的多個候選式進行試探性匹配。若能根據面臨的輸入符從產生式的多個候選式中選出一個作為全權代表,使得若該候選式與輸入串匹配成功,則A與輸入串匹配成功, 若該候選式與輸入串匹配不成功,則A與輸入串匹配不成功, 這樣就可以消除回溯。,如何從多個候選式中選出一個全權代表?

63、 例如, A→aA | bB | cC a A→?1| ?2|…|?n a 若A的n個候選式中只有一個推出的終結符串的首字符包含a (設為?i), 則候選式?i可作為A的全權代表。 這就要求匹配前先求出各個候選式所能推出的所有終結符串的首字符, 即候選式的終結首符集FIRST(?)。, 終結首符集FIRST(?) 令G

64、是一個無左遞歸文法, 對G的所有非終結符的每個候選式?, 定義 FIRST(?)＝{a | ? a…, a?VT} 若? ε, 則ε?FIRST(?),即FIRST(?)是由?所能推出的的所有 終結符串的首字符或ε。,A→?1| ?2|…|?n FIRST(A)=FIRST(?1)∪FIRST(?2)∪…,對于A→?1| ?2

65、|…|?n 若A有多個候選式的終結首符集含a, 則仍需進行試探, 此時只是減少了回溯次數, 并未消除回溯。要消除回溯, 準確地指派一個候選式去執(zhí)行匹配任務, 則各個候選式的終結首符集應互不相交, 即 FIRST(?i)∩FIRST(?j)=? (i≠j) 如何使每個非終結符的候選終結首符集互不相交? 方法是提取公共左因子。, 提取公共左因子例如, A→abA | aB | ab

66、 改寫文法: A→aA' A'→bA | B | b,改寫第2式: A'→bA'' | B A''→A |ε,一般地, 假設文法中關于A的產生式為 A→δ?1|δ?2|…|δ?i | ?i+1|…|?j提取公共左因子后, 改寫為

67、 A→δA' | ?i+1|…| ?j A'→?1| ?2| …| ?i,經過反復提取公共左因子,可使每個非終結符的候選終結首符集互不相交。,消除左遞歸和提取公共左因子后, 文法不再含左遞歸且任一非終結符的候選終結首符集互不相交。此時,若?不屬于任一非終結符的候選終結首符集, 則可進行有效的LL(1)分析了。然而,消除左遞歸和提取左因子后, 文法中引進了大量?-生成式, 這就引出自動匹配問題。,

68、3. 自動匹配問題對于文法G[E]: E→TE'??? E'→+TE' |ε??? T→FT'??? T'→*FT' |ε??? F→(E) | i考慮輸入串i+i #,當A面臨輸入符a時, 若a?FIRST(A)且??FIRST(A), 則考慮自動匹配問題。 對于上述算術表達式文法,若輸入串為

69、i/i, 即使讓T'自動匹配, “/”仍不能與后面符號匹配, 此時沒必要讓T'自動匹配。,結論: 只有在當前輸入符能與A后的第一個終結符匹配成功時,才讓A自動得到匹配。這就要求分析前先求出緊跟在A后的終結符, 即FOLLOW(A)。,FOLLOW(A)的定義 對文法G[S]的任一非終結符A, 定義 FOLLOW(A)＝{a|S …Aa…,a∈VT} 若S …A, 則

70、規(guī)定#?FOLLOW(A),即FOLLOW(A)是所有句型中緊跟在 A之后的終結符 或 # 。,自動匹配條件 當A面臨輸入符a時,若a?FIRST(A)且??FIRST(A), 則只有當a?FOLLOW(A)時,才使A自動得到匹配。缺少任一條件,均不自動匹配。,若輸入符a?FIRST(A)且a?FOLLOW(A), 則當??FIRST(A)時仍需進行試探(回溯)。因此,對于存在?-生成式的非終結符A,若要進行