5.4.2　算法描述和实现

算法5-4给出了基于语义分析的库函数区间运算算法(Improved Constraint Solving algorithm based on Inverse Function,ICSIF)的基本流程。

在上述算法中,Judge Type(E)通过输入表达式中的库函数名判定库函数类型F_type,并确定其函数语义。S L是一个由F_type、L i构成的二元组的集合,S L.key为所有F_type组成的集合,S L.value为Li组成的集合。根据此类型在库函数反操作集S L.key选择求反操作类型,根据库函数值域I(约束对库函数取值的限定),以及其参数列表X进行区间运算求出满足库函数定义域的区间D′,进而得出X的取值区间D。

事实上,C语言函数库中的一些库函数是存在互为“反函数”的关系的[10],如math.h中的正弦函数sin(x)和反正弦函数asin(x)。处理这类在函数库里有自身“反函数”的库函数时,只需在语义分析确定函数功能后,直接调用其“反函数”即可完成求反操作。然而,更多的库函数在库中是不存在“反函数”的,因此在语义分析清楚函数功能的基础上,需要根据库函数值域和函数功能,人为地为此库函数定义一个求反操作。另外,约束E对库函数值域的约束会导致一个库函数对应不同的求反操作:abs(int x)表示x的绝对值,当约束表达E为abs(x)＞10时,x的定义域为[11,+∞)∪(-∞,-11];当约束表达式E为abs(x)＜10时,x定义域为[-9,9]。库函数的参数列表中参数的个数及其赋值顺序也可能会导致一个库函数对应不同的求反操作:pow(int x,int y)=9表示x y=9,是一种幂次操作,由数学定义可知x=y 9,y=log x 9,可知在输入参数区间均不为确定值的情况下,如果不明确其赋值次序,就无法确定求反操作类型。(https://www.daowen.com)

针对以上问题可以对库函数类型集合进行图5-17所示的进一步细化,将库函数类型集合S.key分为SAPI.key和SNAPI.key。其中SAPI.key表示在函数库里有自身“反函数”的库函数类型集,SNAPI.key表示需要人为定义“反函数”的库函数类型集。SAPI.key和SNAPI.key互为补集。由于参数列表中不确定的区间的参数变量个数、赋值次序导致了求反操作类型不确定,因此根据参数列表的参数个数对SAPI.key以及SNAPI.key再次进行分类,区别处理流程不同:对于参数类表中只有一个参数的库函数集SAPI.key1(或SNAPI.key1),直接根据其F_type进行求反操作;对于多个变量区间都为不确定的库函数集SAPI.key N(或SNAPI.key N),可以人为规定变量的赋值次序,直到只剩下一个区间不确定的变量,然后再对此变量根据F_type进行求反操作,上述流程由算法5-5给出。

图5-17　库函数类型层次图