Обнаружение эквивалентных выражений

Question

В настоящее время я работаю над приложением Java, где мне нужно реализовать систему для построения выражений BPF . Мне также нужно реализовать механизм обнаружения эквивалентных выражений BPF.

Построить выражение не так уж сложно. Я могу построить синтаксическое дерево, используя шаблон проектирования Interpreter и реализовать toString для получения синтаксиса BPF.

Однако определить, эквивалентны ли два выражения, гораздо сложнее. Простым примером будет следующий:

A: src port 1024 and dst port 1024
B: dst port 1024 and src port 1024

Чтобы определить, что A и B эквивалентны, мне, вероятно, нужно преобразовать каждое выражение в "нормализованную" форму перед их сравнением. Это было бы легко для приведенного выше примера, однако, при работе с комбинацией вложенных операций AND, OR и NOT становится сложнее.

Кто-нибудь знает, как мне лучше всего подойти к этой проблеме?

Answer 1

Одним из способов сравнения логических выражений может быть преобразование как в дизъюнктивной нормальной формы (DNF) , так и сравнение DNF. Здесь переменными будут токены Berkeley Packet Filter, и одному и тому же токену (например, port 80), появляющемуся в любом из двух выражений, нужно будет присвоить одно и то же имя переменной.

Есть интересный апплет на http://www.izyt.com/BooleanLogic/applet.php - к сожалению, сейчас я не могу попробовать его из-за проблем с Java в моем браузере.

Answer 2

Я почти уверен, что обнаружение эквивалентных выражений является либо проблемой np-hard, либо np-complete, даже для выражений типа boolean-only.Это означает, что для того, чтобы сделать это идеально, оптимальный способ - это построить полные таблицы всех возможных комбинаций входных данных и результатов, а затем сравнить таблицы.

Может быть, выражения BPF каким-то образом ограничены, что это меняет?Я не знаю, поэтому я предполагаю, что нет.

Если ваши проблемы невелики, это может не быть проблемой.Я делаю точно , что является частью алгоритма проектирования дерева решений.

В качестве альтернативы, не пытайтесь быть идеальным.Разрешить некоторые ложные отрицания (случаи, которые эквивалентны, но которые вы не обнаружите).

Простой подход может состоять в том, чтобы сделать вариант нормального выражения-оценки, но скорее оценивать альтернативное представление выражениячем результат.Наложить порядок на коммутативные операторы.Примените некоторые очевидные упрощения во время оценки.Замените богатый набор операторов минимальным набором примитивных операторов - например, используйте de-morgans для исключения операторов OR.

Это альтернативное представление формирует каноническое представление для всех членов набора эквивалентных выражений.Это должен быть класс эквивалентности в том смысле, что вы всегда найдете одну и ту же каноническую форму для любого члена этого набора.Но это только смысл теории множеств / абстрактной алгебры класса эквивалентности - это не означает, что все эквивалентные выражения находятся в одном классе эквивалентности.

Для эффективного поиска в словаре вы можете использовать хэши или сравненияна основе этого канонического представления.

Answer 3

Я бы определенно пошел с нормализацией синтаксиса.То есть, как предложил aix, преобразуйте логические значения с использованием DNF и измените порядок абстрактного синтаксического дерева таким образом, чтобы лексически наименьшие аргументы находились слева.Нормализуйте все сравнения с <и <=.Тогда два эквивалентных выражения должны иметь эквивалентные синтаксические деревья. </p>