scope - 符号表如何与静态链和作用域相关？

Question

我现在正在学习编程语言原则类(class)，但我终生无法弄清楚这一点。这不是家庭作业，只是一个笼统的概念问题。

在我们的类(class)中，我们讨论了静态链和显示。我想我明白为什么我们需要这些。否则，当我们有嵌套方法时，我们无法弄清楚当我们有嵌套方法时我们在谈论什么变量。

我的教授也谈到了符号表。我的问题是符号表有什么用？它与静态链有什么关系？

我会给出一些背景(如果我错了，请纠正我)。

(我将定义一些东西只是为了使解释更容易)

假设我们有这样的代码:

main(){
    int i;
    int j;
    int k;
    a(){
        int i;
        int j;
        innerA(){
            int i = 5;
            print(i);
            print(j);
            print(k);
        }
    }

    b(){
        ...
    }
    ...
}

而这个堆栈:

| innerA  |
| a       |
| b       |
| main    |
-----------              

静态链快速说明 作为复习。

静态链用于查找在内部函数中重新定义变量时应使用哪个变量。在上面显示的堆栈中，每个帧都有一个指向包含它的方法的指针。所以:

| innerA  | \\ pointer to a
| a       | \\ pointer to main
| b       | \\ pointer to main
| main    | \\ pointer to global variables
-----------        

(假设静态范围，对于动态范围，我认为每个堆栈帧都将指向它下面的一个)

我认为当我们执行 print(<something>)内 innerA这将发生的方法:

currentStackframe = innerAStackFrame;
while(true){ 
    if(<something> is declared in currentStackFrame)
        print(<something>);
        break;
    else{
        currentStackFrame = currentStackFrame.containedIn();
    }
}

符号表快速复习

我不太确定符号表是干什么用的。但这就是它的样子:

Index is has value, 
Value is reference.
 __
|  |
|--|                        --------------------------------------------------
|  | --------------------> | link to next | name | type | scope level | other |
|--|                        --------------------------------------------------
|  |                              |
|--|                ---------------
|  |                |    
|--|                |             --------------------------------------------------
|  |                 ------->    | link to next | name | type | scope level | other |
|--|                              --------------------------------------------------
|  |
|--|

链接到下一个 - 如果不止一个事物具有相同的哈希值，则这是一个链接

name - 元素的名称(例如:i、j、a、int)

类型 - 事物是什么(例如:变量、函数、参数)

范围级别 - 不是 100% 确定这是如何定义的。我觉得:

0 将是内置的

1 将是全局变量

2 将是主要方法

3 将是 a 和 b

4 将是内部 A

只是重申我的问题:

符号表是干什么用的？

它与静态链有什么关系？

为什么我们需要静态链，因为范围信息在符号表中。

Answer 1

请注意，“符号表”可能表示两种不同的含义:它可能表示编译器使用的内部结构来确定变量的哪个别名具有范围 where，或者表示库在加载时向其用户导出的符号列表时间。在这里，您使用的是前一个定义。

符号表用于确定用户在使用某个名称时所引用的内存地址。当你说“x”时，你想要“x”的哪个别名？

您需要同时保留静态链和符号表的原因是:当编译器需要确定哪些变量在某个范围内可见时，它需要“取消屏蔽”先前在内部范围内别名化的变量。例如，当从 innerA 移动时返回 a ，变量 i改变它的内存地址。同样的事情从 a 再次发生至 main .如果编译器不保留静态链，则必须遍历整个符号表。如果你有很多名字，那就太贵了。对于静态链，编译器只查看当前级别，删除其中包含的每个变量的最后定义，然后沿着链接向上一个作用域。另一方面，如果您没有符号表，那么不在局部范围内的每个变量访问都会使编译器不得不遍历静态链。

综上所述，可以从静态链重构符号表，反之亦然。但是您确实希望同时拥有两者以加快常见情况的操作。如果缺少符号表，编译将花费更长的时间，因为每个非局部范围的变量访问都需要攀爬静态链。如果缺少静态链，则编译将花费更长的时间，因为离开作用域将需要遍历符号表以删除现已失效的条目。

顺便说一句，如果您还没有使用 Michael Scott 的 Programming Language Pragmatics，您应该看看它。这是迄今为止我见过的关于这个主题的最好的教科书。