編譯原理知識點(diǎn)總結(jié)哈工程

1、.第一章 概論1.什么是編譯器？輸入輸出？編譯器是將一種語言翻譯為另一種語言的計(jì)算機(jī)程序。輸入：源語言 ( source language)編寫的程序輸出：目標(biāo)語言 ( target language )編寫的程序。2.匯編語言的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：匯編語言大大提高了編程的速度和準(zhǔn)確度缺點(diǎn)：編寫起來也不容易 ,閱讀和理解很難；而且匯編語言的編寫嚴(yán)格依賴于特定的機(jī)器，所以為一臺計(jì)算機(jī)編寫的代碼在應(yīng)用于另一臺計(jì)算機(jī)時(shí)必須完全重寫。3.什么是解釋器？與編譯器的區(qū)別？解釋程序是如同編譯器的一種語言翻譯程序。與編譯器的區(qū)別：它立即執(zhí)行源程序而不是生成在翻譯完成之后才執(zhí)行的目標(biāo)代碼。4.喬姆斯基分類結(jié)構(gòu)有幾種文法

2、？名稱？相互關(guān)系？4 種名稱：0 型 無限制文法1 型 上下文相關(guān)文法2 型 上下文無關(guān)文法3 型 正則文法相互關(guān)系：其中的每一個(gè)都是其前者的專門化。5.什么是掃描器？掃描器的功能是什么？掃描器就是語法分析程序。功能：依據(jù)詞法規(guī)則，分析由字符組成的源程序，把它分割為一個(gè)一個(gè)word 專業(yè)資料.具有獨(dú)立意義的最小語法單位，即單詞。6.什么是編輯器？ IDE 中編輯器的新功能編譯器通常接受由任何生成標(biāo)準(zhǔn)文件(例如 ASCII 文件 )的編輯器編寫的源程序。IDE 中編輯器的新功能：盡管編輯器仍然生成標(biāo)準(zhǔn)文件，但會轉(zhuǎn)向正被討論的程序設(shè)計(jì)語言的格式或結(jié)構(gòu)。這樣的編輯器稱為基于結(jié)構(gòu)的，且它早已包括了編譯

3、器的某些操作；因此，程序員就會在程序的編寫時(shí)而不是在編譯時(shí)就得知錯(cuò)誤了。從編輯器中也可調(diào)用編譯器以及與它共用的程序，這樣程序員無需離開編輯器就可執(zhí)行程序。7.什么是調(diào)試器，與編譯器的關(guān)系調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯(cuò)誤的程序。運(yùn)行一個(gè)帶有調(diào)試程序的程序與直接執(zhí)行不同，這是因?yàn)檎{(diào)試程序保存著所有的或大多數(shù)源代碼信息 (諸如行數(shù)、變量名和過程 )。它還可以在預(yù)先指定的位置 (稱為斷點(diǎn) )暫停執(zhí)行，并提供有關(guān)已調(diào)用的函數(shù)以及變量的當(dāng)前值的信息。為了執(zhí)行這些函數(shù)，編譯器必須為調(diào)試程序提供恰當(dāng)?shù)姆栃畔ⅰ?.編譯器有哪幾個(gè)功能模塊？各模塊的功能及輸入輸出源代碼掃描程序記號語法分析程序語法樹語義

4、分析程序常量表注釋樹中間代碼生成符號表word 專業(yè)資料中間代碼錯(cuò)誤處理器.9.編譯器有哪幾個(gè)輔助部件？功能？(1) 常量表：存放在程序中用到的常量和字符串(2) 符號表：與標(biāo)識符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中word 專業(yè)資料.的語義分析程序。(3) 錯(cuò)誤處理器對源程序中錯(cuò)誤的反應(yīng)。10.分析，綜合已將分析源程序以計(jì)算其特性的編譯器操作歸為編譯器的分析部分，而將生成翻譯代碼時(shí)所涉及到的操作稱作編譯器的綜合部分。當(dāng)然，詞法分析、語法分析和語義分析均屬于分析部分 ,而代碼生成卻是綜合部分。在優(yōu)化步驟中 ,分析和綜合都有。分析正

5、趨向于易懂和更具有數(shù)學(xué)性，而綜合則要求更深的專業(yè)技術(shù)。因此，將分析步驟和綜合步驟兩者區(qū)分開來以便發(fā)生變化時(shí)互不影響是很有用的。11.前段，后端將編譯器分成了只依賴于源語言(前端 )的操作和只依賴于目標(biāo)語言(后端 )的操作兩部分。12.遍編譯器發(fā)現(xiàn)，在生成代碼之前多次處理整個(gè)源程序很方便。這些重復(fù)就是遍。13.靜態(tài)語義？哪幾類？程序的語義確定程序的運(yùn)行，但是大多數(shù)的程序設(shè)計(jì)語言都具有在執(zhí)行之前被確定而不易由語法表示和由分析程序分析的特征。這些特征被稱作靜態(tài)語義。一般的程序設(shè)計(jì)語言的典型靜態(tài)語義包括聲明和類型檢查。由語義分析程序計(jì)算的額外信息 (諸如數(shù)據(jù)類型 )被稱為屬性，它們通常是作為注釋或“裝

6、word 專業(yè)資料.飾”增加到樹中 (還可將屬性添加到符號表中)。14.編譯器中第一個(gè)考慮目標(biāo)機(jī)的物理特性的模塊是：代碼生成器_15.T 型圖中 |ST|S,T,H 分別代表什么？|H|語言 H( 代表宿主語言 )編寫的編譯器將語言 S(代表源語言 )翻譯為語言T(代表目標(biāo)語言 )16 T 型圖描述自舉及移植的過程第二章 詞法分析正則表達(dá)式三種基本操作選擇，連結(jié)，重復(fù)（閉包）有窮自動機(jī)的組成元素word 專業(yè)資料.開始狀態(tài)，結(jié)束狀態(tài)，狀態(tài)轉(zhuǎn)換函數(shù)正則表達(dá)式a.十六進(jìn)制數(shù)字串(0-9|A-F)+(x|X)b. 包含奇數(shù)個(gè) a 或奇數(shù)個(gè) b(b*ab*a)*ab*|(a*ba*b)*ba*c.包含

7、偶數(shù)個(gè) a 或偶數(shù)個(gè) b(a*ba*b)*a*|(b*ab*a)*b*d.a 或 b 必須成對出現(xiàn)(aa|b)*(a|bb)*從正則表達(dá)式到NFA (Thompson結(jié)構(gòu) )(1) 并置(2) 選擇(3) 重復(fù)word 專業(yè)資料.DFA：構(gòu)成S, , T, S0, AS:狀態(tài)集合:字母表T:轉(zhuǎn)換函數(shù)S0 :初始狀態(tài)A:接受狀態(tài)NFA：NFA 構(gòu)成相同，且可以有，轉(zhuǎn)入狀態(tài)可以是多個(gè)狀態(tài)。例： S=x, y, z=a, b, cT=fS0 =xA=y, zf(x, a) = x, yf(x, c) = zf(y, b) = y, za*ab*=a+b*a*ab*b=a+b+a*ca+b*|a+b+

8、|a*cword 專業(yè)資料.=a*(ab|c)第三章 上下文無關(guān)文法及分析語法分析兩類：自頂向下，自底向上。自頂向下兩類：遞歸下降，LL(1)分析。文法的表示用 BNF（巴克斯范式）形式表示。二義性文法：每一個(gè)字符串產(chǎn)生不同的分析樹錯(cuò)只要有一個(gè)字符串產(chǎn)生不同的分析樹對引起二義性的原因(1) 運(yùn)算的優(yōu)先級：把具有相同優(yōu)先權(quán)的算符歸納在一組中，并為每一種優(yōu)先權(quán)規(guī)定不同的規(guī)則。(2) 運(yùn)算的結(jié)合行：用基本情況代替遞歸，強(qiáng)制重復(fù)算符匹配一邊的遞歸。(3) else 的懸掛問題：最近嵌套規(guī)則。出現(xiàn)這三種情況就是二義性文法不是二義性說明原因，是二義性舉反例，畫出兩個(gè)不同的分析樹。字符串最左推導(dǎo)，不要少步驟

9、（每次只能對一個(gè)非終結(jié)符進(jìn)行替換）。word 專業(yè)資料.最左推導(dǎo)最右推導(dǎo)形成的分析樹的特點(diǎn)：最左推導(dǎo)是前序遍歷，最右推導(dǎo)是后序遍歷的倒序？。最左推導(dǎo)：是指它的每一步中最左的非終結(jié)符都要被替換的推導(dǎo)。最右推導(dǎo)：是指它的每一步中最右的非終結(jié)符都要被替換的推導(dǎo)。最左推導(dǎo)和與其相關(guān)的分析樹的內(nèi)部節(jié)點(diǎn)的前序編號相對應(yīng)；而最右推導(dǎo)則和后序編號相對應(yīng)。句柄：一個(gè)句型的最左直接短語。(第五章，不考 )分析程序的功能及輸入輸出功能：確定程序的語法輸入：由掃描程序生成的記號序列輸出：語法樹二義性文法及解決辦法可生成帶有兩個(gè)不同分析樹的串的文法稱作二義性文法。解決方法：(1) 設(shè)置一個(gè)規(guī)則，該規(guī)則可在每個(gè)二義性情況

10、下指出哪一個(gè)分析樹（或語法樹）是正確的。這樣的規(guī)則稱作消除二義性規(guī)則。(2) 將文法改變成一個(gè)強(qiáng)制正確分析樹的構(gòu)造的格式。編譯過程中，語法分析器的任務(wù)是(1) 分析單詞串是如何構(gòu)成語句和說明的word 專業(yè)資料.(2) 分析語句和說明是如何構(gòu)成程序的(3) 分析程序的結(jié)構(gòu)1) 終結(jié)符集合 T。2) 非終結(jié)符集合 N（與 T 不相交）。3) 產(chǎn)生式或文法規(guī)則 A的集合 P，其中 A 是 N 的一個(gè)元素，是（TN ）?中的一個(gè)元素（是終結(jié)符和非終結(jié)符的一個(gè)可為空的序列） 。4) 來自集合 N 的開始符號。第四章 自頂向下的分析LL(1) 的命名第 1 個(gè)“ L”指的是由左向右地處理輸入第 2 個(gè)“

11、 L”指的是它為輸入串描繪出一個(gè)最左推導(dǎo)。括號中的數(shù)字 1 意味著它僅使用輸入中的一個(gè)符號來預(yù)測分析的方向。（先行一個(gè)符號）遞歸下降分析：將一個(gè)非終結(jié)符 A 的文法規(guī)則看作將識別 A 的一個(gè)過程的定義。消除左遞歸：(1) 簡單直接左遞歸(2) 普遍的直接左遞歸提取左因子：word 專業(yè)資料.First 集定義：令 X 為一個(gè)文法符號（一個(gè)終結(jié)符或非終結(jié)符）或，則集合 First (X) 由終結(jié)符組成，此外可能還有，它的定義如下：1.若 X 是終結(jié)符或 ，則First (X) = X 。2.若 X 是非終結(jié)符，則對于每個(gè)產(chǎn)生式XX1 X2 . . . Xn ，F(xiàn)irst (X) 都包含了 Fir

12、st (X1 ) - 。若對于某個(gè) i n ，所有的集合 First (X1 ), . . . ,First (Xi )都包括了，則 First (X)也包括了 First (X i + 1 ) - 。若所有集合 First (X1 ), . . . , First (Xn ) 包括了，則 First (X) 也包括 。Follow 集定義：給出一個(gè)非終結(jié)符A，那么集合Follow(A) 則是由終結(jié)符組成，此外可能還有 $。集合 Follow (A) 的定義如下：1. 若 A 是開始符號，則 $就在 Follow (A) 中。2. 若存在產(chǎn)生式 BA，則First ( ) - 在 Follow

13、 (A) 中。3. 若存在產(chǎn)生式 BA，且在 First ()中，則 Follow (A) 包括 Follow(B)。LL(1) 證明定理：1. 在每個(gè)產(chǎn)生式 A1 | 2 | . . . | n 中，對于所有的 i 和 j：1 i，jn ，ij，F(xiàn)irst ( i ) First ( j )為空。2. 若對于每個(gè)非終結(jié)符A 都有 First (A)包含了，那么 First (A) Follow(A)為空。自頂向下的基本原理：在最左推導(dǎo)中描述出各個(gè)步驟來分析記號串輸入。word 專業(yè)資料.自頂向下的關(guān)鍵問題：（which rules to use Ch4_2 P6）(P114)第六章 語義分析

14、語義分析：計(jì)算編譯過程所需的附加信息。語義分析的分類(1) 程序的分析，要求根據(jù)編程語言的規(guī)則建立其正確性，并保證其正確執(zhí)行。(2) 由編譯程序執(zhí)行的分析，用以提高翻譯程序執(zhí)行的效率。靜態(tài)語義分析包括(1) 執(zhí)行分析的描述(2) 使用合適的算法對分析的實(shí)現(xiàn)屬性：屬性是編程語言結(jié)構(gòu)的任意特性。屬性在其包含的信息和復(fù)雜性等方面變化很大，特別是當(dāng)它們能確定時(shí)翻譯 / 執(zhí)行過程的時(shí)間。屬性的典型例子有：? 變量的數(shù)據(jù)類型。word 專業(yè)資料.? 表達(dá)式的值。? 存儲器中變量的位置。? 程序的目標(biāo)代碼。? 數(shù)的有效位數(shù)。聯(lián)編：屬性的計(jì)算及將計(jì)算值與正在討論的語言結(jié)構(gòu)聯(lián)系的過程稱作屬性的聯(lián)編。聯(lián)編時(shí)間：聯(lián)

15、編屬性發(fā)生時(shí)編譯/ 執(zhí)行過程的時(shí)間稱作聯(lián)編時(shí)間。執(zhí)行之前聯(lián)編的屬性是靜態(tài)的，執(zhí)行期間聯(lián)編的屬性是動態(tài)的。在如 C 或 Pascal 這樣的靜態(tài)類型的語言中，變量或表達(dá)式的數(shù)據(jù)類型是一個(gè)重要的編譯時(shí)屬性。表達(dá)式的值通常是動態(tài)的，編譯程序要在執(zhí)行時(shí)生成代碼來計(jì)算這些值。變量的分配可以是靜態(tài)的也可以是動態(tài)的，這依賴于語言和變量自身的特性FORTRAN77 中所有的變量都是靜態(tài)分配。LISP 中所有的變量是動態(tài)分配的。C 和 Pascal 語言混合了靜態(tài)和動態(tài)的兩種變量分配。程序的目標(biāo)代碼無疑是一個(gè)靜態(tài)屬性。數(shù)的有效位數(shù)在編譯期間是一個(gè)不被明確探討的屬性。屬性文法：確定語言實(shí)體的屬性或特性，它們必須進(jìn)

16、行計(jì)算并寫成屬性等式或語義規(guī)則，并描述這些屬性的計(jì)算如何與語言的文法規(guī)則相關(guān)。這樣word 專業(yè)資料.的一組屬性和等式稱作屬性文法。符號表的主要操作：插入，查找，刪除。符號表的功能：（ 1） 建立存儲信息（ 2） 類型檢查（ 3） 數(shù)據(jù)地址第七章 運(yùn)行時(shí)環(huán)境運(yùn)行時(shí)環(huán)境：目標(biāo)計(jì)算機(jī)的寄存器以及存儲器的結(jié)構(gòu)，用來管理存儲器并保存指導(dǎo)執(zhí)行過程所需的信息。幾乎所有的程序設(shè)計(jì)語言都使用運(yùn)行時(shí)環(huán)境的 3 個(gè)類型中的某一個(gè)，它的主要結(jié)構(gòu)并不依賴于目標(biāo)機(jī)器的特定細(xì)節(jié)。環(huán)境的這 3 個(gè)類型分別是：FORTRAN77 的完全靜態(tài)環(huán)境。像 C、C+ 、Pascal 以及 Ada 這些語言的基于棧的環(huán)境。像 LISP 這樣的函數(shù)語言的完全動態(tài)環(huán)境。調(diào)用序列設(shè)計(jì)的重要方面有：1) 如何在調(diào)用程序和被調(diào)用程序之間分開調(diào)用序列操作(也就是有多少調(diào)用序列的代碼放在調(diào)用點(diǎn)上，多少放在每個(gè)過程的代碼開頭)；2) 在多大程度上依賴處理器對調(diào)用支持而不是為調(diào)用序列的每一步生成顯式代碼。完全靜態(tài)運(yùn)行時(shí)環(huán)境：最簡單的運(yùn)行時(shí)環(huán)境類型是所有數(shù)據(jù)都是靜態(tài)的，且執(zhí)行程序期間在存儲器中保持固定。這樣的環(huán)境可用來實(shí)現(xiàn)沒有指針或動態(tài)分配，且過程不可遞歸調(diào)用的語言。此類語言的標(biāo)準(zhǔn)例子是 FORTRAN77 。word 專業(yè)資料.基于棧運(yùn)行時(shí)環(huán)境：在允許遞歸調(diào)用以及每一個(gè)調(diào)用中都重新分配局部變量