鄭州大學期末編譯原理知識點超全總結

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