編譯原理語法分析

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

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

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

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

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

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

7、D→0∣1∣…∣9 T→L∣D 用S表示字母數(shù)字串,則ST是字母數(shù)字串,即 S→T | ST 標(biāo)識(shí)符I或?yàn)閱蝹€(gè)字母, 或?yàn)橐蛔帜负?跟字母數(shù)字串, 即 I→L∣LS,解: 產(chǎn)生標(biāo)識(shí)符的文法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 寫一文法, 使其語言是奇數(shù)集, 但不允 許出現(xiàn)以0打頭的奇數(shù)。解: 將奇數(shù)劃分為三個(gè)部分： 最高位允許出

9、現(xiàn)1～9,用非終結(jié)符B表示; 中間部分可出現(xiàn)任意多位數(shù)字0～9, 每一位用非終結(jié)符D表示; 最低位只出現(xiàn)1,3,5,7,9, 用A表示。 由于中間部分可任意位,故需另引入一 非終結(jié)符M,它包括最高位和中間部分。,解: 奇數(shù)集文法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. 文法產(chǎn)生的語言 設(shè)G=(VT,VN,S,ξ)且?,? ∈(VT∪VN)*, 若存在產(chǎn)生式A→δ, δ∈(VT∪VN)*， 則稱?A?可直接推出?δ?,

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

12、則稱?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。,例如,考慮算術(shù)表達(dá)式文法G[E]： E→E+E∣E*E∣(E)│i 非終結(jié)符E代表一類

13、算術(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+i*I注意: 在每一步推 導(dǎo)中,只能對(duì)其中一個(gè) 非終結(jié)符用其對(duì)應(yīng)的產(chǎn)生式右部的 一個(gè)候選式來替換。,假定G[S]是一個(gè)文法, S是其開始符號(hào),若S ?, ?∈(V

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

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

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

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

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

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

20、文法屬于1型文法,3型文法屬于2型文法。四類文法的區(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|n≥1}?{anbncm|m,n≥1} ?{ambnck|m,n,k≥1} 這說明對(duì)文法規(guī)則定義形式的

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

22、經(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ī)文法G[S]如下: S→aA | bB A→aS | bC B→bS | aC C→bA | aB|ε,3.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為開始符；

23、(3)若存在映射關(guān)系f(i,a)=j, 則定義產(chǎn)生式Ai →aAj； (4)若存在映射關(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:,G[A0]: A0→aA0∣bA0∣aA1 A1→bA2

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

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

26、側(cè)面, 二者缺一不可。 (2)正規(guī)式通常適合于描述線性結(jié)構(gòu), 如標(biāo)識(shí)符、關(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)都是對(duì)句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換, 則稱這種推導(dǎo)為最右推導(dǎo)。 最左推導(dǎo): 在

27、推導(dǎo)過程中,若每一步推導(dǎo)都是對(duì)句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換, 則稱這種推導(dǎo)為最左推導(dǎo)。,例如, 考慮句子 i+i*i 按文法G[E]的推導(dǎo) 最左推導(dǎo): E?E+E?i+E?i+E*E ?i+i*E ?i+i*i 最右推導(dǎo): E?E+E?E+E*E?E+E*i ?E+i*i

28、?i+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的一 個(gè)短語,簡(jiǎn)稱?是??δ的一個(gè)短語。 如果S ?Aδ且A ?, 則稱?為句型??δ的一個(gè)直接短

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

30、將句型??δ中的句柄?用產(chǎn)生式的左部 符號(hào)代替便得到新句型?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不是素短

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

32、:(1)每個(gè)結(jié)點(diǎn)用G的一個(gè)終結(jié)符或非終結(jié) 符標(biāo)記;(2)根結(jié)點(diǎn)用文法開始符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,則 A→x1x2…xn一定是G的一條產(chǎn)生式;(4)若某結(jié)點(diǎn)標(biāo)記為ε,則它必為葉結(jié)點(diǎn)且 是其父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。,一個(gè)句型對(duì)應(yīng)的語法樹以文法開始符S作為根結(jié)點(diǎn),并隨著推導(dǎo)逐步展開。當(dāng)

33、某非終結(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)之間都有一連線。在一棵語法樹生長(zhǎng)過程中的任何時(shí)刻,所有沒有后代的葉結(jié)點(diǎn)的自左至右排列是一個(gè)句型。,例如,句子i+i*i的語法樹如下:,構(gòu)造語法樹時(shí), 一個(gè)句型的最左推導(dǎo)及最右推導(dǎo)只決定先生長(zhǎng)左子樹還是先生長(zhǎng)右子樹, 推導(dǎo)結(jié)束時(shí)相應(yīng)的語法樹已看不出先生長(zhǎng)的是哪個(gè)子樹。 因此

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

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

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

37、是二義文法, 否則是無二義文法。,例如, 對(duì)文法(3.1),句子i+i*i存在兩種最左(右)推導(dǎo):,再如,條件語句文法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]的一個(gè)句型if B if B S else S對(duì)應(yīng)兩棵不同的語法樹, 如下圖所示, 因此,文法G[S]是二義性文法。,4. 文法二義性的消除 一個(gè)文法是二義性的, 并不說明文法所描述的語言是二義性的。即對(duì)于一個(gè)二義文法G[S], 若能找到一個(gè)非二義文法G‘[S], 使得L(G’)=L(G), 則該二義文法的二義性可以消除。若找不到這樣的G'[S],則二義文法描述的語言為先天二義性的。,文法二義性的

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

40、 F→(E)∣i此時(shí),句子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ī)則, 僅加 進(jìn)一項(xiàng)非形式的語法規(guī) 定: else與離它最近的if 匹配, 這樣, 句子if b

41、 if b A else A對(duì)應(yīng)唯一的一 棵語法樹。,(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語句, 故改寫文法時(shí)規(guī)定if和else之間只能是if-else語句或其它語句。,編譯過

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

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

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

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

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

47、?A' A'→?A'| ?,,例如, 算術(shù)表達(dá)式文法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,一般地, 設(shè)文法中A的產(chǎn)生式為: A→A?1|A?2|…|A?m| ?1|?2|…|?n 其中,每個(gè)?都不等于ε

49、 每個(gè)?都不以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,如何消除文法的間接左遞歸？ 間接左遞歸的存在是由于非終結(jié)符之間形成了循環(huán)推導(dǎo), 只要把循環(huán)推導(dǎo)中的某個(gè)連接切斷, 間接左遞歸就消除了。,切斷循環(huán)推導(dǎo)中的某個(gè)連接的方法：Step1.

51、 對(duì)n個(gè)產(chǎn)生式中的某一個(gè)進(jì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. 對(duì)其余n-1個(gè)產(chǎn)生式中的某一個(gè)進(jìn)行 至多n-2次替換,再消除直接左遞歸。 …,考慮上述文法的后兩個(gè)產(chǎn)生式: Q→Rb | b R→Sa | a | Qa,消除左遞歸

53、算法:(1)文法的所有非終結(jié)符排序?yàn)锳1,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)化簡(jiǎn), 刪去那些不可達(dá)元的產(chǎn)生式。,通過例子熟悉消除左遞歸算法執(zhí)行過程:例如, G[S]: S→Qc | c Q→Rb | b R→Sa | a,(1) 將非終結(jié)符排序?yàn)镽, Q, S;(2) 對(duì)于R (i=1, P1) 內(nèi)層循環(huán)不執(zhí)行; 消除R的直接左遞歸: R→Sa|a 對(duì)于Q

55、(i=2, P2) 內(nèi)層循環(huán)改寫P2→ P1γ: Q→Sab|ab|b 消除Q的直接左遞歸: Q→Sab|ab|b,對(duì)于S (i=3, P3) 內(nèi)層循環(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) 化簡(jiǎn), 刪去關(guān)于Q和R的產(chǎn)生式。,對(duì)消除左遞歸算法的兩點(diǎn)說明: (1)消除左遞歸算法有兩個(gè)限制條件:文法中不含回路(P P)和ε-生成式。該限制不會(huì)影響消除左遞歸算法的使用,因?yàn)楹罄m(xù)課程《形式語言》中將學(xué)到,對(duì)任一CFG G, 存在一個(gè)不含ε-生成式和單一生成式的CFG G', 使得L(G')=L(G)-{ε}。 (2) 對(duì)非終結(jié)符的不同排序會(huì)導(dǎo)致文法形式上

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

59、]與G'''[S]等價(jià)的證明: 證明: 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},有興趣的同學(xué)課后以下述文法為例熟悉消除左遞歸算法的執(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. 回溯的消除 要消除回溯,首先要清楚回溯存在的原因, 根除這些原因,自然就消除了回溯。 假設(shè)輪到用A去執(zhí)行匹配任務(wù), A→?1| ?2|…|?n, 而A面臨的第1個(gè)輸入符為a1。首先, 用?1的第1終結(jié)符與輸入符a1匹配,若成功,再用?1的第2終結(jié)符與下一輸入符a2匹配,…, 當(dāng)?1的第n終結(jié)符與當(dāng)前輸入符a

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

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

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

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

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

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

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

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

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