程序范围的数据结构？

Question

我正在尝试解析程序的 AST 以获得一种虚构的语言，具体来说，我正在尝试模拟作用域，因此您输入一个函数，然后推送一个新的作用域，当该函数完成时当访问者访问时，它会弹出范围。一个重要的方面是，当我们推送一个新的作用域时，会currentScope设置一个指针，它指向我们当前正在查看的作用域。当我们弹出作用域时，当前作用域被设置为“外部”：

class Scope:
    outer : Scope
    inner : Scope

这将在多次传递中发生，但第一次传递重要的是它构建通用范围树。我要问的问题是如何按照创建树的顺序遍历这棵树？例如：

{ // global scope
    { // a
        { // aa

        }
        { // ab
        }
    }
    { // b
    }
}

当我再次传递完全相同的节点集时，理论上它们会给我相同的范围树，但我想保留我们在每次传递中收集和存储每个范围的所有数据。换句话说，当第二次或第三遍发生在 AST 上时，当我们访问 a 时，currentScope = a，当我们访问 aa 时，currentScope = aa。这可能吗？我真的对这个想法感到困惑，整个递归方面真的让我很困惑，我似乎不知道如何做到这一点。

这是我尝试过的：

class Scope
    outer : Scope
    inner : Scope
    siblings : []Scope

    Scope(outer):
        this.outer = outer

push_idx = 0

push_scope()
    // set global scope
    if current is null
        global = new Scope(null)
        current = global
        return

    if current.inner is not null:
        // first pass over the AST
        if current_pass == 0:
            new_scope = new Scope(current)
            current.siblings.push(new_scope)
            current = new_scope
            return
        current = current.siblings[push_idx++]
    else:
        new_scope = new Scope(current)
        current.inner = new_scope
        current = current.inner

pop_scope()
    push_idx = 0
    current = current.outer

虽然顺序看起来不正确，但我相当确定这是错误的方法。

Answer 1

经常用于跟踪编译器内部作用域的数据结构是意大利面条堆栈，它本质上是一个链接列表数据结构，其中每个作用域都是一个存储指向其父作用域的指针的节点。每当您进入一个范围时，您都会创建一个新节点，将其指向封闭的范围，然后将该节点存储在与该范围关联的 AST 中的某个位置。当您遍历 AST 时，您的 AST 遍历器会存储一个指向当前作用域节点的指针。当您输入范围时，您将创建一个新的范围节点，如上所述。当您离开作用域时，您可以将指针更改为指向当前作用域的父级。这最终会构建一个大型倒置树结构，其中每个作用域都可以跟踪其作用域链直至根作用域 - 意大利面条堆栈。