编译器-PL0解释程序
这次实验不再进行详细说明，参考资料中都讲的很好，主要针对难点进行阐述，难点懂了，这个实验几乎就完成了 ✅。
难点
DL 和 SL
这次实验我一直搞不懂 DL 和 SL 的区别，看了文章也还没搞懂，最终最终问了 AI，让它帮我详细解释解释，才慢慢搞懂。
其实，结合代码来讲是最“形象”🉐。以下的代码来自我的PL0-Compiler仓库中的测试样例 2。
var x;
procedure B;
var y;
begin
y := x;
end;
procedure A;
begin
call B;
end;
begin
x := 1;
call A;
end.
上述代码的调用关系为：
- 主函数(main)–调用->A
- A–调用->B
SL 静态链和 DL 动态链都记录了当前层的上一层的信息，但这上一层和上一层之间也并不是完全一样。
-
SL 静态链：从代码中看程序的嵌套结构，过程 A 和 B 的上一层都是主程序，它们都是在主程序中定义的过程。
-
DL 动态链：从(函数)调用的角度看，因为主程序调用了 A，所以主程序是 A 的上一层，又因为 A 调用了 B，所以 A 又是 B 的上一层。这就有点不一样了，B 的上一层在代码层面明明是主程序，而在这里却成了 A。
这次我们发现了 DL 和 SL 的不同。而我们进行变量查找时，当前层次没找到，沿着静态链 SL 去上一层查找。我们进行过程(函数)返回时，需要恢复基址寄存器，这时是按照 DL 返回的。
下面是 AI 的解释：
DL (动态链)：
- 记录的是调用关系（运行时动态调用的顺序）。
- 表示调用者，只知道当前子程序是由哪一个子程序调用的。
- 回溯关系是 动态的，依赖实际的调用栈。
SL (静态链)：
- 记录的是词法作用域关系（程序的嵌套结构）。
- 表示定义者，知道当前子程序是在哪一个作用域中定义的。
- 回溯关系是 静态的，依赖编译时的嵌套层次。
这里可能会有疑问 🤔，为什么必须按照 SL 去找变量，如果按照 DL 去找有什么问题呢？
var x;
procedure B;
var y;
begin
y := x;
end;
procedure A;
var x;
begin
x := 2;
call B;
end;
begin
x := 1;
call A;
end.
我们详细来分析一下，先将之前的代码改一下，给过程 A 也加一个变量 x 并赋值为 2，那么 B 中的 y 会被赋值为 1 还是 2 呢？
如果是按照 SL 肯定是 1，DL 就是 2。那这对不对呢？其实是不对的，我们通过 C 语言来看一下：
...
int x = 1;
void B() {
y = x;
}
void A(){
int x = 2;
B();
}
int main() {
A();
return 0;
}
你认为上述代码中的 y 应该是几？此时你应该知道为什么不能按照 DL 找了 8️⃣。
层次差
之前语法分析部分埋下的坑终于要填了。我们之前计算层次差会在哪里计算呢？
- 变量的调用部分：当前层次的 level - 符号表中声明时的 level
- 过程的调用部分：CAL 指令生成时，CAL 指令的第一个参数就是层次差
下面我们分开来分析：
首先是变量，如果层次差为 0，说明这个变量的声明和调用都是在同一层次的，就例如下面的 x 和 y：
var x // 声明
procedure m
var y // 声明
begin
y := y + 1; // 调用
end;
begin
x := x + 1; // 调用
end.
如果层次差为 1，说明变量的调用比声明多了一层，比如下面的 x：
var x // 声明
procedure m
var y // 声明
begin
y := x + 1; // 调用
end;
begin
call m;
end.
这时候我们想要给 y 赋值发现这一层竟然没有 x，那我们不就得不断地向上一层找 x，如果一直找不到，那说明有语义错误，如果找到了就把它的值拿过来。而我们现在就要理解它不断向上层找的过程。根据上面我们对于 SL 和 DL 的理解，这里应该顺着 SL 找，是很容易知道的。SL 记录了代码嵌套结构中该层的上一层，根据上述实际的代码来看：m 的上一层其实是主函数，主函数的 level 是 0，而 procedure 里的变量的 level 都是 1，它们之间有层次差 1，所以就根据自己的 SL，找到主函数的基址，并根据偏移量得到了 x 值，这样就可以进行运算了。
如果层次差为 2 怎么办，其实就是多找一层，每一层都有 SL，就像下面的代码，y 变量的层次为 2，但 x 的层次为 0，之间的层次差为 2。n 的 SL 会获取到 m 的基址，从基址就能得到 m 的 SL，我们再从 m 的 SL 获取到主函数的基址，从而根据偏移量找到 x。
var x
procedure m
procedure n
var y
begin
y := x + 1;
end;
begin
call n;
end;
begin
call m;
end.
之后随着层次差的增大就是一个重复的过程，但我们规定代码中最多嵌套三层，所以层次差最多为 3。
然后是过程的调用，和变量几乎一样。还是拿上面的代码来说明：
var x
procedure m
procedure n
var y
begin
y := x + 1;
end;
begin
call n;
end;
begin
call m;
end.
m 的层次为 0，n 的层次为 1，调用都是同层的，所以生成的 CAL 指令第一个参数都是 0，而这时单纯分析代码也能看出，DL 和 SL 其实都是一样的。
var x;
procedure B;
var y;
begin
y := x;
end;
procedure A;
begin
call B;
end;
begin
x := 1;
call A;
end.
上面代码 A 调用 B 的时候就有了层次差，因为 A 和 B 的层次都是 0(在主函数中声明和定义)，但是调用 B 是在 A 内部进行的，A 内部的层次为 1，所以会有一个 1 的层次差。和变量不同的是，这次我们不会顺着 SL 向上找变量，而是顺着 SL 只要找到上一层的基址就可以了，省略了根据偏移量找变量的过程，其实还变得简单了。
这一部分其实还是加深对于 SL 的理解，虽然这里的说明是先是变量后是过程，但实际上应该是先是过程将自己层的 SL 字段给完善了，后续的变量才能根据自己层的 SL 向上层找其他的变量。
执行过程模拟（手动
上述的代码(第一个代码段)生成的中间代码为：
// 指令数组
codelist:
0 F: JMP L: 0 A: 10
1 F: JMP L: 0 A: 2
2 F: INT L: 0 A: 4
3 F: LOD L: 1 A: 3
4 F: STO L: 0 A: 3
5 F: OPR L: 0 A: 0
6 F: JMP L: 0 A: 7
7 F: INT L: 0 A: 3
8 F: CAL L: 1 A: 1
9 F: OPR L: 0 A: 0
10 F: INT L: 0 A: 4
11 F: LIT L: 0 A: 1
12 F: STO L: 0 A: 3
13 F: CAL L: 0 A: 6
14 F: OPR L: 0 A: 0
符号表：
{address=3, level=1, kind=SYM_VAR, name=x}
{address=1, level=1, kind=SYM_PROCEDURE, name=B}
{address=3, level=2, kind=SYM_VAR, name=y}
{address=6, level=1, kind=SYM_PROCEDURE, name=A}
因为这个程序比较简单，下面我们手动模拟一遍：
先定义各个寄存器和栈空间：
B:0 // 基址寄存器
T:-1 // 栈顶指针
code:null // 要执行的指令
P:0 // 要执行的下一条指令的下标（指令数组的下标
null
stack
首先，获取 JMP 无条件跳转指令
B:0
T:-1
code:JMP,0,10 // 会修改P
P:10
null
stack
跳转到第 10 条指令，分配栈空间
B:0
T:3
code:INT,0,4
P:11
3 0 x <- T
2 0 RA
1 0 DL
0 0 SL <- B
stack
将常量 1 放入栈顶
B:0
T:4
code:LIT,0,1
P:12
4 1 常量 <- T
3 0 x
2 0 RA
1 0 DL
0 0 SL <- B
stack
将常量存储到变量 x 中
B:0
T:3
code:STO,0,3
P:13
4 1 常量
3 1 x <- T
2 0 RA
1 0 DL
0 0 SL <- B
stack
调用 A
B:4
T:4
code:CAL,0,6
P:7
6 14 RA
5 0 DL
4 0 SL <- T/B
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
跳转
B:4
T:4
code:JMP,0,7
P:7
6 14 RA
5 0 DL
4 0 SL <- T/B
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
分配空间
B:4
T:6
code:INT,0,3
P:8
6 14 RA <- T
5 0 DL
4 0 SL <- B
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
调用 B
B:7
T:7
code:CAL,1,1
P:1
9 9 RA
8 4 DL
// 通过代码中get_sl计算
7 0 SL <- T/B
6 14 RA
5 0 DL
4 0 SL
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
跳转指令
B:7
T:7
code:JMP,0,2
P:2
9 9 RA
8 4 DL
7 0 SL <- T/B
6 14 RA
5 0 DL
4 0 SL
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
分配空间
B:7
T:10
code:INT,0,4
P:3
10 0 y <- T
9 9 RA
8 4 DL
7 0 SL <- B
6 14 RA
5 0 DL
4 0 SL
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
将 x 的值移到栈顶
B:7
T:11
code:LOD,1,3 //层差是1，需要沿着SL到上一层(main)，然后获取B+3(在这里为3)地址x的值
P:4
11 1 x <- T
10 0 y
9 9 RA
8 4 DL
7 0 SL <- B
6 14 RA
5 0 DL
4 0 SL
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
将栈顶的值存到变量 y 中
B:7
T:10
code:STO,0,3
P:5
11 1 x
10 1 y <- T
9 9 RA
8 4 DL
7 0 SL <- B
6 14 RA
5 0 DL
4 0 SL
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
过程返回
B:4
T:6
code:OPR,0,0
P:9
11 1 x
10 1 y
9 9 RA
8 4 DL
7 0 SL
6 14 RA <- T
5 0 DL
4 0 SL <- B
3 1 x
2 0 RA
1 0 DL
0 0 SL
stack
过程返回
B:0
T:3
code:OPR,0,0
P:14
11 1 x
10 1 y
9 9 RA
8 4 DL
7 0 SL
6 14 RA
5 0 DL
4 0 SL
3 1 x <- T
2 0 RA
1 0 DL
0 0 SL <- B
stack
程序结束
B:0
T:-1
code:OPR,0,0
P:0 // 程序结束
11 1 x
10 1 y
9 9 RA
8 4 DL
7 0 SL
6 14 RA
5 0 DL
4 0 SL
3 1 x
2 0 RA
1 0 DL
0 0 SL <- B
stack