9

我有来自两个不同来源的“if 语句”，它们试图以不同的方式实现相同的条件。“if 语句”是 C。如果可能的话，我需要一个 python 脚本来决定成对条件是否相等。一个基本的例子：

来源1：((op1 != v1) || ((op2 != v2) || (op3 != v3)))

来源2：((op2 != v2) || (op1 != v1) || (op3 != v3))

当然，任何运算符都是允许的，函数调用，当然还有括号。

欢迎任何想法。

编辑 1：函数调用没有副作用。

4

2 回答 2

5

事情就是这样，问题可能（也可能不是）是 NP 完全的，但除非这是在重要事物的内部循环中（并且变量的数量很小），否则请构建整个真值表！这非常容易做到。它显然增长为 2^n，但对于小的 n，这是完全可行的。就像评论所暗示的那样，我假设函数调用没有副作用，只是输出Trueor False。

我已经发布了一个模型示例，可以解决您提出的问题，根据需要进行调整。我依靠 python 解析器来处理表达式的评估。

import pyparsing as pypar
import itertools

def python_equiv(s):
    return s.replace('||',' or ').replace('&&',' and ')

def substitute(s,truth_table, VARS):
    for v,t in zip(VARS,truth_table):
        s = s.replace(v,t)
    return s

def check_statements(A1,A2):  
    VARS = set()
    maths    = pypar.oneOf("( ! = | & )")
    keywords = pypar.oneOf("and or")
    variable = pypar.Word(pypar.alphanums)
    variable.setParseAction(lambda x: VARS.add(x[0]))
    grammar  = pypar.OneOrMore(maths | keywords | variable)

    # Determine the variable names
    grammar.parseString(A1)
    grammar.parseString(A2)

    A1 = python_equiv(A1)
    A2 = python_equiv(A2)

    bool_vals = map(str, [False,True])

    for table in itertools.product(bool_vals,repeat=len(VARS)):
        T1 = substitute(A1,table,VARS)
        T2 = substitute(A2,table,VARS)
        if eval(T1) != eval(T2):
            print "FAIL AT ", table,
            return False

    print "Statements equiv:",

    return True


# Original example
A1 = '''((op1 != v1) || ((op2 != v2) || (op3 != v3)))'''
A2 = '''((op2 != v2) ||  (op1 != v1) || (op3 != v3))'''
print check_statements(A1,A2)

# Example with a failure
A1 = '''((op1 != v1) || ((op2 != v2) || (op3 != v3)))'''
A2 = '''((op2 != v2) ||  (op1 != v1) && (op3 != v3))'''
print check_statements(A1,A2)

给出作为输出：

Statements equiv: True
FAIL AT  ('False', 'False', 'False', 'False', 'False', 'True') False
于 2013-03-07T05:03:30.670 回答
2

为此，您需要控制流分析以确定两个条件是否具有相同的控制依赖关系（否则它们不会在相同的数据上下文中执行），完整的数据流分析包括 C 代码的点对点分析， - 函数的效果分析，在函数调用中从条件的根到表达式的叶子进行反向切片的能力，然后是一个解释 C 语义的布尔等价匹配器（例如短路、溢出……）

这远远超出了您从 C 解析器中得到的。

于 2013-03-06T23:27:12.653 回答