鄭州大學(xué)期末編譯原理知識(shí)點(diǎn)超全總結(jié)

1.編譯程序的工作過程一般劃分為：詞法分析、語法分析、語義分析及中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成，五個(gè)階段。2.文法G（S）：S-SbM|M; M-MaN|N; N-c . （最右推導(dǎo)也稱為規(guī)范推導(dǎo)，規(guī)范推導(dǎo)的逆過程，稱為最左規(guī)約，也稱為規(guī)范規(guī)約。）句型Macbc的規(guī)范推導(dǎo)：S=SbM=Sbc=Mbc=MaNbc=Macbc ;(一個(gè)句型的最左直接短語稱為該句型的句柄，最簡樹下邊為句柄。)句柄是：c。3.語言L=anbicn|n0,i=0對(duì)應(yīng)的文法為：S-AB;A-aAc|ac;B-bB|4.文法G：S0S1|a對(duì)應(yīng)的語言L(G)=0ma1n|n=05.自上而下語法分析（LL（1）分析）的條件：文法不含左遞歸；設(shè)U是文法G的任意一個(gè)非終結(jié)符，其產(chǎn)生式為U-x1|x2|xn，如果FIRST(xi)FIRST(xj)=(ij,i,j=1,2,n)當(dāng)FIRST（xi）時(shí)，有FIRST（xi）FOLLOW(U)=,則文法G為LL（1）文法。6.屬性文法中屬性分為綜合屬性和繼承屬性。7.正規(guī)文法通過定義語言詞法規(guī)則，上下文無關(guān)文法通過定義語言語法規(guī)則，屬性文法通過定義語言語義規(guī)則。8.編譯中常見的優(yōu)化技術(shù)有代碼外提、強(qiáng)度消弱、合并已知量。9.運(yùn)行存儲(chǔ)分配中，用棧式策略解決遞歸調(diào)用存儲(chǔ)分配問題，用堆式策略解決動(dòng)態(tài)數(shù)據(jù)存儲(chǔ)分配問題。一、簡答題1.什么是編譯程序？答：編譯程序是一種將高級(jí)語言程序(源程序)翻譯成低級(jí)語言(目標(biāo)程序)的程序 。將高級(jí)程序設(shè)計(jì)語言程序翻譯成邏輯上等價(jià)的低級(jí)語言(匯編語言,機(jī)器語言)程序的翻譯程序。2.請(qǐng)寫出文法的形式定義？答：一個(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)先文法。二填空題1.不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲(chǔ)分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲(chǔ)分配方案和動(dòng)態(tài)存儲(chǔ)分配方案，而后者又分為（棧式動(dòng)態(tài)存儲(chǔ)分配）和（堆式動(dòng)態(tài)存儲(chǔ)分配）。2.規(guī)范規(guī)約是最（左）規(guī)約。3.編譯程序的工作過程一般劃分為5個(gè)階段：詞法分析、（語法分析）、語義分析與中間代碼生成，代碼優(yōu)化及（目標(biāo)代碼生成）。另外還有（表格管理）和出錯(cuò)處理。4表達(dá)式x+y*z/(a+b)的后綴式為（xyz*ab+/+）。5文法符號(hào)的屬性有綜合屬性和（繼承屬性）。6假設(shè)二位數(shù)組按行存放，而且每個(gè)元素占用一個(gè)存儲(chǔ)單元，則數(shù)組a1.15,1.20某個(gè)元素ai，j的地址計(jì)算公式為（a+(i-1)*20+j-1）。7局部優(yōu)化是局限于一個(gè)（基本塊）范圍內(nèi)的一種優(yōu)化。8 詞法規(guī)則通常可以用_正規(guī)式_，正規(guī)文法、_自動(dòng)機(jī)_描述；語法規(guī)則通常用_2型文法_來描述；語義規(guī)則通常用_屬性文法_來描述。9 編譯原理的工作過程一般劃分為：詞法分析、語法分析、語義分析、優(yōu)化和目標(biāo)代碼生成五個(gè)階段。1.(最右推導(dǎo) )稱為規(guī)范推導(dǎo)。2.編譯過程可分為（詞法分析），（語法分析），（中間代碼生成），（代碼優(yōu)化）和（目標(biāo)代碼生成）五個(gè)階段。3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（二義性的）。4.從功能上說，程序語言的語句大體可分為（執(zhí)行性）語句和（說明性）語句兩大類。5.語法分析器的輸入是（單詞符號(hào)），其輸出是（語法單位）。6.掃描器的任務(wù)是從（源程序）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)）。7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（類型、種屬、所占單元大小、地址）等等。8.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為（現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址）。9.一個(gè)句型的最左直接短語稱為句型的（句柄）。10.常用的兩種動(dòng)態(tài)存貯分配辦法是（棧式）動(dòng)態(tài)分配和（堆式）動(dòng)態(tài)分配。11.一個(gè)名字的屬性包括(類型)和(作用域)。12.常用的參數(shù)傳遞方式有（傳地址），（傳值）和（傳名）。13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（局部優(yōu)化），（循環(huán)優(yōu)化）和（全局優(yōu)化）三個(gè)級(jí)別。14.語法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）分析法。15.預(yù)測分析程序是使用一張（分析表）和一個(gè)（符號(hào)棧）進(jìn)行聯(lián)合控制的。16.常用的參數(shù)傳遞方式有（傳地址），（傳值）和（傳名）。17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為是（初）態(tài);而且實(shí)際上至少要有一個(gè)（終）態(tài)。18.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（局部優(yōu)化），（循環(huán)優(yōu)化）和（全局優(yōu)化）三個(gè)級(jí)別。19.語法分析是依據(jù)語言的（語法）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進(jìn)行的。20.一個(gè)句型的最左直接短語稱為句型的（句柄）。21.一個(gè)文法G，若它的預(yù)測分析表M不含多重定義，則該文法是LL(1)文法）文法。22.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用(靜態(tài))策略，PASCAL采用(動(dòng)態(tài))策略。23.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是(二義性文法)。24.最右推導(dǎo)亦稱為（規(guī)范推導(dǎo)），由此得到的句型稱為（規(guī)范）句型。25.語法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）分析法。26.對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱為(句子)。27.所謂自上而下分析法是指（從開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）。28.語法分析器的輸入是（單詞符號(hào)），其輸出是（語法單位）。29.局限于基本塊范圍的優(yōu)化稱（局部優(yōu)化）。30.預(yù)測分析程序是使用一張（分析表）和一個(gè)（符號(hào)棧）進(jìn)行聯(lián)合控制的。31.2型文法又稱為（上下文無關(guān)文法）文法；3型文法又稱為（正規(guī)）文法。32. 每條指令的執(zhí)行代價(jià)定義為（指令訪問主存次數(shù)加1）。33. 算符優(yōu)先分析法每次都是對(duì)（最左素短語）進(jìn)行歸約。 文法語言（給你一個(gè)文法問語言是什么？）2.2設(shè)有文法GN:ND|ND;D0|1|2|3|4|5|6|7|8|9（1） GN定義的語言是什么？（2） 給出句子0123和268的最左推導(dǎo)和最右推導(dǎo)。2.2(1)分析：問題歸結(jié)為由識(shí)別符號(hào) N 出發(fā)，將推導(dǎo)出什么樣的句子，也就是說 L(GN)是由一些什么樣的符號(hào)串所組成的集合，找出其中的規(guī)律，用式子或自然語言描述出來。 解答： L(GN)=a|a為可帶前導(dǎo)0的正整數(shù) 或 L(GN)=(0|1|2|3|4|5|6|7|8|9)+（2）分析：最右推導(dǎo)是指在推導(dǎo)過程中任何一步=(和都是句型)，都是對(duì)中的最右非終結(jié)符進(jìn)行替換。 最左推導(dǎo)是指在推導(dǎo)過程中任何一步=(和都是句型)，都是對(duì)中的最左非終結(jié)符進(jìn)行替換。 解答： 0123 最左推導(dǎo)：N=ND =NDD =NDDD =DDDD =0DDD =01DD =012D =0123 最右推導(dǎo)：N=ND =N3 =ND3 =ND23 =N123 =D123 =0123（2）268最左推導(dǎo)：N =ND =NDD =DDD =2DD =26D =268最右推導(dǎo)：N =ND =N8 =ND8 =N68 =D68 =268注意問題： (1) 推導(dǎo)符號(hào)的使用：= ( X)(2) 最左和最右不要混肴2.7下面文法生成的語言是什么？G1：SAB；AaA|；Bbc|bBcG2：SaA|a；AaS2.7（1）分析：S=AB=aAB=aaAB=aiB= aibBc = aib2Bc2 =aibncn所以此文法定義的語言為 L(GN) = aibncn|i 0,n 1解答：L(GN) = aibncn|i 0,n 1存在問題：a與b，c次數(shù)是不同的（2）分析：S=aA|a=aaS|a=a2nS|a解答：L(GN)= a2n+1|n 0 語言文法（給你語言求文法）2.3 L1=amdn|m,n1 L2=anbnci|n1i0 L3=anbncmdm|n1m12.3分析：設(shè)計(jì)文法來描述一個(gè)語言，關(guān)鍵是設(shè)計(jì)一組規(guī)則生成語言中的符號(hào)串。 設(shè)計(jì)語言的文法，必須分析這個(gè)語言是由怎樣一些符號(hào)串組成，即首先分析語言中符號(hào)串的結(jié)構(gòu)特征。解答：（1）G1：SAB AaA|a BbB|b 注意：a,b次數(shù)不同，不能寫e m,n=1。（2）G2： SAB AaAb|ab BcB| 或 SSc|A AaAb|ab 注意：a,b次數(shù)相同；n=1; i=0 abA X（3）G3：SAB AaAb|ab BcBd|cd2.11已知文法GS:S(AS)|(b)；A(SaA)|(a)2.11分析：首先要判斷一下符號(hào)串是否是文法的句型。解答：（1）因?yàn)镾=(AS)=(a)S) (a)所以符號(hào)串(a)不是文法的句型，因此它沒有短語、直接短語和句柄。（2）因?yàn)镾=(AS)=(A(A(b)=(A(SaA)(b)所以符號(hào)串)=(A(SaA)(b)是文法的句型，該句型的語法樹如下圖所示：短語：(A(SaA)(b)； (SaA)(b)； (SaA)； (b)直接短語：(SaA)；(b)句柄： (SaA)給正規(guī)文法求正規(guī)式（用下面的性質(zhì)）令 A、B和C均為正規(guī)式，由下列關(guān)系成立：A|B = B|A交換率A|(B|C)=(A|B)|C結(jié)合率A(BC)=(AB)C結(jié)合率A(B|C)=AB|AC分配率 (A|B) C = AC|BCA = A= AA* AA* | A | A*(A|)A*(A*) * A*求解規(guī)則：若 x = x |(或x = x+)，則解為x = *若 x = x|(或x = x+)，則解為x = *設(shè)有正規(guī)文法：AaB|bB BaC|a|bC|aB試給出該文法生成語言的正規(guī)式首先給出相應(yīng)的正規(guī)式方程組（+代替|）A=aB+bB(1)B=aC+a+b (2)C=aB(3)將(3)代入(2)式中得B=aaB+a+b(4)對(duì)(4)使用求解規(guī)則得B=(aa)*(a+b)(5)將(5)代入(1)得A=(a+b)(aa)*(a+b)即正規(guī)文法GZ所生成語言的正規(guī)式是 (a|b)(aa)*(a|b)正規(guī)式到正規(guī)文法的轉(zhuǎn)換字母表上的正規(guī)式到正規(guī)文法 G(VN,VT,P,S)的轉(zhuǎn)換方法如下：1.令 VT = 2.對(duì)任意正規(guī)式 R 選擇一個(gè)非終結(jié)符 Z 生成規(guī)則ZR，并令 SZ；3.若 a 和 b 都是正規(guī)式，對(duì)形如 Aab的規(guī)則轉(zhuǎn)換成 AaB 和 Bb兩規(guī)則，其中 B 是新增的非終結(jié)符；4.在已轉(zhuǎn)換的文法中，將形如 Aa*b 的規(guī)則進(jìn)一步轉(zhuǎn)換成 AaA | b；5.不斷利用規(guī)則(3)和(4)進(jìn)行轉(zhuǎn)換，直到每條規(guī)則最多含有一個(gè)終結(jié)符為止。將描述標(biāo)識(shí)符的正規(guī)式R=l(l|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法令 S 是文法開始符號(hào)，根據(jù)規(guī)則(2)變換為Sl(l|d)*根據(jù)規(guī)則(3)變換為SlA A(l|d)* 根據(jù)規(guī)則(4)變換為SlA A(l|d)A |進(jìn)一步變換為SlA AlA|dA|進(jìn)一步變換為（消除規(guī)則）Sl|lA Al|d|lA|dA一個(gè)確定有窮自動(dòng)機(jī) DFA M 是一個(gè)五元式：M=( Q, , f, S, Z)其中：Q 是一個(gè)有限狀態(tài)集，它的每個(gè)元素稱為一個(gè)狀態(tài)。是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符。f 是一個(gè)從 Q 至 Q 的單值映射。f(qi, a) =qj(qi,qjQ，a)表示：當(dāng)現(xiàn)行狀態(tài)為 qi、輸入字符為 a 時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一狀態(tài) qj 。我們稱 qj 為 qi 的一個(gè)后繼。SS，是唯一的初態(tài)。ZS，是一個(gè)終態(tài)集（可空）。1)其等價(jià)的 DFA 的開始狀態(tài)為A=-CLOSURE(X)=0,1,2,作為未標(biāo)記的狀態(tài)添加到 Q中。2)此時(shí) Q 中僅有唯一的未標(biāo)記狀態(tài) A，因此f(A,a)=-CLOSURE(f(X,0,1,a) =-CLOSURE(0,2)=0,1,2=B未標(biāo)記的 B=Qf(A,a)=B 添加到M中。 f(A,b)=-CLOSURE(f(X,0,1,b) =-CLOSURE(0)=0,1=C未標(biāo)記的 C=Qf(A,b)=C 添加到M中。 對(duì)狀態(tài) A 做標(biāo)記3)此時(shí) Q=A,B,C,其中B，C均未加標(biāo)記f(B,a)=-CLOSURE(f(0,1,2,a) =-CLOSURE(0,2)=0,1,2=B f(B,a)=B 添加到M中。 f(B,b)=-CLOSURE(f(0,1,2,b) =-CLOSURE(0,3)=0,1,3=D未標(biāo)記的 D=Qf(B,b)=D 添加到M中。 對(duì)狀態(tài) B 做標(biāo)記（NFA確定化后的狀態(tài)矩陣）1.首先 M的狀態(tài)分成兩組：終態(tài)組A,B,C,D，非終態(tài)組E形成(A,B,C,D,E)2.考察E，不能再分劃，把E作為new中的一個(gè)子集。3.考察A,B,C,D，A,B,C,Da=BA,B,C,D，但是A,B,C,Db=C,D,E，它既不包含在A,B,C,D中也不包含在E之中，因此，應(yīng)把A,B,C,D一分為二。因?yàn)闋顟B(tài) A,B,C 經(jīng) b 弧到達(dá)同一子集A,B,C,D中的狀態(tài)，而狀態(tài) D 經(jīng) b 弧到達(dá) E，因此，應(yīng)把 D 分出來，形成D、A,B,C。于是new=(A,B,C,D,E), new，令new4.當(dāng)前分劃是 =(A,C,B,D,E)考察A,C，A,Ca=BB，A,Cb=CA,C，所以A,C不能再分劃。此時(shí) new=整個(gè)分劃過程結(jié)束。5.至此，選擇 A 代表A,C,將狀態(tài) C 從狀態(tài)圖中刪去，并將原來引向 C 的弧都引至 A，得到化簡后的 DFA M1 文法規(guī)范句型的活前綴1.字符串的前綴是指字符串的任意首部。如 abc 的前綴有 、a、ab、abc。2.所謂活前綴是指規(guī)范句型的一個(gè)前綴，這種前綴不包含句柄之后的任何符號(hào)。規(guī)范句型：用規(guī)