C編譯器入門~想懂低階系統從自幹編譯器開始~
  • 譯者序
  • 前言
    • 符號與規範
    • 本書的開發環境
    • 關於作者
    • 結束前言之前
  • 機械語言與組譯器
    • CPU 與記憶體
    • 什麼是組譯器
    • C程式和所對應的組合語言
      • 簡單的範例
      • 包含呼叫函式的範例
    • 本章小結
  • 創造計算機等級的語言
    • 第1步:創造能編譯1個整數的語言
    • 第2步:製作可以算加減法的編譯器
    • 第3步:加入標記解析器(tokenizer)
    • 第4步:改良錯誤訊息
    • 文法的記法與遞迴下降分析法
      • 將文法結構表示為樹(tree)
      • 以生成規則定義文法
      • 以 BNF 描述生成規則
      • 簡單的生成規則
      • 以生成規則描述運算子的優先順序
      • 包含遞迴的生成規則
      • 遞迴下降語法分析
    • 堆疊機
      • 堆疊機的概念
      • 編譯成堆疊機指令
      • 以x86-64實作堆疊機的方法
    • 第5步:製作可進行四則運算的編譯器
    • 第6步:單項加與單項減
    • 第7步:比較運算子
      • 修改標記解析器
      • 新的文法
      • 產生組合語言指令
  • 分離編譯與連結
    • 分離編譯
      • 分離編譯與其必要性
      • 標頭檔的必要性與其內容
      • 連結錯誤
      • 全域變數的宣告與定義
    • 第8步:分割檔案與修改 Makefile
      • 分割檔案
      • 修改 Makefile
  • 函式與區域變數
    • 第9步:1個字的區域變數
      • 堆疊上的變數空間
      • 修改標記解析器
      • 修改分析器
      • 左邊值與右邊值
      • 從任意的記憶體位址取得其值
      • 修改指令產生器
      • 修改主函式
    • 第10步:複數文字的區域變數
    • 第11步:return
    • 1973年的C編譯器
Powered by GitBook
On this page

Was this helpful?

  1. 創造計算機等級的語言
  2. 堆疊機

編譯成堆疊機指令

Previous堆疊機的概念Next以x86-64實作堆疊機的方法

Last updated 5 years ago

Was this helpful?

本節會說明把抽象語法樹轉成堆疊機程式的方法。只要做到這點,我們就可以把四則運算的式子分析、建構抽象語法樹,編譯讓以x86-64語法建構的堆疊機可以執行的程式。也就是我們要可以寫出能編譯四則運算的編譯器了。

堆疊機在計算算式的一部份的時候,不論什麼結果,會將1個結果值留在堆疊的頂端。舉例來說我們考慮以下的樹:

A和B是部份算式抽象化的表現,實際上是代表某種型態的結點。不過,該型態具體是什麼、樹的形狀如何,在編譯時並不重要。編譯此樹只要照著下面的步驟:

  1. 編譯左邊的子樹

  2. 編譯右邊的子樹

  3. 輸出把堆疊上的2個元素相加,換成加法的結果的指令

執行1.的程式之後,不管該程式是什麼,堆疊頂端應該放著1個代表左邊子樹結果的值。同理,執行2.的程式之後,堆疊頂端應該放著1個代表右邊子樹結果的值。於是,要計算整個樹的值,就只要把這2個值相加,以合計的值取代就好了。

如此,把抽象語法樹編譯成堆疊機指令時,只要遞迴地思考,從樹的最下方逐步輸出組合語言指令就好了。對遞迴思考不習慣的讀者來說可能有點難,但是遞迴是處理樹結構時的基本。處理像樹這樣自己和自己的內部呈相似形的資料結構時,需要用同樣的方式對待部份和全體,也就是同樣的函式要可以用同樣的方法去處理全體、部份、甚至部份的部份。

我們用以下的範例來具體思考:

產生程式的函式的輸入是樹的根結點(root node)。

按照上述的流程,該函式從左子樹開始編譯。也就是先編譯數值2。2的計算結果就是2,這個子樹編譯的結果就是PUSH 2。

接下來產出程式的函式要編譯右子樹。然後就會遞迴地編譯到子樹的左子樹,輸出PUSH 3。之後編譯子樹的右子樹,輸出PUSH 4。

然後產出程式的函式就會返回到呼叫的地方,根據子樹運算子的型態輸出對應的程式。首先輸出的是把堆疊頂端的2個元素相乘結果的指令,再來是把堆疊頂端的2個元素換成其相加結果的指令。底下就是最後輸出的組合語言指令:

PUSH 2
PUSH 3
PUSH 4
MUL
ADD

使用這樣的手法,就可以機械性地把抽象語法樹轉換成組合語言指令。

表示加法的抽象語法樹
表示加法和乘法的抽象語法樹