编译器在制作 AST 时如何处理超过 2 个节点

Question

我很难理解编译器如何处理超过 2 个节点的情况。

例如，假设我有一个程序，其中包含 3 个已定义的函数。该程序是我们的根节点，其他 3 个函数是子节点。这是否意味着根节点现在有 3 个子节点？根据我的理解，AST 仅由左右子节点组成。解析器如何处理这样的情况？

// AST representation

                Program
            /       |      \ 
      function   function    function

我的另一个假设是解析器创建一个新节点，并且它的所有子节点都将显式用于函数。例如：

// AST representation

                 Node
                /    \
function declaration  Node
                     /    \
    function declaration   Node

当我查看 AST 解析器的一些在线代码（例如 astexplorer.net）时，它显示该程序有 3 个单独的子节点，但这对我来说毫无意义。

我尝试本质上创建一个解析器，为每个函数创建新节点，但它们是链接的（请参阅第二个 AST 表示）。但是我还没有完成它，并且想在继续之前了解一种传统的方法。

Answer 1

AST 构建自由度

AST结构完全由你设计，只要它是一棵树（抽象语法Tree）。

没有定义正确 AST 的标准，但常见的约定是至少删除空格和与语义无关的符号元素。

根据语法生成 AST

如果你想拥有第二种结构，最简单的方法就是设计语法：

node: function_declaration node | epsilon
function_declaration: function_start function_arguments function_block

然后设计实现此语法的解析器，例如，递归下降实现如下所示：

def node():
    ast = Ast(Type.Node)
    if peek(function_start):
        ast.add(function_declaration())
        ast.add(node())
    
    return ast

def function_declaration():
    # Produce a single node with 3 children
    ast = Ast(Type.function_declaration)
    ast.add(function_start())
    ast.add(function_arguments)
    ast.add(function_block)
    
    return ast

输出 ast 将按预期构建。 但是，如果您想要 function_declaration 非终结符的阶梯模式， 你应该更新语法：

node: function_declaration node | epsilon
function_declaration: function_start function_arguments_node
function_arguments_node: function_arguments function_block_node
function_block_node: function_block

并相应修改代码：

def function_declaration():
    ast = Ast(Type.function_declaration)
    ast.add(function_start())
    ast.add(function_arguments_node())
    return ast
    
def function_arguments_node()
    ast = Ast(Type.function_arguments_node)
    ast.add(function_arguments())
    ast.add(function_block_node())
    return ast
    
def function_block_node()
    ast = Ast(Type.function_block_node)
    ast.add(function_block)
    return ast

或者使用原始语法更新 AST 构造：

def function_declaration():
    ast = Ast(Type.function_declaration)
    ast.add(function_start())
    
    astArgumentsNode = Ast(Type.node)
    astArgumentsNode.add(function_arguments)
    
    astBlockNode = Ast(Type.node)
    astBlockNode.add(function_block)
    
    astArgumentsNode.add(astBlockNode)
    ast.add(astArgumentsNode)
    
    return ast

本质上，根据您的语法生成 AST，AST 将看起来像您的语法。

如何更新结构使其不反映语法结构？

假设输入是一组函数：

program: function_declaration*

或者相当于 BNF：

program: node
node: function_declaration node | epsilon

这是一个幼稚的实现：

def program():
    ast = Ast(Type.program)
    ast.add(node())
    
    return ast

def node():
    ast = Ast(Type.Node)
    if peek(function_start):
        ast.add(function_declaration())
        ast.add(node())
    
    return ast

会产生阶梯模式，通常更希望没有中间节点非终结符，因为它们会使 AST 不必要地变大。 要删除它们，我们可以替换递归调用以使其迭代，而不是递归下降：

def program():
    ast = Ast(Type.program)
    while peek(function_start):
        ast.add(function_declaration())
        
    return ast

这将导致一组子节点直接添加到程序节点。

多通道方法

或者，您也可以首先遵循语法来生成 AST。使用 BNF 时，这可能包含楼梯图案。生成 AST 的第一个版本后，您可以生成第二个版本，该版本将内联每个“Node”AST 节点。这会将子级内联到“Node”AST 的父级，从而形成您在第一个图中描述的结构。

如果语义太复杂而无法在初始解析阶段推导，则用于 AST 构造的多遍系统很常见。

我认为这些答案应该可以帮助您进一步按照您想要的方式设计 AST，并帮助您了解其他编译器如何实现这一点。由于没有标准，还有无数其他方法，但这些是更常见的。