人生第一個解釋器， Lisp
全文口胡預警。
為什麼是 Lisp
- 因為簡單
為什麼我會去寫解釋器
根據蕭井陌聚聚的說法：
實現lisp語法的解釋器(以後你可以拿這個金手指找別人約架…)
於是我去實現了一個 Lisp 語法的辣雞語言的解釋器。
為什麼我要寫這篇博客
- 還沒開始看龍書（以及其他相關領域的書），準備先寫下現在的思路，等看了這些書以後再來回顧對照
為什麼我的眼裡常含淚水
- 因為 Markdown 欽定 Tab 為8空格
- 我的代碼變得根本不能看了
那麼下面是正文
Lisp 講道理已經幫你手寫好了語法樹了，整個 parse 的過程也很簡單，無非就是 String.substring() 的邊界問題有點坑。 我目前的語法設計有這麼幾個規則：
- 每個非空()都是一個函數調用，空()是null的字面量。
- (a b c)是一個函數調用，翻譯成C風格就是a(b, c)。
- true false null 都是字面量
- 數字都是字面量，支持C風格的16進位 8進位和2進位。
可以先寫字元串語法樹：
interface StringNode { val strRepr: String val lineNumber: Int}class StringMiddleNode( override val lineNumber: Int, val list: MutableList<StringNode> = mutableListOf<StringNode>()) : StringNode { val empty: Boolean get() = list.isEmpty() override val strRepr: String get() = list.fold(StringBuilder("{")) { sb, last -> sb.append(" [").append(last.strRepr).append("]") }.append(" }").toString() fun add(n: StringNode) { list.add(n) }}class StringLeafNode( override val lineNumber: Int, val str: String) : StringNode { override val strRepr = str}class EmptyStringNode( override val lineNumber: Int) : StringNode { override val strRepr = ""}
我們可以讓 Parse 函數充滿內部狀態卻做到引用透明：
於是有 Parser ：
var beginIndex = 0val currentNodeStack = Stack<StringMiddleNode>()currentNodeStack.push(StringMiddleNode(1))var lineNumber = 1fun check(index: Int) { // 檢查一個Token是否合法，然後加入TokenList。}code.forEachIndexed { index, c -> when (c) { ";" -> // 處理注釋 "(" -> // 括弧 ")" -> // 反括弧 " ", "
", " ", "
" -> // 解析分隔符 //
記得處理注釋 """ -> // 解析字元串 else -> { if (!quoteStarted) elementStarted = true } } lastElement = c}check(code.length - 1)if (currentNodeStack.size > 1) { // 括弧不匹配}return currentNodeStack.peek()
我為了解決這個問題，先把代碼 parse 成一顆字元串組成的樹，然後再進行 int string 等字面量的讀取，然後再解析函數。
運行的時候就遞歸遍歷運行即可。我們先對每個字元串進行解析：
fun parseValue(str: String): Node = when { str.isEmpty() || str.isBlank() -> EmptyNode str.isString() -> ValueNode(Value(str .substring(1, str.length - 1) .apply { // TODO replace
, , etc. })) str.isOctInt() -> ValueNode(str.toOctInt()) str.isInt() -> ValueNode(str.toInt()) str.isHexInt() -> ValueNode(str.toHexInt()) str.isBinInt() -> ValueNode(str.toBinInt()) "null" == str -> ValueNode(Nullptr) "true" == str -> ValueNode(true) "false" == str -> ValueNode(false)// TODO() is float// TODO() is double// TODO() is type else -> { serr("error token: $str") EmptyNode // do nothing }}
然後再對這棵樹進行遍歷，並將它們做成 ValueNode/ExpressionNode 組成的一棵樹：
fun mapAst( node: StringNode, symbolList: SymbolList = SymbolList()): Node = when (node) { is StringMiddleNode -> { val str = node.list[0].strRepr ExpressionNode( symbolList, symbolList.getFunctionId(str) ?: undefinedFunction(str), node.list.subList(1, node.list.size).map { strNode -> mapAst(node = strNode, symbolList = symbolList) } ) } is StringLeafNode -> parseValue(str = node.str) else -> // empty EmptyNode}
然後對它的 root 節點進行 eval() 即可。
關於函數、符號表
我一開始想的是符號表裡面的函數做成 Map<String, List<Value> -> Value> 的形式。 後來發現，這樣是即時求值的。也就是說，如果我需要實現 if ，它在拿到 Value 時實際上已經是 Node 的 eval() 結果了。 if 和 else 分支兩個都會被求值，只是返回其中一個而已。
也就是說
(if (> a b) (print "Van") (print "Darkholm"))
這東西，無論 a b 大小關係如何， Van 和 Darkholm 這倆字元串都會被輸出，區別只是 if 語句的返回值。
而 while 就更悲劇了， condition 和 expression 都只會求值一次，那麼根本就沒有循環。。。
在這個時候循環就只能靠 eval 自己 了。。。
於是我就只能進行了一次大重構，把所有 Value 改成 Node ，在需要用到的時候求值。
然後就可以正常實現 while 循環了。
差不多就是這樣，然後我給搞了一套文件/URL 的 API ，讓這連函數都不能定義的辣雞有了點用途。
比如爬取 Vijos 的題目（方便起見，這裡只爬取 1000 到 1500 號）：
(for-each "i" (.. 1000 1500) (write-file (file (format "%d.html" (<- "i"))) (read-url (url (str-con "https://vijos.org/p/" (to-str (<- "i"))))) ))
在 repl 裡面輸入以上代碼，可以看到文件樹裡面出現了大量奇怪的 html ，打開可以看到題目。
repl 可以在這裡下載。
運行需要 jre 。
推薦閱讀：