為什么要學(xué)習(xí)編譯原理

作為程序員，不管是前端開發(fā)工程師還是后端開發(fā)工程師，編譯技術(shù)都與我們的工作息息相關(guān)。在實際工作中也經(jīng)常會碰到需要編譯技術(shù)的場景。比如，前端開發(fā)工程師想要了解TypeScript是如何把一門語言翻譯成另一門語言的，以及babel是如何編譯JavaScript的等等。學(xué)習(xí)編譯技術(shù)有助于提升我們的職場競爭力，更有助于程序員在技術(shù)的道路上走的更遠(yuǎn)。那么學(xué)習(xí)完本篇文章你會對編譯原理有個初步的認(rèn)識，比如：

• 知道為什么要學(xué)習(xí)編譯

• 了解編譯原理和我們?nèi)粘ｉ_發(fā)中使用的開發(fā)語言的關(guān)系

• 了解編譯在語言系統(tǒng)中所處的位置及編譯系統(tǒng)的結(jié)構(gòu)

• 了解詞法分析、語法分析、語義分析這些我們工作中經(jīng)常聽到的概念等等

• 更重要的是知道我們編寫的代碼是如何被計算機(jī)識別并執(zhí)行的。

什么是編譯原理

編譯原理是介紹如何將高級程序設(shè)計語言轉(zhuǎn)換成計算機(jī)硬件能識別的機(jī)器語言，以便計算機(jī)進(jìn)行處理

編譯與計算機(jī)程序設(shè)計語言的關(guān)系

日常開發(fā)過程中我們使用的語言一般都是高級語法比如 JAVA、Python、PHP、JavaScript等等，但是計算機(jī)只能識別0、1這樣的機(jī)器碼。那么這些高級語言是如何翻譯成機(jī)器能識別的0、1等呢？這就用的了編譯，首先我們通過下面這幅圖看下編譯與計算機(jī)程序語言的關(guān)系，有助于我們直觀的了解編譯的作用。

注意：每種機(jī)器都對應(yīng)一種匯編語言

程序設(shè)計語言的轉(zhuǎn)換方式

翻譯：指把某種語言的源程序，在不改變語義的條件下，轉(zhuǎn)換成另一種語言程序即目標(biāo)語言程序

真正的實現(xiàn)有兩種方式，編譯及解釋

• 編譯：專指由高級語言轉(zhuǎn)換為低級語言，整個程序翻譯。常用的例如：c、c++，delphi,Fortran、Pascal、Ada

• 解釋：接受某種高級語言的一個語句輸入，進(jìn)行解釋并控制計算機(jī)執(zhí)行，馬上得到這個句子的執(zhí)行結(jié)果，然后再接受下一個語句。類似口譯，一句一句進(jìn)行解釋。常用的例如：python 解釋以源程序作為輸入，不產(chǎn)生目標(biāo)程序，一邊解釋一邊執(zhí)行。優(yōu)點：直觀易懂，結(jié)構(gòu)簡單，易于實現(xiàn)人機(jī)對話。缺點：效率低(不產(chǎn)生目標(biāo)程序，每次都需要重新執(zhí)行，速度慢)

編譯的轉(zhuǎn)換過程

• 編譯->運(yùn)行

• 編譯->匯編->運(yùn)行

• 

編譯器在語言處理系統(tǒng)中的位置

了解了編譯與程序設(shè)計語言的關(guān)系，那么我們接下來再來看下編譯器在語言處理系統(tǒng)中所處位置，如下圖

編譯系統(tǒng)的結(jié)構(gòu)

那么機(jī)器是如何把高級語言翻譯為匯編語言程序或機(jī)器語言程序的呢？

我們先來看下人工進(jìn)行英文翻譯的例子，這里引用的哈工大編譯原理中的圖示

圖中的中間表示很重要主要起到了一個橋梁的作用，比如圖中的中間表示可以使用各種語言表示。

根據(jù)上圖可以看出要進(jìn)行語義分析首先需要劃分句子成分，那么我們是如何劃分句子成分的呢？

1. 首先通過詞法分析分析出句子中各個單詞的詞性或者詞類

2. 接下來通過語法分析識別出句子中的各類短語從而獲得句子的結(jié)構(gòu)

3. 然后進(jìn)行語義分析根據(jù)句子結(jié)構(gòu)分析出句子中各個短語在句子中充當(dāng)什么成分，從而確定各個名詞性成分同各個核心謂語動詞間的關(guān)系語意關(guān)系

4. 最后給出中間表示形式

   實際上編譯器在工作的時候也是經(jīng)過了以上幾個步驟，我們成為階段(計算機(jī)的邏輯組織方式，在實現(xiàn)過程中多個階段可能會被組合在一起實現(xiàn))，可以分為兩大部分：分析源語言、生成目標(biāo)代碼,在編譯器中他們分別對應(yīng)編譯器的前端和后端兩個部分。編譯器的結(jié)構(gòu)如下圖

   了解了編譯器的結(jié)構(gòu)，讓我們從編譯器的前端開始講起，看看詞法分析、語法分析、語義分析等各個階段都做了什么。

詞法分析(掃描)

編譯的第一個階段，從左到右逐行掃描源程序的字符，識別出各個單詞(是高級語言中有是在意義的最小語法單元，由字符構(gòu)成)，確定單詞的類型。將識別的單詞轉(zhuǎn)換成統(tǒng)一的機(jī)內(nèi)表示即詞法單元 簡稱Token

名字解釋

• 一詞一碼：例如，關(guān)鍵字是唯一的且事先可以確定，為每個關(guān)鍵字分配一個種別碼

• 多詞一碼：例如，所有的標(biāo)示符統(tǒng)一作為一類單詞分配同一個種別碼，為了區(qū)分不同的標(biāo)示符，用token的第二個分量“屬性值”存放不同標(biāo)示符具體的字面值

• 一型一碼：不同類型的常量他們的構(gòu)成方式是不同的，例如，我們?yōu)槊糠N類型的常量分配一個種別碼，為了區(qū)分同一類型下的不同常量，也用token的第二個分量“屬性值”存放每個常量具體的值 下面圖中是一個詞法分析后得到的token序列的例子

  描述詞法規(guī)則的有效工具是正規(guī)式和有限自動機(jī)。正規(guī)式:用來確定單詞是否和程序語言規(guī)范。有限自動機(jī)：通過有限自動機(jī)進(jìn)行單詞和正規(guī)式比較

語法分析(parsing)

語法分析的定義

語法分析器從詞法分析器輸出的token序列中識別出各類短語，并構(gòu)造語法分析樹(parse tree),語法分析樹描述了句子的語法結(jié)構(gòu)

語法分析的規(guī)則

即語法規(guī)則又稱文法，規(guī)定了單詞如何構(gòu)成短語、句子、過程和程序。

語法規(guī)則的標(biāo)示如下，含義是A定義為B或者C

來看下賦值語句的語法規(guī)則：

• A::=V=E

• E::=T|E+T

• T::=F|T*F

• F::=V|(E)|C

• V::=標(biāo)示符

• C::=常數(shù) 即由標(biāo)示符或者常數(shù)的表達(dá)式進(jìn)行加減乘除運(yùn)算

語法分析的方法

推導(dǎo)(derive)和歸約(reduce)

• 推導(dǎo)：最左推導(dǎo)、最右推導(dǎo)

• 歸約：最右歸約、最左歸約,推導(dǎo)的逆過程就是歸約

最右推導(dǎo)、最左歸約：最左推導(dǎo)、最右歸約：

語法樹

計算機(jī)通過語法樹來進(jìn)行分析，即語法分析過程也可以用一顆倒著的樹來標(biāo)示，這顆樹叫語法樹。正確的語法樹葉子節(jié)點數(shù)必須是表達(dá)式的符號，例如

賦值語句的分析樹：

變量聲明語句的分析樹：

首先看下變量聲明語句的文法(文法是由一系列規(guī)則構(gòu)成的)：

語義分析

語義的任務(wù)主要有兩個

一. 收集標(biāo)識符的屬性信息

• 種屬(Kind)：簡單變量、復(fù)合變量(數(shù)組、記錄、...)、過程、...

• 類型 (Type)：整型、實型、字符型、布爾型、指針型、...

• 存儲位置、長度

• 值

• 作用域

• 參數(shù)和返回值信息，參數(shù)個數(shù)、參數(shù)類型、參數(shù)傳遞方式、返回值類型、... 語義分析階段收集的標(biāo)識符的信息都會存儲在一個符號表里，每個標(biāo)識符都對應(yīng)符號表中的一條記錄，記錄的每個字段記錄標(biāo)識符的每個屬性，符號表通常帶有一個字符串表用來存放程序中用到的標(biāo)識符和字符常數(shù)，Name 就會被分為兩個部分，一部分存放標(biāo)識符在字符串表中的起始位置，另一部分用來存儲標(biāo)識符的長度，符號表如下圖：

  除了符號表還有常量表(登記各類常量表)；標(biāo)號表(登記標(biāo)號的定義和應(yīng)用，不常用目標(biāo))；入口名表(登記過程的層號、程序符號表入口等)，各種表的生成大部分在詞法分析階段但是在后面各個階段都有維護(hù)；中間代碼表

二. 語義檢查

1. 變量或過程未經(jīng)聲明就使用

2. 變量或過程名重復(fù)聲明

3. 運(yùn)算分量類型不匹配

4. 操作符與操作數(shù)之間的類型不匹配

• 數(shù)組下標(biāo)不是整數(shù)

• 對非數(shù)組變量使用數(shù)組訪問操作符

• 對非過程名使用過程調(diào)用操作符

• 過程調(diào)用的**參數(shù)類型或數(shù)目不匹配 **

• 函數(shù)返回類型有誤

中間代碼生成

通常和語義分析一起實現(xiàn)。對語法分析識別出的各類語法范疇，分析他的含義，進(jìn)行初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼質(zhì)檢的一種代碼

常用的中間代碼表示形式

• 三地址碼 (Three-address Code)：三地址碼由類似于匯編語言的指令序列組成，每個指令最多有三個操作數(shù)(operand)

• 語法結(jié)構(gòu)樹/語法樹 (Syntax Trees)

• 逆波蘭式

三地址指令的表示：

• 四元式 (Quadruples)，(op, y, z, x)

• 三元式 (Triples)

• 間接三元式(Indirect triples)

  

下面圖中展示了一個中間代碼生成的例子

代碼優(yōu)化

對前面生成的中間代碼進(jìn)行加工變換，以便在最后極端產(chǎn)生更為高效的目標(biāo)代碼 ，需要遵循等價變換的原則，優(yōu)化的方面包括：公共子表達(dá)式的提取、合并已知量、刪除無用語句、循環(huán)優(yōu)化。

目標(biāo)代碼生成

把經(jīng)過優(yōu)化的中間代碼轉(zhuǎn)化成特定機(jī)器上的低級語言

目標(biāo)代碼的形式：

• 絕對指令代碼：可立即執(zhí)行的目標(biāo)代碼

• 匯編指令代碼：匯編語言程序，需要經(jīng)過匯編陳旭匯編后才能運(yùn)行

• 可重定位指令代碼：先將各目標(biāo)模塊連接起來，確定變量、常數(shù)在主存中的位置，裝入主存后才能成為可以運(yùn)行的絕對指令代碼

其他

出錯處理

如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤并報告給用戶。由專門的出錯處理程序來完成。錯誤類型：

• 語法錯誤：在詞法分析和語法分析階段檢測出來

• 語義錯誤：一般在語義分析階段檢測

• 邏輯錯誤：不可檢測，比如死循環(huán)，一般不處理因為沒辦法在編譯階段檢測出來

遍

指對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)代碼。遍與階段的含義毫無關(guān)系

多遍掃描： 優(yōu)點：節(jié)省內(nèi)存空間，提高目標(biāo)代碼的質(zhì)量，使編譯的邏輯結(jié)構(gòu)清晰。缺點：編譯時間長。在內(nèi)存許可的情況下還是遍數(shù)盡可能少較好

編譯程序生成

1. 直接用機(jī)器語言編寫編譯程序

2. 用匯編語言編寫編譯程序，編譯程序核心部分常用匯編語言編寫

3. 用高級語言編寫編譯程序，這也是普遍采用的方法

4. 自編譯

5. 編譯工具 LEX（語法分析）與YACC(用于自動生成LALR分析表)

6. 移植(同種語言的編譯程序在不同類型的機(jī)器之 間移植) 在某機(jī)器上為某種語言構(gòu)造編譯程序要掌握以下三方面:

• 源語言

• 目標(biāo)語言

• 編譯方法 編譯的基礎(chǔ)知識就是這些啦，后續(xù)會繼續(xù)深入的學(xué)習(xí)并記錄，喜歡麻煩點贊哈