"抽象语法树"术语的使用

Question

我正在努力加深对Scala的理解，有一件事让我感到困惑，那就是术语“抽象语法树”（也称为AST）的使用。

现在，在许多地方，我看到程序员使用术语AST来描述某些代码。以下示例来自Noel Welsh和Dave Gurnell的书籍《高级Scala》中描述类型类模式的部分。

// Define a very simple JSON AST
sealed trait Json
final case class JsObject(get: Map[String, Json]) extends Json
final case class JsString(get: String) extends Json
final case class JsNumber(get: Double) extends Json

我猜上面的内容是一颗树，尽管非常浅显。

                 Json
                  |
      +-----------+-+-----------+
      |             |           |
  JsObject      JsString      JsNumber

我对AST的理解通常是在编译器的上下文中，它从表示代码的具体语法树（Code Syntax Analysis -> Concrete Syntax Tree）创建一个抽象语法树（Abstract Syntax Tree）。

为什么上面的内容是AST？

尽管作者没有在编译器的语法分析上下文中使用这个术语，但由于AST通常用于表示代码的抽象表示形式，因此为什么会有人使用这个术语来描述一些实际的代码呢？

- harry callahan

---

它是说 AST 还是 ADT（代数数据类型）？ - Yuval Itzchakov

如果您将JSON视为一种语言，那么解析其语法将生成AST。JSON根据定义是一种数据交换协议，但术语“语言”相当模糊，因此您可以根据自己的喜好称之为这样。 - Yuval Itzchakov

AST。收到，谢谢。 - harry callahan

Answer 1

它被称为AST不是因为继承树的原因，而是因为它是一种树形结构，代表JSON的语法。

为了看到它是如何成为一种树形结构的，请考虑以下示例：

{"a": 42, "b": {"x": "y"}}

这将被解析为以下对象：

JsObject(Map(
    "a" -> JsInt(42),
    "b" -> JsObject(Map(
      "x" -> JsString("y")
    ))
))

以下是代表以下树的结构：

         Object
    "a" /      \ "b"
      Int    Object
       |        | "x"
       42    String
                |
               "y"

这是上述JSON字符串的抽象语法树。

我知道作者们没有在编译器的语法分析背景下使用这个术语。

虽然不是在编译器的背景下，但是他们在分析JSON的抽象语法时使用了它。

- sepp2k

---

在定义中写着 JsObject(get: Map[String, Json])，我认为 JsString 不应该出现在箭头的左侧。字符串标签应该放在边缘上，它们描述了树的结构：这就是半结构化数据的全部意义所在。但这也取决于你想要多么“抽象”你的“抽象语法树”，没有什么能阻止任何人拥有不同抽象级别的多个AST... - Andrey Tyukin