編譯原理復(fù)習(xí)要點

1/18考試大題：循環(huán)優(yōu)化LL(1).定義之類的算符優(yōu)先算法…自下而上分析法(20分，選擇、填空、大題)第一章引論把某一種高級語言程序等價地轉(zhuǎn)換成另一種低級語言程序(如匯編語言或機器語言程序)二．編譯程序的工作的五個階段:詞法分析、語法分析、中間代碼產(chǎn)生、優(yōu)化、目標代碼產(chǎn)生1.詞法分析依循的原則：構(gòu)詞規(guī)則Pascal語言描述工具：有限自動機FORI:=1TO100DO保留字標識符等符整常數(shù)保留字整常數(shù)保留字2.語法分析任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法依循的原則：語法規(guī)則述工具：上下文無關(guān)文法3.語義分析與中間代碼產(chǎn)生任務(wù):對各類不同語法范疇按語言的語義進行初步翻譯。(變量是否定義、類型是依循的原則：語義規(guī)則例：將Z:=X+0.618*Y翻譯成四元式為(1)*0.618YT1(2)+XT1T2(3):=T2_Z4.優(yōu)化任務(wù)：對于前階段產(chǎn)生的中間代碼進行加工變換，以期在最后階段產(chǎn)生更高效依循的原則：程序的等價變換規(guī)則FORK:=1TO100DOBEGINM:=I+10*K;2/18N:=J+10*K;END4.目標代碼產(chǎn)生任務(wù):把中間代碼變換成特定機器上的目標代碼。依賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令的含義目標代碼三種形式:a)絕對指令代碼:可直接運行b)可重新定位指令代碼:需要連接裝配c)匯編指令代碼:需要進行匯編三.編譯程序結(jié)構(gòu)編譯程序總框(簡答題5分)第二章高級語言及其語法描述詞法規(guī)則：單詞符號的形成規(guī)則。a)單詞符號是語言中具有獨立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標識符、基符等。b)描述工具：正規(guī)式和有限自動機語法規(guī)則：語法單位的形成規(guī)則。a)語法單位通常包括：表達式、語句、分程序、過程、函數(shù)、程序等;c)描述工具：上下文無關(guān)文法語義：一組規(guī)則，用它可以定義一個程序的意義。音無二義性音完整性3/18優(yōu)先級由高自低右線性文法優(yōu)先級由高自低右線性文法：乘冪(**或↑)一元負(-)乘、除加、減關(guān)系符(<,=,>,<=,>=,<>)非(?，not)與(Λ，&，and)或(?,|,or,)等值(等值( )2.3程序語言的語法描述1.幾個概念:b)其中每一個元素稱為一個字符d不包含任何字符的序列稱為空字，記為εbaabb}i圖靈機)：TNTNTNTNNTNNTN非終結(jié)符的替換可以不必考慮上下文。l規(guī)文法，有限自動機)：A4/18左線性文法左線性文法TNTN四種四種類型描述能力比較m)上下文無關(guān)文法的定義：TNTNTNNP：產(chǎn)生式集合(有限)，每個產(chǎn)生式形式為NTN1G(A)的語言?11n)定義：如果一個文法存在某個句子對應(yīng)兩顆不同的語法樹，則說這個文法是二義的。o)語言的二義性：一個語言是二義性的，如果對它不存在無二義性的文法。GG，一個為二義的，一個為無二義的。但L(G)=L(G’)2.狀態(tài)轉(zhuǎn)換圖a)概念：狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。b)結(jié)點代表狀態(tài)，用圓圈表示。c)狀態(tài)之間用箭弧連結(jié)，箭弧上的標記(字符)代表射出結(jié)狀態(tài)下可能出現(xiàn)的輸d)一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個為初態(tài)，至少要有一個終態(tài)3.正規(guī)運算符優(yōu)先順序在不致混淆時，括號可以省去，但規(guī)定算符的優(yōu)先順序為：*(閉包).(連接)|(或)G的任何產(chǎn)生式為AaB或AaTN3.3.2確定有限自動機(DFA)對狀態(tài)圖進行形式化，則可以下定義：05/18a)S:有窮狀態(tài)集，b)：輸入字母表(有窮)，0e)FS：終態(tài)集(可空)。f(0，a)=1f(1，a)=3f(2，a)=1f(3，a)=3f(0，b)=2f(1，b)=2f(2，b)=3f(3，b)=33.3.3非確定有限自動機(NFA)定義：一個非確定有限自動機(NFA)M是一個五元式M=(S,,f,S,F)，其中：02：輸入字母表(有窮)；05FS：終態(tài)集(可空)。2同一個字可能出現(xiàn)在同狀態(tài)射出的多條弧上。自動機理論中一個重要的結(jié)論：判定兩個自動機等價性的算法是存在的。AIisI，則s=-closure(I)；closure(I)例：設(shè)a是中的一個字符，定義I=-closure(J)a6/183.3.4正規(guī)文法與有限自動機的等價性2.對每一個FAM，都存在一個右線性正規(guī)文法G和左線性正規(guī)文法G，使得L(M)RLRL3.3.5正規(guī)式與有限自動機的等價性對轉(zhuǎn)換圖概念拓廣，令每條弧可用一個正規(guī)式作標記。(對一類輸入符號)3.3.6確定有限自動機的化簡DFAMM少的DFAM’，使得L(M)=L(M’)兩個狀態(tài)不等價，則稱它們是可區(qū)別的。對一個DFAM最少化的基本思想:把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個狀態(tài)是等價的。最后，讓每個子集選出一個代表，同時消去其他狀7/18I(1)={0,1,2}I(1)={1,3}aI(11)={0,I(11)={0,2}I(11)={1}aI(2)={3,ab={0}I(2)={3,4,5,6}2}I(12)={1}I(2)={3,4,5,6}={2,5}I(112)={2}I(12)={1}I(2)={3,4,5,6}I(2)={4,5}a語法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個相應(yīng)的子程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現(xiàn)對輸入串的識別。預(yù)測分析程序音優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。4.3LL(1)分析法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性克服回溯4.3.1左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為P→Pa|8/18P,→aP,|e左遞歸變右遞歸一般而言，假定P關(guān)于的全部產(chǎn)生式是左遞歸變右遞歸P→Pa1|Pa2|…|Pam|b1|b2|…|bn其中，每個a都不等于e，每個b都不以P開頭1P,→aP,1P,→aP,|1提取公共左因子:2aP,2aP,2|1y|12y|2…|m那么，可以把這些規(guī)則改寫成經(jīng)過反復(fù)提取左因子，就能夠把每個非終結(jié)符(包括新引進者)的所有候選首符集變4.3.3LL(1)分析條件T*特別是，若S亭???A，則規(guī)定＃=FOLLOW(A)*構(gòu)造不帶回溯的自上而下分析的文法條件2.對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若i=1,2,...,n結(jié)符A，若它存在某個候選首符集包含e，則語法分析的方法：自下而上分析法(Bottom-up)基本思想：從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達式。LR分析法：規(guī)范歸約9/18.1.2規(guī)范歸約如果有特別是，如果有A,則稱是句型a6相對于規(guī)則A的直接短語。一個句型的最左直接短語稱為該句型的句柄。2.歸約采用“移進－歸約”思想進行自下而上分析。棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符5.2算符優(yōu)先分析先乘除后加減，同級從左到右 它的句子有幾種不同的規(guī)范規(guī)約。 歸約即計算表達式的值。歸約順序不同，則計算的順序也不同，結(jié)果也不一樣。如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進行歸約，則歸約過程是唯一的。起決定作用的是相鄰的兩個算符之間的優(yōu)先關(guān)系。所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找“可5.2.1算符優(yōu)先文法及優(yōu)先表構(gòu)造一個文法，如果它的任一產(chǎn)生式的右部都不含兩個相繼(并列)的非終結(jié)符，即不含則我們稱該文法為算符文法。約定：a、b代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；‘…’代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。假定G是一個不含c-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，我們說：++從算符優(yōu)先文法G構(gòu)造優(yōu)先關(guān)系表的算法。確定滿足關(guān)系<和>的所有終結(jié)符對：GP兩個集合FIRSTVT(P)和LASTVT(P)：10/18TN++TN++口有了這兩個集合之后，就可以通過檢查每個產(chǎn)生式的候選式確定滿足關(guān)系<和>的所?假定有個產(chǎn)生式的一個候選形為…aP…?假定有個產(chǎn)生式的一個候選形為…Pb…按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)：LR分析方法：把"歷史"及"展望"綜合抽象成狀態(tài)；由棧頂?shù)臓顟B(tài)和現(xiàn)行的輸入符號唯一確定每一步工作LR分析器的核心是一張分析表：11/18A.XYZAX.YZAXY.ZAXYZ.音A.稱為"歸約項目"音歸約項目S’.稱為"接受項目"音A.a(aV)稱為"移進項目"T音A.B(BV)稱為"待約項目".NS,→EE→aA|bBA→cA|dB→cB|d構(gòu)造識別文法所有活前綴的NFA方法XiXiXni把識別文法所有活前綴的NFA確定化。12/18構(gòu)成識別一個文法活前綴的DFA的項目集(狀態(tài))的全體稱為文法的LR(0)項目集規(guī)LR(0)分析表的構(gòu)造假若一個文法G的拓廣文法G,的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下2)含有多個歸約項目分析表的ACTION和GOTO子表構(gòu)造方法：kkjkkjkkkkj按上述方法構(gòu)造出的ACTION與GOTO表如果不含多重入口，則稱該文法為SLR(1) 每個SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的. 每個SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.13/18我們需要重新定義項目，使得每個項目都附帶有k個終結(jié)符。每個項目的一般形式12k12k12k12k稱為它的向前搜索符串(或展望串)。12k12k12k12k12k12k按上述算法構(gòu)造的分析表，若不存在多重定義的入口(即，動作沖突)的情形，則稱它使用這種分析表的分析器叫做一個規(guī)范的LR分析器。具有規(guī)范的LR(1)分析表的文法稱為一個LR(1)文法。第六章屬性文法和語法制導(dǎo)翻譯6.1屬性文法 屬性文法(也稱屬性翻譯文法) 在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號(終結(jié)符或非終結(jié)符)配備若干相關(guān)的“值”(稱為屬性)。屬性代表與文法符號相關(guān)信息，如類型、值、代碼序列、符號表內(nèi)屬性可以進行計算和傳遞語義規(guī)則：對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則屬性 綜合屬性：“自下而上”傳遞信息 繼承屬性：“自上而下”傳遞信息綜合屬性在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。使用自底向上的方法在每一個結(jié)點處使用語義規(guī)則計算綜合屬性的值 僅僅使用綜合屬性的屬性文法稱S－屬性文法 繼承屬性在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性確定用繼承屬性來表示程序設(shè)計語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便6.2.3一遍掃描的處理方法一遍掃描的處理方法是在語法分析的同時計算屬性值所采用的語法分析方法屬性的計算次序14/18L－屬性文法適合于一遍掃描的自上而下分析S－屬性文法適合于一遍掃描的自下而上分析6.4L-屬性文法和自頂向下翻譯通過深度優(yōu)先的方法對語法樹進行遍歷，計算屬性文法的所有屬性值LL(1)：自上而下分析方法，深度優(yōu)先建立語法樹第七章語義分析和中間代碼產(chǎn)生靜態(tài)語義檢查類型檢查控制流檢查一致性檢查相關(guān)名字檢查名字的作用域分析7.1中間語言常用的中間語言：后綴式，逆波蘭表示三地址代碼三元式四元式間接三元式逆波蘭表示法不用括號。只要知道每個算符的目數(shù)，對于后綴式，不論從哪一端進行掃描，都能對它進行唯一分解。后綴式的計算用一個棧實現(xiàn)。一般的計算過程是：自左至右掃描后綴式，每碰到運算量就把它推進棧。7.4布爾表達式的翻譯布爾表達式的兩個基本作用:用于邏輯演算,計算邏輯值;用于控制語句的條件式.15/18產(chǎn)生布爾表達式的文法:E→EorE|EandE|E|(E)|iropi|i第十章優(yōu)化優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能生成更有效的目標等價：指不改變程序的運行結(jié)果。有效：指目標代碼運行時間短，占用的存儲空