c++ - 对函数 AST 声明的抽象格式的混淆

Question

我正在使用 C++ 实现编程语言，我即将进入 AST 生成阶段。

我想使用一个三步程序:

1. 识别语句的类型；
2. 将左值右值和节点中的标记与表达式分开，作为临时和本地 AST；
3. 设计并将其添加到全局 AST。

例如，这是变量声明的内容:

var MyVar : integer = 8 + 2;

临时形式(右值/节点/左值):

left:
    -left:
         "MyVar"
    -node:
         ":"
    -right:
         "integer"
node:
     "="
right:
    -left:
         "8"
    -node:
         "+"
    -right:
         "2"

表示为经典 AST:

           "="
          /   \
         /     \
        /       \
      ":"       "+"
     /   \     /   \
    /     \  "8"   "2"
   /       \
"MyVar" "integer"

然后，将临时树添加到全局树中，指定声明的类型:

    [EXP]
      |
   VarDecl
      |
   { ... }

这适用于除函数声明和函数调用之外的所有内容:

func add(a : integer, b : integer) : integer;

add(8, 2);

的确，对于这种类型的表达式，没有节点来区分左值和右值。我也不知道如何表示函数参数。我想到了这样的事情:

left:
    "add"
    params:
        [
         -left:
              "a"
         -node:
              ":"
         -right:
               "integer"
        ]
        [
         -left:
              "b"
         -node:
              ":"
         -right:
               "integer"
        ]
node:
    ":"
right:
    "integer"

通话同上:

left:
    "add"
params:
    [
      "8"
    ]
    [
     "2"
    ]

但我觉得如果我这样做就没有逻辑了。

所以，我想知道是否有一种接近我的方法来改进它，或者是否必须完全修改我的方法。

PS:我在抽象语法分析和树领域还很陌生，但我已经阅读了很多关于这个主题的文档和教程。

Answer 1

首先，我会建议研究 C++ 的 bison/flex 或其他解析器生成器，因为您可以更轻松地将语句分组到树结构中。

对于函数参数问题，AST 不仅仅是右节点左。您可以在一个节点下有多个(> 2)个分支，并将这些分支视为它们的语法表达式而不是文字字符。这是词法分析器提供帮助的地方，因为您可以将字符抽象为标记，然后解析器会将标记抽象为语法结构。一般来说，像 a : integer 这样的东西应该被抽象成一个语法结构，可能是所谓的类型化声明。

所以 func add(a : integer, b : integer) : integer; 是真的

函数标识符(参数):返回类型

AST中的节点可以跟踪特定信息。

即您的 AST 应该使用“字符”或“标记”，但内部节点应该是语言语法结构的抽象。特别是对于参数列表，我建议将其作为逗号分隔的类型声明列表，然后 params 节点将有一个子节点声明节点列表。

同样从你关于将语句添加到全局树的声明中，将其视为将语句添加到全局 AST 列表可能更有用。

无论如何，这是一个奇怪的答案，希望对您有所帮助。