總結篇5 編譯器——Compiler

• 0 編譯器概述
  • 0-1 意義
  • 0-2 結構
  • 0-3 說明
• 1 界面
  • 1-1 虛擬機初始化
  • 1-2 解釋性虛擬機結構
  • 1-3 虛擬機生成器
  • 1-4 指令解析
• 2 結構
  • 2-1 解釋器環境
  • 2-2 解釋性虛擬機
  • 2-3 虛擬機
• 3 編譯
  • 3-0 指令組織
  • 3-1 簡單表達式編譯
  • 3-2 變數表達式編譯
  • 3-3 語句表達式編譯
  • 3-4 app表達式編譯
• 4 核心
  • 4-1 編譯入口
• 5 編譯實例
  • 5-1 實例入口
  • 5-2 編譯過程分析
  • 5-3 編譯結果組織

0 編譯器概述

0-1 意義

編譯器求值過程包括：編譯過程，安裝過程運行過程。

編譯過程 將高級語言的表達式翻譯為低級語言的指令序列

安裝過程 將指令序列安裝到虛擬機，並初始化虛擬機

運行過程 啟動虛擬機，依次運行安裝的指令序列

0-2 結構

界面 初始化編譯器虛擬機，啟動編譯虛擬機運行指令序列

結構 編譯器結構，解釋虛擬機，虛擬機

編譯 高級語言編譯低級指令序列

核心 高級語言編譯入口　　　

0-3 說明

SICP 5-5 編譯代碼注釋

裡面包含大量的前面總結篇解釋器,虛擬機的使用

1 界面

1-1 虛擬機初始化

;編譯性虛擬機入口(define (compile-and-gop expression) (let ;編譯生成的指令 ( (instructions (assemble (statements (compile expression val return) ) eceval ) ) ) ;初始化全局環境 (set! the-global-environment (setup-environment)) ;安裝指令到虛擬機 (set-register-contents! eceval val instructions) ;設置編譯模式啟動 (set-register-contents! eceval flag true) ;啟動虛擬機 (start eceval) ))

1-2 解釋性虛擬機結構

;解釋性虛擬機 總結篇-虛擬機擴展2(define eceval (make-machine (exp env val proc argl continue unev) eceval-operations (read-eval-print-loop) ))

1-3 虛擬機生成器

;虛擬機生成器 總結篇-虛擬機(define (make-machine register-name ops controller-text) (let ;生成虛擬機基礎結構 ( (machine (make-new-machine)) ) ;安裝擴展寄存器 (for-each (lambda (register-name) ((machine allocate-register) register-name) ) register-names ) ;安裝自定義操作指令 ((machine install-operations ) ops) ;安裝指令序列 ((machine install-instruction-sequence) (assemble controller-text machine) ) ;返回虛擬機 machine ))

1-4 指令解析

;指令解析 總結篇-虛擬機(define (assemble controller-text machine) (extract-labels controller-text ;extract-labels迭代完後返回的過程 (lambda (insts labels) (update-insts! insts labels machine) insts ) ))

2 結構

2-1 解釋器環境

;解釋器環境 總結篇-解釋器(define (setup-environment))

2-2 解釋性虛擬機

;解釋性虛擬機 總結篇-虛擬機擴展2(define eceval)

2-3 虛擬機

;虛擬機基礎結構 總結篇-虛擬機(define make-new-machine )

3 編譯

3-0 指令組織

3-1 簡單表達式編譯

自求值表達式編譯

主要包括數字，字元串的求值

; 數字 字元串求值(define (compile-self-evaluating exp target linkage) (end-with-linkage linkage (make-instruction-sequence () (list target) ((assign ,target (const ,exp))) ) ))

符號表達式編譯

符號表達式求值

;quoted表達式求值(define (compile-quoted exp target linkage) (end-with-linkage linkage (make-instruction-sequence () (list target) ((assign ,target (const ,(text-of-quotation exp))) ) ))

lambda表達式編譯

主要包括lambda編譯入口，lambda過程體編譯

;lambd表達式編譯入口，編譯lambda表達式結果到target(define (compile-lambda exp target linkage) ;lambda標號 (let ;lambda入口標號,lambda結束標號 ( (proc-entry (make-label entry)) (after-lambda (make-label after-lambda)) ) ;連接描述符 (let ( (lambda-linkage (if (eq? linkage next) after-lambda linkage ) ) ) ;生成lambda過程體表達式 (append-instruction-sequences (tack-on-instruction-sequence ;生成過程體入口指令序列 (end-with-linkage lambda-linkage (make-instruction-sequence (env) (list target) ( (assign ,target (op make-compiled-procedure) (label ,proc-entry) (reg env) ) ) ) ) ;過程體編譯指令序列 (compile-lambda-body exp proc-entry) ) ;過程體結束標號 after-lambda ) ) ))

;編譯lambda過程體 (define (compile-lambda-body exp proc-entry) (let ;形參 ((formals (lambda-parameters epx)) ;過程體指令 (append-instruction-sequences ;env環境擴展指令 (make-instruction-sequence (env proc argl) (env) ( ;過程體入口 ,proc-entry ;過程env參數 (assign env (op compiled-procedure-env) (reg proc) ;過程env擴展 (assign env (op extend-environment) (const ,formals) (reg argl) (reg env) ) ) ) ;過程體序列指令 (compile-sequence (lambda-body exp) val return) ) ))

3-2 變數表達式編譯

變數定義表達式(define)編譯

數值變數，lambda變數定義

;env中添加var的值為value(define (compile-assignment exp target linkage) (let ;變數名稱var，變數值 get-value-code ( (var (definition-variable exp) (get-value-code (compile (definition-value exp) val next) ) ) ;指令組合 (end-with-linkage linkage (preservin (env) ;變數求值指令序列 get-value-code ;變數定義指令序列 (make-instruction-sequence (env val) (list target) ( (perform (op define-variables!) (const ,var) (reg val) (reg env) ) (assign ,target (const ok)) ) ) ) ))

變數修改表達式(set)編譯

; 修改env中var的值(define (compile-assignment exp target linkage) (let ;賦值變數名稱var，賦值變數值get-value-code ( (var (assignment-variable exp)) (get-value-code (compile (assignment-value exp) val next)) ) ;賦值指令序列 (end-with-linkage linkage (preserving (env) ;求值賦值變數值 get-value-code ;變數賦值指令序列 (make-instruction-sequence (env val) (list target) ( (perform (op set-variable-value!) (const ,var) (reg val) (reg env) ) (assign ,target (const ok)) ) ) ) ) ))

變數查找表達式(variable)編譯

; env中查找變數var的值(define (compile-variable exp target linkage) (end-with-linkage linkage (make-instruction-sequence (env) (list target) ( (assign ,target (op lookup-variabel-value) (const ,exp) (reg env) ) ) ) ))

3-3 語句表達式編譯

條件表達式(if)編譯

;if表達式編譯(define (compile-if exp target linkage) (let ;if表達式的三個標號 ( (t-branch (make-label true-barnch)) (f-branch (make-label false-branch)) (after-if (make-label after-if)) ) ; (let ( ;if表達式連接符 (consequent-linkage (if (eq? linkage) next) after-if linkage ) ) (let ;謂詞編譯,真值表達式編譯,假值表達式編譯 ( (p-code (compile (if-predicate exp) val next) ) (c-code (compile (if-consequent exp) target consequent-linkage) ) (a-code (compile (if-alternative exp) target linkage) ) ) ;生成指令序列 (preserving (env continue) ;求值謂詞表達式 p-code ;根據謂詞表達式跳轉對應分支入口 (append-instructon-sequences ;分支跳轉指令 (make-instruction-sequence (val) () ( (test (op false?) (reg val) ) (branch (label ,f-branch)) ) ) ;入口指令 (parallel-instruction-sequences (append-instruction-sequences t-branch c-code) (append-instruction-sequences f-branch a-code) ) ) ;if結束指令 after-if ) ) ) ) ))

表達式序列(begin,sequence)編譯

(define (compile-sequence seq target linkage) (if (last exp? seq) ;最後一條表達式 (compile (first-exp seq) target linkage) ;組合表達式 (preserving (env continue) (compile (first-exp seq) target next) (compile-sequence (rest-exps seq) target linkage) ) ))

3-4 app表達式編譯

app表達式編譯入口

(define (compile-application exp target linkage) (let ( ;運算符編譯 運算對象編譯 (proc-code (compile (operator exp) proc next)) (operand-codes (map (lambda (operand) (compile operand val next) ) operands exp ) ) ) ;組合指令 (preserving (env continue) ;運算符指令序列 proc-code (preserving (proc continue) ;參數求值指令序列 (construct-arglist operand-codes) ;過程調用指令序列 (compile-procedure-call target linkage) ) ) ))

過程體參數求值指令序列

(define (constuct-arglist operand-codes) (let ;倒轉arg列表 ( (operand-codes (reverse operand-codes) ) ) (if (null? operand-codes) ;參數為空 (make-instruction-sequence () (argl) ((assign argl (const ()))) ) ;參數合成 (let ( (code-to-get-last-arg (append-instruction-sequences ;獲取第一個參數求值 (car operand-codes) ;合成參數求值指令序列 (make-instruction-sequence (val) (argl) ((assign argl (op list) (reg val))) ) ) ) ) ;檢查參數是否求值完 (if (null? (cdr operand-codes)) ;當前參數求值指令序列 code-to-get-last-arg ;合併多個參數求值指令序列 (preserving (env) code-to-get-last-arg (code-to-get-rest-args (cdr operand-codes) ) ) ) ) ) ))

參數求值循環

(define (code-to-get-rest-args operand-codes) (let ( (code-for-next-arg ;求值循環當前參數求值 (preserving (argl) (cdr operand-codes) (make-instruction-sequence (val argl) (argl) ((assign argl (op cons) (reg val) (reg argl)) ) ) ) ) (if (null? (cdr operand-codes) code-for-next-arg (preserving (env) code-for-next-arg (code-to-get-rest-args (cdr operand-codes) ) ) ) ) ))

過程應用調用入口指令序列

(define (compile-procedure-call target linkage) (let ( ;原子過程調用入口 (primitive-branch (make-label primitive-branch)) ;複合過程調用入口 (compiled-branch (make-label compiled-branch)) ) (let ;連接符 ( (compiled-linkage (if (eq? linkage next) after-call linkage ) ) ; (append-instruction-sequences ;過程調用分支跳轉指令 (make-instruction-sequence (proc) () ( (test (op primitive-procedure?) (reg proc) (branch (label ,primitive-branch)) ) ) ) ;過程調用指令 (parallel-instruction-sequences ;複合過程調用入口 (append-instruction-sequences compiled-branch (compile-proc-appl target compiled-linkage) ) ;原子過程調用入口 (append-instruction-sequences primitive-branch (end-with-linkage linkage (make-instruction-sequences (proc argl) (list target) ( (assign ,target (op apply-primitive-porocedure) (reg proc) (reg argl) ) ) ) ) ) ) ;過程調用結束標號 after-call ) ) ))

4 核心

4-1 編譯入口

編譯入口

在虛擬機的指令生成過程調用 見界面compile-and-go

;編譯入口(define (compile exp target linkage) (cond ;自求值表達式編譯 ( (self-evaluatin? exp) (compile-self-evaluating exp target linkage) ) ;符號表達式編譯 ( (quoted? exp) (compile-quoted exp target linkage) ) ;lambda表達式編譯 ( (lambda? exp) (compile-lambda exp target linkage) ) ;變數定義表達式define編譯 ( (definition? exp) (compile-definition exp target linkage) ) ;變數修改表達式set編譯 ( (assignment? exp) (compile-assignment exp target linkage) ) ;變數查找表達式variable編譯 ( (variable? exp) (compile-variable exp target linkage) ) ;if語句編譯 ( (if? exp) (compile-if exp target linkage) ) ;cond語句編譯 ( (cond? exp) (compile (cond->if exp) target linkage) ) ;begin語句編譯 ( (begin? exp) (compile-sequence (begin-actions exp) target linkage ) ) ;app表達式編譯 ( (application? exp) (compile-application exp target linkage) ) ;其他報錯 (else (error "Unknown expressions type --COMPILE" exp) ) ))

5 編譯實例

5-1 實例入口

(compile ;編譯語句 (define (factorial n) (if (= n 1) 1 (* (factorial (-n 1)) n ) ) ) ;求值結果寄存器 val ;連接符 next)

5-2 編譯過程分析

define表達式的編譯結果存儲到寄存器val，鏈接符使用next

調用compile-definition，編譯變數值存儲到val，編譯變數定義，最後寫入ok，後面是連接代碼,在變數值求值過程中需要保存env，在定義中使用

編譯變數值的過程使用是一個lambda表達式，調用compile-lambda,使用新標號作為過程入口點，生成指令，將這個新入口點的過程體組合到運行時的環境，並將結果賦值給val。編譯好的過程代碼被插入這個位置，需要跳過這些代碼

過程體使用compile-lambda-body編譯為一個序列，首先是擴充過程的定義環境，然後就是實際的過程體指令序列，

過程體指令需要使用compile-sequence編譯，將結果存儲到val中，並使用return返回。

在過程體指令序列中是一個if表達式，調用compile-if進行表達式編譯,保存編譯結果到val，並使用連接符return

5-3 編譯結果組織

; 編譯結果賦值(assign val (op make-compiled-procedure) (label entry2) (reg env)); 跳轉過程體(goto (label after-lambda1)); 過程體入口，過程調用時入口entry2; env擴展 (assign env (op compiled-procedure-env) (reg proc)) (assign env (op extend-environment) (const (n)) (reg argl) (reg env) ); if 謂詞求值環境壓棧 (save continue) (save env); if = 謂詞運算符 運算對象準備 (assign proc (op lookup-variabel-value) (const =) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookup-variable-vaue) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)); if 謂詞求值分支跳轉 (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch17))compiled-branch16 (assign continue (label after-call5)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val))primitive-branch17 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)); if 謂詞求值結果after-call15 (restore env) (restor continue) (test (op false?) (reg val)) (branch (label false-branch4); if-真表達式分支入口 true-branch5 (assign val (const 1)) (goto (reg continue)); if-假表達式分支入口false-branch4; 運算符 * (assign proc (op lookup-variable-value) (const *) (reg env)) (save continue) (save proc); 運算對象 n (asasign val (op lookup-variabel-value) (const n) (reg env)) (assign argl (op list) (reg val)) (save argl); 子運算符 factorial (assign proc (op lookup-variable-value) (const factorial) (reg env)) ) (save proc); 子運算對象 (- n 1) (assign proc (op lookup-variable-value) (const -) (reg env) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookup-variable-value) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)); 調用分支檢測 (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch8)compiled-branch7 (assign continue (label after-call6)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val))primitive-branch8 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)); val = (- n 1)after-call6 (assign argl (op list) (reg val)); factorial (restore proc) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch11))compiled-branch10 (assign continue (label after-call19)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val))primitive-branch11 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)); val = (factorial (- n 1))after-call9 (restore argl) (assign argl (op cons) (reg val) (reg argl)); * 運算符求值 (restore proc) (restore continue) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch14))compiled-branch13 (assign val (op compiled-procedure-enrty)(reg proc)) (goto (reg val))primitive-branch14 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) (goto (reg continue))after-call12after-if3after-lambda1;最後 定義表達式 (perform (op define-variable) (const factorial) (reg val) (reg env) ); 定義成功的返回值 (assign val (const ok))

推薦閱讀：