符号表如何与静态链和范围界定相关？

Question

我现在正在学习编程语言课程的原则,但我不能为我的生活弄清楚这一点.这不是一个普通的概念问题.

在我们的课堂上,我们讨论了静态链和显示.我想我理解为什么我们需要这些.否则,当我们有嵌套方法时,我们无法弄清楚当我们有嵌套方法时我们正在谈论的变量.

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

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

---

(我将定义一些内容,以便更容易解释)

假设我们有这个代码:

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将是innerA

---

只是为了重申我的问题:

• 什么是用于的符号表？
• 它与静态链有什么关系？
• 为什么我们需要静态链,因为范围信息在符号表中.

Answer 1

请注意,"符号表"可能意味着两个不同的东西:它可能意味着编译器用来确定变量的哪个别名具有范围的内部结构,或者它可能意味着库在加载时将其导出到其用户的符号列表时间.在这里,您使用的是前一个定义.

符号表用于确定当使用某个名称时用户正在引用的内存地址.当你说"x"时,你想要"x"的别名？

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

总而言之,您可以从静态链重构符号表,反之亦然.但是你真的希望两者都能快速完成常见的操作.如果缺少符号表,则编译将花费更长时间,因为每个非本地范围的变量访问都需要爬上静态链.如果缺少静态链,则编译将花费更长时间,因为保留范围将需要遍历符号表以删除现在已解散的条目.

顺便说一句,如果您还没有使用Michael Scott的编程语言语用学,那么您应该看看它.这是迄今为止我见过的关于这个主题的最好的教科书.