程序范围的数据结构？

Question

我正在尝试通过程序的 AST 来解析一种合成语言，具体来说，我正在尝试模拟作用域，例如，您输入一个函数并推送一个新的作用域，然后当函数完成被访问者访问时，它会弹出作用域。一个重要的方面是，当我们推送一个新范围时，会设置一个指针 currentScope，它指向我们当前正在查看的范围。当我们弹出作用域时，这个 currentScope 被设置为 "outer":

class Scope:
    outer : Scope
    inner : Scope

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

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

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

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

这是我试过的方法：

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 walker 会存储一个指向当前作用域节点的指针。当您进入范围时，您将创建一个新的范围节点，如上所述。离开作用域时，会将指针更改为指向当前作用域的父级。这最终构建了一个大的倒置树结构，其中每个作用域都可以跟踪其作用域链直到根作用域——意大利面条堆栈。

Answer 2

"Scope"实际上是程序的一个区域，该区域中的所有标识符都具有恒定的含义。

如果你的语言有纯嵌套的词法作用域，你可以用树（"spaghetti" 堆栈，如果你喜欢的话）对作用域集建模，其中每个叶子都包含从该作用域中引入的符号到它们的符号的映射对应的类型信息。这就是 class 编译器 classes.

中教导的内容。

但是对于更复杂的范围规则（命名空间、使用构造等），通常您可能需要一个图，其叶子是各个范围，图弧表示范围之间的关系。是的，其中一个关系通常是 "lexical parent"。其他可能包括 "inherits from" 等。您可能还会发现叶映射中的名称可能是一种类型，它实际上可能是图中任意其他（叶）范围的访问路径。

（我构建了通用程序分析工具基础设施 [见生物]。我们定义了一个图形样式的符号 table API 来支持我们遇到的所有不同的范围规则。一个有趣的 [= arc 的 24=] 对于任意整数 N 是 "inherits from with priority N"；这让我们可以轻松地对 C++ 提供的有序多重继承进行建模。

Answer 3

也许你应该考虑一下Segment tree:

每个段代表一个范围（范围开始 | 范围结束）。
树结构将根据代码层次结构。
树的叶子将是每个范围内的关键字。

祝你好运！

程序范围的数据结构？

Data structure for program scope?

compiler-construction

tree

data-structures