編譯原理教案(專業版)

　　

【正文】 在此意義下，利用上一節圖4．9中的語義動作可為每一個記錄類型建立一張單獨的符號表。前一子項隨i1, i2 而改變是一個變數。文法中end之后的語義動作是將offset的棧頂的總域寬作為綜合屬性T．width的值。假定整數類型域寬為4；實數域寬為8；一個數組的域寬可以通過把數組元素數目與一個元素的域寬相乘獲得；每個指針類型的域寬假定為以4增加。對于后面給出的三地址代碼中，用戶定義的名字在實際實現時將由指向符號表中的相應名字入口的指針所代替。現在我們可以在分析棧中使用一個附域來存放綜合屬性值。 35＋4n ： 在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定。授課題目（教學章、節或主題）：第四章 語法制導翻譯和中間代碼產生課時安排8授課時間 第11周 第4節 第12周 第14節第13周 第2節教學目的、要求（分掌握、熟悉、了解三個層次）：理解屬性文法的定義，語法制導翻譯方法熟悉中間代碼的形式掌握中間代碼形式變換掌握簡單賦值語句的翻譯、布爾表達式的翻譯、控制語句的翻譯教學重點和難點：屬性文法的定義，屬性的計算、中間代碼的形式、簡單賦值語句的翻譯、布爾表達式的翻譯、控制語句的翻譯授課類型（請打√）：理論課254。這本質上是一種折衷方法。即在構造LR分析表的算法中做一些改變：1）若當前輸入符a=b，做移進；2）若當前輸入符a 206。S?的狀態，這就是唯一的接受態。 LR分析器模型。每一項ACTON[s，a]所規定的動作不外是下述四種可能之一。現在必須證明：若a= 算符優先分析算法 在正確的情況下，算法工作完畢時，符號棧S應呈現：N。LASTVT(P),我們有a和(2) ab當且僅當G中含有形如P174。基于這一點，我們可用句柄來刻畫移進—歸約過程的“可歸約串”。最右推導常被稱為規范推導。(3)如果把FIRST(A)中的符號加入非終結符A的同步符號集，那么，當FIRST(A)中的一個符號在輸人中出現時，可以根據A恢復語法分析。我們現在要介紹的預測分析程序就是屬于這種類型的LL(1)分析器 預測分析程序工作過程 預測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號a行事的。dA’|g1|g2|… |gmA’174。 αp39。授課題目（教學章、節或主題）：第三章 語法分析——自上而下分析課時安排12授課時間 第4周 第36節 第6周 第16節 第7周 第12節 教學目的、要求（分掌握、熟悉、了解三個層次）：了解確定的自頂向下分析思想熟悉某些非LL（1）文法到LL（1）文法的等價變換掌握LL（1）文法的判別、確定的自頂向下分析方法教學重點和難點：語法分析器的功能、確定的自頂向下分析思想、LL（1）文法的判別、某些非LL（1）文法到LL（1）文法的等價變換、不確定的自頂向下分析思想、確定的自頂向下分析方法授課類型（請打√）：理論課254。P2β, ……,Pn1 222。這幾類文法的差別在于對產生式施加不同的限制。開始符號是一個特殊的非終結符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”。這個推導提供了一個證明，證明(i+i)是文法()所定義的一個算術表達式。我們可以從E出發，進行一系列的推導，推出種種不同的算術表達式來。 LEX的實現 LEX的編譯程序旨在將一個LEX源程序改造為一個詞法分析器L，這個詞法分析器L將像有限自動機那樣工作。上述結論加上前面章節所證明的結論，說明正規文法、正規式、確定有限自動機和非確定有限自動機在接收語言的能力上是互相等價的。稱為s的一個后繼狀態；4. S0206。8. RETRACT 子程序過程，把搜索指示器回調一個字節位置，把CHAR中的字符置為空白。（a）狀態轉換圖示例 狀態轉換圖的實現 一個狀態轉換圖可用于識別（或接受）一定的字符。 預處理的工作包括：剔除無用的空白、跳格、回車和換行符等編輯性字符；預處理工作還可以包括源程序和出錯信息的列表打印。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業：P63：3，6，7，8，12，14教學內容第二章 詞法分析 對于詞法分析器的要求 首先討論詞法分析器輸出的單詞符號的一般形式，然后研究詞法分析器應如何和語法分析器相銜接。如：編譯程序編譯程序、編譯程序產生器、翻譯程序書寫系統等，它們是按照對源語言和目標語言（或機器）的形式描述（作為輸入數據）而自動產生編譯程序的。只要實際使用的操作平臺上實現了的Java解釋器，這個操作平臺就可以執行各種Java程序。但遍數多勢必增加輸入／輸出所消耗的時間。 編譯過程的每一階段都可能檢測出錯誤，其中，絕大多數錯誤可以在編譯的前三階段檢測出來。合理地設計和使用表格是編譯程序構造的一個重要問題。 高級語言程序除了像上面所說的先編譯后執行外，有時也可“解釋”執行。一個源語言的解釋程序是這樣的程序，它以該語言寫的源程序作為輸入，但不產生目標程序，而是 邊解釋邊執行源程序本身。在編譯程序使用的表格中，最重要的是符號表。源程序中的錯誤通常分為語法錯誤和語義錯誤兩大類。因此，在主存可能的前提下，一般還是遍數盡可能少一點為好。這就是所謂Java語言操作平臺無關性。本課程將把自動產生器作為一個重要課題來討論。 詞法分析器的功能和輸出形式 詞法分析器的功能是輸入源程序，輸出單詞符號。 單詞符號的識別：超前搜索詞法分析器的結構如下圖所示：當詞法分析器調用預處理子程序處理出一串輸入字符放進掃描緩沖區之后，掃描器就從此緩沖區中逐一識別單詞符號。大多數程序語言的單詞符號都可以用轉換圖予以識別。 正規表達式與有限自動機 正規式與正規集 設Σ是一個有窮字母表，它的每個元素稱為一個字符。S，是唯一的一個初態；5. Z205。 確定有限自動機的化簡 等價狀態；最少化。相關介紹：人們已建立了多種編制部分編譯程序或整個編譯程序的有效工具。例如，根據規則E一(E)我們可以說：從‘E’可直接(一步地)推出‘(E)’。注意，推導每前進一步總是引用一條規則(產生式),而符號‘222。但在程序語言中，我們最終感興趣的是“程序”這個語法范疇，而其它的語法范疇都只不過是構造“程序”的一塊塊磚石。 0型文法：也稱短語文法，其能力相當于圖靈機。Pnγ，Pn 222。 討論課□ 實驗課254。|ε(ε 為空字)這種形式和原來的形式是等價的，也就是說，從P推出的符號串是相同的。|b1|b2|…|bn LL(1)分析條件 假定S是文法G的開始符號，對于任何非終結符A我們定義： FOLLOW(A) = { a | S222。 預測分析表的構造 為了構造預測分析表M，我們需要先構造與文法G有關的集合FIRST和FOLLOW. 消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。(4)如果一個非終結符產生空串，那么，推導6的產生式可以作為缺省的情況，這樣做可以推遲某些錯誤檢查，但不能導致放棄一個錯誤。由規范推導所得的句型稱為規范句型。因此，規范歸約的實質是，在移進過程中，當發現棧頂呈現句柄時就用相應產生式的左部符號進行替換。…aR…的產生式，R而R222。的終結符對，我們需要對G的每個非終結符P 構造兩個集合FIRSTVT(P)和LASTVT(P): FIRSTVT(P)={a | P222。b.我們首先討論構造集合FIRSTVT(P)的算法。注意，在上述算法中，我們并沒有指出應把所找到的最左素短語歸約到哪一個非終結符號‘N’。b，則f(a)＝g(b)；若a(1)移進 把(s，a)的下一狀態s’=GOTO[s，a]和輸入符號a推進棧，下一輸人符號變成現行輸入符號。 LR分析器 一個LR分析器實質上是一個帶先進后出存儲器（棧）的確定有限狀態自動機。 假定一個文法G 的拓廣文法G39。 Follow(A)，按A174。LALR分析表比規范分析表要小得多，能力也差一點，但它卻能對付一些SLR所不能對付的情形。 討論課□ 實驗課254。用繼承屬性來表示程序語言結構中的上下文依賴關系很方便。State val… …X Y Z … … L—屬性文法和自頂向下翻譯 一個屬性文法稱為L—屬性文法：如果對于每個產生式A174。三地址語句類似于匯編語言代碼。 保留作用域信息 過程readarray，exchange和quicksord的符號表有指針指向其外圍過程的符號表。類型T．type通過對指向本記錄符號表的指針施用類型構造符record而得到。特別是當low=1， 時有：V=(i1*n2+i2)*w C= base –(n2+1)*w應該牢記。如果t是一個指向某個記錄類型的指針，把類型構造符record 施于該指針，返回所形成的類型record(t)作為屬性T．type的值。這樣做的好處是可以把用在符號表中查找名字的程序同樣用來查找域名。即若high2為i2的上界，則n2=high2 – low2 +1.假定i1,i2是編譯時唯一尚未知道的值，我們可以重寫上述表達式為： ( (i1*n2) + i2) *w +( base –（ (low1 *n2) + low2) *w）后一項子表達式( base – （(low1 *n2) + low2) *w ）的值是可以在編譯時確定的,為常數。當記錄的所有域名都被檢查過之后，在offset的棧頂將存放著記錄之內的所有數據對象的總域寬。非終結符號T有兩個綜合屬性T．type和 T．width，分別表示名字的類型和名字的域寬(即該類型名字所占用的存儲單元個數)。之所以稱為三地址代碼是因為每條語句通常包含三個地址，兩個用來表示操作數，一個用來存放結果。我們使用一個棧來存放已經分析過的子樹的信息。僅僅使用綜合屬性的屬性文法稱S—屬性文法。YACC輸入用戶提供的語言的語法描述規格說明，基于LALR語法分析的原理，自動構造一個該語言的語法分析器，同時，它還能根據規格說明中給出的語義子程序建立規定的翻譯。 LALR分析表的構造 現在來討論構造分析表的LALR方法。 Follow(B),則可以根據當前讀頭下符號a來消除沖突。這樣，便會產生一個僅含項目S39。棧頂狀態為Sm，符號串X1X2…Xm是至今已移進歸約出的部分。顯然，[s，X]定義了一個以文法符號為字母表的DFA。如果有矛盾，那么，就不存在優先函數。 Xi+1 END 至此我們完成了從文法G構造優先表的算法。 類似地，假定有產生式的一個候選式為…Pb…那末，對任何a206。為了找出所有滿足關系…aQb…的產生式。對于規范句型來說，句柄的后面不會出現非終結符I號(即，句柄的后面只能出現終結符)。因此，規范規約也稱最左規約。這樣，在一個賦值語句后少一個分號就可能導致作為下一語句開頭的關鍵字被跳過。實現LL(1)分析的另一種有效方法是使用一張分析表和一個棧進行聯合控制。db1|db2|…|dbn|g1|g2|… |gm （其中每個g不以d開頭）那么，可以把這些規則改寫成：A174。p39。 我們以后所討論的文法均假定滿足上述兩條件。 P1α，P1 222。0型強于1型，1型強于2型，2型強于3型。因而，也可以說，每個非終結符號表示一定符號串的集合(由終結符號和非終結符號組成的符號串)。我們稱這樣的一串替換序列是從E推出(i+i)的一個推導。例如，我們考慮下面的文法G: EE十E | E*E | (E) |i 其中，唯一的非終結符E可以看成是代表一類算術表達式。 超前搜索 在某些語言中，要識別一個單詞符號必須超前看若干字符。（2） 對任何的正規式r，都存在一個FA M，使得L（M）＝L（r）。我們把s39。 7. RESERVE 整型函數過程，對TOKEN中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。一張轉換圖只包含有限個狀態（即有限個結點），其中有一個被認為是初態，而且實際上至少要有一個終態（用雙圈表示）。但在許多情況下，把輸入串預處理一下，對單詞符號的識別工作將是比較方便的。 其他□教學資源（請打√）：多媒體254。有些能用于自動產生掃描器，有些可用于自動產生語法分析器，有些甚至可用來自動產生整個的編譯程序。 又如，在Java語言環境中，為了使編譯后的程序從一個平臺移到另一個平臺，Java定義一種虛擬機代碼Bytecode。遍數多一點有個好處，即整個編譯程序的邏輯結構可能清晰一點。但是，自動校正錯誤的代價是非常高的。 編譯程序在工作過程中需要保持一系列的表格，以登記源程序的各類信息和編譯各階段的進展狀況。如果 源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級語言”，而目標語言是諸如匯編語言或機器語言之類的“低級語言”，這樣的一個翻譯程序就稱為編譯程序。本書將不對解釋程序作專門的討論。它用來登記源程序中出現的每個名字以及名字的各種屬性。語法錯誤是指源程序中不符合語法(或詞法)規則的錯誤，它們可在詞法分析或語法分析時檢測出來。應當注意的是，并不是每種語言都可以用單遍編譯程序實現。 編譯程序與程序設計環境 開發通常還需要一些其它的工具；如編輯程序、連接程序，調試工具等等。 近些年來，有些人主張采用“自編譯方式”產生編譯程序。單詞符號是一個程序語言的基本語法符號，程序語言的單詞符號一般可分為下列五種：1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等；2 標識符 用