在OOP中解析S表达式的正确方法

Question

我正在寻找一种方法来实现一个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;
  };

每种方案都有一个Sexpr的子类Atom,或者类似的东西.

我不确定,但这对我来说似乎是一个黑客......这项工作不应该由翻译而不是读者完成吗？

我想知道的是,这是否被认为是读取S表达式的最佳(或正确)方式,还是解析器的作用比解析器更重要？解析器是否应该有自己的AST而不是依赖于cons细胞？

Answer 1

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

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

这些附加信息可以实现诸如带有源指针的错误消息和卫生宏之类的功能。

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

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