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

Question

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

我想使用三步程序：

识别语句类型；
将左值、右值和节点中的标记与表达式分开，作为临时和本地 AST；
设计并添加到全局 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

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

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

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

func identifier(params) : returnType

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

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

另外，根据你关于将语句添加到全局树的声明，将其视为将语句添加到 AST 的全局列表可能更有用。

总之有点奇怪的答案，希望对您有所帮助。

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

Confusion over the abstract formatting of an AST declaration of functions

c++

compiler-construction

abstract-syntax-tree

language-theory