編譯原理考試知識(shí)點(diǎn)復(fù)習(xí)

編譯原理考試知識(shí)點(diǎn)復(fù)習(xí)編譯原理考試知識(shí)點(diǎn)復(fù)習(xí)編譯原理考試知識(shí)點(diǎn)復(fù)習(xí)xxx公司編譯原理考試知識(shí)點(diǎn)復(fù)習(xí)文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度第一章：編譯過(guò)程的六個(gè)階段：詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成解釋程序：把某種語(yǔ)言的源程序轉(zhuǎn)換成等價(jià)的另一種語(yǔ)言程序——目標(biāo)語(yǔ)言程序，然后再執(zhí)行目標(biāo)程序。解釋方式是接受某高級(jí)語(yǔ)言的一個(gè)語(yǔ)句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。編譯程序：就是指這樣一種程序，通過(guò)它能夠?qū)⒂酶呒?jí)語(yǔ)言編寫(xiě)的源程序轉(zhuǎn)換成與之在邏輯上等價(jià)的低級(jí)語(yǔ)言形式的目標(biāo)程序(機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序)。解釋程序和編譯程序的根本區(qū)別：是否生成目標(biāo)代碼第三章：Chomsky對(duì)文法中的規(guī)則施加不同限制，將文法和語(yǔ)言分為四大類(lèi)：0型文法（PSG）0型語(yǔ)言或短語(yǔ)結(jié)構(gòu)語(yǔ)言文法Ｇ的每個(gè)產(chǎn)生式α→β中：若α∈Ｖ*ＶNＶ*,β∈(ＶN∪ＶT)*，則Ｇ是0型文法，即短語(yǔ)結(jié)構(gòu)文法。1型文法（CSG）1型語(yǔ)言或上下文有關(guān)語(yǔ)言在0型文法的基礎(chǔ)上：若產(chǎn)生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外，則Ｇ是１型文法,即：上下文有關(guān)文法另一種定義：文法G的每一個(gè)產(chǎn)生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+；2型文法（CFG）2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言文法Ｇ的每個(gè)產(chǎn)生式A→α，若A∈ＶN,α∈(ＶN∪ＶT)*，則Ｇ是２型法，即：上下文無(wú)關(guān)文法。22型文法1型文法0型文法3型文法3型文法（RG）3型語(yǔ)言或正則(正規(guī))語(yǔ)言若Ａ、Ｂ∈ＶN，ａ∈ＶT或，右線(xiàn)性文法：若產(chǎn)生式為Ａ→ａＢ或Ａ→ａ左線(xiàn)性文法：若產(chǎn)生式為Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正規(guī)文法）最左（最右）推導(dǎo)在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換規(guī)范推導(dǎo)：即最右推導(dǎo)。規(guī)范句型：由規(guī)范推導(dǎo)所得的句型。句子的二義性（這里的二義性是指語(yǔ)法結(jié)構(gòu)上的。）文法G[S]的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)句子是二義性的。文法的二義性一個(gè)文法如果包含二義性的句子，則這個(gè)文法是二義文法，否則是無(wú)二義文法。短語(yǔ)若S*αAδ且A+β，則稱(chēng)β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。簡(jiǎn)單短語(yǔ)（直接短語(yǔ)）若S*αAδ且Aβ，則稱(chēng)β是句型αβδ相對(duì)于非終結(jié)符A的簡(jiǎn)單短語(yǔ)。句柄一個(gè)句型的最左簡(jiǎn)單短語(yǔ)。（產(chǎn)生式的右部）子樹(shù)與短語(yǔ)的關(guān)系(1)短語(yǔ)：子樹(shù)的末端結(jié)點(diǎn)(即樹(shù)葉)組成的符號(hào)串；(2)直接短語(yǔ)：簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)組成的符號(hào)串；(3)句柄：最左簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)組成的符號(hào)串；左圖所示的關(guān)于句型E+E*i的語(yǔ)法樹(shù)來(lái)說(shuō)：它有3棵子樹(shù)，即3個(gè)短語(yǔ)分別為i、E*i和E+E*i；直接短語(yǔ)、句柄均為i。從語(yǔ)法樹(shù)中可以看出，所有樹(shù)葉的組合就是其相對(duì)應(yīng)的父結(jié)點(diǎn)的短語(yǔ)。句型i+i*i的語(yǔ)法樹(shù)有8棵子樹(shù)，短語(yǔ)和直接短語(yǔ)如下：直接短語(yǔ)：i1，i2，i3短語(yǔ)：i1，i2，i3，i1*i2，i1*i2+i3句柄：i1注意：i2+i3不是短語(yǔ)不是某棵子樹(shù)的結(jié)果第四章：?jiǎn)卧~符號(hào)的輸出形式二元組：（單詞種別，單詞自身的值）單詞符號(hào)的分類(lèi)關(guān)鍵字，標(biāo)識(shí)符，常數(shù)，運(yùn)算符，界符等（這種分類(lèi)不是唯一的）【例4.2】令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有:正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,aa,…任意個(gè)a的串}(ab) {,a,b,aa,ab…所有由a和b組成的串}(ab)(aabb)(ab){*上所有至少含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}DFA定義:一個(gè)確定的有窮自動(dòng)機(jī)Md是一個(gè)五元組：Md=（K,Σ,f,S,Z），其中：(1)K：有窮狀態(tài)集；(2)Σ：有窮輸入字母表；(3)f：轉(zhuǎn)換函數(shù)，K×ΣK的單值映射；即f(ki,a)=kj，其中ki、kj∈K，a∈Σ；(4)S：S∈K，惟一初態(tài)；(5)Z：ZK，是一個(gè)終態(tài)集，也稱(chēng)可接受狀態(tài)或結(jié)束狀態(tài)?！纠緿FAM=({S,U,V,Q}，{a,b}，f，S，{Q})，其中f定義為：f（S，a）=U，f（V，a）=Uf（S，b）=V，f（V，b）=Qf（U，a）=Q，f（Q，a）=Qf（U，b）=V，f（Q，b）=QDFA的表示（1）用轉(zhuǎn)換函數(shù)；（2）狀態(tài)轉(zhuǎn)換矩陣；（3）狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換函數(shù)：DFAM=({0,1,2,3},{a,b},f,0,{3})f:f(0,a)=1f(0,b)=2f(1,a)＝3f(1,b)＝2f(2,a)=1f(2,b)=3f(3,a)＝3f(3,b)＝3轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換圖NFAM的定義:一個(gè)非確定有窮自動(dòng)機(jī)Mn是一個(gè)五元組Mn=(K,Σ,f,S,Z)，其中：(1)K、Σ、Z的意義與DFA相同；(2)f：從K×Σ*K的子集映射；(3)SK，是一個(gè)非空初態(tài)集。與DFA的主要區(qū)別允許有多個(gè)初始狀態(tài)。允許狀態(tài)在其輸出邊上有相同的符號(hào)(多值映射)。允許輸出邊上有空串符號(hào)。特點(diǎn):在給定狀態(tài)和符號(hào)的情況下，不能唯一的確定下一個(gè)狀態(tài)。NFA的確定化基本方法基本方法:邊合并,符號(hào)合并(NFA轉(zhuǎn)化成的DFA不是唯一的)【例】NFAM如右圖所示，試將其確定化為DFAM'?！窘獯稹浚?）用子集法將圖所示的NFAM確定化為表1。（2）對(duì)表1中的所有子集重新命名得到表2的狀態(tài)轉(zhuǎn)換矩陣ε_(tái)closure(S0ε_(tái)closure(S0)確定有窮自動(dòng)機(jī)的化簡(jiǎn)：第五章：語(yǔ)法分析是編譯程序的核心部分：在詞法分析的基礎(chǔ)上，識(shí)別單詞符號(hào)序列是否是給定文法的正確句子（程序）。自上而下分析的前提：消除左遞規(guī)和消除回溯。自頂向下分析法就是從文法的開(kāi)始符號(hào)出發(fā)，試圖推導(dǎo)出與輸入的單詞串完全匹配的句子。如果能夠推導(dǎo)出，則該輸入串是給定文法的句子。如果不能推導(dǎo)出，則該輸入串不是給定文法的句子。自頂向下分析法分兩種不確定性分析法：是帶有回溯的分析方法，效率低，代價(jià)高，極少使用。確定性分析法：對(duì)文法有一定的限制，但實(shí)現(xiàn)簡(jiǎn)單直觀(guān)，便于手工或自動(dòng)構(gòu)造。LL(1)文法的定義一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是：對(duì)每個(gè)非終結(jié)符A的任兩個(gè)不同產(chǎn)生式A，Aβ，滿(mǎn)足：Select(A)∩Select(Aβ)=,其中：、β不同時(shí)推導(dǎo)出注：對(duì)LL(1)文法進(jìn)行語(yǔ)法分析時(shí)不會(huì)產(chǎn)生回溯。LL(1)的含義：(LL(1)文法是無(wú)二義的；LL(1)文法不含左遞歸)第1個(gè)L：從左到右掃描輸入串第2個(gè)L：生成的是最左推導(dǎo)1：向右看1個(gè)輸入符號(hào)便可決定選擇哪個(gè)產(chǎn)生式某些非LL(1)文法到LL(1)文法的等價(jià)變換:1.提取公因子2.消除左遞歸1.提取左公因子形如:A→aβ1｜aβ2｜...｜aβn｜γ提取左公因子：A→a(β1｜β2｜...｜βn)｜γ改寫(xiě)為：A→aA'｜γA'→β1｜β2｜...｜βn2.消除左遞歸（如果一個(gè)文法是左遞歸時(shí)，則不能采用自頂向下分析法。）(1)左遞歸的定義（含有左遞歸的文法絕對(duì)不是LL（1）文法）一個(gè)文法含有下列形式的產(chǎn)生式時(shí)，AAAVN,V*直接左遞歸②A(yíng)BBAA,BVN,，V*間接左遞歸(2)直接左遞歸的消除（改為右遞歸）SbS’S’aS’|εSSaSb形如：SbS’S’aS’|εSSaSb改寫(xiě)為：A→βA￠A￠→aA￠|形如：A→Aa1|Aa2|...|Aan|b1|b2|...|bm其中，每個(gè)a都不等于，b1,...,bm均不以A開(kāi)頭。改寫(xiě)為：A→b1A￠|b2A￠|...|bmA￠A￠→a1A￠|a2A￠|...|anA￠|EE→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜iEE→E+T｜TT→T*F｜FF→(E)｜i預(yù)測(cè)分析法（又稱(chēng)LL(1)分析法，屬于確定的自頂向下分析方法）基本思想：從左到右掃描源程序，直接根據(jù)：(1)當(dāng)前(需推導(dǎo))的語(yǔ)法變量;(2)輸入串的當(dāng)前輸入符號(hào);確定進(jìn)行分析所需的候選式：使其第一個(gè)符號(hào)與當(dāng)前輸入符號(hào)相同，或該候選式可推導(dǎo)出的第一個(gè)符號(hào)與當(dāng)前符號(hào)相同。預(yù)測(cè)分析器構(gòu)成：預(yù)測(cè)分析程序，先進(jìn)后出棧，預(yù)測(cè)分析表——與文法有關(guān)第七章對(duì)輸入串的分析過(guò)程（已知文法的分析表）LR分析法：是一種規(guī)范規(guī)約過(guò)程LR(k)含義L：從左到右掃描輸入符號(hào)R：最右推導(dǎo)對(duì)應(yīng)的最左歸約(反序完成最右推導(dǎo))k：超前讀入k個(gè)符號(hào)，以便確定歸約用的產(chǎn)生式LR(0)項(xiàng)目分類(lèi)移進(jìn)項(xiàng)目，形如A→?a，a是終結(jié)符,,V*以下同【例】S→?bBB待約項(xiàng)目，形如A→?B【例】S→b?BBS→bB?B歸約項(xiàng)目，形如A→?【例】S→bBB?接受項(xiàng)目，形如S’→S?第八章：一個(gè)屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列語(yǔ)義規(guī)則,這些語(yǔ)義規(guī)則附在每個(gè)產(chǎn)生式上。文法符號(hào)的屬性:單詞的含義，即與文法符號(hào)相關(guān)的一些信息。如，類(lèi)型、值、存儲(chǔ)地址等。一個(gè)屬性文法(attributegrammar)是一個(gè)三元組A=(G,V,F)G：上下文無(wú)關(guān)文法。V：屬性的有窮集。每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。F：關(guān)于屬性的斷言或謂詞(一組屬性的計(jì)算規(guī)則)的有窮集。斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)，只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。綜合屬性:若產(chǎn)生式左部的單非終結(jié)符A的屬性值由右部各非終結(jié)符的屬性值決定,則A的屬性稱(chēng)為綜合屬性。繼承屬性:若產(chǎn)生式右部符號(hào)B的屬性值是根據(jù)左部非終結(jié)符的屬性值或者右部其它符號(hào)的屬性值決定的,則B的屬性為繼承屬性。在兩種情況下，都說(shuō)屬性b依賴(lài)于屬性c1,c2,…,ck(1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開(kāi)始符

號(hào)沒(méi)有繼承屬性。(2)終結(jié)符只有綜合屬性，沒(méi)有繼承屬性，它們由詞法程序提供。在計(jì)算時(shí)：綜合屬性沿屬性語(yǔ)法樹(shù)向上傳遞；繼承屬性沿屬性語(yǔ)法樹(shù)向下傳遞。語(yǔ)法制導(dǎo)翻譯：是指在語(yǔ)法分析過(guò)程中，完成附加在所使用的產(chǎn)生式上的語(yǔ)義規(guī)則描述的動(dòng)作。語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要構(gòu)造屬性依賴(lài)圖，遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。中間代碼（中間語(yǔ)言）1、是復(fù)雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言的一種表示形式。/2、一般，快速編譯程序直接生成目標(biāo)代碼。3、為了使編譯程序結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，常采用中間代碼，這樣可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生成階段仔細(xì)處理，并且可以在中間代碼一級(jí)進(jìn)行優(yōu)化工作，使得代碼優(yōu)化比較容易實(shí)現(xiàn)。何謂中間代碼：源程序的一種內(nèi)部表示，不依賴(lài)目標(biāo)機(jī)的結(jié)構(gòu)，易于代碼的機(jī)械生成。為何要轉(zhuǎn)換成中間代碼邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語(yǔ)言。便于移植，便于修改，便于進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化。中間代碼的幾種形式：逆波蘭記號(hào)，三元式和樹(shù)形表示，四元式逆波蘭記號(hào)：把運(yùn)算分量(操作數(shù))寫(xiě)在前面，把運(yùn)算符寫(xiě)在后面的表示法，又稱(chēng)后綴表示法。中綴表達(dá)式向逆波蘭表達(dá)式轉(zhuǎn)換postfix(x)=xpostfix(c)=cpostfix(E1opE2)=postfix(E1)postfix(E2)oppostfix((E))=postfix(E)第九章：符號(hào)表的一般形式：一張符號(hào)表的的組成包括兩項(xiàng)，即名字欄和信息欄。信息欄包含許多子欄和標(biāo)志位，用來(lái)記錄相應(yīng)名字和種種不同屬性，名字欄也稱(chēng)主欄。主欄的內(nèi)容稱(chēng)為關(guān)鍵字（keyword）。符號(hào)表的功能：（1）收集符號(hào)屬性在分析語(yǔ)言程序中標(biāo)識(shí)符說(shuō)明部分時(shí)，編譯程序根據(jù)說(shuō)明信息收集有關(guān)標(biāo)識(shí)符的屬性，并在符號(hào)表中建立符號(hào)的相應(yīng)屬性信息。(2)上下文語(yǔ)義的合法性檢查的依據(jù)：檢查標(biāo)識(shí)符屬性在上下文中的一致性和合法性。(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)符號(hào)的主要屬性及作用：1.符號(hào)名2.符號(hào)的類(lèi)型（整型、實(shí)型、字符串型等））3.符號(hào)的存儲(chǔ)類(lèi)別（公共、私有）4.符號(hào)的作用域及可視性（全局、局部）5.符號(hào)變量的存儲(chǔ)分配信息（靜態(tài)存儲(chǔ)區(qū)、動(dòng)態(tài)存儲(chǔ)區(qū)）6.符號(hào)的其它屬性數(shù)組內(nèi)情向量(類(lèi)型、維數(shù)、各維的上下界、首地址等)記錄結(jié)構(gòu)型的成員信息函數(shù)及過(guò)程的形參第十章：運(yùn)行時(shí)的存儲(chǔ)區(qū)為了使目標(biāo)程序能夠運(yùn)行，編譯程序要從操作系統(tǒng)中得到一塊存儲(chǔ)區(qū)，以使目標(biāo)程序能夠在其上運(yùn)行。運(yùn)行時(shí)的存儲(chǔ)區(qū)劃分目標(biāo)區(qū)：存放目標(biāo)代碼。靜態(tài)數(shù)據(jù)區(qū)：編譯時(shí)能確定所占用空間的數(shù)據(jù)。棧區(qū)和堆區(qū)：可變數(shù)據(jù)及管理過(guò)程活動(dòng)的控制信息。存儲(chǔ)分配方案策略：靜態(tài)存儲(chǔ)分配；動(dòng)態(tài)存儲(chǔ)分配：棧式、堆式。靜態(tài)存儲(chǔ)分配1、基本策略在編譯時(shí)就安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。2、適用的分配對(duì)象：子程序的目標(biāo)代碼段；全局?jǐn)?shù)據(jù)目標(biāo)（全局變量）3、靜態(tài)存儲(chǔ)分配的要求：不允許遞歸調(diào)用，不含有可變數(shù)組。FORTRAN程序是段結(jié)構(gòu)，不允許遞歸，數(shù)據(jù)名大小、性質(zhì)固定。是典型的靜態(tài)分配動(dòng)態(tài)存儲(chǔ)分配1、如果一個(gè)程序設(shè)計(jì)語(yǔ)言允許遞歸過(guò)程、可變數(shù)組或允許用戶(hù)自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。2、兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式，堆式棧式動(dòng)態(tài)存儲(chǔ)分配分配策略：將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧?！纠吭诰哂羞f歸結(jié)構(gòu)的語(yǔ)言程序中，每當(dāng)調(diào)用一個(gè)過(guò)程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過(guò)程工作結(jié)束時(shí)就釋放這部分空間。過(guò)程所需的數(shù)據(jù)空間包括兩部分一部分是生存期在本過(guò)程這次活動(dòng)中的數(shù)據(jù)對(duì)象。如局部變量、參數(shù)單元、臨時(shí)變量等；另一部分則是用以管理過(guò)程活動(dòng)的記錄信息(連接數(shù)據(jù))?；顒?dòng)記錄（AR）一個(gè)過(guò)程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來(lái)管理，這個(gè)區(qū)(塊)叫做一個(gè)活動(dòng)記錄。構(gòu)成1、臨時(shí)工作單元；2、局部變量；3、機(jī)器狀態(tài)信息；4、存取鏈；5、控制鏈；6、實(shí)參；7、返回地址第十一章：什么是代碼優(yōu)化所謂優(yōu)化，就是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少。優(yōu)化原則：等價(jià)原則：經(jīng)過(guò)優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小。合算原則：以盡可能低的代價(jià)取得較好的優(yōu)化效果。常見(jiàn)的優(yōu)化技術(shù)(1)刪除多余運(yùn)算(刪除公共子表達(dá)式)(2)代碼外提:是針對(duì)循環(huán)的(3)強(qiáng)度削弱;把執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算(4)變換循環(huán)控制條件(5)合并已知量與復(fù)寫(xiě)傳播(6)刪除無(wú)用賦值基本塊定義程序中只有一個(gè)入口和一個(gè)出口的一段順序執(zhí)行的語(yǔ)句序列，稱(chēng)為程序的一個(gè)基本塊。對(duì)四元式序列，各個(gè)基本塊的入口語(yǔ)句是：(1)代碼序列的第一個(gè)語(yǔ)句。(2)轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句。(3)轉(zhuǎn)移語(yǔ)句