編譯原理教案-wenkub

　

【正文】 所構(gòu)成的一個(gè)有窮序列。6. LETTER和DIGIT布爾函數(shù)過程，它們分別CHAR中的字符是否為字母和數(shù)字，從爾給出真值TRUE或假值FALSE。而CHAR中存放著39。3. GETCHAR 子程序過程，把下一個(gè)輸入字符讀到CHAR中，把搜索指示器前移一字節(jié)位置。轉(zhuǎn)換圖非常易于用程序?qū)崿F(xiàn)，最簡(jiǎn)單的辦法是讓每個(gè)狀態(tài)結(jié)點(diǎn)對(duì)應(yīng)一小段程序。若輸入字符Y，則讀進(jìn)Y，并轉(zhuǎn)換到狀態(tài)3。狀態(tài)之間用箭弧連結(jié)。這里就需要用到超前搜索。當(dāng)緩沖區(qū)里的字符串被處理完之后，它又調(diào)用預(yù)處理程序裝入新串。詞法分析的工作（單詞符號(hào)的識(shí)別）可以直接在這個(gè)緩沖區(qū)中進(jìn)行。 詞法分析器作為一個(gè)獨(dú)立子程序 可以使整個(gè)編譯程序的結(jié)構(gòu)更簡(jiǎn)潔、清晰和條例化。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的算符（如所有關(guān)系符）視為一種。單詞符號(hào)是一個(gè)程序語言的基本語法符號(hào)，程序語言的單詞符號(hào)一般可分為下列五種：1 基本字 如FORTRAN中的DIMENSION、IF和DO 等等；2 標(biāo)識(shí)符 用來表示各種名字，如變量名、數(shù)組名和過程名等等；3 常 數(shù) 各種類型的常數(shù)，如125，、TRUE等等； 4 運(yùn)算符 如+、*、/等等； 5 界 符 如逗號(hào)、括號(hào)、分號(hào)等等。 討論□ 示教□ 指導(dǎo)254。授課題目（教學(xué)章、節(jié)或主題）：第二章 詞法分析課時(shí)安排12授課時(shí)間第1周 第36節(jié) 第2周 第16節(jié)第3周 第2節(jié) 教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：了解詞法分析器的構(gòu)造方法熟悉詞法分析的任務(wù)和過程掌握正規(guī)式和有限自動(dòng)機(jī)的基本概念教學(xué)重點(diǎn)和難點(diǎn)：詞法分析器的設(shè)計(jì)、正規(guī)表達(dá)式和有限自動(dòng)機(jī)、正規(guī)表達(dá)式和有限自動(dòng)機(jī)的等價(jià)性、正規(guī)文法和有限自動(dòng)機(jī)間的轉(zhuǎn)換授課類型（請(qǐng)打√）：理論課254。 現(xiàn)在，有些編譯程序是通過“移植”得到的。 近些年來，有些人主張采用“自編譯方式”產(chǎn)生編譯程序。 人們已經(jīng)建立了多種編制部分編譯程序或整個(gè)編譯程序的有效工具。 編譯程序的生成 以前人們構(gòu)造編譯程序大多是用機(jī)器語言或匯編語言做工具的。一個(gè)集成化的程序設(shè)計(jì)環(huán)境的特點(diǎn)是，它將相互獨(dú)立的程序設(shè)計(jì)工具集成起來，以便為程序員提供完整的、一體化的支持，從而進(jìn)一步提高程序開發(fā)效率，改善程序質(zhì)量。 編譯程序與程序設(shè)計(jì)環(huán)境 開發(fā)通常還需要一些其它的工具；如編輯程序、連接程序，調(diào)試工具等等。編譯前端與不同的編譯后端以Diana為界面，實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)改變。也可以設(shè)想將幾種源語言編譯成相同的中間語言，然后為不同的前端配上相同的后端，這樣就可為同一臺(tái)機(jī)器生成不同語言的編譯程序。后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。應(yīng)當(dāng)注意的是，并不是每種語言都可以用單遍編譯程序?qū)崿F(xiàn)。 一個(gè)編譯程序究竟應(yīng)分成幾遍，如何劃分，是與源語言、設(shè)計(jì)要求、硬件設(shè)備等諸因素有關(guān)的，因此難于統(tǒng)一劃定。在優(yōu)化要求很高時(shí)，往往還可把優(yōu)化階段分為若干遍來實(shí)現(xiàn)。 遍 遍:是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生產(chǎn)新的中間結(jié)果或目標(biāo)程序。語法錯(cuò)誤是指源程序中不符合語法(或詞法)規(guī)則的錯(cuò)誤，它們可在詞法分析或語法分析時(shí)檢測(cè)出來。如果不僅能夠發(fā)現(xiàn)錯(cuò)誤，而且還能自動(dòng)校正錯(cuò)、誤，那當(dāng)然就更好了。一個(gè)編譯程序不僅應(yīng)能對(duì)書寫正確的程序進(jìn)行翻譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。但這時(shí)不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填人。它用來登記源程序中出現(xiàn)的每個(gè)名字以及名字的各種屬性。在編譯程序使用的表格中，最合理的是符號(hào)表。 編譯過程概述編譯程序過程: 從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)編譯過程可分為以下五個(gè)階段：詞法分析,語法分析,語義分析,中間代碼產(chǎn)生,優(yōu)化和目標(biāo)代碼生成. 編譯程序的結(jié)構(gòu) 編譯程序的結(jié)構(gòu)可以按照從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)編譯過程可分為以下五個(gè)階段：詞法分析,語法分析,語義分析,中間代碼產(chǎn)生,優(yōu)化和目標(biāo)代碼生成?，F(xiàn)在很多編譯程序同時(shí)提供了調(diào)試、優(yōu)化等多種功能，用戶可以通過“開關(guān)”進(jìn)行選擇。本書將不對(duì)解釋程序作專門的討論。第一章 引論 什么叫編譯程序？ 通常所說的翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語言程序(稱為源語言程序)轉(zhuǎn)換成另一種語言程序(稱為目標(biāo)語言程序)，而后者與前者在邏輯上是等價(jià)的。 討論課□ 實(shí)驗(yàn)課□ 練習(xí)課□ 其他□教學(xué)方式（請(qǐng)打√）：講授254。 討論□ 示教□ 指導(dǎo)254。如果 源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級(jí)語言”，而目標(biāo)語言是諸如匯編語言或機(jī)器語言之類的“低級(jí)語言”，這樣的一個(gè)翻譯程序就稱為編譯程序。實(shí)際上，許多編譯程序的構(gòu)造與實(shí)現(xiàn)技術(shù)同樣適用于解釋程序。運(yùn)行編譯程序的計(jì)算機(jī)稱宿主機(jī)，運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)稱目標(biāo)機(jī)。 編譯程序總框 編譯程序的結(jié)構(gòu)可以按照這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。 編譯程序在工作過程中需要保持一系列的表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。例如，一個(gè)名字是常量名、變量名，還是過程名等等；如果是變量名，它的類型是什么、所占內(nèi)存是多大、地址是什么等等。例如，名字的類型等要在語義分析時(shí)才能確定，而名字的地址可能要到目標(biāo)代碼生成才能確定。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。但是，自動(dòng)校正錯(cuò)誤的代價(jià)是非常高的。例如，詞法分析階段能夠檢測(cè)出“非法字符”之類的錯(cuò)誤；語法分析階段能夠檢測(cè)出諸如“括號(hào)不匹配”、“缺少；”之類的錯(cuò)誤。通常，每遍的工作由從外存上獲得的前一遍的中間結(jié)果開始(對(duì)于第一遍而言，從外存上獲得源程序)，完成它所含的有關(guān)工作之后，再把結(jié)果記錄于外存。 當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。遍數(shù)多一點(diǎn)有個(gè)好處，即整個(gè)編譯程序的邏輯結(jié)構(gòu)可能清晰一點(diǎn)。 編譯前端與后端 概念上，我們有時(shí)把編譯程序劃分為編譯前端和編譯后端。通常，后端不依賴于源語言而僅僅依賴于中間語言。然而，由于不同語言存在某些微妙的區(qū)別，因此在這方面所取得的成果還非常有限。 又如，在Java語言環(huán)境中，為了使編譯后的程序從一個(gè)平臺(tái)移到另一個(gè)平臺(tái)，Java定義一種虛擬機(jī)代碼Bytecode。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。在一個(gè)好的集成化程序設(shè)計(jì)環(huán)境中，不僅包含豐富的程序設(shè)計(jì)工具，而且還支持程序設(shè)計(jì)方法學(xué)，支持程序開發(fā)的全生命周期。為了發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然采用這種工具來構(gòu)造編譯程序。有些能用于自動(dòng)產(chǎn)生掃描器，有些可用于自動(dòng)產(chǎn)生語法分析器，有些甚至可用來自動(dòng)產(chǎn)生整個(gè)的編譯程序。意思是，先對(duì)語言的核心部分構(gòu)造一個(gè)小小的編譯程序（可用手編實(shí)現(xiàn)），再以它為工具構(gòu)造一個(gè)能夠編譯更多語言成分的較大編譯程序。即把某一機(jī)器上的編譯程序移植到另一機(jī)器上。 討論課□ 實(shí)驗(yàn)課254。 其他□教學(xué)資源（請(qǐng)打√）：多媒體254。 標(biāo)識(shí)符一般統(tǒng)歸為一種。界符一般用一符一種的分法。 詞法分析器的設(shè)計(jì) 我們將按照詞法分析的任務(wù)和作為一個(gè)獨(dú)立子程序的要求來考慮詞法分析器的設(shè)計(jì)。但在許多情況下，把輸入串預(yù)處理一下，對(duì)單詞符號(hào)的識(shí)別工作將是比較方便的。 詞法分析器下面我們來介紹一下單詞符號(hào)識(shí)別的一個(gè)簡(jiǎn)單方法——超前搜索。 狀態(tài)轉(zhuǎn)換圖 使用狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)詞法分析程序(掃描器)的一種好途徑。箭弧上的標(biāo)記（字符）代表在射出結(jié)(即箭弧始節(jié))狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中有一個(gè)被認(rèn)為是初態(tài)，而且實(shí)際上至少要有一個(gè)終態(tài)（用雙圈表示）。下面我們將引進(jìn)一組全局變量和過程，把它們作為實(shí)現(xiàn)轉(zhuǎn)換圖的基本成分。4. GETBC 子程序過程，則GETCHAR直到CHAR中進(jìn)入一個(gè)非空白符。C39。 7. RESERVE 整型函數(shù)過程，對(duì)TOKEN中的字符串查找保留字表，若它是一個(gè)保留字則返回它的編碼，否則返回0值(假定0不是保留字的編碼)。不包含任何字符的序列稱為空字，記為ε。L（V）、L（U）.L（V）（連接積）和 （L（U））*（閉包）。兩個(gè)等價(jià)的正規(guī)式U和V記為U=V。我們把s39。 一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示f（s，a）的值，這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。上例所定義的DFA M相應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：它能識(shí)別Σ上所有含有相繼兩個(gè)a或相繼兩個(gè)b的字。S，是一個(gè)終態(tài)集（可空）。（2） 對(duì)任何的正規(guī)式r，都存在一個(gè)FA M，使得L（M）＝L（r）。 語言LEX的一般描述 一個(gè)LEX源程序主要包括兩部分。a 其中，箭頭(有時(shí)也用：：＝)左邊的A是一個(gè)非終結(jié)符，稱為產(chǎn)生式的左部符號(hào)；箭頭右邊的a是由終結(jié)符號(hào)或非終結(jié)符號(hào)組成的符號(hào)串，稱為產(chǎn)生式的右部。例如，令i 代表已定義的范疇“變量”，那么，產(chǎn)生式 算術(shù)表達(dá)式174。 超前搜索 在某些語言中，要識(shí)別一個(gè)單詞符號(hào)必須超前看若干字符。這些構(gòu)造編譯程序的工具稱為編譯程序——編譯程序、編譯程序產(chǎn)生器或翻譯程序書寫系統(tǒng)，它們是按對(duì)源程序和目標(biāo)語言(或機(jī)器)的形式描述(作為輸入數(shù)據(jù))而自動(dòng)產(chǎn)生編譯程序的。 其他□教學(xué)方式（請(qǐng)打√）：講授254。在后面的討論中，根據(jù)不同情況，我們將用大寫字母A、B、C…或漢語詞組(如，算術(shù)表達(dá)式)代表非終結(jié)符號(hào)，特別是用小寫字母a、b、c…代表終結(jié)符，用α、β、γ等代表由終結(jié)符和非終結(jié)符組成的符號(hào)串。例如，我們考慮下面的文法G: EE十E | E*E | (E) |i 其中，唯一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式?！硎尽爸苯油瞥觥保@樣，這句話就可表示為:E222。即，從‘(E)’可直接推出‘(E+E)’。再對(duì)‘(E+E)’中的E相繼兩次使用規(guī)則Ei之后，我們就有(E) 222。我們稱這樣的一串替換序列是從E推出(i+i)的一個(gè)推導(dǎo)。我們可以用一種圖示化的方法來表示這種推導(dǎo)，說明He gave me a book是一個(gè)語法正確的句子。歸納起來，一個(gè)上下文無關(guān)文法C包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組產(chǎn)生式。例如，“算術(shù)表達(dá)式”、“布爾表達(dá)式”、“賦值句”、“分程序”、“過程”等，它們都是現(xiàn)今程序語言常見的語法范疇。因而，也可以說，每個(gè)非終結(jié)符號(hào)表示一定符號(hào)串的集合(由終結(jié)符號(hào)和非終結(jié)符號(hào)組成的符號(hào)串)。語法樹有助于理解一個(gè)句子語法結(jié)構(gòu)的層次。每個(gè)新結(jié)和其父結(jié)間都有一條連線。這樣的一棵語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表。0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型。 1型文法：也稱上下文有關(guān)文法，對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必聯(lián)系上下文，并且一般不允許替換成空串。、增廣文法定義：設(shè)文法G[S]={VN,VT,P,S}，構(gòu)造文法G’[S’]=(VN∪{S’},VT,P’,S’),其中，P’={A α|A α ∈P}∪{S’ S},顯然L(G)= L(G’)，稱G’為文法G的增廣文法。+ Pα,則稱該文法含有左遞歸。 P1α，P1 222。其中P,P1, …,Pn ∈ VN, α, β, γ,δ ∈ (VN∪ VT)*。βP’ P’ 222。這一方面意味著，必須存在含P的句型；也就是，從開始符號(hào)出發(fā)，存在推導(dǎo) S222。 我們以后所討論的文法均假定滿足上述兩條件。 其他□教學(xué)方式（請(qǐng)打√）：講授254。輸入串是指由單詞符號(hào)（文法的終結(jié)符）組成的有限序列。 自上而下分析面臨的問題 本節(jié)主要是通過例子使我們認(rèn)識(shí)到，作自上而下分析所遇到的主要困難是語法的左遞歸性使分析陷入無限循環(huán)；回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來，為解決這些問題我們要消除左遞歸和消除回溯。p39。前面已經(jīng)說過，欲實(shí)行自上而下的分析，文法不得含左遞歸。*ε，則規(guī)定ε206。FIRST(aj) = f那么，當(dāng)要求A匹配輸入串時(shí)，A 就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù)。db1|db2|…|dbn|g1|g2|… |gm （其中每個(gè)g不以d開頭）那么，可以把這些規(guī)則改寫成：A174。VT}特別是，若S222。 （2）對(duì)于文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。j ） (3) 對(duì)文法中每一個(gè)終結(jié)符A，若它存在某個(gè)候選首符集包含ε，則 FIRST(A) 199。實(shí)現(xiàn)LL(1)分析的另一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制。 LL(1)分析中的錯(cuò)誤處理 我們以預(yù)測(cè)分析為例。發(fā)現(xiàn)錯(cuò)誤后，要盡快地從錯(cuò)誤中恢復(fù)過來，使分析能繼續(xù)進(jìn)行下去。(1)把FOLLOW(A)中的所有符號(hào)放人非終結(jié)符A的同步符號(hào)集。這樣，在一個(gè)賦值語句后少一個(gè)分號(hào)就可能導(dǎo)致作為下一語句開頭的關(guān)鍵字被跳過。(5)如果不能匹配棧頂?shù)慕K結(jié)符號(hào)，一種簡(jiǎn)單的想法是彈出棧頂?shù)倪@個(gè)終結(jié)符號(hào)，并發(fā)出一條信息，說明已經(jīng)插入這個(gè)終結(jié)符，繼續(xù)進(jìn)行語法分析。 練習(xí)課254。 模型□ 實(shí)物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P133：1，2，3，5教學(xué)內(nèi)容第三章 語法分析程序自下而上分析所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說從語法樹的末端開始，步步向上“歸約”，直到根結(jié)。因此，規(guī)范規(guī)約也稱最左規(guī)約。 句柄：令G是一個(gè)文法，S是文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有S222。β則稱β是句型αβδ相對(duì)于規(guī)則A174。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。對(duì)于規(guī)范句型來說，句柄的后面不會(huì)出現(xiàn)非終結(jié)符I號(hào)(即，句柄的后面只能出現(xiàn)終結(jié)符)。這種方法特別有利于表達(dá)式分析，宜于手工實(shí)現(xiàn)。我們用下面方法表示任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符a和b(它們之間可能插有一個(gè)非終結(jié)符)的優(yōu)先關(guān)系。在后面的定義中，a、b代表任意終結(jié)符；P