編譯原理教案(完整版)

　　

【正文】 S，是非空初態集；5. Z 205。S，是一個終態集（可空）。例如，令Σ ={a，b} ，下面是 Σ上的正規式和相應的正規集：ba*： Σ上所有以b為首后跟任意多個a的字a(a| b)* ： Σ上所有以a為首的字(a| b)* (aa| bb)(a|b)*： Σ上所有含有兩個相繼的a或兩個相繼的b的字 又例如，令Σ={A，B，0，1} ，則 (A|B)(A|B|0|1)* ： Σ上的標識符的全體 (0|1)(0|1)* ： Σ上的數的全體 若兩個正規式所表示的正規集相同，則認為二者等價。Σ上的一個字（也叫字符串）是指由Σ中的字符所構成的一個有窮序列。而CHAR中存放著39。轉換圖非常易于用程序實現，最簡單的辦法是讓每個狀態結點對應一小段程序。狀態之間用箭弧連結。當緩沖區里的字符串被處理完之后，它又調用預處理程序裝入新串。 詞法分析器作為一個獨立子程序 可以使整個編譯程序的結構更簡潔、清晰和條例化。單詞符號是一個程序語言的基本語法符號，程序語言的單詞符號一般可分為下列五種：1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等；2 標識符 用來表示各種名字，如變量名、數組名和過程名等等；3 常 數 各種類型的常數，如125，、TRUE等等； 4 運算符 如+、*、/等等； 5 界 符 如逗號、括號、分號等等。授課題目（教學章、節或主題）：第二章 詞法分析課時安排12授課時間第1周 第36節 第2周 第16節第3周 第2節 教學目的、要求（分掌握、熟悉、了解三個層次）：了解詞法分析器的構造方法熟悉詞法分析的任務和過程掌握正規式和有限自動機的基本概念教學重點和難點：詞法分析器的設計、正規表達式和有限自動機、正規表達式和有限自動機的等價性、正規文法和有限自動機間的轉換授課類型（請打√）：理論課254。 近些年來，有些人主張采用“自編譯方式”產生編譯程序。 編譯程序的生成 以前人們構造編譯程序大多是用機器語言或匯編語言做工具的。 編譯程序與程序設計環境 開發通常還需要一些其它的工具；如編輯程序、連接程序，調試工具等等。也可以設想將幾種源語言編譯成相同的中間語言，然后為不同的前端配上相同的后端，這樣就可為同一臺機器生成不同語言的編譯程序。應當注意的是，并不是每種語言都可以用單遍編譯程序實現。在優化要求很高時，往往還可把優化階段分為若干遍來實現。語法錯誤是指源程序中不符合語法(或詞法)規則的錯誤，它們可在詞法分析或語法分析時檢測出來。一個編譯程序不僅應能對書寫正確的程序進行翻譯，而且應能對出現在源程序中的錯誤進行處理。它用來登記源程序中出現的每個名字以及名字的各種屬性。 編譯過程概述編譯程序過程: 從輸入源程序開始到輸出目標程序為止的整個編譯過程可分為以下五個階段：詞法分析,語法分析,語義分析,中間代碼產生,優化和目標代碼生成. 編譯程序的結構 編譯程序的結構可以按照從輸入源程序開始到輸出目標程序為止的整個編譯過程可分為以下五個階段：詞法分析,語法分析,語義分析,中間代碼產生,優化和目標代碼生成。本書將不對解釋程序作專門的討論。 討論課□ 實驗課□ 練習課□ 其他□教學方式（請打√）：講授254。如果 源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級語言”，而目標語言是諸如匯編語言或機器語言之類的“低級語言”，這樣的一個翻譯程序就稱為編譯程序。運行編譯程序的計算機稱宿主機，運行編譯程序所產生目標代碼的計算機稱目標機。 編譯程序在工作過程中需要保持一系列的表格，以登記源程序的各類信息和編譯各階段的進展狀況。例如，名字的類型等要在語義分析時才能確定，而名字的地址可能要到目標代碼生成才能確定。但是，自動校正錯誤的代價是非常高的。通常，每遍的工作由從外存上獲得的前一遍的中間結果開始(對于第一遍而言，從外存上獲得源程序)，完成它所含的有關工作之后，再把結果記錄于外存。遍數多一點有個好處，即整個編譯程序的邏輯結構可能清晰一點。通常，后端不依賴于源語言而僅僅依賴于中間語言。 又如，在Java語言環境中，為了使編譯后的程序從一個平臺移到另一個平臺，Java定義一種虛擬機代碼Bytecode。在一個好的集成化程序設計環境中，不僅包含豐富的程序設計工具，而且還支持程序設計方法學，支持程序開發的全生命周期。有些能用于自動產生掃描器，有些可用于自動產生語法分析器，有些甚至可用來自動產生整個的編譯程序。即把某一機器上的編譯程序移植到另一機器上。 其他□教學資源（請打√）：多媒體254。界符一般用一符一種的分法。但在許多情況下，把輸入串預處理一下，對單詞符號的識別工作將是比較方便的。 狀態轉換圖 使用狀態轉換圖是設計詞法分析程序(掃描器)的一種好途徑。一張轉換圖只包含有限個狀態（即有限個結點），其中有一個被認為是初態，而且實際上至少要有一個終態（用雙圈表示）。4. GETBC 子程序過程，則GETCHAR直到CHAR中進入一個非空白符。 7. RESERVE 整型函數過程，對TOKEN中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。L（V）、L（U）.L（V）（連接積）和 （L（U））*（閉包）。我們把s39。上例所定義的DFA M相應的狀態轉換圖如下所示：它能識別Σ上所有含有相繼兩個a或相繼兩個b的字。（2） 對任何的正規式r，都存在一個FA M，使得L（M）＝L（r）。a 其中，箭頭(有時也用：：＝)左邊的A是一個非終結符，稱為產生式的左部符號；箭頭右邊的a是由終結符號或非終結符號組成的符號串，稱為產生式的右部。 超前搜索 在某些語言中，要識別一個單詞符號必須超前看若干字符。 其他□教學方式（請打√）：講授254。例如，我們考慮下面的文法G: EE十E | E*E | (E) |i 其中，唯一的非終結符E可以看成是代表一類算術表達式。即，從‘(E)’可直接推出‘(E+E)’。我們稱這樣的一串替換序列是從E推出(i+i)的一個推導。歸納起來，一個上下文無關文法C包括四個組成部分：一組終結符號，一組非終結符號，一個開始符號，以及一組產生式。因而，也可以說，每個非終結符號表示一定符號串的集合(由終結符號和非終結符號組成的符號串)。每個新結和其父結間都有一條連線。0型強于1型，1型強于2型，2型強于3型。、增廣文法定義：設文法G[S]={VN,VT,P,S}，構造文法G’[S’]=(VN∪{S’},VT,P’,S’),其中，P’={A α|A α ∈P}∪{S’ S},顯然L(G)= L(G’)，稱G’為文法G的增廣文法。 P1α，P1 222。βP’ P’ 222。 我們以后所討論的文法均假定滿足上述兩條件。輸入串是指由單詞符號（文法的終結符）組成的有限序列。p39。*ε，則規定ε206。db1|db2|…|dbn|g1|g2|… |gm （其中每個g不以d開頭）那么，可以把這些規則改寫成：A174。 （2）對于文法中每個非終結符A的各個產生式的候選首符集兩兩不相交。實現LL(1)分析的另一種有效方法是使用一張分析表和一個棧進行聯合控制。發現錯誤后，要盡快地從錯誤中恢復過來，使分析能繼續進行下去。這樣，在一個賦值語句后少一個分號就可能導致作為下一語句開頭的關鍵字被跳過。 練習課254。因此，規范規約也稱最左規約。β則稱β是句型αβδ相對于規則A174。對于規范句型來說，句柄的后面不會出現非終結符I號(即，句柄的后面只能出現終結符)。我們用下面方法表示任何兩個可能相繼出現的終結符a和b(它們之間可能插有一個非終結符)的優先關系。…aQb…的產生式。+…aQ。為了找出所有滿足關系+…aQ, a206。 類似地，假定有產生式的一個候選式為…Pb…那末，對任何a206。Q…，則a206。 Xi+1 END 至此我們完成了從文法G構造優先表的算法。=如果有矛盾，那么，就不存在優先函數。但是，我們可以通過檢查棧頂符號和輸入符號的具體內容來發現那些原先不可比較的情形。顯然，[s，X]定義了一個以文法符號為字母表的DFA。(3)接受 宣布分析成功，停止分析器的工作。棧頂狀態為Sm，符號串X1X2…Xm是至今已移進歸約出的部分。假定文法是一個以S 為開始符號的文法，我們構造一個G39。這樣，便會產生一個僅含項目S39。上面所說的LR(0)文法是一類非常簡單的文法。 Follow(B),則可以根據當前讀頭下符號a來消除沖突。 Follow(A)，就確定采用A174。 LALR分析表的構造 現在來討論構造分析表的LALR方法。但是，某些二義文法是非常有用的。YACC輸入用戶提供的語言的語法描述規格說明，基于LALR語法分析的原理，自動構造一個該語言的語法分析器，同時，它還能根據規格說明中給出的語義子程序建立規定的翻譯。這些屬性代表與文法符號相關的信息，例如它的類型、值、代碼序列 、符號表內容等等。僅僅使用綜合屬性的屬性文法稱S—屬性文法。 例如，屬性 :=f( , ) 對應于產生式 A174。我們使用一個棧來存放已經分析過的子樹的信息。 (2) 如果E是E1opE2形式的表達式，這里op是任何二元操作符，則E的后綴式為E1’E2’op，這里E1’和E2’分別為El和E2的后綴式。之所以稱為三地址代碼是因為每條語句通常包含三個地址，兩個用來表示操作數，一個用來存放結果。有關活動記錄我們將在第九章詳細介紹。非終結符號T有兩個綜合屬性T．type和 T．width，分別表示名字的類型和名字的域寬(即該類型名字所占用的存儲單元個數)。(2)enter(table，name，type，offset)在指針table指示的符號表中為名字建立一個新項，并把類型type、相對地址offset填入到該項中。當記錄的所有域名都被檢查過之后，在offset的棧頂將存放著記錄之內的所有數據對象的總域寬。該翻譯模式中說明了如何查找符號表的入口。即若high2為i2的上界，則n2=high2 – low2 +1.假定i1,i2是編譯時唯一尚未知道的值，我們可以重寫上述表達式為： ( (i1*n2) + i2) *w +( base –（ (low1 *n2) + low2) *w）后一項子表達式( base – （(low1 *n2) + low2) *w ）的值是可以在編譯時確定的,為常數。，即維數。這樣做的好處是可以把用在符號表中查找名字的程序同樣用來查找域名。 布爾表達式的翻譯在程序設計語言中，布爾表達式有兩個基本作用： 一個使用作計算邏輯值；另一個是用作控制流語句如ifthen、ifthenelse和 wh。如果t是一個指向某個記錄類型的指針，把類型構造符record 施于該指針，返回所形成的類型record(t)作為屬性T．type的值。最后，用來臨時存放由Elist中的下標表達式計算出來的值。特別是當low=1， 時有：V=(i1*n2+i2)*w C= base –(n2+1)*w應該牢記。如果有，則返回一個指向該表項的指針，否則，返回nil表示沒找到。類型T．type通過對指向本記錄符號表的指針施用類型構造符record而得到。(4)enterproc(table，name，newtable)在指針table指示的符號表中為名字為name的過程建立一個新項。 保留作用域信息 過程readarray，exchange和quicksord的符號表有指針指向其外圍過程的符號表。例如，假定在一個以字節編址的目標機上，整數必須存放在4的倍數的地址單元，那么，計算地址時就應以4的倍數增加。三地址語句類似于匯編語言代碼。根據運算量和算符出現的先后位置，以及每個算符的目數，就完全決定了一個表達式的分解。State val… …X Y Z … … L—屬性文法和自頂向下翻譯 一個屬性文法稱為L—屬性文法：如果對于每個產生式A174。 如果在語法樹中應用這個產生式，,。用繼承屬性來表示程序語言結構中的上下文依賴關系很方便。 屬性一般分為兩類：綜合屬性和繼承屬性。 討論課□ 實驗課254。例如，若用下面的文法來描述含有+、*的算術表達式：E174。LALR分析表比規范分析表要小得多，能力也差一點，但它卻能對付一些SLR所不能對付的情形。但是，在某種情況下，當狀態k呈現于棧頂時，棧里的符號串所構成的活前綴βα未必允許把α歸約為A。 Follow(A)，按A174。如果LR(0)項目集中某個項目存在有沖突的項目集，可以根據讀頭下符號的不同來消除沖突。 假定一個文法G 的拓廣文法G39。 ，并加進了一個新產生式S39。 LR分析器 一個LR分析器實質上是一個帶先進后出存儲器（棧）的確定有限狀態自動機。LR分析器的總控程序本身的工作是非常簡單的。(1)移進 把(s，a)的下一狀態s’=GOTO[s，a]和輸入符號a推進棧，下一輸人符號變成現行輸入符號。針對上述情況，處理錯誤的子程序也可分成幾類。b，則f(a)＝g(b)；若a=注意，在上述算法中，我們并沒有指出應把所找到的最左素短語歸約到哪一個非終結符號‘N’。在我們有了每個非終結符P 的FISTVT(P)和LASTVT(P)之后我們就能夠造文法G的優先表。b.我們首先討論構造集合FIRSTVT(P)的算法。VN }有了這兩個集合后，就可以通過檢查每個產生式的候選式確定滿足關系的終結符對，我們需要對G的每個非終結符P 構造兩個集合FIRSTVT(P)和LASTVT(P): FIRSTVT(P)={a | P222。b, a…aR…的產生式，R而R222。例如，ab并不一定意味著ba。因