文章目錄

• 編譯原理引論
• • （一）認識編譯程序
  • （二）編譯過程概述
  • • 1、階段劃分
    • 2、編譯程序的結(jié)構(gòu)
    • 3、編譯程序的生成

編譯原理引論

（一）認識編譯程序

什么是編譯程序？

這要從翻譯程序、解釋程序以及編譯程序的聯(lián)系與區(qū)別說起：

翻譯程序：把一種語言程序（稱為源語言程序）等價地轉(zhuǎn)換成另一種語言程序（稱為目標語言程序）的程序。

編譯程序是一種特殊的翻譯程序，編譯程序特指把某一種高級語言程序等價地轉(zhuǎn)換成另一種低級語言程序（如匯編語言或者機器語言程序）的程序。

在翻譯程序中，有一種方式和編譯程序不太一樣，即解釋程序：把源語言寫的源程序作為輸入、但不產(chǎn)生目標程序，而是邊解釋邊執(zhí)行源程序本身。

根據(jù)不同的用途和側(cè)重，編譯程序還可進一步分類。

• 診斷編譯程序：專門用于幫助程序開發(fā)和調(diào)試的編譯程序稱為診斷編譯程序
• 優(yōu)化編譯程序：著重于提髙目標代碼效率的編譯程序
• 如果一個編譯程序產(chǎn)生不同于其宿主機的機器代碼， 則稱它為交叉編譯程序
• 如果不需重寫編譯程序中與機器無關(guān)的部分就能改變目標機，則稱該編譯程序為可變目標編譯程序

編譯程序運行的平臺叫做宿主機
編譯后產(chǎn)生的目標代碼運行的平臺叫做目標機
通常這兩種平臺在同一臺機器上。

（二）編譯過程概述

1、階段劃分

編譯過程是一種語言的翻譯過程，它的工作過程類似于外文的翻譯過程。

比如英文句子翻譯成中文句子的大致過程是：

詞法分析：根據(jù)英語的詞法規(guī)則，從由字母、空格字符和各種標點符號所組成的字符串中識別出一個一個的英文單詞。

語法分析：根據(jù)英語的語法規(guī)則，對詞法分析后的單詞串進行分析、識別，并做語法正確性檢查，看其是否組成一個符合英語語法的句子。

語義分析：對正確的英文句子分析其含義并用漢語表示出來.

根據(jù)上下文的關(guān)系以及漢語語法的有關(guān)規(guī)則對詞句做必要的修飾工作。

最后翻譯成中文。

編譯過程一般分為以下五個階段（與自然語言翻譯過程對比）：

詞法分析

語法分析

語義分析與中間代碼產(chǎn)生

優(yōu)化

目標代碼生成

（1）詞法分析（掃描器）

• 任務(wù)：源程序 → 單詞符號串 （線性分析）。 即輸人源程序,對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞（亦稱單詞符號或簡稱符號），如基本字、標識符、常數(shù)、算符和界符（標點符號、左右括號等等）。

• 依據(jù)：語言的詞法規(guī)則

• 描述詞法規(guī)則的工具：正則式、正則文法、有限自動機

（2）語法分析

• 任務(wù)：單詞符號串 → 各類語法范疇 （層次結(jié)構(gòu)分析）。 即在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī) 則，把單詞符號串分解成各類語法單位（語法范疇），如“短語”、“子句”、“句子”（“語句”）、 “程序段”和“程序”等。通過語法分析，確定整個輸人串是否構(gòu)成語法上正確的“程序”
• 依據(jù)：語言的語法規(guī)則
• 描述語法規(guī)則的工具：上下文無關(guān)文法、確定的下推自動機

（3）語義分析與中間代碼產(chǎn)生

• 任務(wù)：語法范疇 → 初步翻譯、產(chǎn)生中間代碼。 即對語法分析所識別出的各類語法范疇，分析其含義，并進行初步翻譯（產(chǎn)生中間代碼）。這一階段通常包括兩個方面的工作。首先，對每種語法范疇進行靜態(tài)語義檢查，例如，變量是否定義、類型是否正確等等。如果語義正確，則進行另一方面工作，即進行中間代碼的翻譯。
• 中間代碼：獨立于具體硬件的記號系統(tǒng)，四元式、三元式、逆波蘭式等。（介于高級語言和低級語言之間）
• 依據(jù)：語言的語義規(guī)則
• 描述語義規(guī)則的工具：屬性文法

（4）優(yōu)化

• 任務(wù)：中間代碼 → 高效的中間代碼。 即在于對前段產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為髙效（省時間和空間）的目標代碼。優(yōu)化的主要方面有:公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等等。有時，為了便于“并行運算”，還可以對代碼進行并行化處理。
• 依據(jù)：等價變換規(guī)則
• 變換方法：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼、并行處理等

（5）目標代碼生成

• 任務(wù)：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機器上的低級語言代碼。這階段實現(xiàn)了最后的翻譯，它的工作有賴于硬件系統(tǒng)結(jié)構(gòu)和機器指令含義。

這階段工作非常復(fù)雜，涉及的主要問題：

• 指令的選擇
• 內(nèi)存的分配
• 寄存器的分配
• 目標代碼的形式：
  • 絕對指令代碼：這種目標代碼可立即執(zhí)行
  • 匯編指令代碼：需匯編器匯編之后才能運行
  • 可重定位的指令代碼（現(xiàn)代多數(shù)的情況）：在運行前必須借助于一個連接裝配程序把各個目標模塊（包括系統(tǒng)提供的庫模塊）連接在一起,確定程序變量（或常數(shù)）在主存中的位置, 裝入內(nèi)存中指定的起始地址，使之成為一個可以運行的絕對指令代碼程序。
    、

目標代碼形式為可重定位的指令代碼的背后其實支撐的是源代碼的模塊化。

2、編譯程序的結(jié)構(gòu)

（1）編譯程序總框

上述編譯過程的五個階段是編譯程序工作時的動態(tài)特樁。編譯程序的結(jié)構(gòu)可以按照這五個階段的任務(wù)分模塊進行設(shè)計

詞法分析器，又稱掃描器，輸人源程序,進行詞法分析，輸出單詞符號。

語法分析器，簡稱分析器，對單詞符號串進行語法分析（根據(jù)語法規(guī)則進行推導(dǎo)或歸約），識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”

語義分析與中間代碼產(chǎn)生器，按照語義規(guī)則對語法分析器歸約出（或推導(dǎo)出）的語法單位進行語義分析并把它們翻譯成一定形式的中間代碼。
有的編譯程序在識別出各類語法單位后，構(gòu)造并輸出一棵表示語法結(jié)構(gòu)的語法樹，然后，根據(jù)語法樹進行語義分析和中間代碼產(chǎn)生。還有許多編譯程序在識別出語法單位后并不真正構(gòu)造語法樹，而是調(diào)用相應(yīng)的語義子程序。在這種編譯程序中，掃描器、分析器和中間代碼產(chǎn)生器三者并非是截然分開的，而是相互穿插的。

優(yōu)化器，對中間代碼進行優(yōu)化處理。

目標代碼生成器，把中間代碼翻譯成目標程序

除了上述五個功能模塊外，一個完整的編譯程序還應(yīng)包括“表格管理”和“出錯處理”兩部分

（2）表格與表格管理

本質(zhì)是一個數(shù)據(jù)結(jié)構(gòu)，編譯程序在工作過程中需要保持一系列的表格，以査記源程序的各類信息和編譯各階段的進展狀況。

在編譯程序使用的表格中，最重要的是符號表。它用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。

此外，還有與管理、構(gòu)造、查找、更新有關(guān)的表格。

（3）出錯處理

任務(wù)：發(fā)現(xiàn)并向用戶指出源程序中錯誤的性質(zhì)和位置。如果可以的話，自動校正錯誤。

錯誤有以下類型：
詞法錯誤：不符合詞法規(guī)則
語法錯誤：不符合語法規(guī)則

• 非法字符、括號不匹配、缺少 ；、…

語義錯誤：不符合語義規(guī)則

• 說明錯誤、作用域錯誤、類型不一致、…

（4）遍（pass)：
遍：就是對源程序或源程序的中間結(jié)果從頭至尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標程序的處理過程。

比如小明一天五節(jié)課（對應(yīng)五個階段），其中有一節(jié)是勞動課，課程內(nèi)容是將垃圾運到垃圾處理區(qū)，第一次的路程（對應(yīng)第一遍），將可回收垃圾運過去了，第二次的路程（對應(yīng)第二遍）將不可回收垃圾運過去了。小明做這件事有了兩次路程（對應(yīng)兩遍）
如果小明一次性都運過去了，那么這一節(jié)課就只有一次路程（對應(yīng)一遍）。

可以把一個階段分為若干遍，也可以把多個階段合為一遍，通常有一遍和多遍編譯程序。

一個編譯程序究竟應(yīng)分成幾遍，如何劃分，是與源語言、設(shè)計要求、硬件設(shè)備等諸因素有關(guān)的，因此難于統(tǒng)一劃定。遍數(shù)多一點有個好處，即整個編譯程序的邏輯結(jié)構(gòu)可能清晰點（也可能有更多的優(yōu)化）。但遍數(shù)多勢必増加輸人/輸出所消耗的時間。因此，在主存可能的前提下，一般還是遍數(shù)盡可能少一點為好。應(yīng)當注意的是，并不是每種語言都可以用單遍編譯程序?qū)崿F(xiàn)。

（5）編譯的前端與后端：

前端（front end） ：由與源語言有關(guān)但與目標機無關(guān)的部分組成。
后端（back end） ：包括與目標機有關(guān)的部分。而一般不依賴于源語言，只與中間代碼有關(guān)的編譯階段。

3、編譯程序的生成

這個地方書寫的非常拗口，其實理解很簡單，就是我現(xiàn)在有一個簡易的編譯器A，它可以編譯A語言，A語言的語法雖然簡單，但是只要符合語法，編寫出來的代碼就能通過A編譯器的編譯，并能在計算機上執(zhí)行。
這個時候，我希望語法更豐富點，我就用A語言寫了一個編譯器B，編譯器B支持的語法更加豐富些，可以抽象成B語言，只要符合B語言的語法，編寫出來的代碼就能通過B的編譯，最終能夠在計算機上執(zhí)行（本質(zhì)上還是A的作用，只不過抽象了一層，編譯過程做了更多轉(zhuǎn)換的事情）。

這個就引出來一個方式、即自編譯方式：先實現(xiàn)語言的內(nèi)核編譯再進行自編譯擴展，先實現(xiàn)某語言的編譯再用該語言實現(xiàn)另一語言的編譯，即編譯—>編譯程序。

參考：陳火旺、劉春林等，《程序設(shè)計語言編譯原理》，國防工業(yè)出版社，第三版

總結(jié)

以上是生活随笔為你收集整理的【编译原理】引论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。