第一講：緒論
特别聲明：以下内容，源自 大學慕課 《編譯原理》哈爾濱工業大學 陳鄞，文章經個人整理所得，僅供學習交流
(一) 什麼是編譯
(1) 基本概念
先說幾個必備的概念
A：機器語言
機器語言是機器能直接識别的程式語言或指令代碼，勿需經過翻譯，每一操作碼在計算機内部都有相應的電路來完成它，或指不經翻譯即可為機器直接了解和接受的程式語言或指令代碼。機器語言使用絕對位址和絕對操作碼。不同的計算機都有各自的機器語言，即指令系統。從使用的角度看，機器語言是最低級的語言。
—— 百度百科
個人了解：
- 從表面形式來看，機器語言就是一堆1和0組成的代碼，也就是用二進制代碼表達指令，但更确切一點來說，機器語言是由高低電位構成的，指定高電位為1，低電位為0，而我們對電路進行一定的設計後，電路中高低電位的輸入輸出正好與2進制狀态相符，是以我們也就看到了 1、0的那種表現形式
- 計算機能直接了解機器語言，不需要經過任何處理（因為1、0 和其實體電路結構是相關的）
- 如下圖中 C706 0000 0002（16進制）C706 代表操作碼，0000 0002 代表操作數 代表指派語句 X = 2
- 補充：為了簡化二進制，照顧人的易讀性是以用十六進制來表示（0~9和a~f），機器可不能直接識别十六進制數，計算機内部的一切資訊的存取以及傳輸還都是以二進制形式進行的
疑問：實際情況下，我們直接用二進制進行描述一些程式等是非常麻煩的，那為什麼不直接轉換成容易了解的十進制呢？然後運作的時候再轉為二進制呢？而出現了八進制或者十六進制這樣的概念
答案：首先直接使用二進制當然是比較麻煩的，枯燥，且很長很長，是以轉換成一些更高的進制，就可以大幅度縮小長度，而十進制描述雖然符合人的行為習慣，容易被人接受，但是直接與計算機結構關聯卻有一些不太合适，而八進制或者十六進制分别是 2^3 以及 2^4 這一點使得，進制之間的轉換會比較容易，同時8位二進制數為一個位元組，而兩位十六進制剛好可以表示一個位元組，例如，F1 對應二進制為 11110001，同樣可以看到，每一位十六進制數，也轉換成了四位二進制數
B：彙編語言
彙編語言（assembly language）是一種用于電子計算機、微處理器、微控制器或其他可程式設計器件的低級語言，亦稱為符号語言。在彙編語言中，用助記符代替機器指令的操作碼，用位址符号或标号代替指令或操作數的位址。在不同的裝置中，彙編語言對應着不同的機器語言指令集，通過彙編過程轉換成機器指令。特定的彙編語言和特定的機器語言指令集是一一對應的，不同平台之間不可直接移植。[1]
—— 百度百科
簡單概括：低級，不具有移植性，能直接通路計算機硬體，效率高，占用資源少，同時使用助記符（Memoni）代替操作碼，用位址符号（Symbol）或标号（Label）代替位址碼。如上圖的MOV X,2 同樣代表指派語句 X = 2
C：進階語言
進階程式設計語言（High-level programming language）是高度封裝了的程式設計語言，與低級語言相對。它是以人類的日常語言為基礎的一種程式設計語言，使用一般人易于接受的文字來表示，有較高的可讀性，以友善對電腦認知較淺的人亦可以大概明白其内容。
—— 維基百科
這沒什麼好說的，就日常程式設計所做的，x = 2
Em 鋪墊好像是長了點哈
從上圖可知，内容經過編譯這個過程以後，從進階轉換到低級的形式（從人樂意看的内容轉換成機器樂意看的内容）
編譯的定義：将進階語言（源語言）翻譯成彙編語言或機器語言（目智語言）的過程
(2) 編譯器在語言處理系統中的位置
前面我們說了編譯的一個基本概念，而為了建立可執行的目标程式，除了編譯器外，我們還需要一些其他的程式進行配合，下圖就是一個語言處理的基本過程，注意留意編譯器所處的位置
簡單介紹一下流程中的内容
A：預處理器（Preprocessor）
- 一個源程式可能分成幾個子產品存放在不同的檔案裡，将這些源程式彙集在一起的任務，這時候就需要預處理器把存儲在不同檔案中的源程式聚合在一起
- 把稱為宏的縮寫語句轉換為原始語句
B：編譯器（Compiler）
- 将進階語言翻譯成彙編語言或機器語言
C：彙編器（Assembler）
- 将彙編語言翻譯成可重定位的機器語言
- 若在編譯器階段已經直接将進階語言翻譯成機器語言，則可以省略彙編器
- 可重定位（Relocatable）/ 可再裝配：資料在記憶體存放的起始位置 L 不是固定的，起始位置 + 相對位址 = 絕對位址
D：加載器（Loader）
- 修改可重定位位址
- 将修改後的指令和資料放到記憶體中适當的位置
E：連結器（Linker）
- 将多個可重定位的機器代碼檔案（包括庫檔案）連接配接到一起
- 解決外部記憶體位址問題
(二) 編譯系統結構
(1) 結構概述
A：前端（fornt end）
與源語言相關，字元流——詞法分析器——詞法單元流——文法分析器——文法樹——語義分析器——文法樹——中間代碼生成器
B：後端（back end）
與目智語言相關，中間表示形式 ——機器無關代碼優化器——中間表示形式——目标代碼生成器——目标機器語言——機器相關代碼優化器——目标機器語言
上述字型加粗的為後端部分
(三) 詞法分析概述
(1) 基本概念
從左向右逐行掃描源程式的字元，識别出各個單詞，确定單詞的類型，将識别出的單詞轉換成統一的機内表示——此法單元（token）形式
token：<種别碼，屬性值>
| 單詞類型 | 種别 | 種别碼 | |
|---|---|---|---|
| 1 | 關鍵字 | program、is、else、then、… | 一詞一碼 |
| 2 | 辨別符 | 變量名、數組名、記錄名、過程名、… | 多詞一碼 |
| 3 | 常量 | 整型、浮點型、字元型、布爾型、… | 一型一碼 |
| 4 | 運算符 | 算數（+ - * 、 ++ --）關系（> < == != >= <=）邏輯（&|~） | 一詞一碼或一型一碼 |
| 5 | 界限符 | ; () = {} … | 一詞一碼 |
(2) 例題一
種别碼本身應該是一個整數，為了上例中為了直覺，使用了宏定義的形式
- WHILE：表示 while ，關鍵字，一詞一碼
- IDN（identify）：表示辨別符，第一個分量全為IDN，第二個分量為其字面值以互相區分
- NE（not equal）：表示不等，運算符，一詞一碼或一型一碼
- CONST：表示常量，一型一碼
- SLP、SRP、LP、RP：分别表示左右小括号以及左右花括号，界限符， 一詞一碼
- INC：表示 自增 ++ 運算符，一詞一碼或一型一碼
- SEMI：表示 分号 ；界限符，一詞一碼
(四) 文法分析概述
(1) 基本概念
文法分析器(parser)從詞法分析器輸出的token序列中識别出各類短語，并依據這些規則所展現出的語言構造的層次性，用各記号的第一進制建成一種樹形的中間表示
(2) 例題一：指派語句的分析樹
從下往上看，一個辨別符 rete * 一個數字60 組成了一個新的表達式，而它又 + 另一個辨別符 initial 組成了一個更大的表達式，接着通過 = 與辨別符 postion 組成了最終的指派語句
(3) 例題二：變量聲明語句的分析樹
D：declaration（聲明）
T：type（類型 ）
IDS：identifiers sequence（辨別符序列）
文法在圖檔中有提到，即 ① 聲明 = 類型 + 辨別符序列 + ; ② 類型 = int 或 real 或 char 或bool ③ 一個辨別符 id 本身 可以構成一個辨別符序列，一個辨別符序列 + , + 辨別符 id 可以構成一個更大的辨別符序列
這樣一看這個圖就很直覺了
(五) 語義分析概述
(1) 收集辨別符的屬性資訊
A：種屬（Kind）
簡單變量、符合變量（數組、記錄 …）、過程、…
B：類型（Type）
整型、實型、字元型、布爾型、指針型、…
C：存儲位置、長度
一個例子就明白了：
例如，建立一個實型數組x ，是以其相對位址為 0 ，其含有 8個元素，同時假設一個實型變量占用 8 個位元組，這個數組占據了0-63的位址 ，是以下一個 整型變量 i 隻能從 64 開始，而假設一個整型變量占用 4 個位元組，j 就需要從64 + 4，68開始
D：值
E：作用域
F：參數和傳回值資訊
參數個數、參數類型、參數傳遞方式、傳回值類型
總結：符号表
這些收集到的标記符屬性資訊，都會被存放到一個叫做符号表的資料結構中，其中有着例如 TYPE、KIND 等多種屬性，同時符号表通常帶有一個字元串表如下圖
NAME = 辨別符在字元串表中的起始位置 + 長度
(2) 語義檢查
- 變量或過程未經聲明就使用
- 變量或過程名重複聲明
- 運算分量類型不比對
- 操作符與操作數之間的類型不比對
- 數組下标不是整數
- 對非數組變量使用數組通路操作符
- 對非過程名使用過程調用操作符
- 過程調用的參數類型或數目不比對
- 函數傳回類型有誤
(六) 中間代碼生成
中間代碼生成：經過文法分析和語義分析後，許多編譯器為源程式産生更低級的顯示中間表示，可以了解為一種抽象的程式
(1) 常用的中間表示形式
三位址碼 (Three-address Code) （在這裡進行簡單介紹）
- 三位址碼由類似于彙編語言的指令序列組成，
- 每個指令最多有三個操作數(operand)
文法結構樹/文法樹 (Syntax Trees)（後面詳細講，這裡不涉及）
(2) 常用的三位址指令
- x = y op z ：op 是一個二進制運算符，y 和 z 是兩個運算分量的位址，x 是運算結果的存放位址
- x = op y：op 在這裡是一個一進制運算符，是以隻有兩個操作數 x y
- x = y ：也隻有兩個操作數
- if x relop y goto n ：如果 x 和 y 滿足 relop 關系，就跳轉到 n 對應的指令
- goto n：直接跳轉到 n 對應的指令
- param x：将 x 設定為參數
- call p,n：p 是過程的名字，n 是過程的個數
- return：跳轉到位址 x 對應的指令
- x = y[i]：y 表示數組的名字，即基位址，i 是數組元素的偏移位址，不是下标
- x[i] = y：将一個變量的值指派給數組元素
- 最後三個：與指針相關的指令
(3) 三位址指令的表示
- 四元式 (Quadruples)（下面提一下這個）
- (op, y, z, x)
- 三元式 (Triples)
- 間接三元式 (Indirect triples)
(4) 中間代碼生成的例子
說明一下，右邊，冒号左邊的數字代表指令的編号，例子中從100取到112，j 代表 jump
如何看這個程式做了什麼呢，例如第一行：100:(j<,a,b,102) 就是說，當 a < b 的時候 跳轉到 102 指令，若不滿足就繼續執行 101 指令，找這種方式，對應着代碼看，這個例子是非常直覺的
(七) 目标代碼生成
- 目标代碼生成以源程式的中間表示形式作為輸入，并把它映射到目智語言
- 目标代碼生成的一個重要任務是為程式中使用的變量合理配置設定寄存器
(八) 機器無關/有關優化器
代碼優化
- 為改進代碼所進行的等價程式變換，使其運作得更快一些、占用空間更少一些，或者二者兼顧
(九) 整點題目練練手
① 編譯是對( ) 【正确答案：C】
- A：機器語言的執行
- B：彙編語言的翻譯
- C：進階語言的翻譯
- D：進階語言程式的解釋執行
② 用進階語言編寫的程式經編譯後産生的程式叫( ) 【正确答案：B】
- A：源程式
- B：目标程式
- C：連接配接程式
- D：解釋程式
③ ( )不是編譯程式的組成部分 【正确答案：C】
- A：詞法分析程式
- B：代碼生成程式
- C：裝置管理程式
- D：文法分析程式
④ 源程式是句子的集合，( )可以較好地反映句子的結構 【正确答案：B】
- A：線性表
- B：樹
- C：完全圖
- D：堆棧
⑤ 編譯程式是一種( ) 【正确答案：B】
- A：彙程式設計式
- B：翻譯程式
- C：解釋程式
- D：目标程式
⑥ 按邏輯上劃分，編譯程式第三步工作是( ) 【正确答案：A】
- A：語義分析
- B：詞法分析
- C：文法分析
- D：代碼生成
⑦ 編譯程式中文法分析器接收以( )為機關的輸入 【正确答案：A】
- A：單詞
- B：表達式
- C：産生式
- D：句子
⑧ 編譯過程中，文法分析器的任務就是( ) 【正确答案：B】
- A：分析單詞是怎樣構成的
- B：分析單詞串是如何構成語句和聲明的
- C：分析語句和聲明是如何構成程式的
- D：分析程式的結構
⑨ 文法分析時所依據的是( ) 【正确答案：A】
- A：文法規則
- B：詞法規則
- C：語義規則
- D：等價變換規則
總結
緒論部分的知識比較少，主要是對編譯原理的基本知識進行了一定的總結概括，以及一些基本知識的入門，讓我們對編譯有一個初步的概念，更加詳細的課程在後面的章節，後面再更新，最近在忙着寫一些東西，可能更新文章會慢一些，希望大家見諒，再次感謝大家的支援，謝謝！！！