4.從語(yǔ)法樹(shù)到OP CODE
知道咱們的虛擬機(jī)能夠執(zhí)行OP CODE之后，下一步就要考慮，怎么從語(yǔ)法樹(shù)里面生成咱們需要的OP CODE了。簡(jiǎn)單來(lái)講，語(yǔ)法樹(shù)就是將程序的邏輯按照樹(shù)狀組織并保存在內(nèi)存中的一種形式。有關(guān)于更詳細(xì)的信息，搜“Syntax Tree”，到處都是解釋。
一時(shí)不明白也沒(méi)關(guān)系，我們來(lái)看一個(gè)直觀的例子。考慮a+b這樣一個(gè)基本形式的表達(dá)式。這個(gè)表達(dá)式既可以按照我們所寫(xiě)的這樣，分為a，+，b三個(gè)部分串行表示，也可以表示成下圖的樣子
可能一個(gè)表達(dá)式你還看不出來(lái)樹(shù)形的優(yōu)勢(shì)。要是表達(dá)式級(jí)聯(lián)起來(lái)，就顯示出這種表示的威力了：
這樣一個(gè)語(yǔ)法樹(shù)，可以不借助任何別的手段，保存了表達(dá)式的優(yōu)先級(jí)關(guān)系。這里的語(yǔ)法樹(shù)表示的就是(A+B)*C的表達(dá)式。同時(shí)，在語(yǔ)法樹(shù)上求值也很方便，后根遍歷語(yǔ)法樹(shù)就可以了。即先算出左右節(jié)點(diǎn)的值，再根據(jù)當(dāng)前節(jié)點(diǎn)符號(hào)求出當(dāng)前節(jié)點(diǎn)值。
王陽(yáng)明說(shuō)，知行合一。知道了語(yǔ)法樹(shù)是什么東西，我們就要開(kāi)始考慮怎么用了。“怎么用”這個(gè)問(wèn)題可以分成兩個(gè)部分，第一，語(yǔ)法樹(shù)怎么實(shí)現(xiàn)。第二，語(yǔ)法樹(shù)怎么生成op code。啊，先不要把語(yǔ)法樹(shù)想象的這么復(fù)雜。在這里，我們的運(yùn)算符只有加號(hào)，一個(gè)加號(hào)也只能帶兩個(gè)int的值節(jié)點(diǎn)，而不能遞歸的帶上一個(gè)符號(hào)節(jié)點(diǎn)。也就是說(shuō)，這棵樹(shù)只可能有一種形式而已。
首先來(lái)解決語(yǔ)法樹(shù)怎么實(shí)現(xiàn)的問(wèn)題。在這個(gè)問(wèn)題上，我們只需要把握一點(diǎn)，語(yǔ)法樹(shù)是一個(gè)天然的composite模式。我們用一個(gè)UML來(lái)看看這個(gè)只有加法算符的語(yǔ)法樹(shù)定義：
唔，很簡(jiǎn)潔，不是么。Node_type是一個(gè)syntax_node_types類(lèi)型的枚舉，這個(gè)枚舉告訴以后的代碼生成器這個(gè)抽象的node究竟是個(gè)什么類(lèi)型，然后代碼生成器再還原它原本的類(lèi)型并生成適當(dāng)?shù)拇a。op是一個(gè)operators類(lèi)型的枚舉，表示一個(gè)二元運(yùn)算的操作符。對(duì)于本例，只有operators::add可用。
在有了基本實(shí)現(xiàn)之后，再考慮一下其它需求，例如語(yǔ)法樹(shù)節(jié)點(diǎn)類(lèi)型之間的可能存在的循環(huán)依賴(lài)問(wèn)題，語(yǔ)法樹(shù)的深淺拷貝問(wèn)題，等等，最終SASL的語(yǔ)法樹(shù)節(jié)點(diǎn)接口是這樣的：
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ù)雜，不過(guò)實(shí)際上，并沒(méi)有那么復(fù)雜吧？
下面來(lái)解決第二個(gè)問(wèn)題：怎么用表達(dá)式樹(shù)產(chǎn)生代碼？我不多解釋?zhuān)苯由洗a，相信你一定會(huì)看明白的：
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 }
然后我們將生成語(yǔ)法樹(shù)，生成code，運(yùn)行code的代碼補(bǔ)上，運(yùn)行，OK~
你一定會(huì)說(shuō)，啊，硬性綁定寄存器！太可怕了！如果表達(dá)式復(fù)雜了該怎么辦呢？呵呵。這些都是以后的問(wèn)題了。以后的問(wèn)題，就由以后的我們?nèi)ソ鉀Q好了。今日事，今日畢，時(shí)間不早，咱們還是洗洗睡了。