5

我正在寻找一种实现 S 表达式阅读器的方法（稍后将与 Scheme 解释器和编译器一起使用），但我一直在问自己（如果有的话）我应该如何（如果有的话）为它编写一个 AST。

我一直在阅读 SICP，这在 Scheme 中非常简单，但我希望以 OO 方式在 C++ 中实现解释器和编译器。

请记住，我这样做只是为了学习目的，所以我并不是在寻找最简单或最快的方法，而是寻找正确且可重用的方法。

我在一些 Scheme 实现中看到人们解析 s 表达式并轻松输出 cons 单元格，如下所示：

  struct Sexpr
  {
  };

  struct Cons : public Sexpr
  {
    Sexpr* left;
    Sexpr* right;
  };

  struct IntAtom : Sexpr
  {
    int value;
  };

每种 Scheme 都有一个 Sexpr 子类Atom，或者类似的东西。

我不确定，但这对我来说似乎是一种黑客行为......这项工作不应该由口译员而不是读者来完成吗？

我想知道的是，这是否被认为是阅读 S 表达式的最佳（或正确）方式，或者这更像是解释器而不是解析器的工作？解析器是否应该拥有自己的 AST 而不是依赖于 cons 单元？

4

4 回答 4

3

如果你想让你的语法有点完整，你需要支持

sexpr ::= atom | sexpr sexpr
atom ::= nil | intatom | etc.

但这比您将遇到的大多数性行为更普遍。在 LISP/Scheme 中，最简单和最常见的 S-expr 形式类似于 (abcd)，其中 a、b、c、d 中的每一个都是原子或列表。在配对形式中，这是 [a [b [c [d nil] ] ] ]，这意味着您的 conses 的所有右侧都是列表。

因此，如果您要清洁，您可能会这样做

class sexpr {};
class atom : sexpr {};
class s_list : forward_list<smart_ptr<sexpr>> {};
于 2012-02-24T18:00:40.903 回答
3

虽然人们可能会来回争论什么是“正确”的方法，但在我看来，你建议的方法——使用相同的数据结构进行读取、编译、评估和处理——是最能教给你的方法关于 Lisp 和“代码就是数据”的口头禅是关于什么的，特别是quote运算符的实际含义（这是一个非常深刻的事情）。

顺便说一句，这也是大多数 Lisps（有趣的是，不包括 Scheme）传统上的工作方式。

所以是的，让读者生成 Lisp 数据：conses、symbol、Lisp 数字、字符串等等，与用户级 Lisp 代码将处理的内容完全相同。它将使实现的其余部分变得更简单和更有指导意义。

于 2012-02-24T18:08:52.480 回答
3

从围栏的方案/球拍侧跟进：

Racket（和其他一些 Scheme 实现）对语法对象使用更丰富的表示，以便它们可以附加属性来指示（至少在 Racket 中）它们绑定在什么上下文中，它们来自什么源位置，通过什么的编译器插入了它们，以及您可能想要存储的任何其他信息（参见 Racket 中的“语法属性”）。

这些附加信息支持诸如带有源指针的错误消息和卫生宏之类的东西。

请注意，我在这里的“更丰富”的意思只是“包含更多价值”的意思，而不是任何非价值中立的方式。

我还应该补充一点——在陷入图灵焦油坑之前——你也可以使用旁边的表格来表示这些完全相同的信息；假设您有指针比较，将值放入结构中和使用表将结构与值相关联之间没有表现力差异。

于 2012-02-24T20:01:08.953 回答
1

您可能想查看这个 c/c++ s-expr 解析器库，以了解它是如何完成的。

看起来基本表示是：

struct elt {
  int type;
  char *val;
  struct elt *list; 
  struct elt *next;
};

我从他们的文档中引用：

由于元素可以是列表或原子，因此元素结构具有可以是 LIST 或 VALUE 的类型指示符。如果类型指示符是 LIST，则结构成员“list”将是指向此元素表示的列表头部的指针。如果类型指示符为 VALUE，则结构成员“val”将包含由元素表示的原子作为字符串。在这两种情况下，“next”指针都将指向当前 s 表达式的下一个元素。

此外，这里是 s-expr 阅读器的其他实现的完整列表，其中包含可能感兴趣的多种语言。

于 2013-10-09T03:25:53.230 回答