編譯原理教案(更新版)

　　

【正文】 此，規范歸約的實質是，在移進過程中，當發現棧頂呈現句柄時就用相應產生式的左部符號進行替換。一個句型的最左直接短語稱為該句型的句柄。由規范推導所得的句型稱為規范句型。 討論□ 示教□ 指導254。(4)如果一個非終結符產生空串，那么，推導6的產生式可以作為缺省的情況，這樣做可以推遲某些錯誤檢查，但不能導致放棄一個錯誤。這種做法的效果有賴于同步符號集的選擇。 預測分析表的構造 為了構造預測分析表M，我們需要先構造與文法G有關的集合FIRST和FOLLOW. 消除左遞歸和提取左因子將有助于獲得無多重定義的分析表M。a1 | a2 |…| an 則： FIRST(ai)199。|b1|b2|…|bn LL(1)分析條件 假定S是文法G的開始符號，對于任何非終結符A我們定義： FOLLOW(A) = { a | S222。換句話說FIRST(a)是a的所有可能推導的開頭終結符或可能的ε。|ε(ε 為空字)這種形式和原來的形式是等價的，也就是說，從P推出的符號串是相同的。所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號。 討論課□ 實驗課254。 （1）文法中不含任何下面形式的產生式： P→P因為這種產生式除了產生二義性外沒有任何用處。Pnγ，Pn 222。其中P ∈VN ，β1，β2… βn ∈ (VN∪ VT)*。 0型文法：也稱短語文法，其能力相當于圖靈機。例如，對于文法()，關于(i*i+i)的推導()。但在程序語言中，我們最終感興趣的是“程序”這個語法范疇，而其它的語法范疇都只不過是構造“程序”的一塊塊磚石。從語法分析的角度來看，終結符號是一個語言的不可再分的基本符號。注意，推導每前進一步總是引用一條規則(產生式),而符號‘222。(E)222。例如，根據規則E一(E)我們可以說：從‘E’可直接(一步地)推出‘(E)’。 其他□教學資源（請打√）：多媒體254。相關介紹：人們已建立了多種編制部分編譯程序或整個編譯程序的有效工具。a是關于A的一條產生規則。 確定有限自動機的化簡 等價狀態；最少化。 2S4. S0205。S，是唯一的一個初態；5. Z205。算符的優先順序為：先*，次.，最后|。 正規表達式與有限自動機 正規式與正規集 設Σ是一個有窮字母表，它的每個元素稱為一個字符。例如，TOKEN原來的值為‘AB39。大多數程序語言的單詞符號都可以用轉換圖予以識別。在狀態轉換圖中，結點代表狀態，用圓圈表示。 單詞符號的識別：超前搜索詞法分析器的結構如下圖所示：當詞法分析器調用預處理子程序處理出一串輸入字符放進掃描緩沖區之后，掃描器就從此緩沖區中逐一識別單詞符號。若一個種別含有許多個單詞符號，那么對于它的每個單詞符號，除了給出種別編碼之外，還應給出自身的值。 詞法分析器的功能和輸出形式 詞法分析器的功能是輸入源程序，輸出單詞符號。但是，由于建立通用中間語言實際上辦不到，因此，移植也只能在幾種語言和幾種機器之間進行。本課程將把自動產生器作為一個重要課題來討論。廣大讀者所熟悉的Pascal、TurboC、VisualC++等語言環境也都可認為是集成化的程序設計環境。這就是所謂Java語言操作平臺無關性。如果后端的設計是經過精心考慮的，那么后端的改寫將用不了太大工作量，這樣就可實現編譯程序的目標機改變。因此，在主存可能的前提下，一般還是遍數盡可能少一點為好。例如，詞法分析這一階段可以單獨作為一遍，但更多的時候是把它與語法分析合并為一遍；為了便于處理，語法分析和語義分析與中間代碼產生又常常合為一遍。源程序中的錯誤通常分為語法錯誤和語義錯誤兩大類。 出錯處理 遍:是對源程序或源程序的中間結果從頭到尾掃描一次，并作有關的加工處理，生產新的中間結果或目標程序。在編譯程序使用的表格中，最重要的是符號表。如果不需重寫編譯程序中與機器無關的部分就能改變目標機，則稱該編譯程序為可變目標編譯程序(Retargetable Compiler)。一個源語言的解釋程序是這樣的程序，它以該語言寫的源程序作為輸入，但不產生目標程序，而是 邊解釋邊執行源程序本身。《編 譯 原 理》教案授課題目（教學章、節或主題）：第一章 引論課時安排2授課時間 第1周 第2節 教學目的、要求（分掌握、熟悉、了解三個層次）：簡單介紹學習此課程的目的和要求初步了解編譯技術的基本原理和方法熟悉Compiler的基本概念掌握Compiler的結構和功能教學重點和難點：編譯程序的基本結構和功能授課類型（請打√）：理論課254。 高級語言程序除了像上面所說的先編譯后執行外，有時也可“解釋”執行。 如果一個編譯程序產生不同于其宿主機的機器代碼， 則稱它為交叉編譯程序(CrOSS Compiler)。合理地設計和使用表格是編譯程序構造的一個重要問題。 由此可見，編譯各階段都涉及到構造、查找或更新有關的表格。 編譯過程的每一階段都可能檢測出錯誤，其中，絕大多數錯誤可以在編譯的前三階段檢測出來。既可以將幾個不同階段合為一遍，也可以把一個階段的工作分為若干遍。但遍數多勢必增加輸入／輸出所消耗的時間。 可以取編譯程序的前端，改寫其后端以生成不同目標機上的相同語言的編譯程序。只要實際使用的操作平臺上實現了的Java解釋器，這個操作平臺就可以執行各種Java程序。有代表性的集成化程序設計環境有Ada語言程序設計環境APSE、LISP語言程序設計環境INTERLISP等。如：編譯程序編譯程序、編譯程序產生器、翻譯程序書寫系統等，它們是按照對源語言和目標語言（或機器）的形式描述（作為輸入數據）而自動產生編譯程序的。著需要尋求某種適當的“中間語言”。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業：P63：3，6，7，8，12，14教學內容第二章 詞法分析 對于詞法分析器的要求 首先討論詞法分析器輸出的單詞符號的一般形式，然后研究詞法分析器應如何和語法分析器相銜接。 如果一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編碼就完全代表它自身了。 預處理的工作包括：剔除無用的空白、跳格、回車和換行符等編輯性字符；預處理工作還可以包括源程序和出錯信息的列表打印。轉換圖是一張有限方向圖。（a）狀態轉換圖示例 狀態轉換圖的實現 一個狀態轉換圖可用于識別（或接受）一定的字符。5. CONCAT 子程序過程，把CHAR中的字符連接TOKEN之后。8. RETRACT 子程序過程，把搜索指示器回調一個字節位置，把CHAR中的字符置為空白。僅由有限次使用上述三步驟而定義的表達式才是Σ上的正規式，僅由這些正規式所表示的字集才是Σ上的正規集。稱為s的一個后繼狀態；4. S0206。 狀態轉換圖 非確定有限自動機(NFA) 設一個確定的有限自動機（DFA）M是一個五元式M=(S,Σ,f,S0, Z)其中1. S是一個有限集，它的每個元素稱為一個狀態；，它的每個元素稱為一個輸入字符；3. f是一個從SΣ*到S的子集的映照，即 f：SΣ*174。上述結論加上前面章節所證明的結論，說明正規文法、正規式、確定有限自動機和非確定有限自動機在接收語言的能力上是互相等價的。我們有時也說，產生式A174。 LEX的實現 LEX的編譯程序旨在將一個LEX源程序改造為一個詞法分析器L，這個詞法分析器L將像有限自動機那樣工作。 討論□ 示教□ 指導254。我們可以從E出發，進行一系列的推導，推出種種不同的算術表達式來。把上述這兩步合并起來，就有E222。這個推導提供了一個證明，證明(i+i)是文法()所定義的一個算術表達式。 所謂終結符號乃是組成語言的基本符號，在程序語言中就是以前屢次提到的單詞符號，如基本字、標識符、常數、算符和界符等。開始符號是一個特殊的非終結符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結自左至右排列起來就是一個句型。這幾類文法的差別在于對產生式施加不同的限制。例：[Z]:Z →abZA|a A→b經等價變換后可得到增廣文法G[A‘]: Z’ →Z Z →abZA|a A→b、提取左因子定義：若文法中有產生式P→δβ1|δβ2|…|δβn,則稱該文發含有左因子δ。P2β, ……,Pn1 222。αP’|ε間接左遞歸的消除方法：將間接左遞歸轉化為直接左遞歸；消除直接左遞歸；化簡文法，刪除含有從起始符號無法到達的非終結符的產生式最后，作為描述程序語言的上下文無關文法，我們對它有幾點限制。授課題目（教學章、節或主題）：第三章 語法分析——自上而下分析課時安排12授課時間 第4周 第36節 第6周 第16節 第7周 第12節 教學目的、要求（分掌握、熟悉、了解三個層次）：了解確定的自頂向下分析思想熟悉某些非LL（1）文法到LL（1）文法的等價變換掌握LL（1）文法的判別、確定的自頂向下分析方法教學重點和難點：語法分析器的功能、確定的自頂向下分析思想、LL（1）文法的判別、某些非LL（1）文法到LL（1）文法的等價變換、不確定的自頂向下分析思想、確定的自頂向下分析方法授課類型（請打√）：理論課254。語法分析的方法：可大致分為兩類，一類是自下而上分析法，另一類是自上而下分析法。 αp39。FIRST(a)。dA’|g1|g2|… |gmA’174。即，若 A174。我們現在要介紹的預測分析程序就是屬于這種類型的LL(1)分析器 預測分析程序工作過程 預測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號a行事的。基本的做法就是跳過輸入串中的一些符號直至遇到“同步符號”為止。(3)如果把FIRST(A)中的符號加入非終結符A的同步符號集，那么，當FIRST(A)中的一個符號在輸人中出現時，可以根據A恢復語法分析。 其他□教學方式（請打√）：講授254。最右推導常被稱為規范推導。b的直接短語。基于這一點，我們可用句柄來刻畫移進—歸約過程的“可歸約串”。這種關系有三種：ab a的優先性低于ba＝b a的優先性等于bab a的優先性高于b注意，這三個關系不同于數學中的‘’，‘＝’和‘’。(2) ab當且僅當G中含有形如P174。如果一個文法G中的任何終結符對（a, b ）至多只滿足下述三關系之一： a=和VT而Q206。LASTVT(P),我們有aFIRSTVT(P)同樣我們可以構造LASTVT(P)的算法。 算符優先分析算法 在正確的情況下，算法工作完畢時，符號棧S應呈現：N。b，那么，就從fa畫一箭弧至gb；如果a現在必須證明：若a= 算符優先分析中的出錯處理 使用算符優先分析法時，可在兩種情況下，發現語法錯誤：(1)若在棧頂終結符號與下一輸人符號之間不存在任何優先關系；(2)若找到某一“句柄”(此處“句柄”指素短語)，但不存在任一產生式，其右部為此“句柄”。每一項ACTON[s，a]所規定的動作不外是下述四種可能之一。(4)報錯 發現源程序含有錯誤，調用出錯處理程序。 LR分析器模型。 它包含了整個G ，但它引進了一個不出現在G 中的非終結符S39。S?的狀態，這就是唯一的接受態。這種文法的活前綴識別自動機的每一個狀態（項目集）都不含沖突性的項目。即在構造LR分析表的算法中做一些改變：1）若當前輸入符a=b，做移進；2）若當前輸入符a 206。α產生式進行歸約。這本質上是一種折衷方法。本節將討論如何使用LR分析法的基本思想，憑借一些其它的條件，來分析二義文法所定義的語言。授課題目（教學章、節或主題）：第四章 語法制導翻譯和中間代碼產生課時安排8授課時間 第11周 第4節 第12周 第14節第13周 第2節教學目的、要求（分掌握、熟悉、了解三個層次）：理解屬性文法的定義，語法制導翻譯方法熟悉中間代碼的形式掌握中間代碼形式變換掌握簡單賦值語句的翻譯、布爾表達式的翻譯、控制語句的翻譯教學重點和難點：屬性文法的定義，屬性的計算、中間代碼的形式、簡單賦值語句的翻譯、布爾表達式的翻譯、控制語句的翻譯授課類型（請打√）：理論課254。屬性和變量一樣，可以進行計算和傳遞。 35＋4n ： 在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定。XY的語義規則,。現在我們可以在分析棧中使用一個附域來存放綜合屬性值。這種表示法用不著使用括號。對于后面給出的三地址代碼中，用戶定義的名字在實際實現時將由指向符號表中的相應名字入口的指針所代替。當產生中間代碼地址時，對目標機一些情況做到心中有數是有好處的。假定整數類型域寬為4；實數域寬為8；一個數組的域寬可以通過把數組元素數目與一個元素的域寬相乘獲得；每個指針類型的域寬假定為以4增加。(3)addwidth(table，width)在指針table指示的符號表表頭中記錄下該表中所有名字占用的總寬度。文法中end之后的語義動作是將offset的棧頂的總域寬作為綜合屬性T．width的值。過程lookup()檢查是否在符號表中存在此名字的入口。前一子項隨i1, i2 而改變是一個變數。函數Limit(arry, j) 返回nj ，即由arry所指示的數組的第j 維的長度。在此意義下，利用上一節圖4．9中的語義動作可為每一個記錄類型建立一張單獨的符