3.1.5 变量级别确定算法
确定变量的级别是为变量排序所做的预处理工作。简单来讲,变量的级别就是变量在表达式中出现的次序。区间运算的工作机制是从程序入口开始对待覆盖路径进行数据流分析,如果变量的取值在某个分支节点处导致不可达路径的产生,则变量取值失败,不再向下进行数据流分析。距离程序入口越近的表达式对于赋值成功与否的影响越大。因此,需要对程序中的变量进行分级。目前对于变量级别的确定方式如下。
①默认所有变量的级别为-1。
②第一个表达式中出现的变量级别为0。
③同一个表达式中出现的变量的级别相同。
④表达式每增加1个,级别增加1级。
⑤变量的级别为-1时,这种变量是没有出现在表达式中的变量,它们并不影响其他变量的赋值,因此将它们的优先级设为最低。
在提取完所有表达式之后,接下来的工作就是从表达式中提取变量。在从表达式中提取变量的同时确定变量的级别。因为变量的级别是按变量在表达式中出现的先后次序确定的。由于在提取表达式时提取的是含有表达式的节点,并将这些含有表达式的节点依次存储在线性链表explist中,因此为了提取表达式中的变量,需要依次遍历线性链表explist中的每一节点。任一变量的级别都初始化为-1。提取变量,确定变量级别的流程如图3-6所示,算法如下所述。(https://www.daowen.com)
①定义一个线性链表symlist存储提取出来的变量,symlist初始化为空,由于每一个变量都有与之对应的符号,实际上symlist中存储的是变量对应的符号。
②如果explist中还有未被访问的控制流图节点,则依次取explist中的一个控制流图节点node,转去执行③;否则,返回symlist,算法结束。
③获取控制流图节点node中的表达式exp,获取exp中的所有变量expvarlist(调用已有接口就可实现)。
④若expvarlist中还有未被访问的变量,则依次取expvarlist中的一个变量var,转去执行⑤;否则转去执行②。
⑤如果symlist中不含变量var,则设置变量var的级别为node在explist中的序号,并将变量var添加到symlist中。
⑥转去执行④。
