我目前正在研究一个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操作的组合操作时，它变得越来越困难。
有谁知道我应该如何最好地解决这个问题？
比较布尔表达式的一种方法可能是将两者都转换为disjunctive normal form (DNF)，并比较DNF。在这里，这些变量将是伯克利包过滤令牌，并且出现在两个表达式的任何一个中的相同标记（例如port 80）将需要被分配相同的变量名称。
在http://www.izyt.com/BooleanLogic/applet.php有一个有趣的外观小程序 - 遗憾的是，由于浏览器中的Java问题，我现在无法尝试。
转换为DNF可能需要指数时间 –
我很确定检测等价表达式是一个np-hard或np-complete问题，即使对于布尔表达式也是如此。这意味着要做到这一点，最佳方式基本上是建立所有可能的输入组合和结果的完整表格，然后比较表格。
也许BPF表达式以某种方式受到限制，这会改变它？我不知道，所以我假设不是。
如果您的问题很小，那可能不成问题。我做确切作为决策树设计算法的一部分。
另外，不要试图做到完美。允许一些错误的否定（相同的情况，但不会检测到的情况）。
一个简单的方法可能是做一个正常表达式评估的变体，但是评估表达式的替代表示而不是结果。对交换操作符进行排序。在评估过程中应用一些明显的简化。用一组最基本的操作符替换一个丰富的操作符集 - 例如使用de-morgans消除OR运算符。
此替代表示法形成一组等效表达式的所有成员的规范表示形式。从某种意义上说，它应该是一个等价类，它总是为该集合的任何成员找到相同的规范形式。但这只是等价类的集合论/抽象代数意义 - 并不意味着所有等价的表达式都在同一个等价类中。
对于高效字典查找，可以使用基于该规范表示的散列或比较。
我一定会去语法标准化。也就是说，就像aix所建议的那样，使用DNF转换布尔值并重新排序抽象语法树，使词汇最小的参数位于左侧。将所有比较标准化为<和< =。那么，两个等价的表达式应该有等价的语法树。
我想我们在这里需要一个更好的“等价”定义。上下文是否重要（正如'net xx.xx.xx.xx/24'相当于DNS中的net xyz'）。 –
检测变量并将它们按某种顺序放入，而不更改表达式。认识到b-a和a-b不一样。 – aartist
@Jim Garrison它应该检测两个表达式在语法上是否相同。它不会做任何dns解析，它只会考虑你的两个表达式是不同的。 – StackedCrooked