《編譯原理》教案(文件)

　

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