java - 检测等效表达式

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

比较 boolean 表达式的一种方法可能是将两者都转换为 disjunctive normal form (DNF) ，并比较DNF。此处，变量将是 Berkeley Packet Filter token ，并且需要为出现在两个表达式中任意位置的相同 token (例如 port 80)分配相同的变量名称。

在http://www.izyt.com/BooleanLogic/applet.php 有一个看起来很有趣的小程序。 - 遗憾的是，由于浏览器中的 Java 问题，我现在无法尝试。