1、第五章自上而下語(yǔ)法分析,語(yǔ)法分析是繼詞法分析之后編譯過(guò)程的第2階段。它的主要任務(wù)是對(duì)詞法分析的輸出結(jié)果單詞序列進(jìn)行分析，識(shí)別合法的語(yǔ)法單位。 語(yǔ)法分析最常用的方法有：優(yōu)先方法、遞歸下降法、LL方法和LR方法。 所謂自上而下分析是指從樹(shù)的根結(jié)點(diǎn)開(kāi)始,為給定的輸入串構(gòu)造一棵語(yǔ)法樹(shù)。 本章中,我們通過(guò)討論一個(gè)一般的非確定的自上而下分析器來(lái)討論上下無(wú)關(guān)語(yǔ)言的自上而下分析器的設(shè)計(jì)。,5.1 非確定的下推自動(dòng)機(jī),下面所要構(gòu)造的非確定的自上而下分析器屬于一般的下推自動(dòng)機(jī)（PDA）類(lèi)。 所謂一個(gè)下推或棧自動(dòng)機(jī)（Stack Automaton）,非形式地說(shuō)，應(yīng)包含： 一個(gè)輸入符號(hào)串； 一個(gè)讀頭，它從左至右移動(dòng)，

2、每次讀進(jìn)一個(gè)輸入符號(hào)； 一個(gè)有窮狀態(tài)自動(dòng)機(jī)，用于控制整個(gè)系統(tǒng)的操作； 一個(gè)后進(jìn)先出下推棧，,下推自動(dòng)機(jī)的非空移動(dòng):,5.1.1 PDA形式定義,形式上說(shuō)，一個(gè)PDA是一個(gè)七元組： (Q,H,q0,Z0,F) Q 是狀態(tài)的有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)； 是有窮的字母表，它的每個(gè)元素是一個(gè)輸入符號(hào)； H 是有窮的下推棧字符表，它的每個(gè)元素稱為一個(gè)棧符號(hào)。 q0Q 是該P(yáng)DA的初態(tài)； Z0H 是下推棧的初始符號(hào)； F Q 是一個(gè)終態(tài)集(或接收狀態(tài)集)；它的每個(gè)元素稱為終態(tài)；(可空)。,5.1.1 PDA形式定義, 是描述PDA動(dòng)作與狀態(tài)變化的。 PDA的動(dòng)作可用定義式來(lái)表示為： （q,a,z)=

3、(p1,h1),(p2,h2)(pn,hn) 它的含義為： 在控制器當(dāng)前狀態(tài)為q,下推棧頂符號(hào)為z ,輸入符號(hào)為a的情況下，把控制器的狀態(tài)改為pi,用hi 替換棧頂?shù)膠，并讓讀頭右移一格。,5.1.2 PDA的 構(gòu)形和移動(dòng),PDA的一個(gè)構(gòu)形是一個(gè)三元組：(q,w,h) 其中，qQ；w*是尚待掃描的輸入串，包括讀頭當(dāng)前所指的符號(hào)；hH*是棧的內(nèi)容。 PDA的一次移動(dòng)可看作是從一種構(gòu)形變換成另一種構(gòu)形的一種方式。反過(guò)來(lái)，構(gòu)形又為定義PDA的移動(dòng)提供了一種更簡(jiǎn)單的手段。我們稱 (q,ax,Zh)(p,x,hh) 是一次可能的移動(dòng)，當(dāng)且僅當(dāng)(p,h)(q,a,Z) 。 常用+表示由一次或多次移動(dòng)組成的

4、序列。用*表示由零次或多次移動(dòng)組成的序列。注意“零”次移動(dòng)并不改變當(dāng)前的構(gòu)形。,5.1.2 PDA的 構(gòu)形和移動(dòng),PDA M 所識(shí)別的語(yǔ)言L（M）可表示為： L（M）= *（P0,，Z0)*(P,)(空棧接收）或者 L（M）= *（P0,，Z0)*(P,h) pF（終態(tài)接收）,例5.1 考慮下表定義的兩狀態(tài)PDA，其的兩個(gè)狀態(tài)分別是p和Q，(p,a,Z)=（p1,h1）,(p2,h2),輸入符號(hào)是0和1，棧符號(hào)是R，B和G。該P(yáng)DA識(shí)別由符號(hào)0和1組成的所有回文(Palindrome) 。,這個(gè)自動(dòng)機(jī)是非確定的，因?yàn)樵谛?和行6包含了可供選擇的移動(dòng)；也因?yàn)闊o(wú)輸入符號(hào)(如在行7)時(shí)照樣可進(jìn)行移動(dòng)

5、，而且此時(shí)存在相應(yīng)的選擇。該P(yáng)DA的開(kāi)始狀態(tài)時(shí)p，初始棧內(nèi)容時(shí)R。它停止于空棧。用該P(yáng)DA識(shí)別輸入串001100，其識(shí)別過(guò)程如下：,（p,001100,R） （p,01100,BR） 由行1 或 （Q,001100,） 由行7(阻塞) （p,01100,BR） （p,1100,BBR） 由行3a 或 （Q,1100,R） 由行3b （Q, 1100,R） （Q,1100,） 由行10(阻塞) （p,1100,BBR） （p,100,GBBR） 由行5 （p, 100,GBBR） （p,00,GGBBR） 由行6a,或 （Q,00,BBR） 由行6b （p,00,GGBBR） （p,0,BGGB

6、BR） 由行4 （p,0,BGGBBR） （p,BBGGBBR） 由行3a(阻塞) 或 （Q,GGBBR） 由行3b(阻塞) （Q,00,BBR） （Q,0,BR） 由行8 （Q,0,BR） （Q,R） 由行8 （Q,R） （Q,） 由行10(接收),5.1.3 上下文無(wú)關(guān)語(yǔ)言與PDA,聯(lián)系PDA和上下文無(wú)關(guān)語(yǔ)言的一個(gè)重要定理是： 定理5.1 對(duì)每一個(gè)上下文無(wú)關(guān)語(yǔ)言L，存在一個(gè)恰好識(shí)別L的非確定的PDA M，反之亦然。 這個(gè)定理在編譯系統(tǒng)中的實(shí)際重要性在于：現(xiàn)有的大多數(shù)高級(jí)程序設(shè)計(jì)語(yǔ)言都可用上下文無(wú)關(guān)文法描述。因此定理5.1隱含了：識(shí)別這個(gè)語(yǔ)言的機(jī)械識(shí)別器必是PDA。,5.1.3 上下文無(wú)關(guān)語(yǔ)

7、言與PDA,定理5.1包含兩方面含義： 給定一個(gè)上下文無(wú)關(guān)語(yǔ)言，存在一個(gè)識(shí)別它的PDA M； 反過(guò)來(lái)，給定一個(gè)PDA M，可以根據(jù)它構(gòu)造出一個(gè)等價(jià)的上下文無(wú)關(guān)文法。 前者對(duì)編譯程序的構(gòu)造很有吸引力，但后者則不然。,算法5.1 從CFG到NDPDA 給定 CFG G=（N，P，S） 可以構(gòu)造 一個(gè)相應(yīng)的非確定的PDA M： M=(Q,H,q0, Z0,F) 它只有一個(gè)狀態(tài)q和下面的轉(zhuǎn)換規(guī)則： 對(duì)P中每一個(gè)形如Aw的產(chǎn)生式，(q,A)包含(q,w); 對(duì)每個(gè)a，(p,a,a)包含(q,) 且 Q=q = H=N q0=q Z0=S F為終態(tài)集(可空)。 這個(gè)PDA停止于空棧。,例5.2 考慮文法

8、S0S1|c 該文法描述語(yǔ)言0*c1*,其中0的個(gè)數(shù)和1的個(gè)數(shù)相等。轉(zhuǎn)換規(guī)則是： 1.(q,0,0)=(q,) 2.(q,1,1)=(q,) 3.(q,c,c)=(q,) 4.(q,S)=(q,0S1) ,(q,c)(其中可與任何合法輸入符號(hào)匹配) 其中規(guī)則1、2、3根據(jù)前面的規(guī)則構(gòu)造，4根據(jù)規(guī)則 構(gòu)造。,使用例5.2分析句子,給定輸入串00c11，所構(gòu)造的PDA用下面的移動(dòng)序列來(lái)接收它(注意，我們可從構(gòu)形中省掉狀態(tài)，因?yàn)樗偸窍嗤?： (q,00c11,S)4a(q,00c11,0S1)1(q,0c11,S1) 4a(q,0c11,0S11)1(q,c11,S11) 4b(q,c11,c1

9、1)3(q,11,11) 2(q,1,1)2(q,) (接收),輸入串，棧和句型,由算法5.1構(gòu)造的非確定的PDA的一個(gè)有趣特性是由下面的定理表示出來(lái)的。 定理5.2 令(q,y,h)是某個(gè)文法G相關(guān)的NDPDA的任意構(gòu)形，其中輸入串是xy，如果 (q,xy,S)*(q,y,h) 那么xh是G的一個(gè)最左句型，換言之，S*xh(S是G的開(kāi)始符號(hào))。 上述定理反過(guò)來(lái)也成立：給定G中的任何句型xh，如果x是一個(gè)終結(jié)符串，而且h中至多最左符號(hào)是終結(jié)符，那么，(q,y,h)是該NDPDA的一個(gè)構(gòu)形，而且 (q,xy,S)*(q,y,h),5.2 消除左遞歸方法 5.2.1 文法的左遞歸性,文法的左遞歸性

10、屬文法遞歸性的一種，在一文法中，所有形如 AxAy x,y (N) *，AN 稱為遞歸產(chǎn)生式(或自嵌入產(chǎn)生式)。 若其中x=，則有 AAy 稱之為直接左遞歸產(chǎn)生式。,5.2.1 文法的左遞歸性,若其中y=，則有 AxA 稱之為直接右遞歸產(chǎn)生式。 若一文法中至少含有一條遞歸產(chǎn)生式，或在用該文法推導(dǎo)符號(hào)串的過(guò)程中，存在AA或AA或AA形式的推導(dǎo)，則稱該文法是(直接)遞歸的。,非確定的自頂向下分析存在的問(wèn)題,非確定的自上而下的分析法：對(duì)任何輸入串W試圖用一切可能的辦法，從文法的開(kāi)始符號(hào)出發(fā)，自上而下地為它建立一棵語(yǔ)法樹(shù)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)，如果試探成功，則W為相應(yīng)文法的句子，否則W就不

11、是文法的句子。這種分析過(guò)程本質(zhì)上是一種窮舉試探過(guò)程，反復(fù)使用不同的規(guī)則，謀求匹配輸入串的過(guò)程。,回溯現(xiàn)象 侯選式：我們把文法中每個(gè)非終結(jié)符A的右部（可能有多個(gè)）稱為A的侯選式。 當(dāng)某非終結(jié)符對(duì)應(yīng)多個(gè)侯選式時(shí)，如果其中有幾個(gè)侯選式的右部左端第一個(gè)符號(hào)相同，那么就會(huì)使得語(yǔ)法分析程序無(wú)法根據(jù)當(dāng)前的輸入符號(hào)準(zhǔn)確地決定選用哪個(gè)侯選式來(lái)替換A，只能采用試探的辦法，任選某個(gè)侯選式去試探一次。如果不能導(dǎo)致最終地匹配，只得再換另一個(gè)侯選式去試探，這就造成了回溯現(xiàn)象。所以這種帶回溯的自頂向下分析法，實(shí)際上是采用了一種窮盡一切可能選擇的試探法。,回溯現(xiàn)象：在回溯之前，編譯程序?qū)嶋H已經(jīng)做了大量薄記工作，包括語(yǔ)義翻譯工

12、作在內(nèi)。在回溯時(shí)，要清除這些內(nèi)容，然后開(kāi)始重新薄記，這就降低了分析效率。 左遞歸現(xiàn)象：回溯使語(yǔ)法分析器的動(dòng)作不穩(wěn)定，左遞歸會(huì)使分析程序進(jìn)入到無(wú)窮的循環(huán)之中，這些問(wèn)題都和描述語(yǔ)言的文法有直接關(guān)系。,5.2.2 用擴(kuò)展的BNF表示法消除左遞歸,在前面，文法的產(chǎn)生式都是采用巴科斯范式（BNF）描述的，它使得文法更嚴(yán)謹(jǐn)、簡(jiǎn)潔和清晰。為了消除文法的左遞歸，需對(duì)巴科斯范式進(jìn)行擴(kuò)展，增加以下元符號(hào)： 花括號(hào) ：表示符號(hào)串x出現(xiàn)零次或多次。 ：n表示符號(hào)串x能重復(fù)出現(xiàn)的最大次數(shù)，m表示符號(hào)串x能重復(fù)出現(xiàn)的最小次數(shù)。 方括號(hào) 方括號(hào)用來(lái)表示可選項(xiàng)。x = x或，表示符號(hào)串x可出現(xiàn)一次或不出現(xiàn)。可以用來(lái)定義某些高

13、級(jí)語(yǔ)言中的“條件語(yǔ)句”。 圓括號(hào)（ ） 利用圓括號(hào)可提出一個(gè)非終結(jié)符的多個(gè)產(chǎn)生式右部的公共因子。例如， Axy|xw|xz 可寫(xiě)成 Ax(y|w|z),利用下面的兩條規(guī)則，可把包含直接左遞歸的產(chǎn)生式轉(zhuǎn)換成用擴(kuò)展BNF表示法表示的產(chǎn)生式。 提公因子 每當(dāng)一條產(chǎn)生式中有公因子可提的時(shí)候，就把它提出來(lái)，若原產(chǎn)生式是 Ax|xy 則可寫(xiě)成 Ax(y|)，這里把當(dāng)作最后一個(gè)候選式。 若 Ax|y|z|Av 是一組產(chǎn)生式，且它只有一個(gè)直接左遞歸的右部位于最后，則可把這組產(chǎn)生式變換成如下形式： A(x|y|z)v 也就是說(shuō)，使用上述規(guī)則，可把產(chǎn)生式改寫(xiě)成相對(duì)于某個(gè)非終結(jié)符而言，至多只含一個(gè)直接左遞歸的右部；

14、然后，利用上述規(guī)則消除這個(gè)直接左遞歸。,5.2.3 直接改寫(xiě)文法,設(shè)產(chǎn)生式 U Uxy 此產(chǎn)生式稱為直接左遞歸形式。其中，x和y是兩個(gè)符號(hào)串，y的首字符不是U。 產(chǎn)生式為直接左遞歸形式，可直接改寫(xiě)為一個(gè)等價(jià)的非直接左遞歸形式 U yU U xU 其中U是新引進(jìn)的非終結(jié)符號(hào)。顯然，這種形式與原形式是等價(jià)的，即從A推出的符號(hào)串是相同的。,直接左遞歸更一般的形式 U Ux1Ux2Uxmy1y2yn 其中，xi (i=1, 2, , m) yi (i=1, 2, , n), yj的頭字符都不是U, xi 都不是,則有 U y1U y2UynU U x1U x2UxmU,消除左遞歸舉例。 例如 ：有文法

15、： SSa 可改寫(xiě)為：SbS Sb SaS| 表達(dá)式文法： 消除左遞歸后： EE+T|T ETE E+TE| TT*F|F TFT T*FT| F(E)|i F(E)|i,消除間接左遞歸 1重新改寫(xiě)文法 2先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再按上述方法消除。 例（1）AaB 用（1）（2）去替換（3）中的A可得： （2）ABb （1）BaBc （3）BAc （2）BBbc （4）Bd （3）Bd 消除左遞歸后可得： B(d|aBc)B BbcB| 最終文法為： （1）AaB （2）ABb （3）B(d|aBc)B （4）BbcB|,5.2.4 消除所有左遞歸的算法,若一個(gè)文法不含形如A+A的推

16、導(dǎo)，也不含有以為右部的產(chǎn)生式，那么，執(zhí)行下面的算法將保證消除該文法中的所有左遞歸: 將文法G的所有非終結(jié)符整理成某一順序U1，U2，Un。 for i:= 1 to n do begin for j:= 1 to i1 do begin 把產(chǎn)生式Ui Uj替換成 Ui 12m (其中Uj 12m 是該文法中關(guān)于Uj的所有產(chǎn)生式) end; 消除Ui產(chǎn)生式中的直接左遞歸 end; 化簡(jiǎn)改寫(xiě)之后的文法，刪除多余產(chǎn)生式。,5.3 LL(k)文法,LL(k)文法是上下文無(wú)關(guān)文法的一個(gè)真子集。同時(shí)，LL(k)文法也是允許采用確定的自上而下分析技術(shù)的最大一類(lèi)文法。 LL（K）的含義：自左至右掃描(輸入串)

17、，自上而下進(jìn)行最左推導(dǎo)。K的含義是指在分析的過(guò)程中至多向前查看K個(gè)符號(hào)，一般情況下，K1。 給定一文法，判斷它是否是一個(gè)LL(k)文法并不是很容易的事。我們將給出一個(gè)判斷條件。根據(jù)這個(gè)條件就能推斷一個(gè)給定的文法是否是LL(k)文法。此外，由于分析表是分析器的核心，因此，我們將給出構(gòu)造LL(k)分析器的分析表的方法。,LL（1）文法的引入,為了保證能夠進(jìn)行確定的自頂向下的分析，文法應(yīng)該滿足在分析的過(guò)程中，每次對(duì)產(chǎn)生式的選擇都是唯一的。 S-文法：（舉例） 每個(gè)產(chǎn)生式右邊都以終結(jié)符開(kāi)始； 同一個(gè)非終結(jié)符的各個(gè)侯選式的首終結(jié)符不同； Q-文法：（舉例） 每個(gè)產(chǎn)生式右邊都為或以終結(jié)符開(kāi)始； 具有相同左

18、部的產(chǎn)生式具有不相交的可選集； LL（1）文法： 一個(gè)上下文無(wú)關(guān)文法稱為是LL（1）文法，當(dāng)且僅當(dāng)同一非終結(jié)符的各個(gè)產(chǎn)生式的可選集互不相交。,5.3.1 LL(1)文法的判斷條件,按照前面所述方法改造，消除左遞歸后的文法不一定就是一個(gè)LL(1)文法，還必須借助于某種判斷條件才能確定。為此，我們將引進(jìn)三個(gè)集合：FIRST,FOLLOW和SELECT。 先定義集合FIRST和FOLLOW。 設(shè)是文法G的一個(gè)符號(hào)串，(VNVT)*，定義 FIRST() = a a, aVT, (VNVT)* 特別，若有 ，則FIRST（）。即，F(xiàn)IRST()是從可推導(dǎo)出的所有首終結(jié)符或可能的。 設(shè)S是文法的識(shí)別符號(hào)

19、，U VN ，定義 FOLLOW(U) = bS xUby，bVT，x, y(VNVT)* 若S xU，則規(guī)定“$”FOLLOW(U)。即，F(xiàn)OLLOW(U)是文法的所有句型中緊接在U之后出現(xiàn)的終結(jié)符或$($不是文法符號(hào)，而是一個(gè)特定的結(jié)束符)。,再來(lái)看看SELECT集合。 假定U是文法G的任一產(chǎn)生式，其中UVN，(VNVT)*，集合SELECT(U)的構(gòu)造如下： 利用上面的三個(gè)集合可建立LL(1)文法的判斷條件如下： 令G是一個(gè)CFG，當(dāng)且僅當(dāng)對(duì)于G中每個(gè)具有相同左部的產(chǎn)生式(即一個(gè)非終結(jié)符的所有產(chǎn)生式) U1|1|n 都有 SELECT (Ui)SELECT(Uj)= (ij, i, j=

20、1, 2, , n)，則文法G是一個(gè)LL(1)文法。,5.3.2 集合FIRST、FOLLOW與SELECT的構(gòu)造,1.FIRST（）的求法：設(shè)A是一產(chǎn)生式， （1）若=a，且aVt，則FIRST（）=a； （2）若=X，X是非終結(jié)符（XVn），且X=*b，則把終結(jié)符b加入到FIRST（）中； （3）若=X1X2Xk，X1，X2，Xk都是非終結(jié)符，而X1X2Xi =* ，則把FIRST（Xi+1Xk）加入到FIRST（）中，其中1ik-1；如果X1X2Xk ，則把FIRST()加入到FIRST()中。,2.FOLLOW（A）的求法： （1）若有產(chǎn)生式BAa，a是終結(jié)符，把a(bǔ)加入到FOLLOW（

21、A）中； （2）若有產(chǎn)生式BAX，X是非終結(jié)符，則把FIRST（X）加入到FOLLOW（A）中； （3）若BaA，或BaA，但=* 則把FOLLOW（B）加入到FOLLOW（A）中； （4）若A是文法的開(kāi)始符號(hào)，則把結(jié)束符$加入到FOLLOW（A）中。,3. SELECT可選集的求法： 設(shè)A是文法G的任意產(chǎn)生式，它的編號(hào)為i，則它的可選集SELECT（i）定義如下： （1）如果，且是不可空的，則SELECT（i）=FIRST（）； （2）如果，但是可空的，則SELECT（i）=FIRST（） FOLLOW（A）； （3）如果=，即產(chǎn)生式為A則SELECT（i）=FOLLOW（A）。,例5.9

22、設(shè)文法G32 S： (1) S A (2) A BA (3) A iBA (4) A (5) B CB (6) B +CB B (8) C ) A* (9) C ( SELECT (AiBA)SELECT(A)= FIRST(iBA)(FIRST()FOLLOW(A)= i*, $, =, SELECT (B +CB)SELECT(B) = FIRST(+CB)(FIRST()FOLLOW(B)= +i, *, $, =, SELECT (C )A*)SELECT(C ( )= FIRST( )A*)FIRST ( ( )= ) ( =。 此文法G是一個(gè)LL(1)文法,需要注意的是，對(duì)于LL(

23、1)文法，利用SELECT集，我們還可以得到十分有助于句子分析的結(jié)果： 在分析過(guò)程中的某一步，當(dāng)非終結(jié)符U正處于棧頂時(shí)，若aSELECT (U)是當(dāng)前的輸入符號(hào)，則可立即選用產(chǎn)生式U；若aSELECT (U)是當(dāng)前的輸入符號(hào)，則可選用產(chǎn)生式U。 由于LL(1)文法的任何一對(duì)具有相同左部的產(chǎn)生式的SELECT集是不相交的，因此，根據(jù)現(xiàn)行的非終結(jié)符(已在棧頂)和當(dāng)前的輸入符號(hào)就能唯一地確定分析過(guò)程中的下一步動(dòng)作，也就是說(shuō)，我們完全可以為L(zhǎng)L(1)文法構(gòu)造一個(gè)確定的分析器。,5.4 確定的LL(1)分析器的構(gòu)造,主要由三個(gè)部分組成： （1）LL(1)(預(yù)測(cè))分析表 （2）分析棧 （3）分析器總控程序

24、,5.4.1 LL(1)分析表的構(gòu)造 預(yù)測(cè)分析表是根據(jù)文法產(chǎn)生式的可選集(SELECT)構(gòu)造的，可用一個(gè)二維數(shù)組 MU,a來(lái)描述。 行：文法中所有非終結(jié)符VN。 列：文法中所有終結(jié)符VT及文法結(jié)束符號(hào)$。 矩陣元素：當(dāng)前行非終結(jié)符VN面臨列終結(jié)符 VT時(shí)，繼續(xù)推導(dǎo)所應(yīng)采用的產(chǎn)生 式（產(chǎn)生式標(biāo)號(hào)） 方法: 如果 a SELECT(U ) 則 MU,a = U MU,a中也可能存放一個(gè)ERROR，表示此時(shí)輸入串中存在語(yǔ)法錯(cuò)誤。,例5.11 對(duì)于例5.9中的文法G S，構(gòu)造分析表。 對(duì)于產(chǎn)生式S A， FIRST(A)=(, )， MS, ( = S A，MS, ) = SA。 對(duì)于產(chǎn)生式ABA，

25、FIRST(B)=(, )， MA, C = A BA，MA, ) = A BA。 對(duì)于產(chǎn)生式A iBA, FIRST (iBA) = i, MA, i= A iBA。 對(duì)于產(chǎn)生式A ， FOLLOW(A)=* , $， MA, * = A , MA, $=A 。,對(duì)于產(chǎn)生式BCB, FIRST(C) = (, ), MB, C = B CB，MB, ) = BCB。 對(duì)于產(chǎn)生式B +CB， FIRST(+CB) = +， MB, + = B +CB。 對(duì)于產(chǎn)生式B ， FOLLOW(B) = i, *, $, MB, i = B ，MB, * = B , MB, $ = B。 對(duì)于產(chǎn)生式C

26、)A*， FIRST ( )A*) = ) ， MC, ) = C )A*。 對(duì)于產(chǎn)生式C (， FIRST ( ) ) = ( ， MC, ( = C (。,分析表M,5.4.2 LL(1)分析器的總控算法,LL(1)分析器就是帶有LL(1)分析表的一個(gè)PDA，也稱預(yù)測(cè)分析程序。下面給出LL(1)分析器的總控算法： 最初，分析器把文法的開(kāi)始符號(hào)S置于棧頂(假定輸入串以$結(jié)束)； 若棧頂為一終結(jié)符，而且與當(dāng)前輸入符號(hào)匹配，則讀頭前進(jìn)一位置(掃描下一輸入符號(hào))，并逐出棧頂符號(hào)。否則報(bào)錯(cuò)。(匹配動(dòng)作) 若棧頂符號(hào)是一非終結(jié)符U，且當(dāng)前的輸入符號(hào)為a，則查看分析表M，若MU,a置有關(guān)于U的產(chǎn)生式Uw

27、，則先從棧中逐出U再把w 反序進(jìn)棧；若w=，則不推進(jìn)任何信息進(jìn)棧，僅逐出棧頂符號(hào)；若MU,a為空白，則調(diào)用出錯(cuò)處理子程序。(應(yīng)用動(dòng)作) 重復(fù)步驟、，直至棧變?yōu)榭铡?該分析器停止于空棧。(接收),例5.14 按照LL（1）分析器總控算法，對(duì)文法G32S的符號(hào)串 ( i (進(jìn)行分析，分析過(guò)程見(jiàn)下表。分析結(jié)果表明該符號(hào)是文法G32S的一個(gè)句子。,LL(1)分析法的優(yōu)缺點(diǎn): 預(yù)測(cè)分析法是確定的自頂向下分析，不會(huì) 產(chǎn)生回溯現(xiàn)象。 分析時(shí)間大約正比于程序長(zhǎng)度。 具有良好的診斷和錯(cuò)誤恢復(fù)能力。 預(yù)測(cè)分析表較其它分析方法中的分析表相 對(duì)較小，節(jié)省空間。 只適用于一類(lèi)可用預(yù)測(cè)分析文法描述的語(yǔ) 言的語(yǔ)法分析。存在

28、對(duì)非LL（1）文法的改造問(wèn)題。,5.5 LL(k)文法的幾個(gè)結(jié)論,可以證明： LL(k)文法是不含左遞歸的； LL(k)文法是無(wú)二義性的； 一文法G是LL(1)，當(dāng)且僅當(dāng)對(duì)于G的每一非終結(jié)符U的任何兩個(gè)不同產(chǎn)生式A|，下面的條件成立： FIRST()FIRST()= ; ,中至多只有一個(gè)能推出空串； 若 ，則FIRST()FOLLOW(A)= 。,5.6 遞歸下降分析程序及其設(shè)計(jì),遞歸下降法的實(shí)現(xiàn)思想： 遞歸下降法又稱為遞歸子程序法，是比較簡(jiǎn)單、直觀，易于構(gòu)造的一種語(yǔ)法分析方法。它的實(shí)現(xiàn)思想是對(duì)應(yīng)文法中每個(gè)非終結(jié)符編寫(xiě)一個(gè)遞歸(子程序)過(guò)程，每個(gè)過(guò)程的功能是分析與識(shí)別由該非終結(jié)符推出的串，當(dāng)某

29、非終結(jié)符的產(chǎn)生式有多個(gè)侯選式時(shí)能夠按LL（1）形式可唯一地確定選用某個(gè)侯選式進(jìn)行推導(dǎo)。,遞歸子程序的設(shè)計(jì)方法,一般情況下，用非終結(jié)符表示過(guò)程的名字，過(guò)程體則按產(chǎn)生式右部符號(hào)串順序編寫(xiě)。每匹配一個(gè)終結(jié)符，則再讀入下一個(gè)符號(hào)，對(duì)于產(chǎn)生式右部的每一個(gè)非終結(jié)符，則調(diào)用相應(yīng)的過(guò)程。當(dāng)一個(gè)非終結(jié)符對(duì)應(yīng)多個(gè)侯選式時(shí)，則過(guò)程體將按可選集來(lái)決定選用哪個(gè)侯選式。在遞歸下降法中，遞歸子程序數(shù)等于文法中的非終結(jié)符個(gè)數(shù)。,構(gòu)造遞歸下降分析程序時(shí)，每個(gè)函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體則是根據(jù)規(guī)則右部符號(hào)串的結(jié)構(gòu)編寫(xiě)。 （1）當(dāng)遇到終結(jié)符a時(shí)，則編寫(xiě)語(yǔ)句： if （當(dāng)前讀入的輸入符號(hào)=a）,讀入下一個(gè)符號(hào)； （2）當(dāng)遇到非終結(jié)符A時(shí)，則編寫(xiě)語(yǔ)句調(diào)用相應(yīng)的函數(shù)A（）； （3）當(dāng)遇到A時(shí)，則編寫(xiě)語(yǔ)句： if（當(dāng)前讀入的符號(hào)FOLLOW（A）,ERROR( ); (4)當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)侯