編譯原理教案(留存版)

　　

【正文】 來表示各種名字，如變量名、數組名和過程名等等；3 常 數 各種類型的常數，如125，、TRUE等等； 4 運算符 如+、*、/等等； 5 界 符 如逗號、括號、分號等等。當緩沖區里的字符串被處理完之后，它又調用預處理程序裝入新串。轉換圖非常易于用程序實現，最簡單的辦法是讓每個狀態結點對應一小段程序。Σ上的一個字（也叫字符串）是指由Σ中的字符所構成的一個有窮序列。S，是一個終態集（可空）。 詞法分析器的自動產生 教學目的：使用狀態轉換圖構造詞法分析程序；上機實踐LEX的實現。有些能用于自動產生掃描器(如LEX)，有些可用于自動產生語法分析器(如YACC)，有些甚至可用來自動產生整個的編譯程序。與前面一樣，我們用‘222。’指僅推導一步的意思。 語法分析樹與二義性 前面我們提到過可以用一張圖表示一個句型的推導，這種表示稱為語法分析樹，或簡稱為語法樹。任何0型語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。 Pδ,則稱該文法含有間接左遞歸。 練習課254。 消除回溯、提左因子 我們首先來看一下在不得回溯的情況下對于文法有什么要求。*…Aa…,a206。 可以證明，一個文法G的預測分析表M不含多重定義入口，當且僅當該文法為LL(1)的。這種方法減少在錯誤恢復期間必須考慮的非終結符數。如果文法G是無二義的，那么規范推導的逆過程必是規范規約。 算符優先分析法 現在，我們來討論一種簡單直觀、廣為使用的自下而上分析法，叫做算符優先分析法。+b…或R 222。+a…或P222。按定義，我們可用下面兩條規則來構造集合FIRSTVT(P):(1)若有產生式P174。N是指那樣一個產生式的左部符號，此產生式的右部和S[j＋1]…S[k]構成如下一一對應關系：自左至右，終結符對終結符，非終結符對非終結符，而且對應的終結符相同。b，則f(a)g(b)；若a(2)歸約 指用某一產生式A174。我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態” LR（0）項目集族和 LR（0）分析表的構造 字的前綴是指字的任意首部。 的活前綴識別自動機中的每個狀態（項目集）不存在下述情況：（1）既含移進項目又含規約項目；（2）或者含有多個規約項目，則稱G是一個LR(0)文法。α產生式歸約；3）若當前輸入符a 206。對于同一個文法，LALR分析表和SLR分析表永遠具有相同數目的狀態。 練習課254。 如果在一棵語法樹中一個結點的屬性b依賴于屬性c，那么這個結點處計算b的屬性規則必須在確定c的語義規則之后使用。X1X2…Xn其每個語義規則中的每個屬性或者是綜合屬性，或者是Xj(1=j=n)的一個繼承屬性且這個繼承屬性僅依賴于： （1）產生式Xj的左邊符號X1,X2,…Xj1的屬性 （2）A的繼承屬性。語句可以帶有符號標號，而且存在各種控制流語句。另一過程partition是在quicksort中被說明，因此它的符號表有指針指向quicksort的符號表。、類型及域寬等。要生成數組的引用代碼，其主要問題是把常數C和變數V 的計算與數組引用的文法聯系起來。p 是一個指向某個記錄的指針，這個記錄有一個類型為算術型的域名info。一般說來，把這些信息保存在相應的域名的符號表表項之中。： i*w + (base – low*w)其中：i*w 是隨數組下標變量而變化的部分 （base – low*w）是在數組中不變化的常數記為C對于多維數組中二維的情況尤其應注意：若二維數組A按行存放，則可用如下公式計算A[i1,i2]的相對地址： base + (( i1 – low1)*n2 + i1 – low2) *w其中，lowlow2分別為ii2的下界；n2是i2可取值得個數。id：T的語義動作是將域名id的有關信息填入此記錄的符號表中。過程enter(name，type，offset)用來把名字name填入到符號表中，并給出此名字的類型type及在過程數據區中的相對地址offset。 三地址代碼三地址代碼可以看成是抽象語法樹或DAG的一種線性表示。 在自底向上的分析法中。因此，通常使用自底向上的方法在每一個結點處使用語義規則計算綜合屬性的值。 語法分析器的自動生成工具YACC YACC是一個編譯程序的編譯程序，借助它可以構造編譯程序。這就是LR(1)的方法。 Follow(A), b 207。 是G 的拓廣文法。(so，)為分析開始前預先放在棧里的初始狀態和句子括號。GOTO[s，X]規定了狀態s面對文法符號X(終結符或非終結符)時下一狀態是什么。如果沒有矛盾，則f和g就是所要的優先函數。 a IF Xi為非終結符而Xi+1為終結符THEN FOR LASTVT(Xi)中的每個a DO 置 a b。b的終結符對。…ab…或P174。因為，句柄的“最左性”和符號棧的棧頂兩者是相關的。 規范歸約簡述 規范規約是關于α的一個最右推導的逆過程。例如，如果分號作為語句的結束符(C語言中就是這樣的)，那么作為語句開頭的關鍵字就可能不在產生表達式的非終結符的FOLIDW集中。 預測分析程序 用高級語言的遞歸過程描述遞歸下降分析器只有當具有實現這種過程的編譯系統剛才有實際意義。例如，假定關于A 的規則是 A174。 左遞歸的消除 假定關于非終結符P的規則為 :P P|αβ 其中，每個 都不以P開頭，那么我們可以把P的規則改寫成如下的非直接左遞歸形式：p βp39。+g；也就是，對于P不存在永不終結的回路。若存在產生式P 222。 形式語言鳥瞰 前面喬姆斯基把文法分成四種類型，即0型，1型，2型，和3型。例如，“算術表達式”這個非終結符乃代表一定算術式組成的類。(i+i)。一個上下文無關文法如何定義一個語言呢?其中心思想是，從文法的開始符號出發，反復連續使用產生式，對非終結符施行替換和展開?！币灿谩埃海海健北硎荆哼@種表示方法也稱巴科斯范式。（2） 對每一個FA M，都存在一個右線性正規文法GR或左線性正規文法GL，使得L（M）＝L（GR）＝L（GL） 正規式與有限自動機的等價性 我們可以證明：（1） 對任何FA M，都存在一個正規式r，使得L（r）＝L（M）。意味著：當現行狀態為s，輸入字符a時，將轉換到下一狀態s39。6. LETTER和DIGIT布爾函數過程，它們分別CHAR中的字符是否為字母和數字，從爾給出真值TRUE或假值FALSE。若輸入字符Y，則讀進Y，并轉換到狀態3。詞法分析的工作（單詞符號的識別）可以直接在這個緩沖區中進行。 討論□ 示教□ 指導254。 人們已經建立了多種編制部分編譯程序或整個編譯程序的有效工具。編譯前端與不同的編譯后端以Diana為界面，實現編譯程序的目標機改變。 一個編譯程序究竟應分成幾遍，如何劃分，是與源語言、設計要求、硬件設備等諸因素有關的，因此難于統一劃定。如果不僅能夠發現錯誤，而且還能自動校正錯、誤，那當然就更好了。在編譯程序使用的表格中，最合理的是符號表。第一章 引論 什么叫編譯程序？ 通常所說的翻譯程序是指這樣的一個程序，它能夠把某一種語言程序(稱為源語言程序)轉換成另一種語言程序(稱為目標語言程序)，而后者與前者在邏輯上是等價的。實際上，許多編譯程序的構造與實現技術同樣適用于解釋程序。例如，一個名字是常量名、變量名，還是過程名等等；如果是變量名，它的類型是什么、所占內存是多大、地址是什么等等。例如，詞法分析階段能夠檢測出“非法字符”之類的錯誤；語法分析階段能夠檢測出諸如“括號不匹配”、“缺少；”之類的錯誤。 編譯前端與后端 概念上，我們有時把編譯程序劃分為編譯前端和編譯后端。編譯程序與這些程序設計工具一起構成所謂的程序設計環境。意思是，先對語言的核心部分構造一個小小的編譯程序（可用手編實現），再以它為工具構造一個能夠編譯更多語言成分的較大編譯程序。 標識符一般統歸為一種。 詞法分析器下面我們來介紹一下單詞符號識別的一個簡單方法——超前搜索。下面我們將引進一組全局變量和過程，把它們作為實現轉換圖的基本成分。不包含任何字符的序列稱為空字，記為ε。 一個DFA可用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示f（s，a）的值，這個矩陣稱為狀態轉換矩陣。 語言LEX的一般描述 一個LEX源程序主要包括兩部分。這些構造編譯程序的工具稱為編譯程序——編譯程序、編譯程序產生器或翻譯程序書寫系統，它們是按對源程序和目標語言(或機器)的形式描述(作為輸入數據)而自動產生編譯程序的?！硎尽爸苯油瞥觥?，這樣，這句話就可表示為:E222。我們可以用一種圖示化的方法來表示這種推導，說明He gave me a book是一個語法正確的句子。語法樹有助于理解一個句子語法結構的層次。 1型文法：也稱上下文有關文法，對非終結符進行替換時務必聯系上下文，并且一般不允許替換成空串。其中P,P1, …,Pn ∈ VN, α, β, γ,δ ∈ (VN∪ VT)*。 其他□教學方式（請打√）：講授254。前面已經說過，欲實行自上而下的分析，文法不得含左遞歸。VT}特別是，若S222。 LL(1)分析中的錯誤處理 我們以預測分析為例。(5)如果不能匹配棧頂的終結符號，一種簡單的想法是彈出棧頂的這個終結符號，并發出一條信息，說明已經插入這個終結符，繼續進行語法分析。 句柄：令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有S222。這種方法特別有利于表達式分析，宜于手工實現。Qb…。+Qa…,a206。a…或P174。由于非終結符對歸約沒有影響，因此，非終結符根本可以不進符號棧S。b，則f(a) g(b).在實際實現算符優先分析算法時，一般不用上述這樣的優先表，而是用兩個優先函數f和g相對應，函數f稱為人棧優先函數，g稱為比較優先函數。b進行歸約。所謂活前綴是指規范句型的一個前綴，這種前綴不含句柄之后的任何符號。 由于假定LR(0) 文法規范族的每一個項目集不含沖突項目，因此，按上述方法構造的分析表的每一個入口都是唯一的（即不含多重定義）。 Follow(B)，按B174。對于ALGOL一類語言來說，一般要用幾百個狀態，但若用規范LR分析表，同一類語言，卻要用幾千個狀態。 其他□教學方式（請打√）：講授254。在一顆語法樹中的結點的繼承屬性和綜合屬性之間的相互依賴關系可以用稱作依賴圖的一個有向圖來描述。L—屬性文法允許通過一次遍歷就計算出所有屬性值。符號標號代表存放中間代碼的數組中三地址代碼語句的下標。在下面的語義規則中用到如下操作： (1)mktable(previous)創建一張新符號表，并返回指向新表的一個指針。有關類型構造符和類型表達式概念將在4．7節介紹。 id 出現的地方也允許下面產生式中的L出現，則可把數組元素引用加入到賦值語句中。如果類型像圖4．8和圖4．9一樣構造，則p173。 記錄中域的作用 編譯器必須將記錄中的域的類型和相對地址保持下來。假定數組的每個元素的寬度為w，則一維數組A[i] 這個元素的起始地址為： base + (i – low)*w （）其中low為數組下標的下界， 并且base是分配給數組的相對地址，即base為A的第一個元素A[low]的相對地址。產生式D174。在處理第一條說明語句之前，先置offset為0，以后每次遇到一個新的名字，便將該名字填入符號表中并置相對地址為當前offset之值，然后使offset加上該名字所表示的數據對象的域寬。 圖表示法 這里的圖表示法包括DAG（無循環有向圖）與抽象語法樹。 下面我們討論分析棧中的綜合屬性。都有一套與之相關聯的語義規則，每條語義規則的形式為： b:=f(c1,c2,…,ck) 這里f是一個函數，而且或者 （1）b是A的一個綜合屬性并且c1,c2,…,ck是產生式右邊文法符號的屬性； 或者 （2）b是產生式右邊某個文法符號的一個繼承屬性并且c1,c2,…，ck是A或 產生式右邊任何文法符號的屬性 在這兩種情況下，我們都說屬性b依賴于屬性c1,c2，…,ck.： 在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。發現錯誤后，便進入相應的出錯處理子程序。?對策：給每個LR(0)項目添加展望信息，即：添加句柄之后可能跟的終結符，因為這些終結符確實是規范句型中跟在句柄之后的。α?}LR(0)項目集，若Follow(A) ∩Follow(B)= f且b 207。那么，我們稱G39。棧的每一項內容包括狀態s和文法符號X兩部分。ACTONIs，a]規定了當狀態s面臨輸入符號a時應采取什么動作。(3)檢查所構造出來的函數f和g，看它們同原來的關系表是否有矛盾。Xi+2 IF Xi為終結符而Xi+1為非終結符 THEN FOR FISTVT(Xi+1)中的每個a DO 置 XiFISTVT(P),我們有a 通過檢查G的每個產生式的每個候選式，可以找出滿足a=對于任何一對終結符a、b，我們說：（1） a=b 當且僅當文法G中含有形如P174。請注意句柄的“最左”特征，這一點對于移進—歸約來說是重要的。我們可用句柄來刻畫移進—歸約過程的“可歸約串”。(2)對于非終結符A來說，只用FOLLOW(A)作為它的同步符號集是不夠的。這樣的一個分析程序稱為遞歸下降分析器。如何把一個文法改造成任何終結首符集的所有候選首符集兩兩不相交呢？其辦法是提取公共左因子。為構造不帶回溯的自上而下分析算法，首先要消除文法的左遞歸性，并找出克服回溯的