用 OCaml 编写解释器

Question

我正在学习我大学的一门课程，该课程要求我从操作语义开始用一种语言的 OCaml 编写解释器。不幸的是，除了课程的幻灯片之外，他们并没有给我们提供太多可以让我们了解它的资源。有人可以向我推荐一些书或一些网站，我可以在其中找到有关它（或类似内容）的信息吗？谢谢。

Answer 1

我会推荐这个 MOOC（英语！）：ocamlmooc

书籍（我用的那些……但还有很多其他的）：
Developping applications with Ocaml
real world ocaml.

第一本书，看看Chapter 6，应该能撑住你。

Answer 2

一旦您拥有代表该语言的合适数据类型，主要就是使用模式匹配逐条规则地翻译语义。

例如，给定这种具有整数文字、加法和可分配变量的简单语言：

type Expression = Literal of int | Variable of string | Addition of Expression * Expression;;
type Statement = Assignment of string * Expression | Sequence of Statement * Statement;;

和一个用于存储变量值的 Store：

type Store = <something>
lookup : Store -> string -> int
update : Store -> string -> int -> Store

我们可以像这样定义语义函数（我将跳过正式定义语义的步骤）：

let semE store = function
   | Literal l -> l
   | Variable x -> lookup store x
   | Addition e1 e2 -> (semE e1 store) + (semE e2 store);;

let semS store = function
   | Assignment x e -> update store x (semE e store)
   | Sequence (s1, s2) -> let store' = semS store s1 
                          in semS store' s2;;

这是该语言的完整解释器，但它没有用于将该语言的语法转换为上述表示的解析器。

例如，

semS (Sequence (Assignment "x" (Literal 3), 
                Assignment "x" (Addition (Variable "x") (Literal 1)))) 
      empty_store

在输入语言中可能表示为 x := 3; x := x + 1，结果应该是 Store，其中 x 的值为 4。

Answer 3

也许您应该尝试 B. Pierce 的 Types and Programming Languages，这可能是关于该主题的一个很好的参考（特别是如果您的输入语言是实用的）。

如果您想更深入地研究语义，我会建议 Formal Semantics of Programming Languages G. Winskel。但它不会帮助你实施。

最后，如果您有时需要编译您的语言而不是解释它，您应该看看 A. Appel 的 Modern Compiler Implementation in ML。

但是这些书对你想做的事情来说可能有点矫枉过正（你的讲义应该足够了）。

用 OCaml 编写解释器

Writing an interpreter in OCaml

ocaml

interpreter

ml