(本文首發於i春秋,本人為本文原作者,目前該編譯器及虛擬機已經在Github中開源,歸屬於PainterEngine項目中)

matrixcascade/PainterEngine?

github.com圖標

在說些什麼實現的東西之前,筆者仍然想話嘮嘮叨下虛擬機這個話題,一是給一些在這方面不甚熟悉的讀者簡單介紹下虛擬機的作用和包治百病的功效,二來是題頭好好吹一吹牛,有助於提升筆者在讀者心中的逼格,這樣在文中犯錯的時候,不至於一下就讓自己高大上的形象瞬間崩塌。

是的，當前虛擬化技術已經在計算機及互聯網中烈火燎原了，從伺服器到個人PC上直至手機甚至手錶上，幾乎都離不開它的身影，儘管當前說起虛擬機，更多的人想到的是Java是運行在JVM上的，而JVM是個虛擬機，或者大家非常熟悉的虛擬機軟體VMWare或者是Virtual Box，KVM等大牌虛擬機軟體。但實際上虛擬化技術早而有之甚至不那麼容易界定明顯，例如，我們在PC上想玩紅白機遊戲，那麼FC模擬器就是個虛擬機，我們想在PC上做做電路實驗，試試我們在89C51上編寫的跑馬燈好不好使，proteus也是虛擬機,甚至於做做虛擬儀器的業內標杆軟體Labview,這個無需解釋估計是最直觀的虛擬機了,大多數虛擬機本質上是執行在宿主的一款程序,對宿主機CPU沒辦法直接執行的指令位元組流或別的一些什麼東西進行解釋執行,最終達到某種功能或目的的一種程序,那麼按照這種推論,瀏覽器裏的JavaScript,Lua腳本語言運行環境,或者是Python算不算虛擬機呢,實際上大多數人更願意使用解釋器來描述這些語言的執行環境,但是不管怎麼說,乍看之下其似乎也完全符合虛擬機的特性,不管是文字解釋還是將代碼編譯為位元組流再進行解釋本質上並沒有多少區別,因此筆者認為將它們歸為虛擬機也一點毛病也沒有,糾結這些毫無意義.

那麼簡單來講虛擬機到底是什麼呢,簡單來說,假如你只會中文而不會英文,某天一個老外要和你交談,語言不通怎麼辦,請翻譯啊,那麼,這個翻譯的作用就像虛擬機.

為什麼我們要設計一個虛擬機

相信在文章的開篇就有人跳出來提出這個問題了,為什麼要自己做個虛擬機,現在那麼多現成的執行體系不好麼,為什麼要重複造輪子,何況這個輪子還未必有別人的圓,當然筆者寫這篇文章的目的也並不是吹噓自己寫的虛擬機有多好,但筆者相信只要你在計算機開發的遊戲引擎或二進位安全或圖形圖像或是人機交互PLC工控…等等等領域之一混的足夠久,你就會知道自己擁有自己的一套虛擬機系統所帶來的好處和必要性了,筆者相信時間和經驗會告訴你做一件事有沒有這種必要,而別人說再多話也是別人說的,當然,就像別人設計的虛擬機再好也是別人的,自己設計的虛擬機再挫也是自己的.當你在一套虛擬系統中有所疑惑或者是需要額外的功能實現時,你就知道」就算別人的花兒再漂亮,自己種的終歸是自己種的」這句話的深刻含義了.

那麼,一套虛擬機系統有什麼好處呢?筆者總結了部分功能.

  1. 跨平臺使用,在這臺機器上是這套虛擬機指令集,在另一套計算機上也是同樣的虛擬機指令集,一次開發,永久奔放,當然,你必須也保障目標機能夠移植你的虛擬機。

  1. 執行環境可控，畢竟每一條指令都由虛擬機負責解釋執行，這意味著可以對程序執行的每一個流程進行控制，虛擬機作為一個沙盒環境，對許可權控制，調試都有諸多好處。尤其是在許可權的控制中，可以避免一些惡意程序對原生系統的破壞，當然，這有沒有讓你有種主宰世界的感覺。
  2. 二進位安全，當然目前最讓人頭疼的是一款軟體剛發布又讓人給破解了，當然，破解工作必然的涉及到了軟體的逆向工程，逆向工程就必然和指令集運行環境有所關聯了，當然早期的反逆向技術主要花心思在如何檢測調試器上了，然而當開發了一種檢測調試器的手段，逆向人員很容易就找得到應對的方法，因此，檢測調試器的手段發展到今天基本作為一種備用手段了，雖然說理論上世界上不存在不能被破解的軟體，但是當一款軟體的破解難度遠遠大於其本身價值的話，那麼這款軟體被破解的可能性就變得很低了，那麼為什麼軟體容易被破解呢，很多時候是因為大家都熟悉這套框架這套指令集這套運行原理，用的人多了，資料就多了，資料多了，那程序就沒啥隱私了，但是如果自己設計一套全新的指令集和框架結構的虛擬機的話，要破解運行在這個虛擬機上的軟體，就意味著攻擊者必須熟悉這個指令集和框架的原理，好了，現在問題就變成了當你面對一個運行在全新的架構全新的指令集上的程序時，你有幾年的青春可以揮霍了，當前反調試技術並非是讓人做到無法破解，而是需要花大於程序本身的價值的精力去破解，正因如此，虛擬機尤其是自己設計的虛擬機成了反逆向分析中的「寵兒」。

當然如果說讀者讀完這篇文章就能馬上擼出一個虛擬機+完整的編譯系統,那真是難為筆者了,這也就是為什麼題目中筆者加了導引兩個字,這是一個龐大的工程,筆者無法在寥寥萬餘字中將每一個技術細節都說明白,當中涉及的東西太多不僅在書裏更要在實現中去體會而不是紙上談兵(相信我,那些把編譯理論吹得稀爛的大多自己也沒有寫過編譯器最多就使用LLVM描了個邊,當他們真正從底層去處理詞法和語法上的問題基本也是一臉懵,那一刻就會體會到真正要他們解決的玩意書和那套聽不懂的裝逼理論並不會告訴他們),雖然書不能幫你解決所有問題,但筆者仍然向有興趣寫編譯器虛擬機的推薦<<編譯原理>><<遊戲腳本高級編程>>這兩本書,前者有一套完整的編譯理論的構架對學習編譯優化非常有好處,當然其實很大一部分理論用不到,後者那本書則是結結實實的寫了一套完整的虛擬機和編譯器,不過也厚的多,足足2本書近千頁的內容(當然,還是無法完全提及每一個技術細節:),但非常有參考價值值得一讀.最後是筆者的這篇文章了,是的,雖然無法讓讀者直接寫出個編譯器和虛擬機,但是至少可以說個大概,2w字的篇幅說長不長說短不短,半個小時就能讀完,買不了喫虧買不了上當,可以讓你初略地瞭解下虛擬機和編譯器到底是怎麼回事.

虛擬機開發前的準備工作

在碼農界設計一個虛擬機一直被當做高端大氣上檔次的事.然而事實上虛擬機的設計並沒有什麼複雜的內容,乃至於說解釋器裏的語法和詞法分析都比虛擬機複雜的多,當前,假如你想設計一款和VMWare或者Virtual Box一樣的的虛擬機軟體,那當我之前的話沒說,在本文中,筆者通過設計一款較為簡單的虛擬機程序並且在虛擬機完成我們需要的功能.

因此,在開始這個項目之前，我們首先要確立以下目標

  1. 我們要虛擬機主要功能是什麼，功能的不同，將很大程度改變虛擬機的架構，例如是我們的虛擬機實作為遊戲引擎的腳本控制，那麼我們的指令設計就應該儘可能的精簡穩定並便於優化，這樣使用虛擬機設計的遊戲引擎纔不至少不至於在虛擬機方面卡成PPT讓每一個玩家罵娘，而如果是做演算法的反逆向保護，那麼我們就要好好的藏好我們指令集「真正的」功能，甚至不做優化讓破解者繞圈圈，這個時候冗餘設計反而有助於保護我們的演算法。
  2. 我們的虛擬機開發環境是什麼，用在什麼地方，當然，這包括使用什麼語言，什麼環境來開發我們的虛擬機都在考慮的範圍之內，當然，當前相當一部分有名的虛擬機環境都選擇使用C語言進行開發，這有很多好處，首先目前絕大部分的運行環境都提供C語言的編譯器，虛擬機寫好後，可以非常方便地在多平臺進行移植，再者只要編譯器給力，C語言編譯出來的指令流相對執行效率優秀，這對容易帶來明顯性能損失的虛擬機尤為有利，最後，C語言學習較為容易，學習成本不高，能讓我們把更多的注意力放在「如何實現」而不是「如何讓別人覺得我代碼語法糖寫的有多牛逼」上。
  3. 我們的虛擬機的指令集如何實現，當然這是一個籠統的說法，這還包括如何我們虛擬機如何對內存進行管理，需要哪些寄存器，這些寄存器分別由什麼用，指令的數據結構是怎麼樣的之類多種的問題，不過不用擔心，我們有很多現成的指令集可以供我們參考,例如MIPS這種指令集至今仍作為眾多CPU粉樂於用虛擬機模擬實現的指令集,這原於這個指令集的精簡併容易實現,因此每年的畢設上,總能看到相關的設計論文,相對的x86 ARM指令集就複雜得多,但不用擔心,我們可以學習他們部分的實現,管中窺豹可見一斑,即使我們只完成了一部分實現,對於我們的虛擬機而言,大部分的功能也足夠實現了.
  4. 如何設計調試器方便我們的虛擬機調試,這個是非常重要的一點,假如你設計的虛擬機沒有對應的調試方案,那麼即使是作為虛擬機作者的你編寫的虛擬機程序進行親自調試,也將會是一場噩夢,因此在你真正動手開發虛擬機之前,你最好想好你的調試器如何架構在你的虛擬機之上.
  5. 虛擬機的運行方式及IO,簡單來說就是你得想好你的虛擬機如何去解析指令執行,另外虛擬機執行完後也不能光運行啊,演算法把結果算出來了總得把結果輸出來,這就涉及到了虛擬機和本地代碼的數據交互,這些都需要提前考慮好.
  6. 虛擬機的異常處理方式,老規矩,除0異常,越界訪問,無效指令,內存不足…不管你設計的虛擬機再如何的優秀,如果沒有異常處理方式,那就是一句話」怎麼死的都不知道」,因此不管你設計哪一種虛擬機,你最好先把算盤打好當出現這些異常的時候,你的虛擬機應該如何應對.

架構一個虛擬機

給虛擬機項目個名字和LOGO

項目開始的第一步,自然沒多少難度,不過但凡幹大事者,都要先立個名號,雖然說這並不算什麼大事,但筆者自認為是一個比較中二病的人,因此,左思右想還是得給這個虛擬機項目取個名字.比如終結者,雙子星,地球毀滅者,宇宙收割機之類的,不過好像又過了那個年紀,還是務實一點,當然,本篇文章的事例虛擬機取自筆者早前已經寫好的一個虛擬機項目,它被用在遊戲引擎,嵌入式系統控制及UI界面當中,名字是早已訂好了叫StoryVM,屬於StoryEngine(遊戲/圖像引擎)的一部分

至於為什麼叫StoryVM,筆者自己也不是很清楚.就覺得叫著舒服,當然,本篇文章的目的也是告訴大家這個虛擬到底如何實現的,讀者們如果有興趣,不妨也花點時間為自己的虛擬機項目起個霸氣的名字和LOGO,萬一火了,那麼就可以為這個虛擬機名字怎麼來的想個故事了.

認識馮諾依曼結構和哈佛架構

在開始部署我們的虛擬機程序之前,我們先來複習一下計算機專業的經典知識點,馮諾依曼的計算機體系結構和哈佛結構,相信計算機系的看官們應該並不陌生畢竟多多少少都有幾位是栽在他們手上的

馮諾依曼和哈佛結構主要的不同點是程序和運行數據是否是存儲在同一個空間中,實際上兩種體系虛擬機都能夠實現,畢竟時間有限,因此,筆者無法將兩種體系的虛擬機實現都說一遍,出於演示和儘可能偷懶原則,筆者在本文中採用的是哈佛結構體系的虛擬機架構,為什麼使用哈佛結構(程序和數據分開存儲)呢,其中有以下幾點好處

  1. 從執行安全性考慮,方便進行越界檢查,當指令地址不在指令的存儲範圍內時,肯定是無效指令越界訪問了.
  2. 二進位漏洞十有八九都是越界訪問或者缺少邊界檢查的數據修改造成的,程序修改程序造成遠程代碼執行的事兒咱們也不是第一天見過了,因此,分開存儲有利於提高腳本的安全性與可控性.
  3. 簡單啊,寫起來方便啊,偷懶舒服啊,分開存儲意味著很多時候你不必再使用多個數據費力尋找數據的真實偏移量了,實際上筆者在虛擬機的實現過程中,將字元串,文本,內存,寄存器空間全部分開存儲.

那麼,這個虛擬機的數據空間看起來是怎麼樣的呢:

是的,筆者將虛擬機的各個數據都進行分類存儲,一來不僅便於訪問,二則方便管理及許可權控制,只要設計得當,常量區的只讀數據就能得到很好的保護,程序代碼區也不會被修改,需要注意的是,筆者仍然將棧空間和堆空間設計在同一空間裏,當然這是有一定原因的,這點我會在後面的章節中說出原因.

元數據

那麼從現在開始,我們就要開始接觸一些編碼方面的東西了,當然,為了保證這篇文章儘可能的受眾面廣,筆者並不打算過於地強調用何種語言來編寫這個虛擬機,但筆者編寫這個虛擬機使用的是C語言進行開發的,因此在很多的地方,仍然不可避免需要使用C語言中的一些代碼對功能的實現進行說明,明顯的,本文並不打算寫有關C語言怎麼寫之類的問題,因此如果讀者不熟悉C語言的話,筆者仍然建議讀者自行查閱相關資料.

在虛擬機開發的第一步,我們先來瞭解一下元數據

什麼是元數據呢,簡單來說就是虛擬機能夠定義的最小單位,我們以C語言為例,C語言排除結構體和修飾符外,那麼能夠定義char short int float double long….等幾種類型,其中,char類型不論在哪種編譯器下必定佔據一位元組,排除位域或編譯器額外的實現,char是C語言能夠定義的最小數據大小,因此我們稱char為元數據類型

而在Basic語言中,定義則簡單的多,可以直接使用dim a=3141,或者dim b=」hello world」來定義類型,在這個時候,類型所需的內存空間不再是一個定數.在這裡定義的元數據類型可以是一個整數小數或者是字元串類型.

在很多的情況下,我們把類似於C語言的類型稱為強類型,表示類型間無法直接相互轉換,而Basic則稱為弱類型,不同類型間可以相互轉換.

當然,對於那些依靠CPU直接執行的指令,基本不會採用弱類型的數據訪問方式,這將導致電路實現過於複雜,但是虛擬機完全可以採用弱類型的方式來編碼數據的訪問,這主要有以下幾個優點.

  1. 編寫程序時簡便的多,這意味著開發虛擬機程序時不用花過多的心思在數據轉換上
  2. 寫起來方便,看起來直觀,比如」Hello」+」World」這樣的字元串相加運算,順手
  3. 不需要再關注一些例如字元串類型帶來的內存管理上的麻煩,這些都由虛擬機適時分配與回收(garbage collection)

當然,弱類型帶來了優點,缺點也不少

  1. 顯然的,虛擬機的實現要複雜的多,必須考慮資源分配、深淺拷貝、垃圾回收等問題。
  2. 必定帶來性能損失，尤其是面臨深拷貝和垃圾回收。
  3. 不論內存管理如何優秀，這種分配回收機制都不可避免引發更多的內存碎片
  4. 對一些特殊類型的操作,比如字元串,可能需要額外增加一些關鍵字來加強對類型功能的使用,比如字元串不可避免需要引入strlen函數統計其長度,或者用[]運算符修改其某個字元.
  5. 容易引發語法上的歧義，例如一個字元串類型和一個整數類型相加，如何定義？例如

「數字:」+4294967295的結果應該是字元串』』數字:4294967295」麼?,要知道,4294967295在32位類型中和數字-1是一樣的,如果」數字:」+4294967295是字元串」數字:4294967295」那」數字」+-1又該是什麼,你可以說給類型定義有符號還是無符號的標識啊,那麼好,定義一個類型為100,那麼這個100是有符號還是無符號的,你可以說加修飾符來修飾啊,那問題又來了,既然要加修飾符,那我還用弱類型做什麼,繞個彎子再自找麻煩麼.

總結了弱類型的幾個好處,但同時我們也發現其糟糕的地方也不少,那我們虛擬機需要設計成支持弱類型的訪問麼,當然要,弱類型有如此多的好處,不能因為他存在某些缺點就全盤否定,但這也是為什麼本章標題筆者起名為元數據而非」都聽好了,我們要設計一個弱類型數據訪問型的虛擬機」,為了規避弱類型訪問的一些缺點,我們需要對虛擬機的數據結構進一步改造,我們可以這樣規定,一個元數據(可能是常規寄存器,堆棧裏的某一數據)可以是一個整數,小數,或者是字元串或數據流類型,但是,不同的數據類型不能夠直接進行運算,需要使用特殊的指令進行操作,這樣我們就解決了弱類型帶來的歧義的問題.

說完了理論,我們來看看實踐,我們先來看看C語言如何定義一個元數據

typedef struct
{
int type;
union
{
char _byte;
char _char;
word _word;
dword _dword;
short _short;
int _int;
uint _uint;
float _float;
string _string;
memory _memory;
};
} VARIABLE;

觀察結構體VARIABLE定義,其中type表示該變數的類型,在該虛擬機中,有如下枚舉定義

typedef enum
{
VARIABLE_TYPE_INT,
VARIABLE_TYPE_FLOAT,
VARIABLE_TYPE_STRING,
VARIABLE_TYPE_MEMORY,
} VARIABLE_TYPE;

VARIABLE_TYPE_INT,表示這個數據是一個整數類型定義,

VARIABLE_TYPE_FLOAT表示這個數據是一個浮點類型,

VARIABLE_TYPE_STRING表示這是一個字元串類型定義

VARIABLE_TYPE_MEMORY 表示這是一個數據流類型

接下來是一個聯合體,數據類型公用一塊內存儘可能節省一個元類型佔用的內存空間

數據表達方式

如果在高中數學的角度上來說,6和6.00這兩個數字並沒有什麼區別,6.00後面的兩個0可以省略,但是在很多的編程語言當中,6和6.00有著本質上的區別,6是一個整數,6.00是一個浮點數,它們在內存中的佈局常常天差地別,同時,6/4和6.00/4的結果也截然不同

筆者在本章開頭寫這個,目的並不是給讀者講解整數和浮點數編碼的區別,而是希望提及一點,數據的不同寫法所表達出的數據也截然不同,那麼StoryVM支持幾種數據呢,在上一章節我們已經講過元數據的組成方式,從結構體定義我們可以看到,支持char short int uint float string memroy幾種類型(word ,dword..本質上是unsigned short和unsigned int),但是筆者並不打算讓StoryVM關注於如此多的類型,因此,在筆者設計的StoryVM中,僅僅支持int float string memroy四種類型

讀者可能會表示疑問.如果我需要表示一個無符號數,或者只需要表示一位元組那怎麼辦,int類型不是隻能表示有符號整數呢

其實按照讀者的設計,在方便的時候,數據長度可以寧多不寧少,int類型完全可以用來表示位元組類型,無非是使用時自己注意點將它當做位元組類型來用時不要超過255就行了,而有符號無符號類型在內存中表示其實並沒有什麼出入,例如,-1和4294967295在內存中並沒有什麼區別,而有符號數適用面更為廣泛,至於到底顯示出來時是有符號或者是無符號,完全可以靠自己把握.

在StoryVM中,如何使用彙編表示一個數據類型呢

顯然的 int類型可以直接使用數字來表示,例如 12345,這個是一個合法的int類型,當然,為了方便,還引入了十六進位表達,例如0xffffffff也是一個合法的int類型,當然,需要注意的是StoryVM最大支持32位的整數類型,這也意味著十六進位範圍是0~0xffffffff,最後是字元類型,例如『A』表示字元A的asc碼值,也是一個合法的整數類型,』B』表示字元B的ascii碼值…..以此類推

Float類型應該無需筆者多說了,1.0,3.14,6.66都是合法的float類型

String也就是字元串類型和C語言的字元串表示保持一致,」Hello World」這就是一個合法的字元串類型,用雙引號包含,當然,和C語言有些不同的是,字元串類型中僅支持
三種類型轉義

最後是數據流類型,這個是StoryVM中自定的一種數據類型,理解起來並不複雜,例如

@0102030405060708090A0B0C0D0F@這就是一個數據流類型,一個數據流類型使用兩個@包含,當中的文本是一個十六進位表示的數據流,兩兩為一對為一位元組,這也就意味著當中的字元數必須在範圍0-F中,並且必定是偶數個.

指令集數據結構

在開始設計具體的指令前,我們先來考慮下虛擬機指令集如何設計,當然,當前的指令集大多以如下的模式設計:

其中,操作碼錶示這條指令的具體作用,例如x86彙編中的MOV eax,1中的mov就是操作碼

緊接在操作碼之後的是操作數類型(或者也可以叫參數類型),例如上上面這條彙編指令中一共有2個操作數(參數),分別是eax和數字1,它們分別表示一個寄存器類型和一個立即數類型,最後是操作數了,也就是我們常說的參數.

當然,上述的規則適用於大多數的指令編碼格式,對於一些非常常用的指令,甚至會將一些操作數給」集成」到操作碼中,例如上述的MOV eax,1指令中,mov eax,被直接用E8代替,而操作數1則直接使用一個dword來設置,在這條指令中,只有一個操作碼和一個操作數.

如此的設計可以保證編譯的程序儘快能的小,但是作為代價,執行對於的指令集的CPU或虛擬機也需要設計更多的實現而變得越來越複雜

設計出x86類似的複雜指令集需要耗費大量的心血,但在我們的虛擬機系統中,我們無需使用如此複雜的指令集設計

筆者斟酌了定長指令和不定長指令的一些特點,設計出如下的一套指令集規範

  1. 操作碼以1位元組進行標識
  2. 接著是3位元組的操作數類型
  3. 依據指令類型最終決定之後跟幾個操作數,每個操作數都是一個4位元組寬度的類型

這意味著我們的指令設計每個指令至少佔4位元組寬度,並且最多隻能接受3個操作數.

寄存器設計

在CPU設計,寄存器用於數據的暫存,在電路設計中,這不同的寄存器被賦予不同的意義,在筆者的虛擬機架構中,並不需要關注電路設計如此複雜的內容,但筆者仍然將寄存器設計分為兩種寄存器,一種是臨時數據寄存器,一種是特殊寄存器.

其中,臨時數據寄存器本質上就是之前提到的元數據,它與堆棧中的元數據並沒有別的區別,訪問臨時寄存器用R+寄存器標號的方式訪問,在筆者設計的虛擬機中,每個虛擬機實例一共有16個這樣的臨時寄存器,用R0~R15對他們進行訪問.

之後是三個特殊寄存器,SP,IP,BP,如果有閱讀過彙編代碼的讀者應該對這三個寄存器再熟悉不過了,SP永遠指向棧頂,IP寄存器指向當前正在執行的指令,BP更多是為了支持函數調用中尋找參數的偏移地址用的,提前將它加進來為後期設計高級語言的編譯器做下準備

這三個特殊寄存器都是dword類型,這意味這我們的虛擬機最大的定址範圍是4GB.

堆棧數據結構

在虛擬機的堆棧是由元數據構建起來的,當然,棧的增長方向為高地址向低地址,而堆的方向則是低地址到高地址

在StoryVM中,一般使用GLOBAL[索引號]訪問堆棧的元數據,一般使用LOCAL[索引號]來訪問棧數據

當然

GLOBAL[BP+i]和LOCAL[i]是等價的,LOCAL表示在偏移量加上一個BP寄存器的值,主要用來訪問參數和臨時變數.

虛擬機是如何運行的

實際上不僅僅是虛擬機,目前我們見到的大部分的計算機架構都可以把程序當做一張很長的寫滿指令的紙條,而計算姬要做的就是從頭讀到尾,並從頭執行到尾,我們的虛擬機同樣遵循著這樣的」執行守則」

當一個腳本被編譯為指令流後,虛擬機依次讀取一條指令然後執行,當然,指令也並不是完全按照順序讀取,因為指令當中也包含一些」跳轉」指令,這將會讓虛擬機」跳轉」到紙條的其它地方執行指令.

當然,虛擬機設計是一個龐大的需要深思熟慮的系統,如果考慮IO(輸入輸出)及中斷,多線程的線程調度的話,我們無法簡簡單單用一個字條來描述一個虛擬機的執行過程,但是在文章的開始,初學者依照這個比喻,對虛擬機是如何運行的有個初步的概念.

虛擬機指令集設計

千里之行始於足下,MOV指令設計

筆者在最初設計StoryVM的時候,指令只有短短的幾條,一個指令集的完善,不能僅僅是靠初期想當然的腦補,在StoryVM部署到實際的項目之後,筆者再不斷去添加那些需要的指令,當然,在本文當中筆者並不打算演示所有的指令實現,筆者決定挑選幾個非常具有代表性的指令進行講解,當然,首當其衝的就是mov這條指令,這也就是為什麼本章筆者並不把標題起為虛擬機指令設計,筆者認為,有幾個特殊指令是值得專門花費一章節去講解的.

那麼,MOV指令是怎麼回事,有什麼用呢

其實非常簡單的說法,這是一個數據傳送(賦值)指令,比如下面的算式

就是把變數i賦值為314

當然,如果把這條語句寫為StoryVM的彙編代碼形式,那麼就是

當然,i在彙編中並不存在,假設它是一個全局變數,那麼它應該在堆中,假設它在GLOBAL[0]的位置,那麼,應該寫成

這樣,GLOBAL[0]就被正式賦值為一個整數,為314,當然看到這裡,你應該會覺得MOV指令非常簡單,例如,下面的彙編語句即使筆者不說讀者也很容易理解要表達的意思

MOV R1,123 //R1寄存器賦值為123

MOV R2,3.14 //R2寄存器賦值為3.14

MOV R3,」Hello World」 //R3寄存器賦值為字元串」Hello World」

MOV R4,@0102@//R4寄存器賦值為兩位元組長度的0x01 0x02

上面的語句沒什麼問題,其中,R1和寄存器R2順利地被賦值到了元數據寄存器中,但是R3和R4不得不提及一下,當一個元數據被賦值為一個字元串和數據流類型時,不可避免地涉及到了內存分配的問題,但還好,這實現起來並不複雜,當一個寄存器被賦值為了字元串或者數據流類型時,從內存池中劃出一塊內存將字元串或數據類型存儲進去,然後這個元數據中指定一個字元串指針指向它就行了.

那麼我們來看看下面的兩個語句

MOV R1,123

MOV R1,」Hello」

先將寄存器R1賦值為123,然後再將字元串賦值到寄存器R1中(在內存池申請內存,然後將元),這沒什麼問題,但是我們將兩個語句換一下,那麼問題就來了

MOV R1,」Hello」

MOV R1,123

首先,R1寄存器被賦值為」Hello」,在這之後,它又被賦值為123,這將會帶來一個問題,如果將R1直接賦值為123,為字元串hello在內存池分配的空間將得不到釋放,因此,當一個字元串或是數據流時,在內存池分配的空間都應該被釋放

MOV指令和內存管理機制

從上一章節MOV的討論中我們可以看出當一個元數據由一種類型變換為另一種類型時,一是可能伴隨著內存的分配,既然有了分配那就應該有回收機制,例如當一個元數據由int類型變為了string類型,那麼,在內存池中必須申請一塊內存區域用於存儲字元串類型,而由string類型變為了int類型,將伴隨著string類型所佔用的內存釋放,也就是內存的回收,那麼在什麼時候內存需要分配而什麼時候需要回收呢,筆者總結了以下幾種情況

  1. 當一個數據由其他類型變為了string或者是memory類型時,需要在內存池中為其分配內存空間.
  2. 當一個數據進行拷貝時,需要為其分配內存空間

即如下代碼

MOV R1,」ABC」

MOV R2,R1 //需要為R2分配內存以進行字元串類型的拷貝

  1. 當一個元數據由string或memory類型變為其它類型時,當然,這也包括string類型變為memory或者是memroy類型變為了string類型,需要對原內存進行回收
  2. 當一個元數據的長度發生改變時,例如下面語句

MOV R1,」Hi」

MOV R1,」Hello」

那麼,R1所在的字元串所在內存可能因為字元串長度的改變需要進行重新分配,需要分配與回收

  1. 最後需要提及的一點是,當MOV指令對特殊寄存器進行操作時,不涉及內存的分配與回收機制,畢竟在StoryVM中,特殊寄存器(SP BP IP)都是int類型,如果將特殊寄存器賦值為其它類型,虛擬機將會拋出一個異常並結束運行.

因為採用了這種」元數據」的存儲方式,對於字元串及數據流類型,不可避免地就需要好好思考下如何管理內存了,畢竟內存泄漏在虛擬機的執行過程中是決不允許的,誰也不希望自己的程序跑著跑著內存就被一點點喫光最後導致崩潰.這種內存管理機制我們常常稱之為GC(garbage collection 垃圾回收機制)

不過在StoryVM中,我們只要遵循並注意這個」元數據」的類型切換時內存的管理就可以避免內存泄漏了,除此之外我們也注意到了,內存的回收分配機制,是一個非常耗費性能的調度機制,並且優化的難度大且難以避免,這也難怪在網上經常看得到對java這種重度依賴GC的語言被各種的吐槽,不過幸好在StoryVM中我們使用的是自行架構的內存池方案,避免了直接使用malloc/free等需要syscall的API額外調用開銷.

當然,不僅僅是mov指令,所有對元數據造成修改(不管它是寄存器還是堆棧中的元數據)的指令我們都需要遵循上述的gc規則進行管理,否者結果必定是災難性的,筆者使用mov指令做」拋磚引玉」之用,是因為Mov指令太具有代表性了,這個看上去最簡單的指令,其實現卻是storyVM中最複雜的指令,不過讀者們也無需擔心,在mov指令設計完成後,剩下的指令要設計起來就簡單多了.

運算中的隱式轉換

如果說讓個小學生做個加減乘除運算,想必並也並不是什麼複雜的事情,但在StoryVM上,我們考慮的就有點多了.

首先我們先來看看下面兩個表達式

1+1=2

1+1.0=2.0

在數學的意義上,1和1.0是等價的,上面兩個表達式同樣是個等價的表達式運算,但是,在計算機當中,數字的不同表示方式可能導致截然不同的運算規則,首先,整數和浮點數的編碼在計算機中是不同的這也就意味著

1+1是一個整數運算而1+1.0是一個浮點類型的運算

出於精度的考慮,在計算的結果中我們會以精度更高的表達方式進行表達,因此.當一個整數和一個浮點數進行運算後,它的結果也是一個浮點數.這點在StoryVM中需要被認真的考慮,與此同時的,在編程開發時,我們也常常使用的到浮點截斷(去掉小數點後面的數值),因此,必須也設計相應的指令,將浮點數轉換成整數,或者是將一個整數轉換成浮點數的表示方式

在StoryVM的指令運算設計中,雙目運算符(需要兩個數字進行運算的操作符)遵循以下的運算規律

  1. 整數與整數運算,得到的也是一個整數
  2. 整數與浮點數運算,得到一個浮點數
  3. 浮點數與浮點數運算,得到一個浮點數

同時,浮點數的編碼方式也需要被嚴格的考慮,如果因為編譯環境的不同而導致浮點的編碼方式不同,那麼腳本在跨平臺運行方面就會出現錯誤,但幸運的是,StoryVM使用C語言進行編寫開發,而C語言的編譯器基本都使用IEEE 754的標準對浮點數進行編碼.

虛擬機中的加減乘除指令

在StoryVM中,參考了x86指令中加減乘除的助記符,加減乘除的彙編指令分別為

ADD SUB MUL DIV

寫起來也基本類似,例如要實現1+1=2的這個表達式方式,指令編寫如下

MOV R1,1 //寄存器R1賦值為1

ADD R1,1 //R1+1=2

在ADD R1,1指令中,ADD稱之為操作碼,R1,1稱之為操作數,其中R1位操作數1,數字1為操作數2

實際上嚴格來說,ADD應該稱之為加法操作碼對應的助記符(mnemonic),R1是寄存器1對應的助記符,1是一個常量,當然,ADD函數遵循著運算隱式轉換的規則,如果指令改為

ADD R1,1.0

那麼寄存器R1對應的元數據類型也會相應的轉換為一個浮點數據類型.

如果彙編器將ADD,R1,1這個指令編譯成指令流,那麼,它應該是下面這個樣子的

參照之前提到的編碼格式,其對應的指令流為0x02 0x02 0x01 0x00 0x00000001 0x00000001一共12位元組.

下面,我們用opcode表示操作碼.op1表示操作數1,op2表示操作數2,GLOBAL表示接受堆數據數據類型,LOCAL表示接受棧數據數據類型,REG表示接受寄存器數據類型,int,float,string,memory分別表示接受整形,浮點型,字元串型和數據流型常量.num表示接受一個數字,即可是是浮點類型也可是整數類型.

例如減法指令sub的描述如下

減法指令,op1=op1-op2,將操作數1的值減去操作數2的值,然後將結果賦值給操作數1

當然,操作數1必須是一個寄存器或者是堆棧中的元數據,因為常量不能被賦值,操作數2可以是一個寄存器或者堆棧中的元數據或者一個數字常量都可.

sub [reg,local,global],[num,reg,local,global]

依次類推,那麼,在StoryVM中,幾個運算指令的描述如下(為了說明方便,後面的表達式用C語言的運算符進一步描述)

add
加法指令,op1=op1+op2
add [reg,local,global],[num,reg,local,global]

sub
減法指令,op1=op1-op2
sub [reg,local,global],[num,reg,local,global]

neg
符號求反指令,op1=-op1
neg [reg,local,global]

div
除法指令,op1=op1/op2
div [reg,local,global],[num,reg,local,global]

mul
乘法指令,op1=op1*op2
mul [reg,local,global],[num,reg,local,global]
mod
餘數指令,兩個操作數必須為整數 op1=op1%op2
mod [reg,local,global],[int,reg,local,global]

shl
左移位指令,兩個操作數必須為整數 op1=op1<<op2
shl [reg,local,global],[int,reg,local,global]

shr
右移位指令,兩個操作數必須為整數 op1=op1>>op2
shr [reg,local,global],[int,reg,local,global]

and
與運算指令,op1=op1&op2
and [reg,local,global],[num,reg,local,global]

or
或運算指令,op1=op1|op2
or [reg,local,global],[num,reg,local,global]

xor
異或運算指令op1=op1^op2
xor [reg,local,global],[num,reg,local,global]

inv
位取反指令,op1=~op1
inv [reg,local,global]

not
邏輯非指令 op1=!op1
not [reg,local,global]

andl
邏輯與指令 op1=op1&&op2
andl [reg,local,global],[num,reg,local,global]

orl
邏輯或指令 op1=op1||op2
andl [reg,local,global],[num,reg,local,global]

pow
階乘指令(op1為底數,op2為指數,結果在op1中) op1=op1_op2
pow [reg,local,global],[num,reg,local,global]

sin
正弦函數op1=sin(op2)
sin [reg,local,global],[num,reg,local,global]

cos
餘弦函數 op1=cos(op2)
cos [reg,local,global],[num,reg,local,global]

int
強制類型轉換為int型(原類型float)
int [reg,local,global]

flt
強制類型轉換為float型
flt [reg,local,global]

條件跳轉指令

相比於可能修改元數據需要小心翼翼管理內存的指令,條件跳轉指令的實現可就簡單的多了,唯一需要注意的是,如何確定跳轉的位置,在x86指令集中,跳轉指令的設計就複雜的多了,有近跳轉,遠跳轉,相對跳轉和絕對跳轉,但是在StoryVM中,跳轉指令並不需要設計的那麼複雜,所有的跳轉指令都為絕對跳轉.

在StoryVM中,使用JMP指令表示一個無條件跳轉指令,例如

JMP 10表示程序跳轉到地址為10的位置執行

這麼設計當然沒有一點問題,但是我們不可能在編寫程序時,手工去計算我們要跳轉的位置,那麼問題就是如何確定跳轉的地址了,幸運的是,每條指令的長度都可以很方便的進行計算,我們只需要設計一個標誌,就可以很容易計算出標誌所在的地址了

在StoryVM中,標誌的表示方式是一個助記符加上一個冒號,例如

FLAG:
MNEMONIC:
ADDR:
TRUE:

都是合法的標誌類型,很多時候為了表現這是一個函數,在標號前可以加入描述符FUNC

例如

FUNC FLAG:

和FLAG是等價的,FUNC這個助記符對源代碼沒有任何的影響,只是為了代碼方便查看及分類添加的一個沒有意義的關鍵字

現在觀察下面的指令

MOV R1,1 //長度為12位元組
ADD R1,2 //長度為12位元組
FLAG: //偏移地址為24
ADD R1,2//長度為12位元組
JMP FLAG//跳轉到FLAG處開始執行

需要注意的一點是,如果一個彙編程序從開始編譯到結束,那麼,標號必須在JMP指令之前,也就是說JMP必須是向前跳轉的,這顯然不符合一個跳轉指令應該具有的功能,要解決這一個問題實際也並不複雜,在彙編指令的編譯期間,對源代碼進行兩次掃描,第一次掃描確定所有的標號對應的位置,第二次掃描才將JMP指令」連接」到對應的標號中實現跳轉,

除了無條件跳轉指令,當然還有一系列的跳轉指令,具體描述如下

je
條件跳轉,當op1等於op2,跳轉到op3
je [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jne
條件跳轉,當op1不等於op2,跳轉到op3
jne [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jl
條件跳轉,當op1小於op2,跳轉到op3
jl [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jle
條件跳轉,當op1小於等於op2,跳轉到op3
jle [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jg
條件跳轉,當op1大於op2,跳轉到op3
jg [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jge
條件跳轉,當op1大於等於op2,跳轉到op3

堆棧操作指令

堆棧操作本身屬於數據結構的一種,當然,堆棧的操作和特殊的寄存器SP,BP相關,就和我們之前說的那樣LOCAL[i]和GLOBAL[BP+i]是等價的,而SP指令和

PUSH

POP

兩個指令相關

PUSH x指令實際上和下面的指令等價

SUB SP,1

MOV GLOBAL[SP],x

也就是說,每當執行一條PUSH指令,SP寄存器的值會被減去1,然後將PUSH的值賦值到對應的堆空間GLOBAL[SP]中

而POP x指令和PUSH指令剛好相反,其等價於

ADD SP,1

MOV x,GLOBAL[SP]

在指令的編寫及設計中,PUSH指令和POP指令常常是成對出現的,也就是我們常常說的要保證堆棧平衡,如果PUSH POP不成對出現,往往容易導致內存泄漏,越界訪問等異常現象.

函數跳轉指令

實際上虛擬機有上述指令就已經可以完成大部分的工作了,但除了一般的跳轉指令,在StoryVM中還設計了一個特殊的指令CALL指令,CALL指令本身並沒有什麼特別的地方,它的作用是將下一條指令的地址壓棧,然後跳轉到目的標號中,CALL指令的設計同樣是一種數據結構上的調度處理,當我們為這個彙編語言設計高級語言編譯器的時候,CALL指令就會被經常的用到.

StoryVM指令表

介紹完幾種關鍵的指令後,最後貼上StoryVM所支持的所有指令集,讀者可以參照這些指令自行實現

mov
賦值指令,將op2的值賦值給op1
mov [reg,local,global],[num,string,reg,local,global]

add
加法指令,op1=op1+op2
add [reg,local,global],[num,reg,local,global]

sub
減法指令,op1=op1-op2
sub [reg,local,global],[num,reg,local,global]

neg
符號求反指令,op1=-op1
neg [reg,local,global]

div
除法指令,op1=op1/op2
div [reg,local,global],[num,reg,local,global]

mul
乘法指令,op1=op1*op2
mul [reg,local,global],[num,reg,local,global]

mod
餘數指令,兩個操作數必須為整數 op1=op1%op2
mod [reg,local,global],[int,reg,local,global]

shl
左移位指令,兩個操作數必須為整數 op1=op1<<op2
shl [reg,local,global],[int,reg,local,global]

shr
右移位指令,兩個操作數必須為整數 op1=op1>>op2
shr [reg,local,global],[int,reg,local,global]

and
與運算指令,op1=op1&op2
and [reg,local,global],[num,reg,local,global]

or
或運算指令,op1=op1|op2
or [reg,local,global],[num,reg,local,global]

xor
異或運算指令op1=op1^op2
xor [reg,local,global],[num,reg,local,global]

inv
取反指令,op1=~op1
inv [reg,local,global]

not
邏輯非指令 op1=!op1
not [reg,local,global]

andl
邏輯與指令 op1=op1&&op2
andl [reg,local,global],[num,reg,local,global]

orl
邏輯或指令 op1=op1||op2
andl [reg,local,global],[num,reg,local,global]

pow
階乘指令(op1為底數,op2為指數,結果在op1中) op1=op1_op2
pow [reg,local,global],[num,reg,local,global]

sin
正弦函數op1=sin(op2)
sin [reg,local,global],[num,reg,local,global]

cos
餘弦函數 op1=cos(op2)
cos [reg,local,global],[num,reg,local,global]

int
強制類型轉換為int型(原類型float)
int [reg,local,global]

flt
強制類型轉換為float型
flt [reg,local,global]

strlen
字元型長度指令
op1=strlen(op2)
strlen [reg,local,global],[reg,local,global,string]

strcat
字元型拼接指令
strcat(op1,op2)
strcat [reg,local,global],[int,reg,local,global,string]

strrep
字元串替換函數
將op1存在的op2字元串替換為op3中的字元串, 注意:op2 op3必須為字元串類型
strrep [reg,local,global],[reg,local,global,string],[reg,local,global,string]

strchr
將op2在索引op3中的字存儲在op1中, 注意:op2必須為字元串類型
strchr [reg,local,global],[reg,local,global,string],[reg,local,global,int]

strtoi
將op2轉換為整數保存在op1中,注意:op2必須為字元串類型
strtoi [reg,local,global],[reg,local,global,string]

strtof
將op2轉換為浮點數保存在op1中,注意:op2必須為字元串類型
strtof [reg,local,global],[reg,local,global,string]

strfri
將op2整數類型轉換為字元串類型保存在op1中
strfri [reg,local,global],[reg,local,global,int]

strfrf
將op2浮點類型轉換為字元串類型保存在op1中
strfrf [reg,local,global],[reg,local,global,float]

strset
將op1所在字元串索引為op2 int的字元置換為op3
如果op3為一個int,則取asc碼(第八位1位元組),如果op3為一個字元串,則取第一個字母
strset [reg,local,global],[reg,local,global,int],[reg,local,global,string,int]

strtmem
將op1字元串類型轉換為內存類型
strfrf [reg,local,global]

asc
將op2的第一個字母以asc碼的形式
asc [reg,local,global],[reg,local,global,string]

membyte
將op3 內存類型對應op2索引複製到op1中,這個類型是一個int類型(小於256)
membyte [reg,local,global],[reg,local,global,int],[reg,local,global,memory]

memset
設置op1對應op2索引的內存為op3
memset [reg,local,global],[reg,local,global,int],[reg,local,global ,int]

memtrm
將op1內存進行裁剪,其中,op2為開始位置,op2為大小
memcpy [reg,local,global],[reg,local,global,int],[reg,local,global,memory]

memfind
查找op2對應於op3內存所在的索引位置,返回結果存儲在op1中,如果沒有找到,op1將會置為-1
memfind [reg,local,global],[reg,local,global,memory],[reg,local,global,memory]

memlen
將op2的內存長度存儲在op1中
memlen [reg,local,global],[reg,local,global,memory]

memcat
將op2的內存拼接到op1的尾部
memcat [reg,local,global],[int,reg,local,global,memory]

memtstr
將op1內存類型轉換為字元串類型,如果op1的內存結尾不為0,將會被強制置為0
memtstr [reg,local,global]

datacpy
複製虛擬機data數據,從地址op2到地址op1,長度為op3
datacpy [reg,local,global,int], [reg,local,global,int], [reg,local,global,int]
jmp
跳轉指令 跳轉到op1地址
jmp [reg,num,local,global,label]

je
條件跳轉,當op1等於op2,跳轉到op3
je [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jne
條件跳轉,當op1不等於op2,跳轉到op3
jne [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jl
條件跳轉,當op1小於op2,跳轉到op3
jl [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jle
條件跳轉,當op1小於等於op2,跳轉到op3
jle [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jg
條件跳轉,當op1大於op2,跳轉到op3
jg [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

jge
條件跳轉,當op1大於等於op2,跳轉到op3
jge [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]

lge
邏輯比較指令,當op2等於op3時將op1置1,否則為0
lge [reg,local,global], [num,string,reg,local,global] , [num,string,reg,local,global]

lgne
邏輯比較指令,當op2等於op3時將op1置0,否則為1
lge [reg,local,global], [num,string,reg,local,global] , [num,string,reg,local,global]

lgz
邏輯比較指令,當op1等於0時將op1置1,否則為0
lgz [reg,local,global]

lggz
邏輯比較指令,當op1大於0時將op1置1,否則為0
lggz [reg,local,global]

lggez
邏輯比較指令,當op1大於等於0時將op1置1,否則為0
lggez [reg,local,global]

lglz
邏輯比較指令,當op1小於0時將op1置1,否則為0
lglz [reg,local,global]

lglez
邏輯比較指令,當op1小於等於0時將op1置1,否則為0
lglez [reg,local,global]

call
調用指令,如果op1是本地地址則將當期下一條指令地址壓棧,然後跳轉到op1,如果op1是一個host地址,則該call為一個hostcall,hostcall不會將返回地址壓棧
call [reg,int,local,global,label,host]

*Host Call的返回值在r[0]中
*由被調用者清理堆棧
push
將op1壓棧 sp-1,stack[0]=op1
push [num,reg,local,global,string,label]

pop
出棧，並將該值
pop [reg,local,global]

adr
取堆棧的絕對地址,返回該堆棧的絕對地址
ADR [reg,local,global], [local,global]
popn
將op1個元素出棧
popn [reg,local,global]

ret
返回,pop一個返回地址,跳轉到該地址.

wait
等待一個信號量置為0,否者這個虛擬機實例將被暫時掛起(但並不不影響suspend標準位),在每個虛擬機實例中都有16個信號量,通過signal指令對這些信號量進行設置

signal
等待op1對應索引的信號量置為op2, 在每個虛擬機實例中都有16個信號量,這意味著op1的範圍是0-15,當一個信號量被設置為非0值時,執行wait指令後改虛擬機實例會被阻塞,直到這個信號量被置為0時才能繼續執行後續指令

bpx
如果啟動了調試器,將會在該指令上斷點,否者作為一個空指令

nop
空指令

虛擬機彙編編譯器

也許製作一個高級語言的編譯器會複雜得多,但是編寫一個彙編編譯器並不複雜,在大部分的時候,彙編編譯器所做的工作無非是將助記符」編譯」為指令數據流,這有以下幾點好處

  1. 指令流往往所佔的空間更小
  2. 指令流解析速度遠遠快於直接解析助記符
  3. 指令流更加安全(當然這也就意味著程序編譯後失去了其可讀性變得難以修改)

一個指令是否被翻譯為指令流也常常被當做是這個語言是解釋型語言還是編譯型語言的分水嶺,但是就和之前提到的,其實本質上都是對指令的解釋只是方法不同,並沒有特別的區別

預處理

在將指令編譯為指令集之前,我們需要先處理幾種情況以為開始編譯做準備.

首先要處理的是之前提到的標誌,標誌用於指明跳轉指令的跳轉位置,因此在編譯之前,掃描整個源文件所有的標號,並將標號記錄在表中.

在第二次正式開始編譯時,更新對應標號的跳轉指令,讓他們指向正確的位置

這樣,對標號的處理就算完成了,當然除了標號,還有其他的數據需要處理,觀察下面的幾句彙編代碼:

首先我們編譯MOV R1,255,當操作數作為寄存器和數字常量這沒有一點問題,我們很容易就能寫出其編譯後對應的指令流,但是,MOV R1,」Hello World」就沒有那麼簡單了,依照StoryVM的指令編碼標準,每個操作數對應一個1位元組的操作數類型和一個4位元組的值,顯然,Hello World這個字元串已經超過了四位元組所能容納的範圍了,因此和FLAG一樣,我們也要將所有的字元串和數據流類型在第一次掃描時提取出來,將他們放入一個表中

當第二次正式編譯時,我們同樣和FLAG一樣的方式,將字元串對應的索引號鏈接到對應的操作數當中.

當然除了字元串,對數據流也採用同樣的辦法建立一張表並建立映射關係, 最後是關鍵字ASSUME的處理,這是一條偽指令,其作用類似於C語言的define

例如下面的代碼

ASSUME NUM,123

MOV R1,NUM

它等價於代碼

MOV R1,123

堆棧

因為內存空間是有限的,因此對堆棧的大小必須有一個限制,在C語言或者其他的高級語言中,堆的大小可以從全局或者靜態變數計算出來,而如果棧沒有被明確的設定,那麼編譯器會選擇一個默認值作為棧的大小,以visual studio的MSVC為例,默認的棧大小是2M,正常情況下這個大小是足夠了.

在StoryVM中,因為採用了元數據的存儲方式,這也就意味著我們開闢的棧大小實際佔用的內存會是這個棧的大小十倍乃至二十幾倍,因此控制棧的大小就變得非常有必要,正常情況下,筆者使用65535個元數據作為棧(實際佔用了將近2M的內存空間),但是在很多情況下除非使用深度的迭代並在局部變數中建立了大數組,實際並不需要那麼大的棧空間,我們無法預測用戶實際上會用到多少的棧空間,因此在StoryVM的彙編中,我們引入了.GLOBAL和.STACK兩個關鍵字

例如

.GLOBAL 100

.STACK 1024

表示建立一個大小為100個元數據的堆,大小為1024個元數據的棧,它在內存中實際上是這樣排布的

可以看到,堆棧實際上是訪問了同一塊內存空間,也就是說,如果訪問GLOBAL[101]實際上已經訪問了棧的區域了,需要注意的是,當棧溢出後,它將會覆蓋堆中的數據,當然,StoryVM中做邊界檢查並不複雜.

指令編譯

實際上在之前已經有過非常多的指令編譯的討論了,以下圖為例

上面的指令流實際上是MOV R1,255的編譯,其中MOV被編譯為了01表示MOV指令的實際操作碼就是01,R1的操作數類型是寄存器,其中,02就表示這個操作數是一個寄存器,因為他是寄存器1,所以其對應的操作碼參數也是1,最後是255,他是一個常量,01表示這是一個常量類型的操作數,它的值是255,也就是十六進位的000000ff

實際上,筆者總結了操作數的類型主要為以下幾種

enum PX_SCRIPT_ASM_OPTYPE
{
PX_SCRIPT_ASM_OPTYPE_INT, //整數常量,操作數參數為這個常量的值
PX_SCRIPT_ASM_OPTYPE_FLOAT, //浮點常量,操作數參數為這個常量的值
PX_SCRIPT_ASM_OPTYPE_REG, //寄存器,操作數參數為這個寄存器的索引號
PX_SCRIPT_ASM_OPTYPE_LOCAL, //局部變數類型
PX_SCRIPT_ASM_OPTYPE_LOCAL_CONST, //局部變數引用,例如LOCAL[5],操作數參數就是5
PX_SCRIPT_ASM_OPTYPE_LOCAL_REGREF, //局部變數的寄存器引用,例如LOCAL[R1],就是一個寄存器引用,操作數參數是對應寄存器的索引

PX_SCRIPT_ASM_OPTYPE_LOCAL_GLOBALREF, //局部變數的全局變數引用,例如LOCAL[GLOBAL[1]],就是一個全局變數引用,操作數參數是對應全局變數的偏移量,例如這裡就是1

PX_SCRIPT_ASM_OPTYPE_LOCAL_LOCALREF, //局部變數的局部變數引用,例如LOCAL[LOCAL[2]],就是一個局部變數引用,操作數參數是對應局部變數的偏移量,例如這裡就是2
PX_SCRIPT_ASM_OPTYPE_GLOBAL,//全局變數類型
PX_SCRIPT_ASM_OPTYPE_GLOBAL_CONST, //全局變數引用,例如GLOBAL[5],操作數參數就是5

PX_SCRIPT_ASM_OPTYPE_GLOBAL_REGREF, //全局變數的寄存器引用,例如GLOBAL[R1],就是一個寄存器引用,操作數參數是對應寄存器的索引

PX_SCRIPT_ASM_OPTYPE_GLOBAL_GLOBALREF, //全局變數的全局變數引用,例如GLOBAL[GLOBAL[1]],就是一個全局變數引用,操作數參數是對應全局變數的偏移量,例如這裡就是1

PX_SCRIPT_ASM_OPTYPE_GLOBAL_LOCALREF, //全局變數的局部變數引用,例如GLOBAL[LOCAL[2]],就是一個局部變數引用,操作數參數是對應局部變數的偏移量,例如這裡就是2

PX_SCRIPT_ASM_OPTYPE_GLOBAL_SPREF, //全局變數的SP寄存器引用,例如GLOBAL[SP],就是一個SP寄存器引用,操作數參數是對應局部變數的偏移量,例如這裡就是2

PX_SCRIPT_ASM_OPTYPE_STRING,//字元串常量,操作數參數就是之前所述的對應字元串索引
PX_SCRIPT_ASM_OPTYPE_LABEL,//標籤,實際上標籤並不會被編譯成實體的指令流
PX_SCRIPT_ASM_OPTYPE_HOST,//Host函數標籤,之後再說
PX_SCRIPT_ASM_OPTYPE_MEMORY,//數據流類型常量,操作數參數就是之前所述的對應字元串索引

PX_SCRIPT_ASM_OPTYPE_BP,//BP寄存器
PX_SCRIPT_ASM_OPTYPE_SP,//SP寄存器
PX_SCRIPT_ASM_OPTYPE_IP,//IP寄存器
};

操作數類型由以上定義完成,而操作碼讀者可以自行設計任意一個值,例如筆者設定的StoryVM中

MOV指令的操作碼是01

ADD 是02

SUB是03

MUL 是04

DIV是 05

……..讀者可以根據自己的需要自行設計

導出與導入函數標籤

和原生二進位編譯的代碼有所不同的是,我們編譯出的程序無法直接供外部調用執行,然後腳本的主要作用就是供虛擬機調用需要的函數來執行我們所需要的功能,因此,我們需要將我們的FLAG暴露給外部供原生的程序調用,同時在很多的時候,我們的腳本也需要調用原生代碼裏的一些函數來完成交互,但是目前我們的虛擬機設計仍然沒有辦法滿足這一功能

例如之前我們所說的下面的程序

MOV R1,1
ADD R1,2
FUNC:
MOV R1,3
JMP FUNC

在這裡,FUNC這個標誌僅能供給程序中的跳轉,但卻無法在虛擬機中直接調用.因此,筆者引入了一個關鍵字EXPORT意為導出函數,當一個標號被加上了EXPORT關鍵字後,程序編譯期間將會把這個標號對應的地址記錄在文件當中.以方便虛擬機中進行調用

同樣的,很多時候也需要在腳本中調用原生的代碼函數,這種函數我們一般稱之為host函數

為此,在虛擬機中我們需要設計一個對應的隱射關係表,將host函數名與其地址對應起來以方便腳本進行調用,例如,假如腳本需要調用一個叫print的函數,那麼,對應的腳本代碼應該類似於這樣編寫

MOV R1,」Hello World」
Push R1
Call $print

注意,在CALL這條指令中,print這個標號在這個腳本文件中本身並不存在,但取而代之的是在其前綴中添加了一個$號表示這是一個host函數,當虛擬機執行到這條指令的時候,將會在host函數表中查找是否有對應的函數,如果有,那麼就會跳轉到該函數進行執行,如果沒有那麼虛擬機會拋出一個異常

最後就是關於返回值的問題了,在一般情況下,默認規定函數的返回值都存儲在寄存器R1中,如果需要獲取返回值,讀取R1寄存器就可以了

編譯可執行文件

最終,我們需要將所有的信息進行進一步的整合,以便於虛擬機更好地執行我們編譯出來的指令流,首先我們可以參照PE格式的可執行文件,為我們的可執行文件設置一個文件頭在筆者設計的StoryVM的編譯文件中,其設計滿足以下的描述

其中,文件頭包含以下定義,其中px_dword表示4位元組

typedef struct __PX_SCRIPT_ASM_HEADER
{
//////////////////////////////////////////////////////////////////////////
px_dword magic;//Magic Numeric一定是PASM
px_dword CRC;//CRC校驗
//////////////////////////////////////////////////////////////////////////
px_dword stacksize;//棧大小
px_dword globalsize;//堆大小
px_dword threadcount;//最大執行線程數量
px_dword oftbin;//到代碼區的偏移量
px_dword oftfunc;//到導出表的偏移量
px_dword funcCount;//導出函數數量
px_dword ofthost;//到導入表的偏移量,也就是host函數
px_dword oftmem;//到數據流常量區偏移量
px_dword memsize;//數據流常量區大小
px_dword hostCount;//導入函數數量
px_dword oftString;//到字元串常量區偏移量
px_dword stringSize;//字元串常量區大小
px_dword binsize;//代碼區大小
px_dword reserved[6];//保留
}PX_SCRIPT_ASM_HEADER;

將代碼進行整理打包後,一個可以供虛擬機執行的編譯腳本也就算製作完成了.

執行編譯腳本

虛擬機初始化

當虛擬機載入一個編譯後的可執行腳本後,一般要進行以下幾個步驟

  1. 驗證文件頭中的Magic和CRC,驗證這個腳本是否是一個完整的編譯型腳本,當然,最好引入編譯器的版本號,如果以後對虛擬機的環境有修改,並規定該虛擬機可以運行哪些版本的腳本,這個欄位將尤為重要.
  2. 完成了驗證之後,之後就是對常量區進行一系列初始化了,從文件中讀取字元串及數據流常量區將它們存儲在運行內存中以供調用.
  3. 初始化host函數表,當然,只是初始化一個空表,在這裡我們並不急著將導入函數映射到這個表當中.
  4. 現在要準備運行環境了,第一步當然是為堆和棧分配空間,在這裡這個大小是可以計算的,它等於(堆大小+棧大小*最大支持線程數)*元數據的大小,可以看到這裡我們引入了一個最大支持的線程數,這點我們將在之後討論.
  5. 載入指令流,也就是代碼區的代碼了,到這一步基本也就意味著程序可以準備運行了

上下文切換與多線程調度

在開始運行虛擬機代碼之前,筆者先來聊一聊多線程的問題,如果你是一名開發人員那麼這個問題應該是再熟悉不過了,不過如果你並不瞭解多線程是什麼玩意,你可以理解為一個人同時做多件事情.

在你的PC上你可以看見計算機同時運行著多個軟體,彷彿所有的程序都在同時運行著,在CPU還是單核的年代,這是如何辦到的呢,其實要理解這點也非常的簡單,你可以理解為計算機在一秒鐘,先執行某一程序的一些指令,然後立刻切換到另一個程序中執行另一個程序的指令而不是等待第一個程序的代碼執行完成後再執行另一個程序,如果重複這個過程並且切換的速度非常的快的話,這些程序看上去就像是同時運行的.

那麼問題就是如何進行這種切換了,在多線程當中,存在著數據共享區,也有那些獨立的區域,共享數據區好說,就是堆區了,不管哪一個線程都訪問同一個堆,獨立的區域那就是棧了,這關係到函數調用問題,除了棧之外,寄存器也非常重要,因此每一次切換我們都要保存當前線程的棧和寄存器狀態,當再次執行到這個線程的時候,再把這個棧和寄存器進行恢復,這就是我們說的上下文切換,可以說,上下文切換時多線程實現的關鍵技術.

瞭解了以上這幾點,那麼就可以解釋之前在分配運行時內存空間為什麼是參者這個(堆大小+棧大小*最大支持線程數)*元數據的公式了,是的,我們需要為每一個線程分配一個獨立的棧空間,並且我們為每一個線程設定一個寄存器實例,那麼每一個線程使用的寄存器實際上是分開的.

因此在虛擬機的設計中,執行的步驟是,先執行某一線程的一些指令,然後切換到下一個線程執行另一些指令,這樣就產生了一種多個程序同時執行的情況,但我們也注意到多線程運行的同時也附帶著上下文切換帶來的性能開銷,不過幸運的是,由於在StoryVM中所有的線程都有自己獨立的寄存器實例與獨立的棧空間,因此上下文切換帶來的性能開銷基本可以忽略不計,我們要做的就是根據實際情況看給線程分配多少的時間片了(每個線程每次執行多少條指令後切換).

信號量與中斷

我們注意到多線程的引入產生了一些新的問題,那就是如何解決多線程的資源競爭問題(多個線程同時訪問修改一個數據),在windows中,提供了互斥體才避免這種情況的發送,相信讀者也發現了在多線程章節給出的說明圖中,多出了一個信號量最高東西,實際上這和互斥體類似,同樣是為瞭解決資源競爭所帶來的問題的

在之前的StoryVM指令表中有以下兩個特殊的指令

wait

等待一個信號量置為0,否者這個虛擬機實例將被暫時掛起(但並不不影響suspend標誌位),在每個虛擬機實例中都有16個信號量,通過signal指令對這些信號量進行設置

signal

等待op1對應索引的信號量置為op2, 在每個虛擬機實例中都有16個信號量,這意味著op1的範圍是0-15,當一個信號量被設置為非0值時,執行wait指令後改虛擬機實例會被阻塞,直到這個信號量被置為0時才能繼續執行後續指令

這也就意味著,當一個線程需要訪問一片資源時,他需要先進行wait某一信號量.如果不需要等待,再使用signal對其置為非0值防止其他線程對其進行訪問,最後完成後再對signal歸0操作

程序的開始與結束

終於到實際執行指令的時候了,那麼程序從哪裡開始運行呢,當然,StoryVM中並沒有像PE文件裏那樣有一個OEP(程序最開始執行的地址),但我們的程序的的確確需要執行一些必須先執行的指令,在StoryVM中筆者定義其為_BOOT,一般情況下它是代碼區中的第一條指令,還記得我們之前提到的導出標籤麼,是的,_BOOT實際上就是一個導出標籤,在_BOOT標籤後緊跟著是一些全局變數的初始化操作,當然這是後話了,在目前我們提到的彙編中,還沒有全局變數初始化這一概念.這點我們將在後期StoryScript的高級語言中討論,但現在我們需要執行代碼怎麼辦,當然,這些都由用戶自己決定,如果你希望從某處開始執行,那麼你就應該在這裡添加一個導出標籤,例如如下代碼

EXPORT _MAIN:

MOV R1,」Hello,從這裡開始運行」

Ret

現在從哪裡運行解決了,那麼程序怎麼結束呢,注意上面的代碼有一個ret指令,這個指令的作用是從棧中彈出一個值,並將這個值作為這個函數的返回地址,可以看到,在這個函數前我們並沒有對棧進行操作,是的,虛擬機在調用這個導出標籤的時候,將會在棧中壓入一個值為-1的返回地址,當程序執行到ret時,發現返回地址是-1的話,就意味著這個程序已經執行完成了,那麼就會對程序進行資源回收,如果這是一個多線程調用的話,就會註銷這個線程,如果虛擬機中已經沒有需要執行的線程的話,就會掛起這個虛擬機.

StoryScript編譯器

如果說彙編語言是為了簡化直接編寫機器語言而誕生的,那麼大多數的高級語言的出現就是為了進一步簡化彙編語言而帶來的繁瑣.

在前幾章節中,筆者闡述了彙編語言的編譯與虛擬機的工作流程,但要將虛擬機實際應用這些還遠遠不夠,我們需要更具有效率的編程語言來提高開發的效率,在接下來的章節中主要討論高級語言編譯器的實現技術,當然鑒於篇幅的關係,我們仍然無法討論所有的技術細節,如果你有相關的需要,你可能需要在網上或書中查找更多相關的資料.

一段StoryScript程序

毫無疑問的是,編寫一個高級語言的編譯器需要花費大量的心血,其工作量甚至比之前的虛擬機和彙編編譯器加起來還多,不過幸運的是,彙編器已經為我們完成了大量的重要工作,比如字元串數據流資源的整理,符號的掃描和集成的彙編指令的實現.

在開始之前,我們仍然需要探討我們到底需要編寫一個什麼樣的高級語言編譯器,關於這點筆者參考了多種方案,最終使用了一個類C語言的方案來編寫StoryScript編譯器.這主要有以下幾個優點.

  1. 有現成的語言做參考,C語言有相當多的資料
  2. 函數式語言,過程化,實現起來相對簡單
  3. 筆者編寫C語言程序估摸算算也有十多年之久了,是的,筆者也使用過Java Pascal C++但最終還是回到了C語言的懷抱.
  4. C語言用的人也不少
  5. IDE就更多了,甚至很多情況下可以直接使用C語言的IDE來編寫StoryScript
  6. 筆者是堅定的C語言死忠粉.

那麼說了那麼多,到底StoryScript是怎麼樣的呢,筆者先寫一段StoryScript看看

#name 「Main」
#runtime thread 4
#runtime stack 4096
#define Num 9
Host void Print(string t);
String a,b;
Void print9x9(int c,int d)
{
Int I,j;
For(i=1;i<= Num;i++)
{
For(j=1;j<=I;j++)
Print(string(i)+」*」+string(j)+」=」+string(i*j)+」 」);
Print(「
」);
}
}
Export int start()
{
Print9x9(1,2);
}

這是一個輸出99乘法表的程序,你可以注意到i這個變數,不過這沒關係.,StoryScript是一個大小寫無關的語言.下面我們對這段程序進行分析,並最終闡述編譯器是如何工作的.

預處理

和彙編腳本語言一樣,StoryScript同樣有預處理指令,在這章節中將這段程序的預處理命令一起討論,首先我們先明確一點,StoryScript的編譯器其最終目的並不是編譯出指令流,而是將StoryScript高級語言轉換為符合其語法規則的彙編語言,之後再由彙編編譯器將其編譯成指令流.

首先我們要處理的是 #name這個預處理,這個是StoryScript特有的一個標示語句,每一個StoryScript必須在源代碼的開頭有這個語句,他的作用有點像這個源代碼起個名字,當然,每個源文件有且必須有一個名字,這樣當其他的源文件需要包含這個源文件時就可以用#include 」Name」來包含這個源文件了,其功能和C語言中的#include 「xxxx.h」是一樣的,你可能會問為什麼要多此一舉加上這個name專門去指定這個源文件的名字呢.直接用文件名不好麼,但筆者設計StoryScript的目的是,這個語言可以執行在任何可移植StoryVM的平臺上,這也意味著其編譯器可以一併移植到任意只要能提供C語言編譯環境的平臺上(這也任意平臺不僅可以執行編譯後的文件,還可以直接提供源代碼執行,也就是即可以當編譯型腳本用,也可以當解釋型腳本用),在很多的嵌入式平臺中,並不提供文件系統這一概念(實際上,StoryVM的虛擬機和編譯器的C語言代碼不包含任何的C語言標準庫,從內存池實現到數學運算全部都重新實現了一遍),因此筆者最終採用了這個方案來標識每個源代碼的名稱.

接下來是

#runtime thread 4

#runtime stack 4096

兩個語句,這兩個語句,在彙編中會直接被編譯為

.Thread 4

.Stack 4096

如你所見,他設置了這個腳本所支持的最大線程數量和默認的堆棧大小,當然,這兩個是可選的參數,如果你不寫這兩條語句,那麼,線程數會被默認設置為1,棧大小會被默認設置為65535

#define Num 9

這條語句和C語言的#define等價,也就是說,源文件中所有的Num會被替換為數字9

最後是Host void Print(string t);

這是一個函數定義,前面的Host關鍵字表面,這個函數在源文件中並不存在,它是一個host函數,host函數的作用在之前已經討論過了,它是虛擬機使用原生代碼實現的函數,是腳本調用原生代碼的一種方式,在之後的代碼中,如果調用這個Print函數,其彙編代碼會被翻譯為

Call $Print

這樣的指令.

函數的定義和調用

接下來就是start函數的定義和實現了

Void print9x9(int c,int d)

函數的調用一向是函數式語言的工作方式,從在StoryScript中並沒有與C語言類似的main函數,從哪裡開始執行是由用戶定義的,但從上面的這個語句來看這顯然是一個標準的函數定義,

在函數的定義期間,並不會生成實際工作的彙編代碼,但它會產生一個標號,並確定函數的棧分配和調用方式.

談及函數的調用關係,難以不提及當今主流的兩種比較有代表性的函數調用方式stdcall和cdecl,這兩種調用方式的參數傳遞方式都是從右向左壓棧,但唯一不同的是,stdcall在函數結束時由函數來維持堆棧平衡,而cdecl則是由調用方來維持堆棧平衡,為了演示這兩種調用方式的不同,我們查看兩種調用方案的彙編代碼

首先是stdcall的

push d
push c
call print9x9

在print9x9中需要彈出2個棧元素

然後是cdecl的

push d
push c
call print9x9
popn 2

在StoryScript中,我們默認採用的是cdecl的模式由調用者來平衡堆棧,這也就意味著調用者必須清理棧來保證堆棧平衡.

最後是關於訪問參數的問題了,正如我們之前提到的,LOCAL[x]實際訪問的是GLOBAL[x+BP],我們知道,每次CALL指令調用後,會將函數的返回地址壓人棧中,因此按照我們的思維來說,LOCAl[1]訪問的是參數c,LOCAL[2]訪問的是參數d,這也就意味著,我們必須在函數的開頭執行

MOV BP,SP將BP寄存器與棧進行掛鉤

這可以很好的工作沒有什麼問題,但是這樣的設計是存在缺陷的,當我們引入局部變數後,這種方式多多少少會引來不便.

變數與堆棧映射關係

我們在代碼中注意到,在代碼中有兩個變數的定義

其中一個是全局變數string a,b

另一個是局部變數int I,j;

那麼變數是如何隱射到堆棧中的呢,其中全局變數很好理解,我們只需要在堆中進行線性排布就可以了,例如,a實際上是GLOBAL[0],b實際上是GLOBAL[1]

那麼I,j如何處理呢,之前談論的方案很好的解決了參數的問題,但卻沒有解決好局部變數的問題,為了繼續容納局部變數I,j,我們需要對棧結構進行重新部署,在函數的開始時就為局部變數預留好空間,那麼在print9x9這個函數中,在MOV BP,SP之前,我們需要為局部變數開闢棧空間

SUB SP,2

MOV BP,SP

那麼,實際的棧結構變成了下面這個樣子

因此我們最終發現,參數和局部變數實際上存儲在同一個區域並沒有什麼差別,但要注意的是,局部變數的釋放在函數的結束一定要做,例如這裡在函數的結尾一定要加上popn 2否者程序就會崩潰,而在執行ret指令後,需要在做一個popn 2把壓入的參數釋放掉.

AST語法樹與遞歸下降分析法

abstract syntax tree (AST)抽象語法樹,那麼什麼是語法樹呢,簡單來說就是把代碼轉換為一個數結構便於分析的數據結構方案

那麼什麼是遞歸下降分析法呢,簡單來說就是模仿語法樹的分析方案建立起的一套演算法規則,準確來說,遞歸下降分析法主要是用來分析代碼中的表達式的.那麼表達式是什麼呢,通俗點說就是算式

例如下面的表達式

1+2*3

這個式子建立起的AST樹類似於這個樣子

因為2,3節點深度比1節點大,因此先計算2*3,然後結果再和1進行相加得到最終的結果,與AST樹稍有不同的是,遞歸下降分析法是基於堆棧式的語言,我們先來看看遞歸下降分析法是如何解決上述式子的解析的

為了方便描述,我們建立了兩個棧,一個叫做操作碼棧,一個叫操作數棧,操作碼棧簡單而言就是存放數字的,而操作數棧就是存放運算符例如加減乘除的,在進一步討論之前,我們需要先認識到運算符優先順序這一個概念,小學的知識告訴我們,乘法的優先順序比加法的高,因此,我們需要先計算乘法再計算加法,例如下面的表達式

1+2*3+4/5

因為乘法和除法的運算優先順序比加法高,因此,2*3和4/5會被優先計算,那麼遞歸下降分析法會如何處理呢,實際上,遞歸下降分析法會先計算2*3,然後結果與1進行相加,之後再計算4/5,再與之前的結果相加

遞歸下降分析法的核顯是,從左到右依次讀取運算符,如果讀取的運算符優先順序比上一個運算符優先順序小或處於同一優先順序,則進行計算.為了讓讀者更好地理解遞歸下降表達式的作用,我們一步一步對1+2*3+4/5用遞歸下降分析法進行運算

1.讀取第一個操作數1

操作數棧: 1

操作碼棧:

2.讀取操作碼+

操作數棧:1

操作碼棧:+

3.讀取操作數2

操作數棧:1,2

操作碼棧:+

4.讀取操作碼*

操作數棧:1,2

操作碼棧:+,*

5.讀取操作數3

操作數棧:1,2,3

操作碼棧:+,*

6.讀取操作碼+

操作數棧:1,2,3

操作碼棧:+,*

注意,在這個時候,因為加法的運算符優先順序比乘法的小,因此我們需要進行計算,因為乘法是一個雙目運算符,因此從操作數棧中彈出兩個操作數2,3計算2*3得到結果6,在這個時候,再把6壓入操作數棧中得到

操作數棧:1,6

操作碼棧:+

注意,因為加法的運算級和之前那個加號是同等運算優先順序,因此,會在進行計算,因為加法是雙目運算符,因此,從操作數棧彈出2個操作數繼續計算1+6得7,那麼最終結果變為了

操作數棧:7

操作碼棧:

最後,別忘了把讀取到的加號再次壓入棧中,於是就有

操作數棧:7

操作碼棧:+

7.讀取操作數4

操作數棧:7,4

操作碼棧:+

8.讀取操作碼 /

操作數棧:7,4

操作碼棧:+ /

9.讀取操作數5

操作數棧:7,4,5

操作碼棧:+ /

10.表達式結束,這個時候,當作讀取了一個優先順序為最低的運算符,因此需要處理所有還沒有處理的操作碼,,先進行除法運算,4/5的0.8

操作數棧:7,0.8

操作碼棧:+

執行加法運算

操作數棧:7.8

操作碼棧:

至此表達式結束,取得最終的結果7.8

從上面的遞歸下降分析中,我們很好地處理了這個表達式的解析關係,因為這個表達式的計算都是常量,計算起來也沒有那麼多的障礙,在StoryScript中,雖然同樣使用遞歸下降分析法來分析表達式問題,但因為存在變數的引用,實際產生的分析步驟卻複雜的多

例如下代碼

int a=2,b;

b=1+2*a;

那麼,下面的表達式是如何變成彙編代碼的呢

我們現在觀察遞歸下降中的堆棧變換,並最終將上述的表達式變為可執行的彙編代碼

1.讀取第一個操作數b

操作數棧: b

操作碼棧:

2.讀取操作碼=

操作數棧: b

操作碼棧:=

3.讀取操作數1

操作數棧: b,1

操作碼棧:=

4.讀取操作碼+

操作數棧: b,1

操作碼棧:=,+

5.讀取操作數2

操作數棧: b,1,2

操作碼棧:=,+

6.讀取操作碼*

操作數棧: b,1,2

操作碼棧:=,+,*

7.讀取操作數a

操作數棧: b,1,2,a

操作碼棧:=,+,*

8.表達式結束,按照遞歸下降的規則,我們先對乘法進行運算,得到2*a這個算式,為了完成這個算式,我們需要使用寄存器進行操作

MOV R1,2

MUL R1,a

這樣,R1的值就存儲著我們所需要的值了

那麼,棧是否變為了

操作數棧: b,1,R1

操作碼棧:=,+

呢,在這個表達式中,這樣當然沒有問題,然而實際的情況是如果我們直接將R1作為操作數壓入棧中,那麼碰上

b=2*a+4*a這樣的表達式就會出現問題了,因為2*a將結果放在了R1中,那麼4*a就不能再使用R1使用了否者會將原來的值覆蓋掉,那麼就只能選擇R2寄存器了,但是寄存器是有限的,如果這個表達式足夠的長,那麼我們的演算法體系就會瀕臨崩潰,因此我們不能直接將R1作為操作數壓入棧中,我們需要將R1作為一個值變成彙編代碼壓入運行的棧中變成這個樣子

MOV R1,2

MUL R1,a

PUSH R1,那麼,操作數棧實際變為了

操作數棧: b,1,POP

操作碼棧:=,+

那麼我們進行了下一步.下一步是一個加法運算,為了取得前一次計算的值我們需要進行一次pop操作,並將這個值放入R2寄存器當中,同樣的在計算結束後,結果仍然在R1中,我們還需要再次將R1進行壓棧

MOV R1,1
POP R2
ADD R1,R2
PUSH R1

這個時候,遞歸下降的兩個棧變成了

操作數棧: b,POP

操作碼棧:=

最後一次運算了

POP R2
MOV b,R2
MOV R1,b
PUSH R1

讀者可能會疑惑,為什麼還要MOV R1,b再PUSH R1呢,到MOV b,R2不是已經完成了這個表達式麼,當然,我們設計一個程序不能只看到這樣的一個表達式,在很多的時候我們必須要保證其通用性例如當碰上

b=(a=1)這樣的表達式時,你就知道為什麼我們需要」多此一舉」了,為了保證我們編譯的彙編程序的準確性,我們需要考慮各種不同的情況,儘管這可能會引入一系列的冗餘代碼,但這是值的的,冗餘的代碼我們可以在優化的部分再做處理,最後相信讀者也知道了,這個表達式最終的結果是什麼

MOV R1,2
MUL R1,a
PUSH R1
MOV R1,1
POP R2
ADD R1,R2
PUSH R1
POP R2
MOV b,R2
MOV R1,b
PUSH R1
POP R1

最後的POP R1,表示取得表達式的最終計算結果.並將它放入寄存器R1當中,當然我們也發現了這個表達式中仍然有非常多的冗餘代碼可以優化,但這是後話了.當然,最後別忘了彙編代碼中的a,b其實被映射到了LOCAL[]的棧元素中,筆者直接寫a,b只是為了方便讀者觀看,最終a,b會被替換成LOCAL[x]這種格式.

強類型與表達式類型匹配

雖然遞歸下降分析法為我們解決了不少的問題,但是仍然有很多額外的問題需要我們解決,其中一個就是類型在表達式中的作用,其中要說明的一點是StoryScript屬於強類型語言,一共支持四種類型

int---整數型

float----浮點型

string----字元串類型

memory-----數據流類型

除了int和float類型可以互相運算操作,string,其它類型間不允許直接進行計算

例如

string a;

a=」hello」+」world」

這個表達式是一個合法的表達式

但a=」hello」+123這個不是一個合法的表達式,在進行遞歸下降分析時,同樣需要對表達式的類型進行進一步的檢查,上面的字元串類型和一個整數類型進行加法運算顯然不是一個合法的表達式類型的運算,因此在檢查到這類無法類型匹配的表達式時,編譯器應該要拋出一個錯誤.

除了類型匹配之外,還需要注意的是運算符匹配,例如位運算中的與或非異或等操作面向的是整數型,如果表達式結果是其它類型同樣需要拋出一個錯誤

例如

int a=1;

a=a&1;這是一個合法的表達式

但是

int a=1;

a=(a+1.5)&1卻是一個不合法的表達式,因為a+1.5的運算結果是一個浮點數

不同類型間如果需要進行計算,需要專門的函數對其進行轉換,在StoryVM中,這些特殊的函數被直接編程到彙編指令中專門進行這種轉換操作,很多時候也管這種函數稱之為關鍵字,其作用類似於C語言中的sizeof,但有所不同的是,sizeof是編譯期間就已經完成的,而StoryScript中的關鍵字卻會變編譯成實體的彙編指令.

語法結構For語句

繼續觀察代碼,我們來到了For(j=0;j<=I;j++)這條語句,之所以在這個代碼中使用for語句作為示範是因為這個for語句最具有代表性,它包括了while和if語句的實現細節,可以說,如果你可以編譯For語句,你也可以很順利地編譯while和if語句

觀察for語句的結構基本由如下這種方式來完成

for(初始化表達式;條件判斷表達式;末尾循環體)

{

for循環體

}

我們之前已經說了遞歸下降分析表達式的方法,那麼剩下的就是如何構造for的語句結構了,為了方便說明筆者用一張圖來表示for語句結構的剖析

當執行到for語句的時候首先執行的是初始化代碼,執行完成後將會跳轉到條件判斷代碼中判斷代碼是否成立,如果不成立則直接結束,如果成立則會執行for循環體,當for循環體執行完成後再跳轉到末位循環體中,讀者可能會有所疑問,為什麼末位循環體被前置到那個位置,安裝邏輯不應該在for循環體之後麼,雖然道理大家都懂但是從編譯的角度進行分析,在我們編譯for語句的時候,最先被解析的表達式就是初始化代碼區,條件判斷和末位循環體的表達式,而for循環體中的代碼可能很複雜還可能包含有各種的嵌套結構,因此如果將末位循環體放在for循環體之後,其實現起來會複雜的多,一個東西越複雜,那麼其就越有可能出錯,因此我們採用了這種折中的方式來實現for循環體,效果一樣卻節省了大量的代碼,這也是筆者為什麼一直強調,很多問題只有在你真正動手去做了你才知道怎麼回事,有些東西書本上無法告訴你,那套聽上去吊炸天的架構和公式也無法最終幫你解決很多問題

最後,我們手寫下For(j=0;j<=I;j++)的編譯結果

//初始化代碼區
mov R1,0
mov j,R1
JMP _FOR_condition
//末位循環體
_FOR_LOOPEXPR:
ADD I,1
//條件判斷
MOV R1,j
MOV R2,i
LGLE R1,R2 //如果R1小於R2,則R1為1否者為0
JE R1,0,_FOR_END;//如果R1位0,for語句結束
for循環體的彙編代碼
JMP _FOR_LOOP_EXPR
_FOR_END;

IF語句編譯

相對於for語句的實現,if語句的實現就簡單的多了,IF語句的格式如下

if(條件表達式)
{
IF語句塊
}
else
{
ELSE處理
}

如下圖所示

一開始到達的是條件判斷代碼區,如果條件判斷為假,則跳轉到else語句塊中如果為真就繼續執行,當然在if語句塊執行結束後也要跳轉到結束,不然就繼續執行else語句塊裡面的代碼了

相信要編寫相應的彙編代碼並不複雜.筆者就不繼續複述了.

while語句編譯

while語句估計是三種語句中最簡單的一種了,其語法格式如下

while(條件判斷)
{
while語句塊
}

就直接看圖吧

首先執行條件判斷,如果為假,跳轉到結束,否者執行while語句塊也就是循環體,循環體執行結束後再跳轉到條件判斷中繼續執行.

其它語法結構

當然有了上述幾種結構後,對於其它結構怎麼來的讀者應該可以自行發揮想像了,像do while,switch等應該都可以按照上述的思路去完成,在碼農界常常稱這些結構為語法糖,但不管語法糖怎麼造,實際上while和if語句幾乎就可以解決所有的邏輯問題了,因此不管一門語言怎麼變,瞭解其最根本的東西纔是關鍵的,不管一個語言的語法糖有多好,真正適合自己的,能做出自己需要功能的語言纔是一門好語言

當然在StoryScript中筆者自行實現了Compare語句作為switch語句的替代品

其語法格式為

Compare(比較表達式1)
{
with(比較表達式2;比較表達式3…..)
{
with語句塊
}
………
}

其作用為當比較表達式1和with中其中一個表達式的結果相等,那麼就執行with語句塊中的代碼,實際上一個compare語句中可以包含多個with語句,其和switch語句稍有不同的是,with語句中的表達式不同於case需要是一個常量,因此它比switch語句用起來會方便的多,但相對的,其比switch語句在比較較多的條件下性能肯定不如switch,不過既然是一門腳本語言,我們自然不能在性能上奢求太多,畢竟我們無法做到面面俱到.一門語言著眼於做好一類問題,其它方面儘可能好就行了.

嵌套語句的處理

在StoryScript編譯器的最後,筆者想最後聊聊關於語句嵌套的問題,那麼什麼是語句嵌套呢,觀察下面的代碼

if(a>10)
{
if(a>20)
{
}
}

這是一個標準的嵌套語句,由2個IF語句構成,雖然它們都是IF語句,但是處理起來卻不願意,因為if(a>20)是包含在if(a>10)的語句塊裏的,實際上在處理語句嵌套的問題上,編譯器採用棧的方式對這些嵌套語句進行處理,當一個語句塊結束後,再將它從棧中彈出來並且添加其結束代碼(語句塊結束有一個很明顯的特徵,那就是有一個右花括弧)

例如在上面的代碼中,我們把第一個IF叫做IF1,第二個IF叫做IF2,從之前的代碼生成我們知道,語句塊的控制基本是有標籤+跳轉來實現的,那麼因為名字的不同,這兩個if語句塊將會生成不同的標籤

因此實際上述代碼的實際處理流程實際上是這樣的

  1. 碰到了第一個if語句,將它叫做if1,然後將這個if語句壓棧
  2. 碰到了第二個if語句,將它叫做if2,然後將這個if語句壓棧
  3. 碰到了花括弧},從棧中彈出一個語句塊,發現這個花括弧屬於if2的那麼添加if2的跳轉
  4. 碰到了花括弧},從棧中彈出一個語句塊,發現這個花括弧屬於if1的那麼添加if1的跳轉
  5. 分析結束

這個過程適用於任何的語句嵌套,例如

for()
{
if()
{
}
}

這種格式的或者是

while()
{
for()
{
}
}

這種格式的嵌套,每次處理到花括弧}時,都從棧中彈出一個結構,然後再添加相應的處理代碼,這種棧式的處理方式能夠正確的處理嵌套語句的代碼生成,同時這也為我們處理continue和break兩個特殊指令的關鍵字提供了思路

眾所周知的continue和break語句僅對while for switch(這裡應該是compare) do while語句生效,因此當找到這類特殊指令時,應該從棧頂開始搜索並找到第一個符合條件的結構,然後添加對應的處理代碼.

結語

不管怎麼說,設計一套虛擬機和編譯器系統是一個龐大的工程,從詞法到語法分析到整個虛擬機系統的設計和編譯器的優化筆者將近使用了5w餘行的代碼來完成其具體實現,當你真正動手寫一個東西時,你會發現有很多之前你都沒能考慮到或者是考慮周全的問題,因此儘管碼農界一直在說不要重複造輪子,但有一些輪子你不自己造一造恐怕你永遠不知道他具體是怎麼回事.

最後,筆者將之上一章節的99乘法表代碼使用這套編譯系統運行,你可以在本文的附件中找到這段代碼的DEMO,同時你也可以修改這個代碼自己嘗試一下這個編譯器編譯的過程和結果.

點擊文件夾,找到StoryScript Console.exe

運行

點擊Load,然後在文件對話框中選中99乘法表示範程序.txt,觀察輸出結果

你可以任意修改示範程序中的代碼,在示範程序中,程序由Main函數開始執行,有一個導入的host函數為Print,意為在控制檯輸出消息

同時你會發現在腳本的同一目錄下生成了兩個新的文件,一個為.asm後綴的文件,一個是st後綴文件

你可以打開asm文件查看編譯器是如何將StoryScript編譯為彙編代碼的,也可以使用hex打開st文件查看編譯後的文件結果

當然在最後,你可以直接Load編譯後的程序,那麼它將直接運行出99乘法表同樣的結果.


推薦閱讀：
相關文章