基本知識編譯程序：就是指這樣一種程序，通過它能夠?qū)⒂酶呒壵Z言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價的低級語言形式的目標程序解釋程序與編譯程序的主要區(qū)別是： *編譯程序?qū)⒃闯绦蚍g成目標程序后再執(zhí)行目標程序 *解釋程序則是逐條讀出源程序中的語句并解釋執(zhí)行，即在解釋程序的執(zhí)行過程中并不產(chǎn)生目標程序。形式化方法是用一整套帶有嚴格規(guī)定的符號體系來描述問題的方法。 文法是程序語言的生成系統(tǒng)自動機是程序語言的識別系統(tǒng)推導的每一步都是對當前句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進行替換，這樣的推導稱為最右推導（規(guī)范推導）最右推導的逆過程稱為最左歸約（規(guī)范歸約)。符號串集合的正閉包：設(shè)A是符號串的集合，則稱A+為符號串集A的正閉包。具體定義如下： A+A1A2A3符號串集合的(星)閉包：設(shè)A是符號串的集合，則稱A*為符號串集A的星閉包。具體定義如下： A*A0A1A2A3 二義性文法：文法GS的一個句子如果存在兩棵不同的語法樹，或者能找到兩種不同的最左推導(或最右推導)，則稱這個文法是二義性的。先天二義性文法：對于一個二義性文法GS，如果能找到一個非二義性文法GS，使得L(G)=L(G)，則該二義性文法的二義性是可以消除的。如果找不到這樣的GS，則二義性文法描述的語言為先天二義性的。推導的每一步都是對當前句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進行替換，這樣的推導稱為最右推導（規(guī)范推導）最右推導的逆過程稱為最左歸約（規(guī)范歸約)。符號串長度:ab2，0。 四元式，逆波蘭 ，劃分基本塊，作流圖一個句型的最左直接短語稱為該句型的句柄。語法樹的某個結(jié)點連同它的所有后代組成了一棵子樹。2型文法： 文法G的每一個產(chǎn)生式具有下列形式： A 其中，AVN，V*，則稱文法G為2型文法或上下文無關(guān)文法。3型文法： 文法G的每個產(chǎn)生式具有下列形式： A或AB 其中，A、BVN，VT*，則文法G稱為3型文法、正規(guī)文法或右線性文法在編譯方法中：通常用3型文法（正規(guī)文法）來描述高級程序語言的詞法部分，然后用有限自動機FA來識別高級語言的單詞。 利用2型文法（上下文無關(guān)文法）來描述高級語言的語法部分，然后用下推自動機PDA來識別高級語言的各種語法成分編譯程序的結(jié)構(gòu)一般來說，整個編譯過程可以劃分成五個階段，這五個階段的任務(wù)是：1詞法分析 任務(wù)：將源程序的字符串變換成單詞符號流2語法分析 任務(wù)：是在詞法分析的基礎(chǔ)上，把單詞符號流分解成各類語法單位（語法范疇），通過語法分析可以確定整個輸入串是否構(gòu)成一個語法上正確的“程序”。 遵循的是語言的語法規(guī)則（文法規(guī)則） ，用上下文無關(guān)文法描述。3語義分析和中間代碼生成 任務(wù):是對各類不同語法范疇按語言的語義進行初步翻譯，4代碼優(yōu)化 任務(wù)：是對前階段產(chǎn)生的中間代碼進行等價變換或改造，以獲得更高效（節(jié)省時間和空間）的目標代碼。5目標代碼生成 任務(wù)：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機器上的機器語言程序或匯編語言程序，實現(xiàn)最終的翻譯工作。 此階段工作十分依賴硬件系統(tǒng)常用的生成編譯程序的方法： 1自編譯：用某種高級語言書寫自己的編譯程序稱為自編譯。2交叉編譯：是指用A機器上的編譯程序來產(chǎn)生可在B機器上運行的目標代碼。3自展：首先確定一個非常簡單的核心語言L0，然后用機器語言或匯編語言書寫出它的編譯程序T0；再把語言L0擴充到L1，并用L0編寫L1的編譯程序T1（即自編譯）； 然后再把語言L1擴充為L2，并用L1編寫L2的編譯程序T2； 這樣不斷擴展下去，直到完成所要求的編譯程序為止。 4移植：是指A機器上的某種高級語言的編譯程序稍加改動后在B機器上運行。LL(1)分析法和遞歸下降分析法屬于自上而下語法分析方法，LR分析法是一種自下而上進行規(guī)范歸約的語法分析方法語義檢查內(nèi)容 動態(tài)語義檢查：運行時進行 靜態(tài)語義檢查：編譯時完成，例如以下幾方面的檢查。 (1) 類型檢查，如參與運算的操作數(shù)其類型應(yīng)相容。 (2) 控制流檢查，用以保證控制語句有合法的轉(zhuǎn)向點。 (3) 使用性標識符是否被聲明。 (4) 一致性檢查，如在相同作用域中標識符只能說明一次、 case語句的標號不能相同等。符號表中的每一項包括兩個部分： 一部分填入名字(標識符)； 另一部分是與此名字有關(guān)的信息請寫出7種常用的優(yōu)化措施,并指出哪幾種主要用于循環(huán)優(yōu)化1刪除公共子表達式 公共子表達式：計算結(jié)果相同的子表達式。 2復寫傳播 ：盡量不引用值不變只傳遞信息的變量3刪除無用賦值4代碼外提(循環(huán)優(yōu)化)：把循環(huán)中的不變運算提到循環(huán)體前5強度削弱(循環(huán)優(yōu)化)：執(zhí)行時間長的運算替換為執(zhí)行時間短的6刪除歸納變量 (循環(huán)優(yōu)化) ：變換循環(huán)控制條件7、合并已知量在各個基本塊范圍內(nèi)進行的優(yōu)化稱為局部優(yōu)化。 對于編譯程序所用的符號表來說，它所涉及的基本操作大致可以歸納為五類：(1) 判斷一個給定的名字是否在表中；(2) 在表中填入新的名字；(3) 對給定的名字訪問它在表中的有關(guān)信息；(4) 對給定的名字填入或更新它在表中的某些信息；(5) 從表中刪去一個或一組無用的項。符號表的組織方式一般可分為直接方式和間接方式。直接方式是指在符號表中直接填入源程序中定義的標識符及相關(guān)信息間接方式是指單獨設(shè)置一個字符串數(shù)組來存放所有的標識符，并在符號表的名字欄中設(shè)置兩項內(nèi)容：一是指針，用來指向標識符在數(shù)組中的起始位置；二是一整數(shù)值，用來表示該標識符的長度。運行時管理分靜態(tài)存儲管理和動