为具有多行的代码创建一个抽象的语法树

Question

从多行代码创建AST时，总体实践是什么？例如，如果我正在编写翻译器将代码从一种语言转换为另一种语言，并且我遇到了这样的语句：

x = 2
f = k->o
a = 1+2*3

我可以在此处成功为每条代码线创建ASTS。现在，虽然必须生成翻译的代码，但如果代码长n行，我会更好地拥有一个AST而不是N AST？如果是这样，如何形成单个AST？

Answer 1

首先，您可能不应该再考虑"代码行"了。解析器的输入是代币流。你做有一个lexer，不是吗？： - ）

AST跨越许多语句是完全很好的（和正常）。实际上，它通常会跨越整个编译单元，例如一个函数甚至整个模块（读：源文件）。

例如，考虑此程序：

fun f(x, y) {
    z = x + y;
    if (z > 3) {
        return z; 
    } else {
        return g(x);
    }
}
fun g(x) {
    return x * 2;
}

编译器可能会构建一个看起来像这样的AST（请忽略细节并专注于一般结构）：

ModNode
  FunNode[Name = "f"]
    CompoundStmtNode
      AssignStmtNode
        VarNode[Name = "z"]
        BinExprNode[Oper = "+"]
          VarNode[Name = "x"]
          VarNode[Name = "y"]
      IfStmtNode
        BinExprNode[Oper = ">"]
          VarNode[Name = "z"]
          ConstNode[Value = 3]
        CompoundStmtNode
          ReturnNode
            VarNode[Name = "z"]
        CompoundStmtNode
          ReturnNode
            CallNode[Name = "g"]
              VarNode[Name = "x"]
  FunNode[Name = "g"]
    CompoundStmtNode
      ReturnNode
        BinExprNode[Oper = "*"]
          VarNode[Name = "x"]
          ConstNode[Value = 2]

为整个源文件构建AST的好处是，在代码上执行多个逻辑通行非常容易（例如，为了解决前向引用）。当然，缺点是AST可以变得很大。

Answer 2

我会建议您拥有一个由较小AST制成的AST。并使用递归遍历它们。对于树的设计，您可以选择任一侧。但是我将使用右侧为每行，左侧指向下一行代码。将其提出来。我会假设您知道如何解析分子节和删除，只是显示更大的图片

x = 2

f = k-> o

a = 1 2*3

因此，您有。

                                   [AssignNode]
                          left                      right
                      [AssignNode]                  [x=2]
              left                   right  
           [AssignNode]             [f=k->o]
     left                right
    [Null]            a = [ExprNode]
                           [1]  +   [2*3]

遍历将从向右开始，直到我们击中null。一旦我们碰到null返回节点，就向左走。

因为这是一个由较小的AST组成的。每次击中一个新节点/AST时，我们都会进行相同的遍历，然后向左走。

给我们正确获取x = 2然后击中null返回并向左走。到分配节点正确获取f = k-> o然后击中null返回并向左走。获取分配节点正确获取a = exprnode向右解析删除返回并完成任务归还然后向左走。左为空。