1 簡介

1.1 說明

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

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

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

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

比較值得有參考價(jià)值的虛擬機(jī)分析：參考鏈接

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

1.2 名詞

1.2.1 前綴表達(dá)式

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

1.2.2 中綴表達(dá)式

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

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

有一個(gè)比較不錯(cuò)的寫法，鏈接

1.2.3 后綴表達(dá)式

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

1.2.3 二叉樹

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

2 rt-thread的finsh shell

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

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

• finsh_parser_run
  完成xxxx
• finsh_compiler_run
• finsh_vm_run

這樣的流程，在我的理解來看，就是一個(gè) 解析器(語法解析器)，編譯器(解釋器)，虛擬機(jī)執(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í)往數(shù)組global_node_table添加一個(gè)finsh_node。

然后：

1. 返回到proc_postfix_expr，其中將該函數(shù)返回值賦值給struct finsh_node* postfix;該值應(yīng)該就是前面識別出來的結(jié)點(diǎn)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é)點(diǎn)。
4. 后面一直返回到proc_additive_expr，其調(diào)用完成proc_multiplicative_expr后，執(zhí)行next_token，而token的值為finsh_token_type_add。mul是1的結(jié)點(diǎn)。mul_new返回值為 proc_multiplicative_expr的結(jié)果。這一次調(diào)用proc_multiplicative_expr，執(zhí)行到proc_cast_expr，搜尋next_token，這個(gè)時(shí)候找到另外一個(gè)1結(jié)點(diǎn)。最終mul_new就是另外一個(gè)1結(jié)點(diǎn)了。這個(gè)結(jié)點(diǎn)就是global_node_table創(chuàng)建的第二個(gè)值了。
5. 返回到proc_additive_expr，執(zhí)行make_sys_node，創(chuàng)建FINSH_NODE_SYS_ADD結(jié)點(diǎn)。后執(zhí)行賦值，node->child(+)=先找到的結(jié)點(diǎn)1，結(jié)點(diǎn)1->sibling=結(jié)點(diǎn)1。最后返回FINSH_NODE_SYS_ADD結(jié)點(diǎn)。
6. 最后返回到self->root = node;那么self->root就是前面提到的FINSH_NODE_SYS_ADD結(jié)點(diǎn)。

• 對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。

重點(diǎn)在分析finsh_compile上：

• a.判斷node->child是否為空，否則編譯child結(jié)點(diǎn)。這里使用的遞歸的操作方法。
• 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é)點(diǎn)。編譯sibling結(jié)點(diǎn)。

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

所以，虛擬機(jī)執(zhí)行的為：

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

自此，按照例子 1 + 1的整個(gè)路徑分析完成。

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

• finsh_parser_run主要是將字符串，一個(gè)個(gè)分拆，也就是編譯原理中會說的詞法分析。然后形成一棵樹。
• finsh_compiler_run主要是將樹中的數(shù)據(jù)提取出來，放到虛擬機(jī)中的代碼段中。這里并沒有區(qū)分?jǐn)?shù)據(jù)區(qū)和代碼區(qū)，一股腦的放在一起。
• finsh_vm_run主要是將代碼段中的數(shù)據(jù)，根據(jù)操作碼，提取出數(shù)據(jù)，放到棧中。這里面用到了后綴表達(dá)式，先提取出兩個(gè)數(shù)，然后第三個(gè)數(shù)是+，-，*，/等等的操作碼，計(jì)算完成后，可以出一個(gè)棧的數(shù)據(jù)，然后繼續(xù)處理。

接著再來看看輸入一個(gè)函數(shù)，是怎樣的執(zhí)行流程。比如hello()：
我先說明一點(diǎn)，輸入函數(shù)，函數(shù)的參數(shù)個(gè)數(shù)，rt-thread的shell并沒有做檢測，這應(yīng)該是一個(gè)失誤，是一個(gè)很不好的設(shè)計(jì)。

• 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é)點(diǎn)，node_type為FINSH_NODE_ID。也就是下面這幾個(gè)：

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，這個(gè)時(shí)候，添加結(jié)點(diǎn)FINSH_NODE_SYS_FUNC，并把上面的FINSH_NODE_ID添加進(jìn)來。也就是說，root為FINSH_NODE_SYS_FUNC結(jié)點(diǎn)，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ù)個(gè)數(shù)為0
在代碼段中存儲的數(shù)據(jù)為：
0x2C
0

• 執(zhí)行虛擬機(jī)函數(shù)finsh_vm_run()，調(diào)用OP_ld_dword()，將函數(shù)地址入棧，finsh_sp->long_value=函數(shù)地址。然后調(diào)用OP_call()，獲取參數(shù)個(gè)數(shù)，當(dāng)然為0。后面就是相關(guān)的函數(shù)調(diào)用了。

好了，rt-thread的finsh shell就講到這里。實(shí)話說，其調(diào)用關(guān)系比較層疊?？雌饋砻總€(gè)函數(shù)調(diào)用關(guān)系分開，寫得很好。但是，目前很多的特性，支持力度還是有限的。

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

找到函數(shù)proc_param_list，這個(gè)就是處理參數(shù)列表的。
最終調(diào)用到proc_cast_expr() -->proc_type()---> 找到第一個(gè)參數(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));
    }

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

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

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

2.1 一些擴(kuò)展知識

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

2.1.1 siblings

這個(gè)在二叉樹上有介紹，表示的是兄弟結(jié)點(diǎn)。二叉樹有完美二叉樹、完全二叉樹和完滿二叉樹。

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

2.2 分析開始

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

3 picoC

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

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

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

2.1 編譯

在NIX/Linux/POSIX主機(jī)上：

• make
• make test

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

圖1

2.2 移植

1. platform_XXX.c 包含一些支持性的函數(shù)。編譯器這樣才能在你的平臺上運(yùn)行。例如如何向控制臺輸出字符。
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主機(jī)(UNIX_HOST)。

2.3 協(xié)議

picoc遵循"New BSD License".