PL真有意思(一):引言

前言

斷斷續續學編譯原理到之前發過寫一個編譯器和正則表達式引擎系列文章也有一段時間了,然後最近看完PLP這本書,這本書應該算是入門書,但是對我這種半吊子收穫很大。所以為了彌補最近學操作系統和接外包摸的魚,就想寫寫看完這本書的收穫。(為拙劣的標題道歉

程序設計語言的譜系

現在的新語言都是一撮一撮的出來,但是基本都可以用他們的計算模型來分成兩類,一類是更關心計算機做什麼的說明式,一類是更關心計算機怎麼做的命令式

一般認為像函數式邏輯式語言都算是說明式,而馮諾依曼式和面向對象的都被認為是命令式

函數式

函數式是基於函數的遞歸定義的計算模型,一般從本質上來看,函數式把程序認為是一種從輸入到輸出的函數,使用更簡單的函數通過逐步細化的過程來定義

邏輯式

邏輯式里經典的應該就是Prolog了,邏輯式一般將計算看作是一種找出滿足某些特定關係的值的嘗試過程

馮諾依曼式

馮諾依曼式最重要的就是通過副作用也就是修改寄存器里的值來對後續計算產生影響,像C和Fortran都屬於馮諾依曼式

幾個例子

如果C語言來實現求最大公約數,可以發現C語言偏向通過迭代和反覆修改變量的值來實現

int gcd(int a, intb) {
    while (a != b) {
      if (a > b) {
        a = a - b;
      } else {
        b = b - a;
      }
    }
}

從lisp來看,則更加關注輸入和輸出的數學關係,要算出最大公約數,需要對函數的不斷的擴充和精簡

(define gcd
  (lambda (a b)
    (cond ((= a b) a)
          ((> a b) (gcd (- a b) b))
          (else (gcd (- b a) a)))))

對於像C或者Java入門的人,看到Prolog可能頭都大了,因為Prolog和命令式的思考邏輯完全不同,邏輯式更傾向給出一組公理和檢測規則,期望系統能給出相應合理的值,我也僅限於能看懂這些小程序

gcd(A,B,G) :- A = B, G = A.
gcd(A,B,G) :- A > B, C is A - B, gcd(C,B,G)
gcd(A,B,G) :- B > A, C is B-A
gcd(C,A,G)

編譯和解釋

下面再看兩個概念,編譯和解釋。

編譯一般是指從一個語言到另一個語言的翻譯,無論是高級語言到彙編還是高級語言到高級語言都算是編譯。而解釋就是直接執行代碼,但是現代的解釋器,一般還有虛擬機一層,即翻譯到虛擬機指令再由虛擬機進行執行

自舉

很多語言的編譯器都是由自己編譯而成的,所以問題就是,最開始的編譯器是怎麼編譯的?

假設現在要為Java編寫一個編譯器,我們可以先用C語言編寫一個Java小子集的編譯器,然後再手動將C語言翻譯到這個Java子集,就可以由這個子集編譯運行自己,然後就可以不斷擴充這個編譯器

編譯概覽

其實這個在之前那個寫編譯器的系列是說得最詳細的,這個系列是想要寫寫筆記對實踐和語言設計結合的說。

  • 詞法分析

有關詞法分析其實就是將字符流化成單詞流,記錄每個單詞的信息,然後通常還會有其它更多的信息讓編譯器更好的生成錯誤信息

  • 語法分析

語法分析通常會用到一個概念:上下文無關文法,就是用來定義語法形式的,比如while語句就可以這樣表示

while-statment := WHILE ( expr ) statment

一般語法分析過程最後的輸出都是樹狀結構

  • 語義分析和中間代碼生成

語法分析只保證源代碼語法格式的正確,但是卻不能保證其它的正確性,比如對於靜態類型的語言,可能就會在編譯時直接檢測出類型錯誤

而在語義分析過程一般還需要藉助一個叫做符號表的數據結構,這個符號表將每個標識符都映射到關於它的已知信息

中間代碼的生成通常是會將樹形結構翻譯成更接近彙編的中間線性格式,但是中間格式不是必須的,比如之前那個系列里還寫了C的解釋器,雖然很殘缺,它是沒有中間代碼的,連虛擬機都沒有,是直接進行遍歷語法樹進行執行解釋的

  • 代碼優化

有些代碼改進是機器無關的,即可以在中間格式上就進行優化,但是有的代碼優化是平台相關的,所以就需要在最後對目標語言優化

  • 目標代碼生成

代碼生成階段就是根據之前生成的線性結構和符號表信息對目標代碼的生成

小結

這一篇主要說了幾個範式的語言和編譯過程的概括,對摸魚進行懺悔

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象