36

我发现自己加入了一个将解释器整合到现有应用程序中的项目。要解释的语言是 Lisp 的衍生语言，具有特定于应用程序的内置函数。单个“程序”将在应用程序中以批处理方式运行。

令我惊讶的是，这些年来我编写了几个编译器和几个数据语言翻译器/解析器，但我以前从未真正编写过解释器。原型很长，在 C++ 中实现为语法树遍历器。我可能会影响原型之外的架构，但不能影响实现语言（C++）。所以，约束：

  • 实现将在 C++ 中
  • 解析可能会使用 yacc/bison 语法处理（现在是）
  • 像 NekoVM 和 LLVM 这样的完整 VM/Interpreter 生态系统的建议对于这个项目可能并不实用。独立的更好，即使这听起来像 NIH。

我真正想要的是阅读有关实现解释器的基础知识的材料。我浏览了 SO 和另一个名为Lambda the Ultimate 的网站，尽管它们更倾向于编程语言理论。

到目前为止我收集的一些花絮：

  • Lisp in Small Pieces，克里斯蒂安·奎内克（Christian Queinnec）。推荐它的人说它“从琐碎的解释器转向更高级的技术，并完成了字节码和‘Scheme to C’编译器的呈现。”

  • 内科虚拟机。正如我上面提到的，我怀疑我们是否被允许合并一个完整的 VM 框架来支持这个项目。

  • 计算机程序的结构和解释。最初我建议这可能是矫枉过正，但经过一个健康的块，我同意@JBF。信息量大，思路开阔。

  • 保罗格雷厄姆在 Lisp上。我读过这篇文章，虽然它是对 Lisp 原则的信息性介绍，但不足以快速开始构建解释器。

  • 鹦鹉实施。这似乎是一个有趣的阅读。不确定它是否会为我提供基础知识。

  • 从零开始的计划。Peter Michaux 正在攻击 Scheme 的各种实现，从用 C 编写的快速而肮脏的 Scheme 解释器（在以后的项目中用作引导程序）到编译的 Scheme 代码。到目前为止非常有趣。

  • Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages ，在Books On Creating Interpreted Languages的评论线程中推荐。这本书包含两章专门介绍构建解释器的实践，所以我将它添加到我的阅读队列中。

  • New (and yet Old , ie 1979): Writing Interactive Compilers and Interpreters by PJ Brown。这本书早已绝版，但有趣的是提供了与基本解释器的实现相关的各种任务的大纲。我看到这个的评论褒贬不一，但因为它很便宜（我订购它时使用了大约 3.50 美元），我会试一试。

那么怎么样呢？有没有一本好书可以帮助新手并展示如何在 C/C++ 中为类似 Lisp 的语言构建解释器？你喜欢语法树遍历器还是字节码解释器？

回答@JBF：

  • 当前的原型是一个解释器，这对我来说很有意义，因为我们接受了任意代码文件的路径并在我们的应用程序环境中执行它。内置函数用于影响我们的内存数据表示。

  • 它不应该慢得可怕。当前的树行者似乎可以接受。

  • 该语言基于Lisp，但不是 Lisp，因此不需要符合标准。

  • 如上所述，我们不太可能被允许添加一个完整的外部 VM/解释器项目来解决这个问题。

对于其他海报，我也会查看您的引文。谢谢大家！

4

5 回答 5

12

简短的回答：

lisp 解释器的基本阅读清单是 SICP。我一点也不认为它是矫枉过正，如果你觉得你对本书的第一部分的资格过高，请跳到第 4 章并开始解释（尽管我觉得这将是一个损失，因为第 1-3 章真的那么好！） .

添加 LISP in Small Pieces（LISP 从现在开始），第 1-3 章。特别是第 3 章，如果您需要实现任何重要的控制表单。

请参阅 Jens Axel Søgaard 关于最小自托管方案的这篇文章：http ://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html 。

稍微长一点的答案：

在不知道您的口译员需要什么的情况下，很难给出建议。

  • 它真的需要成为解释器，还是你真的需要能够执行 lisp 代码？
  • 它需要快速吗？
  • 它需要符合标准吗？普通的 Lisp？R5RS？R6RS？您需要任何 SFRI 吗？

如果您需要比简单的语法树遍历器更花哨的东西，我强烈建议您嵌入一个快速方案子系统。我想到了 Gambit 方案：http: //dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page。

如果这不是 SICP 中的第 5 章和 LISP 目标编译中的第 5 章以加快执行速度的选项。

为了更快地解释，我会看看最新的 JavaScript 解释器/编译器。似乎有很多关于快速执行 JavaScript 的想法，您可能可以从中学习。V8 引用了两篇重要的论文：http ://code.google.com/apis/v8/design.html和 squirrelfish 引用了一对：http ://webkit.org/blog/189/announcing-squirrelfish/ 。

还有用于 RABBIT 编译器的规范方案文件： http ://library.readscheme.org/page1.html。

如果我进行一些过早的推测，内存管理可能是难以破解的难题。Nils M Holm 出版了一本书“来自空白空间的方案 9” http://www.t3x.org/s9fes/，其中包括一个简单的 stop-the-world 标记和清扫垃圾收集器。包括来源。

John Rose（较新的 JVM 成名）写了一篇关于将 Scheme 集成到 C 的论文： http: //library.readscheme.org/servlets/cite.ss ?pattern=AcmDL-Ros-92 。

于 2008-11-17T12:53:50.557 回答
7

是的，在 SICP 上。

我已经多次完成这项任务，如果我是你，我会这样做：

首先设计你的记忆模型。您将需要某种 GC 系统。先做这件事比以后再装上它要容易得多。

设计你的数据结构。在我的实现中，我有一个基本的 cons 框，其中包含许多基本类型：原子、字符串、数字、列表、布尔值、原始函数。

设计您的 VM 并确保保持 API 干净。我的最后一个实现将其作为顶级 API（请原谅格式 - 所以正在偷看我的预览）

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; }
AtomFactory &GetAtomFactory() { return mAtomFactory; }
Environment &GetEnvironment() { return mEnvironment; }
t_ConsBox *Read(iostream &stm);
t_ConsBox *Eval(t_ConsBox *box);
void Print(basic_ostream<char> &stm, t_ConsBox *box);
void RunProgram(char *program);
void RunProgram(iostream &stm);

不需要 RunProgram - 它是根据 Read、Eval 和 Print 实现的。REPL 是解释器的常见模式，尤其是 LISP。

ConsBoxFactory 可用于制作新的 cons 框并对其进行操作。使用 AtomFactory 以便等效的符号原子映射到一个对象。Environment 用于维护符号与 cons 框的绑定。

你的大部分工作应该进入这三个步骤。然后你会发现你的客户端代码和支持代码也开始看起来很像 LISP：

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list)
{
    return Car(Cdr(list));
}

您可以在 yacc/lex 中编写解析器，但何苦呢？Lisp 是一个非常简单的语法和扫描器/递归下降解析器对，因为它大约需要两个小时的工作。最糟糕的部分是编写谓词来识别标记（即 IsString、IsNumber、IsQuotedExpr 等），然后编写例程将标记转换为 cons 框。

使编写和编写 C 代码的胶水变得容易，并在出现问题时轻松调试问题。

于 2008-11-17T16:57:40.627 回答
5

Samuel Kamin 的书Programming Languages, An Interpreter-Based Approach中的 Kamin Interpreters，由 Timothy Budd 翻译成 C++。我不确定裸源代码会有多大用处，因为它本来是随书而来的，但这是一本很好的书，涵盖了用低级语言实现 Lisp 的基础知识，包括垃圾收集等。（这不是本书的重点，它是一般的编程语言，但它被涵盖了。）

Lisp in Small Pieces更深入，但这对您的情况有利也有弊。有很多关于编译的材料，这些材料与你无关，而且它更简单的解释器在 Scheme，而不是 C++ 中。

SICP 很好，当然。不是矫枉过正，但写口译员当然只是本书的一小部分。

JScheme 建议也是一个很好的建议（它包含我的一些代码），但不会帮助您处理 GC 之类的问题。

稍后我可能会通过更多建议来充实这一点。

编辑：有些人说他们从我的awklisp中学到了东西。这无疑是一种奇怪的建议，但它非常小，可读，实际可用，并且与其他微小但可读的玩具 Lisps 不同，它实现了自己的垃圾收集器和数据表示，而不是依赖于底层的高级实现语言来提供他们。

于 2008-11-17T07:02:44.727 回答
3

查看Peter Norvig的 JScheme 。我发现这非常容易理解并移植到 C++。呃，虽然不知道将方案用作脚本语言 - 将它教给 jnrs 很麻烦并且感觉过时（helloooo 1980 年代）。

于 2008-11-17T04:10:20.473 回答
2

我想扩展我对Programming Languages: Application and Interpretation的推荐。如果你想写一个解释器，那本书会带你走很短的路。如果你通读编写你阅读的代码并进行练习，你最终会得到一堆相似但不同的解释器（一个是渴望的，另一个是懒惰的，一个是动态的，另一个有一些类型，一个有动态范围， other 具有词法范围等）。

于 2008-11-26T14:15:51.620 回答