我有一次面试，有人告诉我可能会复习的领域之一是“动态编程语言”。所以我想我可能会在这个周末写一个作为示例代码。:-)
当然，考虑到时间限制，我计划编写一些非常基本的东西，最好使用一种语言和/或工具集，这将使它变得非常容易。我的大部分经验都是在 Python 中，但我愿意花一点时间学习新的东西，如果它能让任务更容易（并且不会花费太长时间）。有没有人在工具或语言方面对我有任何建议可以使这更容易？
问问题
1669 次
7 回答
4
如果你想写一个非常简单的解释性语言，你应该看看 FORTH。词法分析器很简单（标记用空格分隔），解释器也很简单。如果 FORTH 太复古，请看一下 Scheme——您可以非常快速地构建一个小型 Scheme 解释器。
于 2010-01-09T17:40:02.667 回答
3
用 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"
评估一个表达式以在某个 bound 的上下文中给出一个值vars：
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
于 2013-12-01T14:34:05.450 回答
1
您可能想查看Lex 和 Yacc的词法分析和解析，以及它们的python 实现
于 2010-01-09T17:32:39.367 回答
1
我使用spark编写了一个功能齐全的 DSL，在 2 或 3 天内（包括单元测试）为我的一个旧项目表达复杂的条件。
它在 Python 中应该是非常简单的，因为 spark（和其他此类模块）将为您提供编写词法和语法分析器所需的工具。您可以使用 python 字典轻松实现一个简单的符号表，并且可以将其转换为 Python 和 eval 或将其移动到一些较低级别的语言中运行。
于 2010-01-09T17:33:47.377 回答
1
一种解释型语言！= 一种动态语言，尽管情况并非总是如此。
如果您非常精通 Python（== 动态），那么我认为您应该在面试中表现出色，除非他们询问解释语言和动态语言之间的区别。
于 2010-01-09T17:45:24.690 回答
0
我建议将Haskell与解析组合器一起使用。要了解解析组合器，请不要使用Wikipedia 文章；这是非常理论化的，可能会让你感到困惑。取而代之的是 Graham Hutton 的论文，它非常好。
解释器和编译器是 ML/Haskell 语言家族的“杀手级应用”，我想你会惊讶于你能以多快的速度构建有趣的东西。
开始时，我建议您阅读 Phil Wadler 的论文The Essence of Functional Programming，其中包含许多使用 monad 组织的示例解释器。我认为示例解释器组织良好且易于理解，尽管该论文中对 monad 的解释可能会让您头疼。
还有一个非常不错的博客条目，它更详细地介绍了一个示例；它描述了一个用 Haskell 编写的 Lisp 解释器。该文章还包含一些 Haskell 和 Java 之间的比较，这可能会让您了解为什么许多编译器编写者更喜欢函数式语言而不是 OO 语言来编写编译器和解释器。
玩得开心！！！！
于 2010-01-09T21:10:43.677 回答
0
解释器的典型玩具示例是Brainfuck语言。
于 2010-01-12T01:51:55.907 回答