【输入】
根过程，及每个过程（含根过程）的指令序列
【输出】
调用图，由过程点集和调用边（形如<p,i,q>，p在位置i调用q）集构成
【全局结构】
PVVs：过程值变量集合
PVVals：过程值变量到过程常数集合的映射
PVBinds：过程值变量到过程值变量集合的映射
PVCalls：调用边的集合
【流程核心】
1. 分析过程p内指令，要处理调用指令和赋值指令两种类型。对于调用指令，若被调过程q是过程常数，则将q和<p,i,q>加入调用图，先解析q的过程值形参与传入实参的关系，有4种情况
a）过程常数cp传入过程值形参fp，将偶对<fp,cp>加入PVVals，fp加入PVVs
b）过程值变量vp传入过程值形参fp，将<fp,vp>加入PVBinds，fp和vp加入PVVs
c）过程值形参fp传出过程值变量vp，将<vp,fp>加入PVBinds，vp和fp加入PVVs
d）过程值形参fp传出过程常数cp，将<fp,cp>加入PVVals，fp加入PVVs
若q不是常数而是过程值变量，则将q加入PVVs，<p,i,q>加入PVCalls。再解析q的返回与p的关系，有2种情况
e）返回一个过程值变量vp1赋给另一过程值变量vp2，将<vp2,vp1>加入PVBinds，vp2和vp1加入PVVs
f）返回一个过程常数cp赋给一个过程值变量vp，将<vp,cp>加入PVVals，vp加入PVVs
对于赋值指令，其实情况和上述返回赋值一样
----------------------------------------------------------------
2. 遍历PVVs，传播各过程值变量的PVBinds，直至不再改变（迭代求不动解），本质是计算过程值变量的传递闭包
3. 遍历PVCalls，对每个<p,i,q>，先遍历它的每个PVVals u，将u和<p,i,u>加入调用图；再遍历它的每个PVBinds u及u的每个PVVals v，将v和<p,i,v>加入调用图
----------------------------------------------------------------
以上三环节可使用工作表w来驱动，w初始只有根过程，不断从w移出一个过程p、分析p，每当在环节1或环节3发现一个新过程（过程常数）就加入w，直至w为空，这时所有过程都已分析，调用图构建完成
posted on 2023-09-06 23:04
春秋十二月 阅读(30)
评论(0) 编辑 收藏 引用 所属分类:
Compiler