編譯原理文字總結(jié)

1、編譯原理文字總結(jié) 編譯原理文字總結(jié) 1.高級(jí)程序制定語言的翻譯主要有兩種方式：編譯和解釋。2.編譯過程概述： (1)詞法分析：輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的 單詞亦稱單詞符號(hào)或符號(hào)如基本字，標(biāo)識(shí)符，常數(shù)，算符和界符。 (2)語法分析：在詞法分析的基礎(chǔ)上，依據(jù)語言的語法規(guī)則，把單詞符號(hào)串分解成各類 語法單位語法范疇，如短語，子句，句子，程序段和程序等 (3)語義分析與中間代碼產(chǎn)生：對(duì)語法分析所識(shí)別出的各類語法范疇，分析其含義，并 進(jìn)行初步翻譯產(chǎn)生中間代碼。包括靜態(tài)語義檢查和中間代碼的翻譯。(4)優(yōu)化：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變幻，以期在最后階段能產(chǎn)生出更為高效

2、省 時(shí)間和空間的目標(biāo)代碼。 (5)目標(biāo)代碼生成：把中間代碼或經(jīng)優(yōu)化處理之后變幻成特定機(jī)器上的低級(jí)語言代 碼。 編譯程序結(jié)構(gòu)框圖 3文法是表述語言的語法結(jié)構(gòu)的形式規(guī)則。 4.所謂上下文無關(guān)文法是這樣一種文法，它所定義的語法范疇或語法單位是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。一個(gè)上下文無關(guān)文法g包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組產(chǎn)生式。 5.形式上說，一個(gè)上下文無關(guān)文法g是一個(gè)四元式vt,vn,s,其中vt是一個(gè)非空有 限集，它的每個(gè)元素稱為終結(jié)符號(hào)；vn是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，vtvn=；s是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)；&是一個(gè)

3、產(chǎn)生式集合，每個(gè)產(chǎn)生式的形式是pa，其中p屬于vn，a屬于vtvn*。開始符號(hào)s至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 6.推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則產(chǎn)生式。7.假定g是一個(gè)文法，s是它的開始符號(hào)。如果sa，則稱a是一個(gè)句型0步或假設(shè)干步。 僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法g所產(chǎn)生的句子的全體是一個(gè)語言，將它記為l(g)。l(g)=a|sa&avt*例如終結(jié)符號(hào)串i*i+i是文法2.1的一個(gè)句子。8.從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程往往不是唯一的。所謂最左推導(dǎo)是指任何一步ab都是對(duì)a中最左非終結(jié)符進(jìn)行替換的。同樣可定義最右推導(dǎo)。9.一顆語法樹表示了一個(gè)句型種種可能的但未必是所有的不

4、同推導(dǎo)過程，包括最左最 右推導(dǎo)。這樣的一顆語法樹是這些不同推導(dǎo)過程的共性抽象，是它們的代表。一個(gè)句型不一定只對(duì)應(yīng)唯一的一棵語法樹，也就是不一定只有唯一的一個(gè)最左最右推導(dǎo)。 + 10.某文法如果存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹證實(shí)一個(gè)文法是二義的，則說這個(gè) 文法是二義性文法?；蛘哒f，假設(shè)一個(gè)文法中存在某個(gè)句子，有兩個(gè)不同的最左推導(dǎo)或最右推導(dǎo)，則該文法是二義的。 11.文法的二義性和語言的二義性是兩個(gè)不同的概念。 12.二義性問題是不可判定的，即不存在一個(gè)算法，它能在有限步驟內(nèi)，確切的判定一個(gè)文 法是否為二義的。 13.形式語言俯視：文法分為4種：0型，1型，2性和3型 10型文法也稱短語文法，0

5、型文法的能力相當(dāng)于圖靈機(jī)，任何0型語言就是遞歸可枚舉的 21型文法也成為上下文有關(guān)文法。對(duì)非終結(jié)符進(jìn)行替換的時(shí)務(wù)必合計(jì)上下文，并且一般不同意替換成空串e 32型文法也稱上下文無關(guān)文法，非終結(jié)符的替換可以不必合計(jì)上下文。 43型文法也稱正規(guī)文法，包括右線性文法非終結(jié)符在右邊和左線性文法。14一個(gè)確定有限自動(dòng)機(jī)dfam是一個(gè)五元式，m=(s,s0,f)， s：有限狀態(tài)集，它的每個(gè)元素稱為一個(gè)狀態(tài)。 ：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符。 ：狀態(tài)轉(zhuǎn)換函數(shù)，ss是單值全映射函數(shù)；s0：唯一的初態(tài)，s0sf：終態(tài)集可空，fs 15.一個(gè)dfa可以用一個(gè)矩陣表示，行表示狀態(tài)，列表示輸入字符，矩陣元素

6、表示s,a 的值。這個(gè)矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。 16.一個(gè)dfa也可表示成一張確定的狀態(tài)轉(zhuǎn)換圖。關(guān)于*中的任何字a，假設(shè)存在一條從 初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于a，則稱a可為dfam所識(shí)別讀出或接受。假設(shè)m的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字e可為m所識(shí)別。dfam所能識(shí)別的字的全體記為l(m)。17.一個(gè)非確定有限自動(dòng)機(jī)nfam是一個(gè)五元式，m=(s,s0,f)， s：有限狀態(tài)集，它的每個(gè)元素稱為一個(gè)狀態(tài)。 ：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符。：一個(gè)從s到s的子集的映照，ss0：非空初態(tài)集，s0sf：終態(tài)集可空，fs 18.有限自動(dòng)機(jī)中假設(shè)有e則

7、為nfa。狀態(tài)圖中假設(shè)某一狀態(tài)輸入某字符轉(zhuǎn)換至多個(gè)狀態(tài) 則為nfa。dfa是nfa的特例。關(guān)于每個(gè)nfam存在一個(gè)dfam，使lm=l(m)。nfa確定化為dfa的方法：子集法p49-50必定在有限步內(nèi)完成19.所謂自上而下語法分析，是從文法的開始符號(hào)出發(fā)，反復(fù)使用各產(chǎn)生式，尋找“匹配 于輸入符號(hào)串的推導(dǎo)。從語法樹的角度來看，自上而下方法是從文法符號(hào)開始，將它作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。這種方法是帶回溯的，是一個(gè)推導(dǎo)+匹配的過程。面臨的問題： 1.文法的左遞歸問題2.回溯 3.匹配成功可能是暫時(shí)的(虛假匹配)4.當(dāng)匹配不成功時(shí)不知道出錯(cuò)位置5.

8、效率太低,代價(jià)極高20.直接左遞歸的消除：將p->pa|b改寫為p->bpp->ap|e 21.如果文法g不含以e為右部的產(chǎn)生式并且不存在p=+>p，下述算法消除左遞歸 1對(duì)文法g中所有狀態(tài)進(jìn)行排序，任意順序均可，得p1p2p3.pn2)fori=1tonbegin forj=1toi-1beginif存在pi->pjy 將之改寫為pi->a1y|a2y|a3y.pmy/其中，pj->a1|a2.|am是關(guān)于pj的所有規(guī)則endend采納算法一消除ai產(chǎn)生式的左遞歸end 22.為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠依

9、據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。不能是虛假匹配要求是非終結(jié)符a的所有候選首符集兩兩不相交，即a的任何兩個(gè)不同候選ai和ajfirst(ai)first(aj)=空。 23.為達(dá)到上述目的，辦法是提取公共左因子：假定關(guān)于a的規(guī)則是a->b1|b2|bn|r1|r2|r3|rm其中每個(gè)r不以開頭，那么將之改寫成a->a|r1|r2|r3|rma->b1|b2|b3|bn。 24.ll(1)文法：第一個(gè)l表示從左導(dǎo)游掃描輸入串,第二個(gè)l表示最左推導(dǎo),1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)文法滿足以下條件 1文法不含左遞歸 2

10、關(guān)于文法中每一個(gè)非終結(jié)符a的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即假設(shè)a->a1|a2|an則first(ai)first(aj)=空i!=j 3對(duì)文法中的每個(gè)非終結(jié)符a，假設(shè)它存在某個(gè)候選首符集包括e，則first(a)followa=空25.實(shí)現(xiàn)ll1的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制：猜測(cè)分析程序。26.對(duì)每個(gè)文法符號(hào)xvtvn，構(gòu)造first(x)的方法：1假設(shè)xvt，則firstx=x。2假設(shè)xvn，且有產(chǎn)生式x->a，則把a(bǔ)加入到firstx中，假設(shè)x->e也是一條產(chǎn)生式，則把e也加到firstx中。3假設(shè)x->y是一個(gè)產(chǎn)生式，且yvn，則把f

11、irsty中的所有非e-元素都加入到firstx中；假設(shè)x->y1y2yk是一個(gè)產(chǎn)生式，y1，yi-1都是非終結(jié)符，而且firstyj1ab是一個(gè)產(chǎn)生式，或a->abb是一個(gè)產(chǎn)生式且b=>e,則把followa加至followb中。 28.構(gòu)造猜測(cè)分析表m的算法是：以文法g的終結(jié)符為表頭，以產(chǎn)生式左部為列頭1對(duì)文法g的每個(gè)產(chǎn)生式a->e執(zhí)行第二步和第三步2對(duì)每個(gè)終結(jié)符afirst(e),把a(bǔ)->e加至ma,a中；3假設(shè)efirste，則對(duì)任何bfollowa把a(bǔ)->e加至ma,b中4把所有無定義的ma,a標(biāo)上“出錯(cuò)標(biāo)志。29.我們所討論的自下而上分析法是一種

12、移進(jìn)-歸法法。這種方法的大意是用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)候選式時(shí)，即把棧頂?shù)倪@一部分替換成歸約為該產(chǎn)生式的左部符號(hào)。 30.在算符優(yōu)先分析中，規(guī)范對(duì)象可歸約串：最左素短語，在“規(guī)范歸約分析中，規(guī)范對(duì)象可歸約串：句柄最左直接短語。 31短語，直接短語，一個(gè)句型的最左直接短語稱為該句型的句柄。32.最右推導(dǎo)通常成為規(guī)范推導(dǎo),由規(guī)范推導(dǎo)所得的句型成為規(guī)范句型如果文法g是無二義的,則規(guī)范推導(dǎo)(最右推導(dǎo))的逆過程必須是規(guī)范規(guī)約。 規(guī)范歸約步驟表：表頭：1.步驟標(biāo)號(hào)，從0開始2.符號(hào)棧步驟0時(shí)為#3.輸入串步驟0時(shí)為輸入串+#4.動(dòng)作步驟0時(shí)為預(yù)

13、備，分為進(jìn)和歸，歸包括所用產(chǎn)生式 最后一行4列值分別為步驟號(hào)#和文法開始符號(hào)#接受33.算符優(yōu)先分析法1.不是一種規(guī)范規(guī)約法2.算符優(yōu)先就是尋早可能相繼出現(xiàn)的終結(jié)符a和b的優(yōu)先關(guān)系3.任意產(chǎn)生式右部不能都不含有2個(gè)相繼的非終結(jié)符4.終結(jié)符優(yōu)先級(jí)只有一種5.特別有利于表達(dá)式分析，宜于手工實(shí)現(xiàn)。 34.算符優(yōu)先分析比規(guī)范歸約要快得多，因?yàn)樗惴麅?yōu)先分析跳過了所有單非產(chǎn)生式所對(duì)應(yīng)的歸約步驟，這既是它的優(yōu)點(diǎn)，同時(shí)也是它的缺點(diǎn)。因?yàn)楹雎苑墙K結(jié)符在歸約過程中的作用，存在某種危險(xiǎn)性，可能導(dǎo)致把原本不成句子的輸入串誤認(rèn)為是句子。這種缺陷容易從技術(shù)上彌補(bǔ)。 35.一個(gè)文法，假設(shè)它的任一產(chǎn)生式的右部都不含2個(gè)相繼并

14、列的非終結(jié)符，則為算符文法。 36.算符優(yōu)先表：表頭和列均為終結(jié)符號(hào)，表元素為終結(jié)符的優(yōu)先關(guān)系vw的規(guī)則u，v，wvn 2)終結(jié)符號(hào)集vt中任意兩個(gè)符號(hào)對(duì)之間至多有一種優(yōu)先關(guān)系成立。3)沒有相同的規(guī)則右部。4)沒有形如u->的規(guī)則 a1，2b1，2，3c1，2，3，4d1，2，45動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采納的分配方法是1)以過程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配2)堆存儲(chǔ)分配3)最正確分配方法 a1b2c1，2d1，2，3 二、填空題 1編譯方式和解釋方式的根本區(qū)別在于_。 2ll1分析法中，第一個(gè)l的含義是_，第二個(gè)l的含義是_，“1的含義是_。 3過程調(diào)用時(shí)，參數(shù)的傳遞方法通常有_、_、_和傳名

15、。 4一個(gè)上下文無關(guān)文法所含四個(gè)組成部分是_集、_集、_集和_集。 三、判斷題 1算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。2每個(gè)文法都能改寫為ll(1)文法。3符號(hào)表由詞法分析程序建立，由語法分析程序使用4上下文無關(guān)文法規(guī)則的左部一定是非終結(jié)符號(hào)5ll1文法有可能是二義性的。 四、簡述題 1簡述詞法分析階段的任務(wù)。 2什么是語法治導(dǎo)翻譯？ 3什么是素短語？ 4什么是靜態(tài)存儲(chǔ)分配？ 5畫圖說明編譯程序的組成結(jié)構(gòu)。 五、綜合應(yīng)用題1設(shè)文法g(s)：s(l)|as|all，s|s (1)消除左遞歸和回溯； (2)計(jì)算每個(gè)非終結(jié)符的first和follow；(3)構(gòu)造猜測(cè)分析表。 2已知文法g(e)e

16、t|ettf|t*ff(e)|i (1)給出句型(t*fi)的最右推導(dǎo)及畫出語法樹；(2)給出句型(t*fi)的短語、素短語。參照答案 一、單項(xiàng)選擇題題號(hào)1答案c二、填空題 1是否生成目標(biāo)代碼 2從左向右進(jìn)行分析，每次進(jìn)行最左推導(dǎo)，向輸入串中查看一個(gè)輸入符號(hào)3傳值，傳地址，傳結(jié)果順序可互換 2c3b4d5c4終結(jié)符、非終結(jié)符、開始符號(hào)、產(chǎn)生式順序可互換 三、判斷題12×3×45× 四、名詞解釋 1、答:詞法分析的基本任務(wù)是從左向右掃描每行源程序的符號(hào)，識(shí)別出單詞及其屬性，把單詞換成統(tǒng)一的內(nèi)部表示送給語法分析程序。同時(shí)還要完成在語法分析之前需要做的工作，如刪除注解、

17、空格、換行符等非必要信息，把標(biāo)識(shí)符登錄到符號(hào)表及某些預(yù)加工處理等。 2、答:語法治導(dǎo)翻譯就是在進(jìn)行語法分析的同時(shí)，完成語義的分析，即在語法分析的過程中，依據(jù)語言的語義定義隨時(shí)翻譯已識(shí)別的那部分語法成分的全部含義。 答:有以下特征的短語稱為素短語：1)它首先是一個(gè)短語。2)它至少含一個(gè)終結(jié)符號(hào)。3)除自身外，不再包含其它素短語。 3、答:如果在編譯時(shí)就能確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并確定每個(gè)數(shù)據(jù)項(xiàng)的存儲(chǔ)單元地址，而這些數(shù)據(jù)項(xiàng)的存儲(chǔ)地址在運(yùn)行時(shí)始終不變，這就是靜態(tài)存儲(chǔ)分配。4、答：表格管理詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成錯(cuò)誤處理 五、綜合應(yīng)用題1解：(1) s(l)|asss|lsllsl|(2) first)s)(，afollow(s