4.從語法樹到OP CODE
知道咱們的虛擬機能夠執(zhí)行OP CODE之后，下一步就要考慮，怎么從語法樹里面生成咱們需要的OP CODE了。簡單來講，語法樹就是將程序的邏輯按照樹狀組織并保存在內(nèi)存中的一種形式。有關(guān)于更詳細的信息，搜“Syntax Tree”，到處都是解釋。
一時不明白也沒關(guān)系，我們來看一個直觀的例子。考慮a+b這樣一個基本形式的表達式。這個表達式既可以按照我們所寫的這樣，分為a，+，b三個部分串行表示，也可以表示成下圖的樣子
可能一個表達式你還看不出來樹形的優(yōu)勢。要是表達式級聯(lián)起來，就顯示出這種表示的威力了：
這樣一個語法樹，可以不借助任何別的手段，保存了表達式的優(yōu)先級關(guān)系。這里的語法樹表示的就是(A+B)*C的表達式。同時，在語法樹上求值也很方便，后根遍歷語法樹就可以了。即先算出左右節(jié)點的值，再根據(jù)當(dāng)前節(jié)點符號求出當(dāng)前節(jié)點值。
王陽明說，知行合一。知道了語法樹是什么東西，我們就要開始考慮怎么用了。“怎么用”這個問題可以分成兩個部分，第一，語法樹怎么實現(xiàn)。第二，語法樹怎么生成op code。啊，先不要把語法樹想象的這么復(fù)雜。在這里，我們的運算符只有加號，一個加號也只能帶兩個int的值節(jié)點，而不能遞歸的帶上一個符號節(jié)點。也就是說，這棵樹只可能有一種形式而已。
首先來解決語法樹怎么實現(xiàn)的問題。在這個問題上，我們只需要把握一點，語法樹是一個天然的composite模式。我們用一個UML來看看這個只有加法算符的語法樹定義：
唔，很簡潔，不是么。Node_type是一個syntax_node_types類型的枚舉，這個枚舉告訴以后的代碼生成器這個抽象的node究竟是個什么類型，然后代碼生成器再還原它原本的類型并生成適當(dāng)?shù)拇a。op是一個operators類型的枚舉，表示一個二元運算的操作符。對于本例，只有operators::add可用。
在有了基本實現(xiàn)之后，再考慮一下其它需求，例如語法樹節(jié)點類型之間的可能存在的循環(huán)依賴問題，語法樹的深淺拷貝問題，等等，最終SASL的語法樹節(jié)點接口是這樣的：
1 struct node{
2 syntax_node_types type;
3 template <typename NodeT> NodeT* clone() const;
4 template <typename NodeT> NodeT* deepcopy() const;
5 protected:
6 virtual node* clone_impl() const = 0;
7 virtual node* deepcopy_impl() const = 0;
8 };
9
10 struct binary_expression: public node{
11 operators op;
12 boost::shared_ptr<constant> left_expr;
13 boost::shared_ptr<constant> right_expr;
14 };
15
16 struct constant: public node{
17 int val;
18 };
道理復(fù)雜，不過實際上，并沒有那么復(fù)雜吧？
下面來解決第二個問題：怎么用表達式樹產(chǎn)生代碼？我不多解釋，直接上代碼，相信你一定會看明白的：
1 vm_codegen& vm_codegen::emit_expression( const binary_expression& expr ){
2 if ( expr.op != operators::add ){ return *this; }
3 int c0 = expr.left_expr->val;
4 int c1 = expr.right_expr->val;
5 ins_.push_back( instruction( op_loadrc, r0, c0 ) );
6 ins_.push_back( instruction( op_loadrc, r1, c1 ) );
7 ins_.push_back( instruction( op_add, r0, r1 ) );
8 return *this;
9 }
然后我們將生成語法樹，生成code，運行code的代碼補上，運行，OK~
你一定會說，啊，硬性綁定寄存器！太可怕了！如果表達式復(fù)雜了該怎么辦呢？呵呵。這些都是以后的問題了。以后的問題，就由以后的我們?nèi)ソ鉀Q好了。今日事，今日畢，時間不早，咱們還是洗洗睡了。