如何有步驟地實現一個解釋器?如果採用低級語言，如C之類的語言來實現像Lisp這樣的語言，需要什麼知識和工具?

0.你和我選擇實現R5RSScheme的一部分，由於它比較小巧。

1.開始構思整個runtime的計劃。

1.1計劃一種Scheme內里的值的low-level的表現方法。這裡可以選擇利用taggedpointer，由於其便於實現並且運行服從高。

1.2計劃一種表明實行的方法。這裡可以選用先編譯成bytecode，再表明實行bytecode的方法，由於如許做的運行服從比直接表明實行AST高，並且整個進程比較清楚明白。

1.2.1bytecode可以計劃成stack-based的，由於這種bytecode編譯器來比較大略

1.2.2利用heap-allocatedlinkedlistframe，如許可以簡化call/cc的計劃，並且不會出現stackoverflow，缺點是會對運行服從造成不小的影響

1.3計劃一種garbagecollector。這裡可以選用大略的semispacecopyinggc先拼湊著用。等之後必要更高的服從的時間可以把writebarrier加上，然後改為利用generationalgc。

runtime的一小部分如下：

typedefintptr_tRtsPtr;//全部Scheme的值都是pointer//定義pointertagging的相干常數。這些type會以tagging的情勢存在pointer的值上enum{kFixnumTag=1,//integer用1來舉行tagkPairTag=2,//pair用2來舉行tagkSpecTag=3,//特別的值（#t,#f,"()之類的）用3來舉行tagkTagShift=2,//tag的寬度是2kTagMask=3//用於查抄pointertag};//定義其他的type。這些type會存在obType里enum{kNativeProc=1,kBytecode=2,kBytecodeProc=3};//定義heapobject共有的一些property，用於GC以及其他runtime的操縱//gcMark是garbagecollector所利用的，用於存儲gc進程中對object舉行的標記//obType表現該object的範例（要是該object不是一個taggedpointer的話）HEAP_OBJECT_HEADint8_tgcMark;int8_tobType//將C內里的int轉換成Scheme內里的int（即fixnum）RtsPtrmakeFixnum(intptr_trawInt){returnkFixnumTag+(rawIntkTagShift);}//查抄一個Scheme的值是不是fixnumboolisFixnum(RtsPtrmaybeInt){return(maybeIntkTagMask)==kFixnumTag;}//定義Scheme內里的pairtypedefstruct{HEAP_OBJECT_HEAD;RtsPtrcar,cdr;}Pair;//將一塊已分派好的內存初始化為一個pair，並且返回這個pairRtsPtrmakePair(RtsPtrself,RtsPtrcar,RtsPtrcdr){//你和我可以在obType里記錄這是一個pair//也可以用pointertagging的方法(見下面的解釋)來記錄。//這裡我選擇用pointertagging((Pair*)self)-gcMark=0;((Pair*)self)-car=car;((Pair*)self)-cdr=cdr;//記錄這是一個pair，只不過是用pointertagging的方法。//pointertagging由於是將tag存在pointer的值里，查抄的時間不必要//訪問內存，理論上來說比查抄內存里的obType來得更快一些。固然了，如許會在其他地方//帶來一個速率的低落(查抄一個pointer的範例的時間必要先查抄tag，再查抄obType).//以是表明器/編譯器很多的時間都要根據實際利用環境以及測試結果來做一個棄取。//這裡另有另一個隱含的約定：這個pairpointer肯定是align在//wordboundary上的，以是最低的2-3個bit肯定是0。正由於云云，你和我才華擠出//這幾個bit來存儲type方面的信息。returnself+kPairTag;}//查抄一個Scheme的值是不是pairboolisPair(RtsPtrmaybePair){return(maybePairkTagMask)==kPairTag;}//一個pair的car的地點RtsPtr*getCar(RtsPtrself){return((Pair*)(self-kPairTag))-car;}//同上RtsPtr*getCdr(RtsPtrself){return((Pair*)(self-kPairTag))-cdr;}

2.Parse方面，選擇寫一個LL(1)recursive-descendparser，這個一百來行C就行了。

3.Bytecodecompilation方面，也黑白常機器化的。你必要一個global的symboltable，以及臨時的local的symboltable，然後把temporaryvalue都push到stack上，云云這般...

比如要是你要compile某function內部的(definenameform)

voidcompileLocalDefine(Compiler*self,RtsPtrdefine){RtsPtrname=*getCadr(define);RtsPtrform=*getCaddr(define);uint8_tslot=newLocalSlot(self,name);//在frame里為name這個局部變數找一個位置compileExpr(self,form);//求出form的值並且將該值push到stack上emit2(self,LOCAL_DEFINE,slot);//將該值pop出來並且賦到slot上emit(self,PUSH_VOID);//該表達式的返回值是一個void}4.interpreter的mainloop方面，也黑白常機器化的。起首是instructionfetch，然後decode，再便是dispatch，云云這般...

voidinterpret(VMState*vms){uint8_t*instr=vms-instr;RtsPtr*stackTop=vms-stackTop;RtsPtr*locals=vms-locals;RtsPtrheapPtr=vms-heapPtr;//用於"bump-pointer"allocationRtsPtrheapLimit=vms-heapLimit;//heapPtr高出了的話就要GC了staticvoid*dispatchTable[]={...HANDLE_PUSH_INT8,HANDLE_LOCAL_DEFINE,...};...goto*dispatchTable[*instr++];...HANDLE_CONS:{//這裡有allocation,以是大概會GCRtsPtrnewCons=heapPtr;//分派一塊內存heapPtr+=sizeof(Pair);//下次就從這裡分派if(heapPtrheapLimit){//內存不敷了vms-heapPtr=heapPtr;//同步到VMState，下同vms-limitPtr=limitPtr;vms-stackTop=stackTop;...//都給同步已往了newCons=collectAndAlloc(vms,sizeof(Pair));//GCheapPtr=vms-heapPtr;//同步返來...//都給同步返來了}stackTop++;*stackTop=makeCons(stackTop,stackTop-1);goto*dispatchTable[*instr++];}HANDLE_PUSH_INT8:stackTop--;//假設stack往下生長*stackTop=makeFixnum(*instr++);goto*dispatchTable[*instr++];HANDLE_LOCAL_DEFINE:{uint8_tlocalIndex=*instr++;RtsPtrvalue=*stackTop++;locals[localIndex]=value;goto*dispatchTable[*instr++];}...}

大概便是云云。著實寫完發明也還是挺抽象的...總之表明器這個東西必要理論接洽實際，讀一讀冊本，讀一讀人家寫的代碼（Lua，CPython，TinyScheme，Dart，v8，Hotspot等等等等），然後再寫個表明器，就會容易很多了。

2014-10-12更新：前次忘了寫allocation和GC相干的code

2014-10-19更新：前次寫錯了pair的size。別的添加表明為什麼pair不消obType而用tagging

2016-01-10更新：細緻闡明dispatch的方法（indirectthreading），以及為什麼好