编译器-PL0解释程序

这次实验不再进行详细说明，参考资料中都讲的很好，主要针对难点进行阐述，难点懂了，这个实验几乎就完成了 ✅。

难点

这次实验我一直搞不懂 DL 和 SL 的区别，看了文章也还没搞懂，最终最终问了 AI，让它帮我详细解释解释，才慢慢搞懂。

其实，结合代码来讲是最“形象”🉐。以下的代码来自我的PL0-Compiler仓库中的测试样例 2。

var x;
procedure B;
var y;
beginy := x;
end;procedure A;
begincall B;
end;beginx := 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 返回的。

DL (动态链)：

记录的是调用关系（运行时动态调用的顺序）。
表示调用者，只知道当前子程序是由哪一个子程序调用的。
回溯关系是动态的，依赖实际的调用栈。

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:10null
stack

跳转到第 10 条指令，分配栈空间

B:0
T:3
code:INT,0,4
P:113 0 x  <- T
2 0 RA
1 0 DL
0 0 SL <- B
stack

将常量 1 放入栈顶

B:0
T:4
code:LIT,0,1
P:124 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:134 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:76  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:76  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:86  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:19  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:29  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:310 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:411 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:511 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:911 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:1411 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