java - 在java中将非标准形式解析为标准形式

Question

我想编写一个 Java 解析器，将非标准形式 (NSF) boolean 函数转换为标准形式 (SF)。

NSF 示例:

A * B + D (A + B) C + A * B (A * B '+ A + B) D

要将 NSF 转换为 SF，您必须将括号相乘。上面函数的 SF 是这样的: A*B + D*A*C + D*B*C + A*B*A*B'*D + A*B*A*D + A* B*B*D

有人知道我该如何实现吗？

谢谢

Answer 1

您必须执行 4 个步骤才能实现您的目的:

1) 使用“标准”(与您的术语无关)解析技术解析表达式，并生成代表(解析的)表达式的 boolean 表达式树。

2) 将 boolean 代数规则应用于表达式树，将其从您不想要的表示形式转换为您想要的表示形式。你的“标准形式”似乎是合取范式(CNF)，所以你需要分配律代数规则来“乘以”产品总和(例如，a *(b + c))，“摆脱括号”

3) 然后，您需要应用一些简化规则(例如，包含、取消)来去除多余的项，例如，a*b + a*b+c ==> a*b [a*b*c包含]，并且 a*b*a'+b*c ==> b*c [a*..a' 抵消了]。这只是更多的代数规则。

4) PrettyPrint 以人类可读格式生成的代数项。

你可以通过 A) ad hoc 手工编码的递归下降解析和 ad hoc 规则应用和 pretty-print 来编写所有这些，或者 B) 你可以得到一个解析器生成器(ANTLR 很好)来进行解析，并进行规则操作通过临时方法，并使用字符串模板或 C 等帮助的 pretty-print ，您可以获得一个进行解析、构建树、将应用您定义的代数规则并内置 pretty-print 的工具。

我们的 DMS Software Reengineering Toolkit可以很好地完成案例 C。你可以看到一个 example of applying standard algebra rules that is a direct analog to your problem .

真正难以解决的问题之一是处理代数中的结合性和交换性，例如，知道 A*B*A' 为“假”是代数规则 X*X'=> 的结果false，但您不能直接检查代数规则中的模式。您必须应用计算交换性的代数规则。关联性的相同论点。如果您声明适当的运算符具有这些属性，DMS 擅长的一件事就是为您处理。您可以在示例中看到这一点。

唉，不是用 Java 编码的。