我怎样才能写出一个快速而肮脏的解释器？

Question

我有一次面试，我被告知我可能会复习的领域之一是“动态编程语言”。所以我想我可能会花这个周末写一个作为示例代码。 :-)

当然，考虑到时间限制，我计划写一些非常基本的东西，最好使用一种语言和/或工具集，使其变得非常容易做到。我的大部分经验都是在 Python 方面的，但如果能让任务变得更容易（并且不会花费太长时间），我愿意花一点时间学习新东西。有没有人可以给我一些关于工具或语言方面的建议，让这一切变得更容易？

Answer 1

如果你想编写一种非常简单的解释性语言，你应该看看 FORTH。词法分析器很简单（标记以空格分隔），解释器也非常简单。如果 FORTH 太复古，请看一下Scheme - 您可以非常快速地构建一个小型Scheme 解释器。

Answer 2

用 OCaml 编写的简单解释器

此处完整描述了我的示例解释器。

表达式和值的类型

表达式：

type expr =
  | EAdd of expr * expr
  | EApply of expr * expr
  | EEqual of expr * expr
  | EIf of expr * expr * expr
  | EInt of int
  | ELetRec of string * string * expr * expr
  | EMul of expr * expr
  | EVar of string

值：

type value =
  | VInt of int
  | VBool of bool
  | VClosure of string * (string * value) list * expr

词法分析和解析

使用 Camlp4 进行解析：

#load "camlp4o.cma"

定义词法分析器：

open Genlex
let keywords =
  ["("; ")"; "+"; "-"; "=";
   "if"; "then"; "else";
   "let"; "rec"; "in"]
let lex stream =
  let rec aux = parser
    | [< 'Int n when n<0; t=aux >] -> [< 'Kwd "-"; 'Int(-n); t >]
    | [< 'h; t=aux >] -> [< 'h; t >]
    | [< >] -> [< >] in
  aux(make_lexer keywords stream)

定义解析器：

let rec parse_atom = parser
  | [< 'Int n >] -> EInt n
  | [< 'Ident v >] -> EVar v
  | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e
and parse_apply = parser
  | [< e1=parse_atom; stream >] ->
      (parser
       | [< e2=parse_atom >] -> EApply(e1, e2)
       | [< e2=parse_apply >] -> begin match e2 with
           | EApply(e2, e3) -> EApply(EApply(e1, e2), e3)
           | e2 -> EApply(e1, e2)
           end
     | [< >] -> e1) stream
and parse_arith = parser
  | [< e1=parse_apply; stream >] ->
      (parser
       | [< 'Kwd "+"; e2=parse_arith >] -> EAdd(e1, e2)
       | [< 'Kwd "-"; e2=parse_arith >] -> EAdd(e1, EMul(EInt(-1), e2))
       | [< >] -> e1) stream
and parse_expr : 'a Stream.t -> expr = parser
  | [< e1=parse_arith; stream >] ->
      (parser
       | [< 'Kwd "="; e2=parse_expr >] -> EEqual(e1, e2)
       | [< >] -> e1) stream
  | [< 'Kwd "if"; p=parse_expr; 'Kwd "then"; t=parse_expr;
       'Kwd "else"; f=parse_expr >] ->
      EIf(p, t, f)
  | [< 'Kwd "let"; 'Kwd "rec"; 'Ident f; 'Ident x; 'Kwd "="; body=parse_expr;
       'Kwd "in"; rest=parse_expr >] ->
      ELetRec(f, x, body, rest)

求值

取消装箱 int 或 bool：

let int = function VInt n -> n | _ -> invalid_arg "int"
let bool = function VBool b -> b | _ -> invalid_arg "bool"

求值表达式以在某些绑定 vars< 的上下文中给出值/code>:

let rec eval vars = function
  | EApply(func, arg) ->
      begin
        match eval vars func, eval vars arg with
        | VClosure(var, vars, body), arg -> eval ((var, arg) :: vars) body
        | _ -> invalid_arg "Attempt to apply a non-function value"
      end
  | EAdd(e1, e2) -> VInt (int(eval vars e1) + int(eval vars e2))
  | EMul(e1, e2) -> VInt (int(eval vars e1) * int(eval vars e2))
  | EEqual(e1, e2) -> VBool (eval vars e1 = eval vars e2)
  | EIf(p, t, f) -> eval vars (if bool (eval vars p) then t else f)
  | EInt i -> VInt i
  | ELetRec(var, arg, body, rest) ->
      let rec vars = (var, VClosure(arg, vars, body)) :: vars in
      eval vars rest
  | EVar s -> List.assoc s vars

工作示例

将示例程序定义为字符串：

let program = "let rec fib n = if n=0 then 0 else if n=1 then 1 else fib(n - 1) + fib(n - 2) in fib 30"

Lex 并将该字符串解析为 AST：

let ast = parse_expr(lex(Stream.of_string program))

评估 AST：

eval [] ast

Answer 3

您可能需要查看 Lex 和 Yacc 进行词法分析和解析，以及它们的 Python 实现

Answer 4

我使用 spark 编写了一个功能相当齐全的 DSL 来表达复杂的条件我的旧项目在两三天内完成（包括单元测试）。

在 Python 中这应该是相当简单的，因为 Spark（和其他此类模块）将为您提供编写词法和语法分析器所需的工具。您可以使用 python 字典轻松实现一个简单的符号表，并且可以将其转换为 Python 和 eval 或将其移动到某种较低级别的语言来运行。

Answer 5

解释性语言！=动态语言，尽管反之亦然。

如果你非常精通Python（==动态）那么我认为你应该在面试中表现出色，除非他们询问解释语言和动态语言之间的区别。

Answer 6

我建议使用 Haskell 和解析组合器。
要深入了解解析组合器，不要使用维基百科文章;这是非常理论化的，可能会让你感到困惑。相反，请使用 Graham Hutton 的论文，这是非常好的。

解释器和编译器是 ML/Haskell 系列语言的“杀手级应用程序”，我想您会对构建有趣的东西的速度感到惊讶。

首先，我建议您阅读 Phil Wadler 的论文 The Essence函数式编程，其中包含许多使用 monad 组织的示例解释器。我认为示例解释器组织良好且易于理解，尽管该论文中对 monad 的解释可能会让您头疼。

还有一个非常好的博客条目，其中介绍了一个示例更多细节；它描述了一个用 Haskell 编写的 Lisp 解释器。该文章还包含 Haskell 和 Java 之间的一些比较，这可能会让您了解为什么许多编译器编写者更喜欢使用函数式语言而不是 OO 语言来编写编译器和解释器。

玩得开心！！！！

Answer 7

解释器的典型玩具示例是 Brainfuck 语言。