【正文】 、Q、R代表任意非終結(jié)符；‘…’代表有終結(jié)符和非終結(jié)符組成的任意序列，包括空字?！璦Qb…的產(chǎn)生式。Qb…。+…aQ。b 則稱G是一個(gè)算符優(yōu)先文法。為了找出所有滿足關(guān)系+Qa…,a206。+…aQ, a206。的所有終結(jié)符對(duì)。 類似地，假定有產(chǎn)生式的一個(gè)候選式為…Pb…那末，對(duì)任何a206。a…或P174。Q…，則a206。X1X2…Xn FOR i:=1 TO n1 DO BEGIN IF Xi 和 Xi+1 均為終結(jié)符THEN 置 Xi= Xi+1 END 至此我們完成了從文法G構(gòu)造優(yōu)先表的算法。由于非終結(jié)符對(duì)歸約沒有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧S。=(2)對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)結(jié)點(diǎn)(包括出發(fā)結(jié)點(diǎn)自身在內(nèi))的個(gè)數(shù)。如果有矛盾，那么，就不存在優(yōu)先函數(shù)。b，則f(a) g(b).在實(shí)際實(shí)現(xiàn)算符優(yōu)先分析算法時(shí)，一般不用上述這樣的優(yōu)先表，而是用兩個(gè)優(yōu)先函數(shù)f和g相對(duì)應(yīng)，函數(shù)f稱為人棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。但是，我們可以通過檢查棧頂符號(hào)和輸入符號(hào)的具體內(nèi)容來發(fā)現(xiàn)那些原先不可比較的情形。這張分析表包括兩部分，一是“動(dòng)作”(ACTION)表，另一是“狀態(tài)轉(zhuǎn)換”(G0TO)表。顯然，[s，X]定義了一個(gè)以文法符號(hào)為字母表的DFA。b進(jìn)行歸約。(3)接受 宣布分析成功，停止分析器的工作。不管什么分析表，總控程序都是一樣地工作。棧頂狀態(tài)為Sm，符號(hào)串X1X2…Xm是至今已移進(jìn)歸約出的部分。所謂活前綴是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。假定文法是一個(gè)以S 為開始符號(hào)的文法，我們構(gòu)造一個(gè)G39。 是G39。這樣，便會(huì)產(chǎn)生一個(gè)僅含項(xiàng)目S39。 由于假定LR(0) 文法規(guī)范族的每一個(gè)項(xiàng)目集不含沖突項(xiàng)目，因此，按上述方法構(gòu)造的分析表的每一個(gè)入口都是唯一的（即不含多重定義）。上面所說的LR(0)文法是一類非常簡(jiǎn)單的文法。δ?bβ , A174。 Follow(B),則可以根據(jù)當(dāng)前讀頭下符號(hào)a來消除沖突。 Follow(B)，按B174。 Follow(A)，就確定采用A174。因此此時(shí)用A174。 LALR分析表的構(gòu)造 現(xiàn)在來討論構(gòu)造分析表的LALR方法。對(duì)于ALGOL一類語言來說，一般要用幾百個(gè)狀態(tài)，但若用規(guī)范LR分析表，同一類語言，卻要用幾千個(gè)狀態(tài)。但是，某些二義文法是非常有用的。用這種方法改變算符的優(yōu)先級(jí)是非常方便的。YACC輸入用戶提供的語言的語法描述規(guī)格說明，基于LALR語法分析的原理，自動(dòng)構(gòu)造一個(gè)該語言的語法分析器，同時(shí)，它還能根據(jù)規(guī)格說明中給出的語義子程序建立規(guī)定的翻譯。 其他□教學(xué)方式（請(qǐng)打√）：講授254。這些屬性代表與文法符號(hào)相關(guān)的信息，例如它的類型、值、代碼序列 、符號(hào)表內(nèi)容等等。屬性加工的過程即是語義處理的過程，對(duì)于文法的每一個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，則稱為語義規(guī)則。僅僅使用綜合屬性的屬性文法稱S—屬性文法。在一顆語法樹中的結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以用稱作依賴圖的一個(gè)有向圖來描述。 例如，屬性 :=f( , ) 對(duì)應(yīng)于產(chǎn)生式 A174。XY對(duì)應(yīng)的語義規(guī)則還有： :=g(,) 那么，圖中還應(yīng)有兩條有向邊，,. S—屬性文法的自下而上計(jì)算 這一節(jié)我們考慮這樣一類屬性文法：S—屬性文法，它只含有綜合屬性。我們使用一個(gè)棧來存放已經(jīng)分析過的子樹的信息。L—屬性文法允許通過一次遍歷就計(jì)算出所有屬性值。 (2) 如果E是E1opE2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為E1’E2’op，這里E1’和E2’分別為El和E2的后綴式。只要我們知道每個(gè)算符的目數(shù)，對(duì)于后綴式，不論從哪一端進(jìn)行掃描，都能對(duì)它正確進(jìn)行唯一分解。之所以稱為三地址代碼是因?yàn)槊織l語句通常包含三個(gè)地址，兩個(gè)用來表示操作數(shù)，一個(gè)用來存放結(jié)果。符號(hào)標(biāo)號(hào)代表存放中間代碼的數(shù)組中三地址代碼語句的下標(biāo)。有關(guān)活動(dòng)記錄我們將在第九章詳細(xì)介紹。從而我們需要一個(gè)全程變量如offset來跟蹤下一個(gè)可用的相對(duì)地址的位置。非終結(jié)符號(hào)T有兩個(gè)綜合屬性T．type和 T．width，分別表示名字的類型和名字的域?qū)?即該類型名字所占用的存儲(chǔ)單元個(gè)數(shù))。在下面的語義規(guī)則中用到如下操作： (1)mktable(previous)創(chuàng)建一張新符號(hào)表，并返回指向新表的一個(gè)指針。(2)enter(table，name，type，offset)在指針table指示的符號(hào)表中為名字建立一個(gè)新項(xiàng)，并把類型type、相對(duì)地址offset填入到該項(xiàng)中。 記錄中的域名 當(dāng)遇到保留字record時(shí)，與標(biāo)記非終結(jié)符號(hào)I相應(yīng)的語義動(dòng)作為記錄中的各域名創(chuàng)建一張新的記錄符號(hào)表。當(dāng)記錄的所有域名都被檢查過之后，在offset的棧頂將存放著記錄之內(nèi)的所有數(shù)據(jù)對(duì)象的總域?qū)?。有關(guān)類型構(gòu)造符和類型表達(dá)式概念將在4．7節(jié)介紹。該翻譯模式中說明了如何查找符號(hào)表的入口。 數(shù)組元素的引用現(xiàn)在討論包括數(shù)組元素的表達(dá)式和賦值語句的翻譯問題。即若high2為i2的上界，則n2=high2 – low2 +1.假定i1,i2是編譯時(shí)唯一尚未知道的值，我們可以重寫上述表達(dá)式為： ( (i1*n2) + i2) *w +( base –（ (low1 *n2) + low2) *w）后一項(xiàng)子表達(dá)式( base – （(low1 *n2) + low2) *w ）的值是可以在編譯時(shí)確定的,為常數(shù)。 id 出現(xiàn)的地方也允許下面產(chǎn)生式中的L出現(xiàn)，則可把數(shù)組元素引用加入到賦值語句中。，即維數(shù)。 （ …( ( i1*n2 +i2)n3)…)nm + im利用如下的遞歸公式進(jìn)行計(jì)算： e1 = i1, em = em1* nm + im于是 當(dāng)m=k時(shí)將ek乘以元素的寬度w便可計(jì)算出（）的第一個(gè)子項(xiàng)。這樣做的好處是可以把用在符號(hào)表中查找名字的程序同樣用來查找域名。如果類型像圖4．8和圖4．9一樣構(gòu)造，則p173。 布爾表達(dá)式的翻譯在程序設(shè)計(jì)語言中，布爾表達(dá)式有兩個(gè)基本作用： 一個(gè)使用作計(jì)算邏輯值；另一個(gè)是用作控制流語句如ifthen、ifthenelse和 wh。于是p的類型是record(t)，t可由此先取出來。如果t是一個(gè)指向某個(gè)記錄類型的指針，把類型構(gòu)造符record 施于該指針，返回所形成的類型record(t)作為屬性T．type的值。 記錄中域的作用 編譯器必須將記錄中的域的類型和相對(duì)地址保持下來。最后，用來臨時(shí)存放由Elist中的下標(biāo)表達(dá)式計(jì)算出來的值。其目的是使我們?cè)谡麄€(gè)下標(biāo)表達(dá)式串Elist的翻譯過程中隨時(shí)都知道符號(hào)表中相應(yīng)于數(shù)組名字id的全部信息。特別是當(dāng)low=1， 時(shí)有：V=(i1*n2+i2)*w C= base –(n2+1)*w應(yīng)該牢記。假定數(shù)組的每個(gè)元素的寬度為w，則一維數(shù)組A[i] 這個(gè)元素的起始地址為： base + (i – low)*w （）其中l(wèi)ow為數(shù)組下標(biāo)的下界， 并且base是分配給數(shù)組的相對(duì)地址，即base為A的第一個(gè)元素A[low]的相對(duì)地址。如果有，則返回一個(gè)指向該表項(xiàng)的指針，否則，返回nil表示沒找到。作為翻譯賦值語句為三地址代碼的一個(gè)部分，我們將討論如何在符號(hào)表中查找名字及如何存取數(shù)組和記錄的元素。類型T．type通過對(duì)指向本記錄符號(hào)表的指針施用類型構(gòu)造符record而得到。產(chǎn)生式D174。(4)enterproc(table，name，newtable)在指針table指示的符號(hào)表中為名字為name的過程建立一個(gè)新項(xiàng)。指針previous 之值放在新符號(hào)表表頭，表頭中還可存放一些其它信息如過程嵌套深度等。 保留作用域信息 過程readarray，exchange和quicksord的符號(hào)表有指針指向其外圍過程的符號(hào)表。在處理第一條說明語句之前，先置offset為0，以后每次遇到一個(gè)新的名字，便將該名字填入符號(hào)表中并置相對(duì)地址為當(dāng)前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對(duì)象的域?qū)挕＠?，假定在一個(gè)以字節(jié)編址的目標(biāo)機(jī)上，整數(shù)必須存放在4的倍數(shù)的地址單元，那么，計(jì)算地址時(shí)就應(yīng)以4的倍數(shù)增加。對(duì)每個(gè)局部名字，我們都將在符號(hào)表中建立相應(yīng)的表項(xiàng)，并填入有關(guān)的信息如類型、在存儲(chǔ)器中的相對(duì)地址等。三地址語句類似于匯編語言代碼。 圖表示法 這里的圖表示法包括DAG（無循環(huán)有向圖）與抽象語法樹。根據(jù)運(yùn)算量和算符出現(xiàn)的先后位置，以及每個(gè)算符的目數(shù)，就完全決定了一個(gè)表達(dá)式的分解。 后綴式后綴式表示法是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達(dá)式的方法，因此又稱逆波蘭表示法。State val… …X Y Z … … L—屬性文法和自頂向下翻譯 一個(gè)屬性文法稱為L—屬性文法：如果對(duì)于每個(gè)產(chǎn)生式A174。 下面我們討論分析棧中的綜合屬性。 如果在語法樹中應(yīng)用這個(gè)產(chǎn)生式，,。依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性b依賴屬性c，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條語義規(guī)則的形式為： b:=f(c1,c2,…,ck) 這里f是一個(gè)函數(shù)，而且或者 （1）b是A的一個(gè)綜合屬性并且c1,c2,…,ck是產(chǎn)生式右邊文法符號(hào)的屬性； 或者 （2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2,…，ck是A或 產(chǎn)生式右邊任何文法符號(hào)的屬性 在這兩種情況下，我們都說屬性b依賴于屬性c1,c2，…,ck.： 在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。 屬性一般分為兩類：綜合屬性和繼承屬性。 其他□教學(xué)資源（請(qǐng)打√）：多媒體254。 討論課□ 實(shí)驗(yàn)課254。發(fā)現(xiàn)錯(cuò)誤后，便進(jìn)入相應(yīng)的出錯(cuò)處理子程序。例如，若用下面的文法來描述含有+、*的算術(shù)表達(dá)式：E174。 二義文法的應(yīng)用 任何二義文法決不是一個(gè)LR文法，因而也不是SLR或LALR文法。LALR分析表比規(guī)范分析表要小得多，能力也差一點(diǎn)，但它卻能對(duì)付一些SLR所不能對(duì)付的情形。?對(duì)策：給每個(gè)LR(0)項(xiàng)目添加展望信息，即：添加句柄之后可能跟的終結(jié)符，因?yàn)檫@些終結(jié)符確實(shí)是規(guī)范句型中跟在句柄之后的。但是，在某種情況下，當(dāng)狀態(tài)k呈現(xiàn)于棧頂時(shí)，棧里的符號(hào)串所構(gòu)成的活前綴βα未必允許把α歸約為A。 規(guī)范LR分析表的構(gòu)造在構(gòu)造SLR分析表的方法中，若項(xiàng)目集Ik中含有A174。 Follow(A)，按A174。α?}LR(0)項(xiàng)目集，若Follow(A) ∩Follow(B)= f且b 207。如果LR(0)項(xiàng)目集中某個(gè)項(xiàng)目存在有沖突的項(xiàng)目集，可以根據(jù)讀頭下符號(hào)的不同來消除沖突。使用LR(0) 表的分析器叫做一個(gè)LR(0)分析器。 假定一個(gè)文法G 的拓廣文法G39。那么，我們稱G39。 ，并加進(jìn)了一個(gè)新產(chǎn)生式S39。 文法G的每一個(gè)產(chǎn)生式右部添加一個(gè)圓點(diǎn)就稱為G的一個(gè)LR(0)項(xiàng)目。 LR分析器 一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧）的確定有限狀態(tài)自動(dòng)機(jī)。棧的每一項(xiàng)內(nèi)容包括狀態(tài)s和文法符號(hào)X兩部分。LR分析器的總控程序本身的工作是非常簡(jiǎn)單的。歸約動(dòng)作不改變現(xiàn)行輸入符號(hào)。(1)移進(jìn) 把(s，a)的下一狀態(tài)s’=GOTO[s，a]和輸入符號(hào)a推進(jìn)棧，下一輸人符號(hào)變成現(xiàn)行輸入符號(hào)。ACTONIs，a]規(guī)定了當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。針對(duì)上述情況，處理錯(cuò)誤的子程序也可分成幾類。其缺點(diǎn)是，原先不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于與自然數(shù)相對(duì)應(yīng)，變成可比較的了。b，則f(a)＝g(b)；若a(3)檢查所構(gòu)造出來的函數(shù)f和g，看它們同原來的關(guān)系表是否有矛盾。=Q)進(jìn)行歸約。注意，在上述算法中，我們并沒有指出應(yīng)把所找到的最左素短語歸約到哪一個(gè)非終結(jié)符號(hào)‘N’。Xi+2 IF Xi為終結(jié)符而Xi+1為非終結(jié)符 THEN FOR FISTVT(Xi+1)中的每個(gè)a DO 置 Xi在我們有了每個(gè)非終結(jié)符P 的FISTVT(P)和LASTVT(P)之后我們就能夠造文法G的優(yōu)先表。FIRSTVT(P)(2)若a206。b.我們首先討論構(gòu)造集合FIRSTVT(P)的算法。FISTVT(P),我們有aVN }有了這兩個(gè)集合后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系VN } LASTVT(P)={a | P222。的終結(jié)符對(duì)，我們需要對(duì)G的每個(gè)非終結(jié)符P 構(gòu)造兩個(gè)集合FIRSTVT(P)和LASTVT(P): FIRSTVT(P)={a | P222。 通過檢查G的每個(gè)產(chǎn)生式的每個(gè)候選式，可以找出滿足a=b, a…Rb…的產(chǎn)生式， R而R222?！璦R…的產(chǎn)生式，R而R222。對(duì)于任何一對(duì)終結(jié)符a、b，我們說：（1） a=b 當(dāng)且僅當(dāng)文法G中含有形如P174。例如，ab并不一定意味著ba。也就是說，算符優(yōu)先分析法不是一種規(guī)范歸約法。因此，規(guī)范歸約的實(shí)質(zhì)是，在移進(jìn)過程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時(shí)就用相應(yīng)產(chǎn)生式的左部符號(hào)進(jìn)行替換。請(qǐng)注意句柄的“最左”特征，這一點(diǎn)對(duì)于移進(jìn)—?dú)w約來說是重要的。一個(gè)句型的最左直接短語稱為該句型的句柄。＋β則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。我們可用句柄來刻畫移進(jìn)—?dú)w約過程的“可歸約串”。 討論□ 示教□ 指導(dǎo)254。授課題目（教學(xué)章、節(jié)或主題）：第三章 語法分析——自下而上分析課時(shí)安排16授課時(shí)間