9

同じ条件をおそらく異なる方法で実装しようとする2つの異なるソースからの「ifステートメント」があります。「ifステートメント」はCです。可能であれば、条件のペアが同等かどうかを判断できるPythonスクリプトが必要です。基本的な例：

source1：((op1 != v1) || ((op2 != v2) || (op3 != v3)))

source2：((op2 != v2) || (op1 != v1) || (op3 != v3))

もちろん、すべての演算子、関数呼び出し、そしてもちろん括弧が許可されます。

どんなアイデアでも大歓迎です。

編集1：関数呼び出しには副作用はありません。

4

2 に答える 2

5

問題はNP完全である可能性があります（またはそうでない可能性があります）が、これが重要なものの内部ループ内にない限り（そして変数の数が少ない場合）、真理値表全体を構築してください！やり方は非常に簡単です。明らかに 2^n のように大きくなりますが、小さな n の場合、これは完全に実現可能です。コメントが示唆するように、関数呼び出しには副作用がなく、単にTrueorを出力すると仮定していますFalse。

あなたが述べた問題を解決するモックアップの例を投稿しました。必要に応じて調整してください。式の評価を処理するために、pythons パーサーに依存しています。

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

これを行うには、2 つの条件が同じ制御依存関係を持っているかどうかを判断するための制御フロー分析 (そうでない場合、同じデータ コンテキストで実行されない)、C コードのポイントツー分析を含む完全なデータ フロー分析、サイド-関数の効果分析、条件のルートから関数呼び出し全体の式のリーフまでバックスライスする機能、および C セマンティクスを説明するブール等価マッチャー (例: ショートサーキット、オーバーフローなど)

これは、C パーサーから得られるものをはるかに超えています。

于 2013-03-06T23:27:12.653 に答える