1 簡介

1.1 說明

little c 解釋器
http://blog.csdn.net/redraiment/article/details/4693952
編譯器：https://www.amobbs.com/thread-5536737-1-1.html

這里面所說的虛擬機，其實也算是元編程的一種實現(xiàn)方式。

目前的虛擬機有以下幾種：
CLR, JVM, Parrot, LLVM。

要在小型單片機上運行編譯器痹升，我暫時想到兩個辦法：
（1）如果程序空間足夠裝下編譯器代碼，但內(nèi)存不夠畦韭，可以利用SD卡疼蛾，將asmcode[]、mcode[]等存入SD卡（或其它存儲設(shè)備）艺配。
（2）如果程序空間只能裝下虛擬機的代碼察郁，則可以將這個編譯器的C代碼用“簡單C” 的語法重新寫一下，（在電腦上）編譯成機器碼存入SD卡中转唉，讓單片機運行虛擬機皮钠，運行SD卡中的代碼，就是說在虛擬機中運行編譯器酝掩；

比較值得有參考價值的虛擬機分析：參考鏈接

而標(biāo)準(zhǔn)規(guī)范的java虛擬機文檔：鏈接

1.2 名詞

1.2.1 前綴表達(dá)式

也稱為前綴記法鳞芙、波蘭式眷柔。稱作波蘭式是為了紀(jì)念其發(fā)明者波蘭數(shù)學(xué)家Jan Lukasiewicz期虾。

1.2.2 中綴表達(dá)式

同類型的還有前綴表達(dá)式，后綴表達(dá)式驯嘱。

中綴表達(dá)式是指運算符在運算數(shù)的中間镶苞，計算中綴表達(dá)式時需要用到兩個棧：數(shù)字棧和運算符棧。在整個中綴表達(dá)式求值的過程中主要涉及到的模塊有：棧的相關(guān)操作鞠评、優(yōu)先級表的確立茂蚓、輸入的待計算字符串拆分為數(shù)字和運算符以及運算處理等

有一個比較不錯的寫法，鏈接

1.2.3 后綴表達(dá)式

后綴表達(dá)式(又稱為逆波蘭reverse polish)就是不需要括號就可以實現(xiàn)調(diào)整運算順序的一種技巧。

1.2.3 二叉樹

可以通過不同遍歷方式組合成中輟表達(dá)式和后綴表達(dá)式聋涨。
二叉樹定義：每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)晾浴。

2 rt-thread的finsh shell

先從rt-thead的finsh shell開始研究。
rt-thread的github鏈接地址：下載鏈接

整體代碼邏輯：
在finsh_run_line中調(diào)用以下三個主要函數(shù)牍白，完成大體功能脊凰。

• finsh_parser_run
  完成xxxx
• finsh_compiler_run
• finsh_vm_run

這樣的流程，在我的理解來看茂腥，就是一個 解析器(語法解析器)狸涌，編譯器(解釋器)，虛擬機執(zhí)行的過程最岗。

對finsh_parser_run進(jìn)行分析：

• 若在shell中輸入表達(dá)式： 1 + 1
• a.執(zhí)行： proc_expr_statement
• b.執(zhí)行： proc_expr
• c.執(zhí)行：proc_assign_expr
• d.執(zhí)行：proc_inclusive_or_expr帕胆，帶有后續(xù)處理
• e.執(zhí)行：proc_exclusive_or_expr，帶有后續(xù)處理
• f.執(zhí)行：proc_and_expr般渡，有后續(xù)處理
• g.執(zhí)行：proc_shift_expr懒豹，有后續(xù)處理
• h.執(zhí)行：proc_additive_expr，有后續(xù)處理
• i.執(zhí)行：proc_multiplicative_expr诊杆，有后續(xù)處理
• j.執(zhí)行：proc_cast_expr歼捐，有后續(xù)處理
• k.執(zhí)行：proc_unary_expr
• l.執(zhí)行：proc_postfix_expr，調(diào)用該函數(shù)之前調(diào)用了finsh_token_replay晨汹。
• m.執(zhí)行：proc_primary_expr豹储，最終執(zhí)行到底。

執(zhí)行到proc_primary_expr后淘这，能識別出1剥扣。也就是說，執(zhí)行到分支：finsh_token_type_value_int铝穷。同時往數(shù)組global_node_table添加一個finsh_node钠怯。

然后：

1. 返回到proc_postfix_expr，其中將該函數(shù)返回值賦值給struct finsh_node* postfix;該值應(yīng)該就是前面識別出來的結(jié)點1曙聂。隨后調(diào)用next_token晦炊，經(jīng)過一系列處理，token的值為：finsh_token_type_add宁脊。然后該函數(shù)仍舊執(zhí)行了finsh_token_replay断国，返回了上面提到的postfix。
2. 返回到proc_unary_expr榆苞，仍舊繼續(xù)返回稳衬。返回到，proc_cast_expr坐漏。
3. proc_cast_expr后薄疚，返回的仍然是1的結(jié)點碧信。
4. 后面一直返回到proc_additive_expr，其調(diào)用完成proc_multiplicative_expr后街夭，執(zhí)行next_token砰碴，而token的值為finsh_token_type_add。mul是1的結(jié)點板丽。mul_new返回值為 proc_multiplicative_expr的結(jié)果衣式。這一次調(diào)用proc_multiplicative_expr，執(zhí)行到proc_cast_expr檐什，搜尋next_token碴卧，這個時候找到另外一個1結(jié)點。最終mul_new就是另外一個1結(jié)點了乃正。這個結(jié)點就是global_node_table創(chuàng)建的第二個值了住册。
5. 返回到proc_additive_expr，執(zhí)行make_sys_node瓮具，創(chuàng)建FINSH_NODE_SYS_ADD結(jié)點荧飞。后執(zhí)行賦值，node->child(+)=先找到的結(jié)點1名党，結(jié)點1->sibling=結(jié)點1叹阔。最后返回FINSH_NODE_SYS_ADD結(jié)點。
6. 最后返回到self->root = node;那么self->root就是前面提到的FINSH_NODE_SYS_ADD結(jié)點传睹。

• 對finsh_parser_run進(jìn)行分析：

• a.執(zhí)行finsh_type_check
• b.清除text_segment耳幢，finsh_vm_stack。設(shè)置finsh_compile_sp欧啤，finsh_compile_pc睛藻。
• c.獲取sibling node，調(diào)用finsh_compile邢隧，傳參數(shù)為root node店印，如果有sibling，則彈出棧sibling node倒慧。

重點在分析finsh_compile上：

• a.判斷node->child是否為空按摘，否則編譯child結(jié)點。這里使用的遞歸的操作方法纫谅。
• b.判斷node->node_type炫贤，最先判斷的child的node_type，為FINSH_NODE_VALUE_INT系宜。接著執(zhí)行照激，

finsh_code_byte(FINSH_OP_LD_DWORD);
finsh_code_dword(node->value.long_value);

• c.遞歸獲取到child->sibling結(jié)點发魄。編譯sibling結(jié)點盹牧。

finsh_code_byte(FINSH_OP_LD_DWORD);
finsh_code_dword(node->value.long_value);

• d.判斷的是root->node_type俩垃，是FINSH_NODE_SYS_ADD。執(zhí)行：

finsh_code_byte(FINSH_OP_ADD_BYTE);

從這里看汰寓，仍然是一種后綴表達(dá)式的形式口柳。

• 對finsh_vm_run進(jìn)行分析：

    finsh_sp = &finsh_vm_stack[0];

    /* set pc to the beginning of text segment */
    finsh_pc = &text_segment[0];

    while ((finsh_pc - &text_segment[0] >= 0) &&
        (finsh_pc - &text_segment[0] < FINSH_TEXT_MAX))
    {
        /* get op */
        op = *finsh_pc++;

        /* call op function */
        op_table[op]();
    }

在前面說的compile中，數(shù)據(jù)存儲的內(nèi)容為：
0x24
4字節(jié)數(shù)值有滑，低字節(jié)在前跃闹，高字節(jié)在后。
0x24
4字節(jié)數(shù)值毛好，低字節(jié)在前望艺，高字節(jié)在后。
0x03

所以肌访，虛擬機執(zhí)行的為：

• a.執(zhí)行OP_ld_dword找默，獲取4字節(jié)數(shù)據(jù)，然后放到棧上吼驶。同時pc指針前進(jìn)惩激。
• b.繼續(xù)執(zhí)行a步驟操作。
• c.執(zhí)行OP_add_dword蟹演，最終調(diào)用OP_BIN_DWORD风钻，將棧中數(shù)據(jù)進(jìn)行處理，同時出棧指針遞減酒请，也就是出棧數(shù)據(jù)骡技。

自此，按照例子 1 + 1的整個路徑分析完成羞反。

那么哮兰，三個函數(shù)做的事情，總結(jié)如下：

• finsh_parser_run主要是將字符串苟弛，一個個分拆喝滞，也就是編譯原理中會說的詞法分析。然后形成一棵樹膏秫。
• finsh_compiler_run主要是將樹中的數(shù)據(jù)提取出來右遭，放到虛擬機中的代碼段中。這里并沒有區(qū)分?jǐn)?shù)據(jù)區(qū)和代碼區(qū)缤削，一股腦的放在一起窘哈。
• finsh_vm_run主要是將代碼段中的數(shù)據(jù)，根據(jù)操作碼亭敢，提取出數(shù)據(jù)滚婉，放到棧中。這里面用到了后綴表達(dá)式帅刀，先提取出兩個數(shù)让腹，然后第三個數(shù)是+远剩，-，*骇窍，/等等的操作碼瓜晤，計算完成后，可以出一個棧的數(shù)據(jù)腹纳，然后繼續(xù)處理痢掠。

接著再來看看輸入一個函數(shù)，是怎樣的執(zhí)行流程嘲恍。比如hello()：
我先說明一點足画，輸入函數(shù)，函數(shù)的參數(shù)個數(shù)佃牛，rt-thread的shell并沒有做檢測锌云，這應(yīng)該是一個失誤，是一個很不好的設(shè)計吁脱。

• 1. finsh_parser_run中調(diào)用token_run中桑涎，獲取到current_token為finsh_token_type_identifier。后執(zhí)行到proc_primary_expr兼贡，執(zhí)行finsh_node_new_id()攻冷，會先調(diào)用finsh_var_lookup()，沒找到就調(diào)用finsh_sysvar_lookup()遍希，仍沒找到等曼，就調(diào)用finsh_syscall_lookup()，當(dāng)然按照例子上來看凿蒜，最終是找到了禁谦。最后會調(diào)用finsh_node_allocate()，分配結(jié)點废封，node_type為FINSH_NODE_ID州泊。也就是下面這幾個：

global_node_table[i].node_type = FINSH_NODE_ID;
node->id.syscall = xxx;
node->idtype = FINSH_IDTYPE_SYSCALL;

2. 執(zhí)行到函數(shù)proc_postfix_expr()，調(diào)用完proc_primary_expr()后漂洋，執(zhí)行next_token()遥皂，進(jìn)入分支finsh_token_type_left_paren，接著就去尋找右括號。我們不看找不到右括號或者帶參數(shù)情況，只看找到了右括號后的執(zhí)行路徑衅疙。
   3.調(diào)用make_sys_node，這個時候样悟，添加結(jié)點FINSH_NODE_SYS_FUNC，并把上面的FINSH_NODE_ID添加進(jìn)來。也就是說窟她，root為FINSH_NODE_SYS_FUNC結(jié)點陈症，child為FINSH_NODE_ID，sibling為空礁苗。
   4.調(diào)用finsh_compile，進(jìn)入分支FINSH_NODE_ID徙缴，判斷child是否為空试伙，若不為空，則調(diào)用

                    finsh_code_byte(FINSH_OP_LD_DWORD);
                    finsh_code_dword((long)node->id.syscall->func);

在代碼段中形成的結(jié)構(gòu)為：
0x24
函數(shù)地址
接著執(zhí)行FINSH_NODE_SYS_FUNC于样，調(diào)用：

                    finsh_code_byte(FINSH_OP_SYSCALL);
                    finsh_code_byte(parameters);

其中參數(shù)個數(shù)為0
在代碼段中存儲的數(shù)據(jù)為：
0x2C
0

• 執(zhí)行虛擬機函數(shù)finsh_vm_run()疏叨，調(diào)用OP_ld_dword()，將函數(shù)地址入棧穿剖，finsh_sp->long_value=函數(shù)地址蚤蔓。然后調(diào)用OP_call()，獲取參數(shù)個數(shù)糊余，當(dāng)然為0秀又。后面就是相關(guān)的函數(shù)調(diào)用了。

好了贬芥，rt-thread的finsh shell就講到這里吐辙。實話說，其調(diào)用關(guān)系比較層疊蘸劈』杷眨看起來每個函數(shù)調(diào)用關(guān)系分開，寫得很好威沫。但是贤惯，目前很多的特性，支持力度還是有限的棒掠。

后想了想孵构，對于我們常見的說法，函數(shù)參數(shù)列表先入棧的是最后一個參數(shù)烟很，這里可以驗證一下：

找到函數(shù)proc_param_list浦译，這個就是處理參數(shù)列表的。
最終調(diào)用到proc_cast_expr() -->proc_type()---> 找到第一個參數(shù)(我們先分析參數(shù)全為數(shù)字),則token為finsh_token_type_value_int---->遞歸調(diào)用proc_cast_expr()--->proc_unary_expr()--->proc_postfix_expr()--->proc_primary_expr()--->finsh_node_new_int()溯职。
然后遞歸返回精盅，node->data_type = finsh_type_unknown;node->node_type = FINSH_NODE_VALUE_INT;
當(dāng)然在proc_postfix_expr()中調(diào)用的next_token，會設(shè)置token==finsh_token_type_comma谜酒。--->proc_cast_expr()--->next_token()--->FINSH_NODE_VALUE_INT叹俏。etc

    while (token == finsh_token_type_comma )
    {
        finsh_node_sibling(assign) = proc_assign_expr(self);

        if (finsh_node_sibling(assign) != NULL) assign = finsh_node_sibling(assign);
        else finsh_error_set(FINSH_ERROR_EXPECT_OPERATOR);

        next_token(token, &(self->token));
    }

從這個循環(huán)代碼中，可以發(fā)現(xiàn)是一直在建立siblings僻族。后面finsh_compile被調(diào)用粘驰，然后遞歸生效屡谐，最后一個參數(shù)被加入到棧中。

所以蝌数，很明顯咯愕掏，是遞歸導(dǎo)致的棧序改變。

還可以看看rt-thread的shell的函數(shù)調(diào)用顶伞，一層一層的饵撑，其實是按照操作符的優(yōu)先級來的。

2.1 一些擴展知識

在寫完一些內(nèi)容之后唆貌，發(fā)現(xiàn)finsh shell有一些命名技巧滑潘，這就涉及到一些知識。我也是邊看就搜咯锨咙。

2.1.1 siblings

這個在二叉樹上有介紹语卤，表示的是兄弟結(jié)點。二叉樹有完美二叉樹酪刀、完全二叉樹和完滿二叉樹粹舵。

寫到這里，我只好表示骂倘，我的樹知識欠缺齐婴，只好另外開一個欄，學(xué)習(xí)樹了稠茂。
鏈接：鏈接地址

2.2 分析開始

分析之初柠偶，這幾個結(jié)構(gòu)體比較重要：

3 picoC

源碼的下載地址為：下載鏈接

從其README.md上看，其說明了picoC是一個小的C解釋器腳本睬关。它最初是作為一個無人機的飛行系統(tǒng)板上的腳本語言诱担。核心的C源代碼是大約3500行。并不打算成為一個完整的ISO C實現(xiàn)电爹。picoc已經(jīng)在x86-32蔫仙，x86-64，PowerPC丐箩，arm摇邦，UltraSPARC，HP-PA和Blackfin處理器上測試過屎勘，并很容易地移植到新的目標(biāo)施籍。

picoc代碼上看，基本有如下幾塊:lex詞法解析概漱，table一個基本數(shù)據(jù)結(jié)構(gòu)（用于存放變量）丑慎，是個字符串hash表，heap管理內(nèi)存分配（包括了stack frame的實現(xiàn)）， type做類型管理（基本型別和程序自定義的struct竿裂，typedef等）,expression做表達(dá)式解析,variable變量管理分配釋放棧幀玉吁。

2.1 編譯

在NIX/Linux/POSIX主機上：

• make
• make test

之后，可以執(zhí)行./picoc腻异。
可以有三種執(zhí)行方式：

圖1

2.2 移植

1. platform_XXX.c 包含一些支持性的函數(shù)进副。編譯器這樣才能在你的平臺上運行。例如如何向控制臺輸出字符悔常。
2. platform_library.c包含一些函數(shù)庫影斑，這些庫是提供給用戶程序的。
3. 有clibrary.c这嚣，包含用戶庫函數(shù)鸥昏，比如printf塞俱，這些是平臺無關(guān)的姐帚。

移植系統(tǒng)，需要在platform.h中設(shè)置相應(yīng)的includes和defines障涯。在platform_XXX.c中編寫I/o函數(shù)罐旗。在platform_library.c 中編寫用戶函數(shù)。在picoc.c中編寫一些main函數(shù)內(nèi)容唯蝶。

platform.h默認(rèn)設(shè)置為unix主機(UNIX_HOST)九秀。

2.3 協(xié)議

picoc遵循"New BSD License".