四川大學(xué)編譯原理期末復(fù)習(xí)總結(jié).doc

編譯原理復(fù)習(xí)資料一、簡答題1.什么是編譯程序？答：編譯程序是一種將高級(jí)語言程序(源程序)翻譯成低級(jí)語言(目標(biāo)程序)的程序 。將高級(jí)程序設(shè)計(jì)語言程序翻譯成邏輯上等價(jià)的低級(jí)語言(匯編語言,機(jī)器語言)程序的翻譯程序。2.請寫出文法的形式定義？答：一個(gè)文法G抽象地表示為四元組G=（Vn,Vt,P,S） 其中Vn表示非終結(jié)符號(hào) Vt表示終結(jié)符號(hào)，VnVt=(字母表)，VnVt= S是開始符號(hào)， P是產(chǎn)生式，形如：(V+且至少含有一個(gè)非終結(jié)符號(hào)，V*) 3.語法分析階段的功能是什么？答：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號(hào)串分解成各類語法短語(例：程序、語句、表達(dá)式)。確定整個(gè)輸入串是否構(gòu)成語法上正確的程序。4.局部優(yōu)化有哪些常用的技術(shù)？答：優(yōu)化技術(shù)1刪除公共子表達(dá)式優(yōu)化技術(shù)2復(fù)寫傳播優(yōu)化技術(shù)3刪除無用代碼優(yōu)化技術(shù)4對(duì)程序進(jìn)行代數(shù)恒等變換（降低運(yùn)算強(qiáng)度）優(yōu)化技術(shù)5代碼外提優(yōu)化技術(shù)6強(qiáng)度削弱優(yōu)化技術(shù)7刪除歸納變量優(yōu)化技術(shù)簡介對(duì)程序進(jìn)行代數(shù)恒等變換（代數(shù)簡化）優(yōu)化技術(shù)簡介對(duì)程序進(jìn)行代數(shù)恒等變換（合并已知量）5編譯過程分哪幾個(gè)階段？答：邏輯上分五個(gè)階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。每個(gè)階段把源程序從一種表示變換成另一種表示。6. 什么是文法？答：文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。是一種工具，它可用于嚴(yán)格定義句子的結(jié)構(gòu)；用有窮的規(guī)則刻劃無窮的集合；文法是被用來精確而無歧義地描述語言的句子的構(gòu)成方式；文法描述語言的時(shí)候不考慮語言的含義。7. 語義分析階段的功能是什么？答：對(duì)語法分析所識(shí)別出的各類語法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)；并對(duì)靜態(tài)語義進(jìn)行審查。8.代碼優(yōu)化須遵循哪些原則？答：等價(jià)原則：不改變運(yùn)行結(jié)果有效原則：優(yōu)化后時(shí)間更短，占用空間更少合算原則：應(yīng)用較低的代價(jià)取得較好的優(yōu)化效果9.詞法分析階段的功能是什么？答：逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞任務(wù)： 讀入源程序，輸出單詞符號(hào) 濾掉空格，跳過注釋、換行符 追蹤換行標(biāo)志，指出源程序出錯(cuò)的行列位置 宏展開，10.什么是符號(hào)表？ 答：符號(hào)表在編譯程序工作的過程中需要不斷收集、記錄和使用源程序中一些語法符號(hào)的類型和特征等相關(guān)信息。這些信息一般以表格形式存儲(chǔ)于系統(tǒng)中。如常數(shù)表、變量名表、數(shù)組名表、過程名表、標(biāo)號(hào)表等等，統(tǒng)稱為符號(hào)表。對(duì)于符號(hào)表組織、構(gòu)造和管理方法的好壞會(huì)直接影響編譯系統(tǒng)的運(yùn)行效率。11.什么是屬性文法？答：是在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(含終結(jié)符和非終結(jié)符)配備若干個(gè)屬性值，對(duì)文法的每個(gè)產(chǎn)生式都配備了一組屬性計(jì)算規(guī)則(稱為語義規(guī)則)。在語法分析過程中，完成語義規(guī)則所描述的動(dòng)作，從而實(shí)現(xiàn)語義處理。12.什么是基本塊?答：是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口語句和一個(gè)出口語句，入口是其第一個(gè)語句，出口是其最后一個(gè)語句。13.代碼優(yōu)化階段的功能是什么？答：對(duì)已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為高效(時(shí)間和空間)。14.文法分哪幾類？答：文法有四種:設(shè)有G=(Vn,Vt,P,S),不同類型的文法只是對(duì)產(chǎn)生式的要求不同： 型文法(短文文法)： G的每個(gè)產(chǎn)生式滿足：V+且中至少含有一個(gè)非終結(jié)符,V*型文法(上下文有關(guān)文法)：如果G的每個(gè)產(chǎn)生式 均滿足|=|,僅當(dāng)除外，但S不得出現(xiàn)在任何產(chǎn)生式的右部型文法(上下文無關(guān)文法)：G的每個(gè)產(chǎn)生式為A, A是一非終結(jié)符，V*型文法(正規(guī)文法)：G的每個(gè)產(chǎn)生式的形式都是：AB或A，其中A,B是非終結(jié)符，是終結(jié)符串。(右線性文法)。15.循環(huán)優(yōu)化常用的技術(shù)有哪些？答：代碼外提；強(qiáng)度削弱；刪除歸納變量。16.什么是算符優(yōu)先文法？答：算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有中的一種成立,則G為一算符優(yōu)先文法。二、計(jì)算題（一）推導(dǎo)、最左推導(dǎo)、最右推導(dǎo)和語法樹,復(fù)習(xí)表達(dá)式文法及相關(guān)例題。1. 表達(dá)式的推導(dǎo)例： G = (E, i, +, *, (, ) , P , E) P： E E+E | E*E | (E) | i 答：表達(dá)式(i)和(i+i)*i的推導(dǎo)：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*iE E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i(i+i)*i的最左推導(dǎo)過程： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i(i+i)*i的最右推導(dǎo)過程： E E*E E*i (E + E)*i (E+ i)*i (i + i)*i2語法樹例：對(duì)文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i答： 句子(i+i)*i 的語法樹：例： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i答：句子 ( i * i + i)的語法樹：(1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i) （二）給定語言求文法（三）逆波蘭式（四）將for語句和if語句翻譯成相應(yīng)的四元式序列 1.if2.for(五) 短語、素短語、最左素短語，F(xiàn)irstVT集和LastVT集的求解方法 (復(fù)習(xí)第四章 算符優(yōu)先文法相關(guān)內(nèi)容)1. 短語、素短語、最左素短語 2.FirstVT集和LastVT集的求解方法例：設(shè)文法為： E #E#；TF；EE+T；FPF | P； ET ；P(E)；TT*F；Pi；3. 算符優(yōu)先文法優(yōu)先關(guān)系的定義:算符優(yōu)先文法的定義:三、綜合題1.NFA的確定化和最小化(參看課件第三章62頁：例5)2.自頂向下分析(參看課件第四章（1）67頁：綜合練習(xí))例：求對(duì)應(yīng)于下述文法的預(yù)測分析表: E TEE +TE |T FTT *FT |F (E) |i 答：1） 首先求first集:2） 由于First(E), First(T), 求E和T的Follow集:3） 根據(jù)集合的值填表，得到:例:設(shè)文法G(S)：S(L) | aS | aLL，S | S(1) 消除左遞歸和回溯；(2) 計(jì)算每個(gè)非終結(jié)符的First和Follow集；(3) 構(gòu)造預(yù)測分析表。答：(1) 消除左遞歸和回溯：(2)(3)構(gòu)造預(yù)測分析表：3.LR分析方法(參看課件第四章（3）28頁及30頁)(附)1.短語、直接短語、句柄例：考慮如下文法： E =T | E+T T =F | T*F F =i | (E)求句型 i1 * i2 + i3的短語、直接短語和句柄答：E = F * i2 + i3 E = i1 * F + i3 E = i1 * i2 + F E = T + i3（T =T*F =i1 * i2） F=iE = i1 * i2 + i3 因此： 短語有：i1, i2, i3, i1*i2, i1*i2+i3直接短語有：i1, i2 , i3 句柄是： i1i2 + i3 不是短語，因?yàn)镋 = i1 * E （E =i2 +i3）2. 什么是語法制導(dǎo)翻譯語法制導(dǎo)翻譯：定義翻譯所必須的語義屬性和語義規(guī)則，一般不涉及計(jì)算順序。語法制導(dǎo)翻譯(Syntax-Directed Translations)： 一個(gè)句子的語義翻譯過程與語法分析過程同時(shí)進(jìn)行。在文法中，文法符號(hào)有明確的意義，文法符號(hào)之間有確定的語義關(guān)系。屬性描述語義信息，語義規(guī)則描述屬性間的的關(guān)系，將語義規(guī)則與語法規(guī)則相結(jié)合，在語法分析的過程中計(jì)算語義屬性值。翻譯程序:把一種語言程序轉(zhuǎn)換成另一種語言程序，且在功能上是相同的這樣的程序。編譯程序：把高級(jí)語言轉(zhuǎn)換成低級(jí)語言，且在功能上是相同的這樣的程序。解釋程序：邊解釋邊執(zhí)行源程序的程序。區(qū)別：編譯程序有中間代碼，而解釋程序沒有。編譯過程的五個(gè)階段：1、詞法分析任務(wù)：對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞。2、語法分析任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言規(guī)則，把單詞符號(hào)串分解成各類語法單位。3、語義分析和中間代碼產(chǎn)生任務(wù)：對(duì)語法分析所識(shí)別出的各類語法范疇，分析其含義并進(jìn)行初步翻譯。4、優(yōu)化任務(wù)：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效的目標(biāo)代碼。5、目標(biāo)代碼生成任務(wù)：把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼。編譯程序的七個(gè)部分詞法分析器，語法分析器、語義分析與中間代碼產(chǎn)生器、優(yōu)化器、目標(biāo)代碼生成器、表格管理和出錯(cuò)處理。編譯程序生成的五個(gè)辦法：機(jī)器語言、高級(jí)語言、移植、自編譯方式和使用工具自動(dòng)生成。詞法規(guī)則：指單詞符號(hào)的形成規(guī)則。（也就是正規(guī)式）語法規(guī)則：規(guī)定了如何從單詞符號(hào)形成更大的結(jié)構(gòu)。就是語法單位的形成規(guī)則?？兆郑翰话魏畏?hào)的序列。閉包：中所有的符號(hào)組成的集合。上下文無關(guān)文法是指：所定義的語法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的文法。上下文無關(guān)文法的四個(gè)組成部分：一組終結(jié)符號(hào)、一組非終結(jié)符號(hào)、一個(gè)開始符號(hào)和一組產(chǎn)生式。終結(jié)符號(hào)也就是不可再分的基本符號(hào)。非終結(jié)符號(hào)是用來代表語法范疇，表示一定符號(hào)串的集合。開始符號(hào)是語言中我們最感興趣的語法范疇。產(chǎn)生式是定義語法范疇的書寫規(guī)則。句子：文法中從開始符號(hào)推導(dǎo)的終結(jié)符號(hào)串。句型：從開始符號(hào)推導(dǎo)的符號(hào)串語言：文法中所有句子的集合。程序語言的單詞符號(hào)分為五種：關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符和界符。二元式表示：（種類，屬性）正規(guī)式的運(yùn)算符有三種：或，連接和閉包。優(yōu)先順序是：閉包，連接，或。DFA怎么識(shí)別字：若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字是a，則稱a可為DFA所識(shí)別。DFA怎么識(shí)別空字：若DFA的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字可為DFA所識(shí)別。NFA怎么識(shí)別字：若存在一條從某一初態(tài)結(jié)點(diǎn)到終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字等于a，則稱a可為NFA識(shí)別。NFA怎么識(shí)別空字：若M的某些結(jié)點(diǎn)即是初態(tài)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的空通路，那么，空字可為M所識(shí)別。語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。語法分析分為兩類：自上而下分析法，自下而上分析法。自上而下分析法面臨的問題：1.文法的左遞歸問題。2.回溯3.成功可能是暫時(shí)的，產(chǎn)生虛假匹配。4.難于知道輸入串中出錯(cuò)的確切位置。5.效率低，代價(jià)高為什么消除左遞歸？因?yàn)楹凶筮f歸的文法將自上而下分析的過程陷入無限循環(huán)。為什么消除回溯？因?yàn)榛厮萁y(tǒng)一做一大