1、語法分析目標代碼生成I翻譯程序把某一種語言程序（稱為源語言程序）等價地轉換成另一種語言程序（稱為目口號言程序）的程序? 編譯程序（Complier）將某種高級語言（如 FORTRAN Pascal、C等）程序翻譯為對應的低級語言（如匯編語言或機械語言）程序。 L2編譯程序概述自然語言翻譯過程:編譯程序工作過程,詞法分析語義分析與中間代碼產生識別單詞分析句法初步翻譯譯文潤飾正式翻譯源語言 程序翻譯 程序目標語 官程金L_r翻譯4.遍(Pass)或趟對源程序或源程序的中間結果從頭到尾掃描一次，并作有關處理生成新的中間結果或目標程序.1.3編譯程序的結構L編譯程序總框圖|語法規則；語法單位的形成規則

2、。-語法單位通常包括：表達式、語句、分程序、過程、函數、程序等;-描述工具：上下文無關文法語義：一組規則，用它可以定義一個程序的意義Q標識符與名字標識符：以字母開頭的，由字母數字組成的字符串。標識符與名字兩者有本質區別：-標識符是語法概念-名字有確切的意義和屬性上下文無關文法的定義：一個上下文無關文法G是一個四元式G=（Vt,Vn,S,P）,其中V二終結符集合（非空）V其：非終結符集合（非空）9且VtCVn=0-S：文法的開始符號,SeVNP:產生式集合（有限），每個產生式形式為PfQbPeVN,cce（VTkVMr開始符S至少必須在某個產生式的左部出現一次。一個開始符號：特殊的非終結符，程序

3、語言中,最終感興趣的是“程序”。一組產生式；定義語法范疇的書寫規則,Afa,A是一個非終結符，稱左部符號，a稱為產生式的右部，.是由終結符號或|與非終結符號組成的一個符號串。產生式Afa稱為關于A的一條產生規則o這種表示法稱巴科斯范式，簡稱BNF范式。有的書用“:尸”代替to最左推導：任何一步a=p都是對a中的最左非終結符進行替換。最右推導：任何一步anp都是對a中的最右非終結符進行替換。4.形式語言概述喬姆斯基將其分為四類，0,1,2,3,與上下文無關文法一樣，它們都由四部分組成，差別在于對產生式施加不同的限制。*0型文法:*1型文法。2型文法(PSG)(CSG)(CFG)9 0型語言或短語

4、結構語言91型語言或上下文有關語言今2型語言或上下文無關語言03型文法(RG)今3型語言或正則(正規)語言0型文法（短語文法，圖靈機）：對文法G,若是它的每一個產生式是如此的一種結構：（VnUV）*且至少含有一個非終結符*（VnUVt）0型文法相應的語言為0型語言，或稱遞歸可列舉集，它的識別系統是圖靈（Turing）機。如文法G,其中Vn=A,B,SVk0,1P=S-0AB1B0BfSA|01A1-SB1A0fS0B1型文法（上下文有關）：它是0型文法的特例，對P中的任一產生式a-3,者B|3I1I,僅僅S-e除外，但S不得出此刻任何產生式的右部。1型文法相應的語言稱為1型語言或上下文有關語言

5、，它的識別系統是線性有界自動機。例文法GS:SfaSBESfaBEE-BEaB-abbBfbbbEfbeeEfee2型文法（上下文無關文法）：它是1型文法的特例，對任一產生式“一3,者B有aC%,3C（VnUVt）*2型文法相應的語言稱為2型語言或上下文無關語言。它的識別系統是下推自動機。例文法GS:SfABA一BS|0B一SA|12型文法產生式的一樣形式是：A一，它表示不管A的上下文如何都可把A替換成，因此被稱為上下文無關文法。3型文法（正規文法）：它是2型文法的特例，任一產生式a-3的形式都為ZaB或Za,其中A,BCVn,aCVt這種形式的3型文法也叫右線性文法。3型文法還有一種形式，限

6、定P中的每一個產生式形如ABa或Afa,稱為左線性文法。3型文法描述的語言稱為3型語言或正規語言（也稱正規集）,由有窮自動機識別。例如文法GS:S-0A|1B|020A|1B|0SB-1B|1|0文法類別產生式形式產生的語言說明0型文法（短語文法）0-BaV且至少含一個非終結符，0型語言對產生式基本無限制1型文法（上下文有關文法）afB,|6|刈口|1型語言（上下文有關語言）將A替換成P時，必須考慮A的上下文2型文法（上下文無關文法）A-0,A/,2型語言（上下文無關語言）無需考慮A在上下文中的出現情況3型文法（正規文法）AaB或Aa.,A,BE%jaG%3型語言正規語言）產生式全部是規定的形

7、式?詞法分析的任務：從左至右逐個字符地對源程序進行掃描,產生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。因此，詞法分析是編譯的基礎。執行詞法分析的程序稱詞法分析器，簡稱掃描器。功能：輸入源程序，輸出單詞符號。單詞符號是一個程序語言的大體語法符號。程序語言的單詞符號一樣可分為以下五種：關鍵字、標識符、常數、運算符、界符3.狀態轉換圖設計詞法分析器的一個好工具結點代表狀態，用圓圈表示口狀態轉換圖是一張有限方向圖。狀態之間用箭弧連結，箭弧上的標記字符）代表射出結狀態下可能出現的輸入字符或字符類。一張轉換圖只包含有限個狀態，其中有一個為初態，至少要有一個終態匕預處置子程序：剔除

8、無用的空白、跳格、回車和換行等編輯性字符；區分標號區、連接續行和給出句末符等正規集是字母表s上的符合必然規那么的符號串組成的集合正規表達式是一種適合描述符號的表示法，可由它概念正規集。L正規式與正規集遞歸定義：困。都是上的正規式，其表示的正規集分別為但和任何妙工/是上的一個正規式，其正規集為；假定U和V都是上的正規式,其正規集分別為L(U)和L(V),則(U|V),(U)和(17)*也都是正規式，其正規集分別為L(U)UL(V),L(U),L(V)(連接積)和(L(U)*(閉包)。U|V是正規式，L(U|V)=L(U)UL(V)；UV是正規式，L(U.V)=L(U).L(V)；(U)*是正規式

9、，L(U*尸(L(U)*O僅由有限次使用上述三步驟得到的表達式才是上的正規式，僅由這些正規式所表示的字集才是上的正規集，不致混淆時，括號可省，算符優先：*.號可省。.確定有限自動機(DFA)|一個確定有限自動機(DFA)M是一個五元式M=(S,工6,s0,F)G)S是一個有限集，每個元素為一個狀態X是有窮字母表，每個元素為一個輸入字符6是一個從Sx至S的單值部分映射，5(s,a)=意為：當現行狀態為s,輸入字符a時，將轉換到下一狀態s(后繼狀態).非確定有限自動機(NFA)一個非確定有限自動機(NFA)M是一個五元式M=(S,.5,So,F)S是一個有限集，每個元素為一個狀態有窮字母表，每個元

10、素為一個輸入字符05是一個從SxX*至S的子集的映照，即：5：SxX*f2s小結:將NFA轉換為DFA的步驟：第一步：對NFA的狀態圖進行改造：由于NFA可能有多個初態結點、多個終態結點、每條弧上可能是1上的一個字，因此首先將其改造，使之只有一個初態結點、一個終態結點、每條弧上的標記只能是單個輸入符號或者心二(1)增加狀態X,Y使之成為新的唯一的初態和終態,從X引日邊到原初態結點，從原終態結點引w邊到Y結點。匚(2)對狀態圖進一步進行替換，不斷重復:該過程，直到狀態轉換圖中的每條邊上的標記為Z上的單個符號或者i最霸為NFA使用子集法進行確定化(1)對Z=a1,，ak,構造一個kF列的狀態轉換表

11、。首先置該表的首行首列為jClosure(X),X為第一步完成后唯一的開始狀態。(2)若某行的笫一列的狀態已確定為I,則第i+1(i=1,2,.k)列的值為lai,然后檢查該行上的所有狀態子集，看它是否已在第一列出現。若未出現，將其填加到后面的空行上。重復此過程，直到所有狀態子集均在第一列中出現。n(3)將每個狀態子集視為新的狀態，就得到一個確定的有窮自動機，初態就是首行首列的狀態，終態是含有原有終態的所有狀態。到有窮自動機的轉換已知正規文法(石線性)G=(VNjVT5P,S),求等價的NFA為M=(Q,E,b,S,F)的步驟如下：(1).輸入字母表上就是文法的終結符號：化).初始狀態S：就是

12、開始符號;(3).狀態集合Q： 點；增設一個終態f,以Q=fUVN為狀態結(4),終態集合F：若P中含有SE的產生式,則F=f,S,否則F=f(5),狀態轉換函數。的計算方法：口對P中的產生式A-aB,6(A,a尸B,畫從A到B的弧.標船對P中的產生式Aa,6(A,a尸f,畫從A到f的弧,標a：將正規表達式轉換成有線自動機然后，按下面的三條規則對V進行分裂代之為華9V1代之為v2Vr*0代之為VDFA化簡具體做法:對M的狀態集進行劃分首先，把S劃分為終態和非終態兩個子集,形成基本劃分1L假定到某個時候，n已含m個子集，記為口=1，1億)，噢,檢查口中的每個子集看是否能進一步劃分：口對某個網,令

13、昨收22,SjJ,若存在一個輸入字符a使得I卅不會包含在現行口的某個子集W)中，則至少應把即分為兩個部分。一樣地，對某個a和I，假設Ia(i)落入現行中N個不同子集，那么應把I(i)劃分成N個不相交的組，使得每一個組J的Ja都落入的同一子集。如此組成新的劃分重復上述進程，直到所含子集數再也不增加。關于上述最后劃分中的每一個子集，咱們選取每一個子集I中的一個狀態代表其他狀態，那么可取得化簡后的DFAM。若I含有原先的初態，那么其代表為新的初態，假設I含有原先的終態，那么其代表為新的終態。?語法分析的任務是分析一個文法的句子結構。?語法分析器的功能：依照文法的產生式(語言的語法規那么)，識別輸入符

14、號串是不是為一個句子(合式程序)。算文法G中每個文法符號A(AevNuVT)的First集可用如下算法(1)若ACVt，則First(A)=A；,(2)若有產生式A-*,aeVTf則把a加入到Fist(A)中；(3)若有產生式Ae,則把e加入到First(A)中；(4)若有產生式AXa,XVn，則把First(X)中非e元素加入到First(A)中二(5)若有產生式A】?乂2,其中X1X2X3XkRVn。則-當X1X2X3X產氣(作咨k)時，則把Fimt(X陽XkQ)的所有非元素加入Fist(A)中彳-當XiXPQXk=A*e時，則把First(d)加入FirsHA)中。連續使用上述規則，直到

15、每個集合的First不再增大為止.計算文法G的每個/終結符:A的Follow集的算法(1)如果A是開始符號，#eFollow(A)；(2)若有產生式BaAap,auv把a加入到Follow(A)中；(3)若有產生式B-aAXB，XrVN,把First(X0)中非w元素加FMow(A)中：(4)若B-ctA,或BaAB且(3n*E,把Follow(B)加到Follow(A)中；連續使用上述規則，直到每個Follow不再增大為止口552,規范歸約簡述1）概念E9 T|E+TTf F|T*FF今 i | (E)從語法樹可以看出：il. i2, i3, il*i2, il*i2+i3是句型il*i2+

16、i3的短語直接短語有：il,i2,i314句柄是：il有文法G,開始符號為S,如果有S=從語法分析樹來識別：E 一語法分析樹的一棵子樹是由該樹的某個結/點連同它的所有子孫組成的。/ 一個子樹的所有樹葉結點自左至右排列起來/形成一個相對于子樹根的短語。只有父子兩代結點形成的子樹的樹葉結點自/八左至右排列起來就形成相對于子樹根的直接 / 短語；/ 一個句型的句柄是這個句型所對應的語法樹:中最左那個構成直接短語的子樹的樹葉結點Fi2自左至右的排列對下述文法的的句型il*i2+i3的語法樹如圖：1ap5,則apb是文法C的句副a,6是任意的符號串*+如果有匿13且4n凡則B是句型apb相對于非終結符A

17、的卷語如果有S=*aA&且有A-B,則B是句型apb相對于AB的直接短語位于一個句型最左邊的直接短語稱為句癡句型-短語一直接短語一句柄作為短語的兩個條件均不可缺少規范歸約的定義定義：假定a是文法G的一個句子，我們稱序列dpicn-199a0是的一個規范歸約，如果此序列滿足：an=aa。為文法的開始符號，即a()二S3對任何L0i8.或P=Qa.a為終結符,P,Q為非終結符由優先性低于的定義和fhstVT集合的定義可以得出:若存在某個產生式：aP，對所有：befitVT(P)都有：b。構造FIRSTVT集算法:按照下面兩條規則來構造FIRSTVT集：-若有產生式P-a.或4Qa.，則aFIRST

18、VT(P)-若有產生式P-R.,則FIRSTVT(R)包含在FIRSTVT(P)中通過構造一個二維數組F來實現,該從數組F反映任何一個非終結符p的FIRSRVT集中的元素。步驟:先用第一條規則進行初始化所有非終結符abcPQ組值為真假,J所有終結符為真的條件是ce first(Q)使用第二條規則對數組F進行修改，修改方法是：(1)用一個棧，將所有F數組中值為真的元素FP,a的符號對(P,a)壓入堆棧；(2)對棧施行如下操作：若棧不空，將棧頂符號對出棧，記為(Q,a),檢查所有的產生式，若有形為：P9Q的產生式，且FP,a為假，則變其值為真且將(P,a)壓入堆棧；(3)重復這一過程，直到棧空2.

19、求LASTVT集一定義：LASTVT(P)=a|M=漉耐=.aQ,a為終結符,P,Q為非終結符(1)若有產生式Pf.a或Pf.aQ,貝(JaeLastVT(P),其中P、QeVN,aeVT；(2)若aLastVT(Q),且有產生式PfQ,貝UaLastVT(P)o構造LASTVT集算法：自己作*比較FOLLOWS=aS.Aa.aeVT54、6屬性文法）、屬性文法的基本概念1.性文法屬性是指與文法符號的類型和值等有關的一些信息，在編譯中用屬性描述處理對象的特征。-變量的數據類型-表達式的值存儲器中變量的位置程序的目標代碼數的有效位數:2.屬性分類二綜合屬性（自下而上傳遞信息）?僅僅利用綜合屬性的

20、屬性文法稱S-屬性文法綜合屬性值的計算方法對于S屬性定義通常使用自底向上的分析方法使用語義規則屬性值在建立每一個結點處即在用哪個產生式進行歸約后，就執行那個產生式的S-屬性定義計算屬性的值，從葉結點到根結點進行計算口語法樹中，T結點的繼承屬性由此結點的父結點或/和兄弟結點的某些屬性確定（表示上下文依賴關系）oL-屬性文法可用于一遍掃描的自上而下分析，S-屬性文法適合于一遍掃描的自下而上分析。6.3S屬性文法的自S屬性文法：只含有綜合屬性綜合屬性可以在分析輸入符號串的同時由自下而上的分析器來計算。分析器可以保存與棧中文法符號有關的綜合屬性值，每當進行歸約時，新的屬性值就由棧中正在歸約的產生式右邊

21、符號的屬性值來計算。、614L屬性文法和自頂向下翻譯J通過深度優先的方法對語法樹進行遍歷,計算屬性文法的所有屬性值LL(1)：自上而下分析方法，深度優先建立語法樹L-屬性文法是這樣的一個屬性文法，如果對于每個產生式AfXiX2Xn,其每個語義規則中的每個屬性或者是綜合屬性，或者是XjQWj&i）的一個繼承屬性，并且這個繼承屬性僅依賴于:O產生式Xj的左邊符號XnX2,玉_1的屬性:OA的繼承屬性。可以看出：S屬性文法一定是L屬性文法。常用的中間語言，-后綴式，逆波蘭表示-圖表示,DAG、抽象語法樹-三地址代碼.三元式!1!元式間接三元式符號表的作用在編譯的各個分析階段，每當遇到一個名字都要查找

22、符號表。若是新名字或發現已有名字的新信息，則要加入（填入）。因此，合理組織符號表，使其存儲占用最少，同時提高編譯期間對符號表的訪問效率，至關重要。對符號表的操作大致可以分為五類： TOC o 1-5 h z 查詢某個名字是否已在表中。填入一個新的名字。訪問某個名字的某些信息。添加或更新某個名字的某些信息刪除一個或一組無用的項。符號表的組織方式最簡單的組織方式:各項各欄長度固定一易于組織、填寫和查找。這種表格，每一欄的內容可直接填寫在有關的區段內。例如，對于名字欄，其大小可按標識符最大允許長度來確定。如標準FORTRAN語言規定每一標識符不得超過6個字符，因此就可用6個字符的空間作為名字欄的長度

23、。若標識符長度不足6個字符，則以空白符補齊。82整理與查找J線性表構造符號表最簡單、最容易的辦法是按關鍵字出現的順序依次填寫各個項。用一個一維數組或多個一維數組來存放名字及有關信息。當碰到一個新名字時就按順序將它填入表中，若需要了解一個名字的有關信息，則就從第一項開始順序查找。這種構造方式稱為線性表，其結構如下：（其中AVAILABLE總是指向空白區的首地址）對折查找與二叉樹按名字大小建立有序表，則可采用對折查找法（折半查找）最多比較次數1十log?N（對數查找）。要保持有序，需要每次填入新名字時都進行排序，因此采用二叉樹組織法，左大右小。查找效率比對折查找低了一些，且所需存儲空間增大，但其所

24、需順序化的時間要少得多,且比較次數仍和logzN成比例，因此可取。雜湊技術對表格處理，查表與填表都能高效進行是最理想的。線性表填表快、查表慢，而對折法填表慢、查表快，兩方面綜合雜湊技術（哈希表或散列表）：假定有一足夠大的區域，可填寫一張含N項的符號表，希望構造一個地址函數H,對任何名字SYM,H（SYM）都可獲得一個0和N1之間的值。也就是說，不論對SYM是查表還是填表，都希望通過H（SYM）獲得它在表中的位置。一雜湊函數，哈希函數。參數傳遞e過程（函數）是結構化程序設計的主要手段，也是節省程序代碼和擴充語言能力的主要途徑，調用與被調用（過程）兩者間的信息通過全局變量或參數傳遞。過程定義中的參

25、數稱形式參數，簡稱形參。過程調用語句中的參數稱實在參數，簡稱實參，實參可以是常量、變曷或較復雜的表達式，實參與對應形參在性質上應相容。參數傳遞方式一傳地址把實在參數的地址傳遞給相應的形式參數方法：-調用段預先把實在參數的地址傳遞到被調用段可以拿到的地方；-程序控制轉入被調用段之后，被調用段首先把實在參數的地址抄進自己相應的形式單元中;-過程體對形式參數的引用域賦值被處理成對形式單元的間接訪問。二.得結果傳地址的一種變形方法：-每個形參對應兩個形式單元，第一個形式單元存放實參地址，第二個單元存放實參的值。-在過程體中對形式參數的任何引用或賦值都看作對它的第二個單元的直接訪問。-過程完成返回前把笫

26、二個單元的內容存放到第一個單元所指的實參單元中。三.傳值把實在參數的值傳遞給相應的形式參數方法：-調用段預先把實在參數的的值計算出來并放在被調用段可以拿到的地方;-被調用段開始工作時，首先把實參的值抄入形式參數相應的單元；-被調用段中，象引用局部數據一樣引用形式單元。四.傳名過程調用的作用相當于把被調用段的過程體抄到調用出現的地方，但把其中任一出現的形式參數都替換成相應的實參。方法：-在進入被調用段的之前不對實在參數預先進行計值，而是讓過程體中每當使用到相應的形式參數時才逐次對它實行計值（或計算地址）。因此，通常把實在參數處理成一個子程序（稱為參數子程序），每當過程體中使用到相應的形式參數時就

27、調用這個子程序。例：procedureP(w,x,y,z);beginy:=y*w;z:=z+x;傳傳得傳值地結名 ,址果：5427 7endbegina:=5;b:=3;P(a+b,a-b,a,a);write(a);end活動記錄使用一個連續的存儲塊，來管理過程在一次執行中所需的信息，稱為活動記錄。當發生調用時，產生一個過程的新活動，用一個活動記錄來表示該活動的相關信息并將其壓入棧，當過程返回（活動結束）時，當前活動記錄一般包含以下內容：1.連接數據返回地址動態鏈：指向調用該過 程前的最新活動記錄地 址的指針靜態鏈：指向靜態直接 外層最新活動記錄地址 的指針，用來訪問非局 部數據。FORT

28、RAN不臨時單元 內情向量 局部變量 形式單元參數個數返回地址需要（放在固定地方），而老SPPascal需要。存儲分配策略不同編譯程序，其分配策略可能不同，大致有三種；靜態.忖所有數據對象分配固定的存儲單元.1a在運行時始終保持不變。柳轉動存儲器組織成棧結構。每當調用一個過集八列程，所需存儲空間就動態分配于棧頂，I一旦退出，所占空間就予以釋放。堆式動I存儲器組織成堆結構。凡存儲空間申請態;|者就從堆中分給一塊,凡釋放者退回堆中O優化的目的：產生更高效的代碼。優化必須遵循的原則L等價原則：不應改變程序運行的結果。.有效原則：優化后的目標代碼運行時間較短,占用的存儲空間較小。.合算原則：應盡可能以

29、較低的代價取得較好的優化效果。優化的三個不同級別:-局部優化-循環優化-全局優化優化的種類:-刪除多余運算（或稱刪除公用子表達式）-代碼外提-強度消弱-變換循環控制條件-合并已知量-復寫傳播-刪除無用賦值基本塊及流圖1.基本塊口的口指程序中一順序執行的語句序列，其中只有一個人和一個出中，入口是其中的第一條語句，出口是其中最后一條語句，執行時，只能從其入口進入，從其出退出。4.基本塊構成的流圖每個流圖以基本塊為結點。如果一個結點的基本塊的入口語句是程序的第一條語句，則稱此結點為首結點。如果在某個執行順序中，基本塊B2緊接在基本塊B1之后執行，則從B1到B2有一條有向邊。即，如果-有一個條件或無條件轉移語句從B1的最后一條語句轉移到B2的第一條語句；或者-在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語句不是一個無條件轉移語句。我們就說B1是B2的前驅，B2是B1的后繼。10；3循環優化一個程序運行時，相當多一部分時間往往