什麼語言最適合寫編譯器/解釋器？

01-04

Lisp?
C?
Python?

即便題主說「寫解釋器/編譯器」，其實解釋器與編譯器各自都可以從簡單到複雜、在各種不同的場景下有不同的最合適的實現。就這麼泛泛地問很難引出泛用的好答案…

以解釋器為例，要盡量跨平台而且性能還過得去，同時還不要依賴太多外部的東西的話，那麼C通常是不二之選，因為在各種平台上通常都能找到（至少基本上）符合規範的C編譯器和運行時庫，只要按照規範來寫C的話在各種平台上都能編譯運行。經典案例是C寫的Lua。

然而如果要把解釋器寫得短小精悍，極可能榨乾解釋執行的性能的話，那麼在每個平台上用彙編寫就是最好的選擇。這樣可以最大程度利用平台上的寄存器（例如說可以用CPU的棧指針寄存器來表示解釋器的棧頂指針，這樣就可以把解釋器棧混合到native棧上，有可能減少一層間接訪問，提高性能）；同時還便於精確地安排代碼布局，把常用邏輯對齊、集中在一起，而把不那麼常用的邏輯或者複雜的邏輯安排在別的地方。直接寫彙編也行，或者自己用自己想選用的語言（例如C++）實現一個彙編器庫然後使用這個庫來生成機器碼也行，但最核心的概念是「手寫彙編」。

編譯器的話，其實編譯器中有好些不同的方面，分別有些不同的需求以及對應的用起來順手的語言。

例如說詞法分析常常可以用正則表達式來表達，語法分析常常可以用某種context-free grammar（CFG）或parsing expression grammar（PEG）的DSL來表達，然後tree pattern也可以寫DSL來表達。指令選擇如果選用BURS（bottom-up rewrite system）系的做法，那也常常會有自己的DSL。

要說核心需求，編譯器其實常常要做三種事情：

模式匹配（pattern matching），
代碼形式的轉換（transformation），
然後還有根據一些給定條件來求解（可以是constraint solving）。

前兩者用有algebraic data types（ADT）的語言的話會比較方便，因為這些語言常常會對ADT有配套的模式匹配語言結構，在遍歷和轉換編譯器的內部數據結構時會非常方便。

最後那點的話，有時候會有人用Datalog來做…也是種很方便的做法。

還有一些有趣的話題。例如說有些寫編譯器的人會比較喜歡用有自動內存管理（可以是GC，不過不一定…）的語言來寫。因為編譯的主流程本來就要很多麻煩事，如果要遷就手動內存管理來寫的話，要麼代碼會有點難看，要麼要自己投入一些開發成本去寫一套適合自己使用場景的基類/分配器啊啥的來處理。

結果有些編譯器就乾脆把自己的臨時數據全用一個arena分配器來分配，換句話說說只管分配不管釋放，等到一個編譯任務結束的時候再一口氣整個arena一起扔掉。這放在靜態編譯器場景里可能還OK（但規模一大也常常不OK…），放在動態編譯器里的話就可能不合適。

最後…要是非要挑一種語言來寫整個編譯器的話，我現在可能會選Rust吧（站隊

OCaml / F#我也很喜歡的。

但最終能用啥，咱也未必有控制權。現在工作寫的編譯器就是用C++實現的，沒得選啊。

寫demo的話絕對是OCaml。

OCaml是ML變體，表示抽象語法樹特別方便簡潔，把寫語言最煩人的parsing過程簡化了。另外OCaml是LLVM提供官方API的兩種語言之一（另一個是C++），可以用上最新最穩定的LLVM特性，這樣後端優化也簡化了。如果想做大項目，可以先用OCaml擼個雛形，再逐步自舉——rust就是這麼乾的。

2017年痛苦最低的方法就是，隨便用一個趁手的、支持操作二進位數據的語言寫，然後粗暴地編譯成bytecode或MSIL，後面就什麼都不用管了！配合Antlr，僅需學習0種演算法。

如果你要挑戰一下自己搞類型推導的話，推薦使用F#。

OCaml.

首先是前端, 顯示有ocamllex 和 ocamlyacc 這種傳統的Parser Lexer. 然後超級好用的Menhir錯誤debug都超級友好. 我就是用Menhir然後寫Parser比其他人寫得快:D 當然這是指你想用一個LR的Parser. 如果你要手寫Recursive Descent的話還是OCaml 好用.

生成AST的階段凡是帶Pattern Matching的語言都很好用, OCaml好用但是不突出.

這裡專門比較一下OCaml和Haskell, Haskell這種Side effect free的東西雖然幻想中很美好, 但是真的有些地方為了效率和簡介需要Hack一下的話根本沒有OCaml方便.

然後是後端, 如 @蘅蒻提到的, LLVM官方有OCaml的bindings, 我上學期就是用哪個Binding直接用了LLVM的SSA直接生成機器碼. (文檔在這裡Llvm) 這裡一個Gotcha是貌似最新版本的LLVM Binding會Segfault. 還有就是這個Binding的抽象層度不是很高所以如果你生成SSA的方式不對的話也會segfault.

Coq、Agda 之類的語言我看就很不錯，寫完以後還可以往頂會投稿。

C++

大學本科學編譯原理課程時的大作業就C++寫編譯器。

OCaml

函數式編程更適合寫DSL，比如其他回答提到的haskell, OCaml, Lisp，還有Scala, Clojure等。

有興趣的話可以參考這篇論文: http://dsl2013.math.ubbcluj.ro/files/gibbons-lecture.pdf

前端和你編譯的語言相似，自舉是第一選擇，不自舉的話

傳統的 OOP 語言 → C++、Java、C#
腳本語言 → Python、JS、Lisp 等
有複雜類型系統的函數式語言，寫文檔滿屏 $Gammavdash x:T$ 的那種 → haskell、ML、F# 或者 idris

後端和你編譯的目標相似，比如你要到 x86 就用 C/C++，到 js 就用 js

不是有yacc、lex么。

編譯器的開發我一般用python，有些時候利用動態特性會更方便一些，省很多重複代碼

解釋器的話，額，抱歉我一般是轉目標高級語言，所以不需要解釋器：P，曾經用C和Java寫過位元組碼解釋器，C的話GC需要自己擼，比較麻煩，Java的話，有些時候代碼比較啰嗦

GCC內部的DSL基本就是Lisp那套括弧+前綴表達式的方式做的。

我推薦haskell，真的好用

還是C++吧。為什麼呢？因為有非常多奇技淫巧可以用啊！可以寫出出神入化的魔性感覺！

不管是flex+bison+llvm

還是人肉寫所有代碼。

都能讓你獲得持久的快感。

推薦c++。

新版c++的坑照以往的坑少了許多。

而且可以操作底層。效率，抽象能力等等各項指標都蠻不錯。

最近也在也在寫解釋器。前期用到c和Go但是都因為些許方面很麻煩最後改成c++

標籤里有Lisp？讀過SICP後應該對Scheme如何用及短的代碼寫一個自舉解釋器沒有任何疑問。

racket？最適合做dsl吧

話說編譯原理大作業不是都用C寫的嗎。雖然只有簡單的函數棧。

C語言吧？難道不是么？

發現沒人說這個於是不請自來。

Syntax/Semantic Language (S/SL) 這門語言跟開源社區中其他bison啥的比起來特點是可以用於實現scanners, parsers, semantic analyzers, code generators and virtual machine interpreters這些所有的編譯環節。

euclid, turing, ada都有用ssl實現的編譯器。

利益相關:ssl是自家教授James Cordy寫的。

lisp

用自己寫