将非标准格式解析为Java中的标准格式 [英] Parse non standard form to standard form in java

问题描述

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

I want to write a Java parser that converts a non-standard form (NSF) Boolean function into a standard form (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

To get a NSF to a SF, you must multiply out the brackets. SF from the above function is seen like this: A*B + D*A*C + D*B*C + A*B*A*B'*D + A*B*A*D + A*B*B*D

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

Does anyone have any idea how can I implement this?

谢谢

推荐答案

您必须完成4个步骤才能实现自己的目的:

You have to do 4 steps to achieve your purpose:

1)使用标准"(与您的术语无关)解析技术来解析表达式，并产生等于表示(解析的)表达式的布尔表达式树的值.

1) parse the expression using "standard" (unrelated to your terminology) parsing techniques and produce what amounts to a boolean expression tree representing the (parsed) expression.

2)将布尔代数规则应用于表达式树，以将其从不需要的表示形式转换为您需要的表示形式.您的标准格式"似乎是合取范式(CNF)，因此您需要分配定律代数规则，以将乘积"乘积求和(例如a *(b + c))，以摆脱括号"

2) apply boolean algebra rules to the expression tree, to convert it from the representation you don't want, to the one you do. Your "standard form" appears to be conjunctive normal form (CNF), so you need distributive law algebra rules to "multiply out" products over sums (e.g., a*(b+c)), to "get rid of parentheses"

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

3) You then need to apply some simplification rules (e.g., subsumption, cancellation) to get rid of excess terms, e.g., a*b + a*b+c ==> a*b [a*b*c subsumed], and a*b*a'+b*c ==> b*c [a*..a' cancels out]. This is just more algebra rules.

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

4) PrettyPrint the resulting algebra term in a human readable format.

您可以通过以下方式编写所有这些信息:A)临时手动编码的递归下降分析以及临时规则应用程序和prettyprinting，或者B)您可以使用解析器生成器(ANTLR很好)进行解析，并进行规则处理通过临时方法，以及使用字符串模板或C之类的一些帮助的prettyprint，您可以得到一个工具，该工具可以进行语法分析，构建树，应用您定义的代数规则并内置有prettyprinting.

You can write all this by A) ad hoc hand coded recursive descent parsing and ad hoc rule application and prettyprinting, or B) you can get a parser generator (ANTLR is nice) to do the parsing, and do the rule manipulation by ad hoc methods, and prettyprint using some help like string templates, or C) you could get a tool that does parsing, builds trees, will apply algebra rules you define, and has prettyprinting built in.

我们的 DMS软件再造工具包可以很好地处理案例C.您可以看到一个应用与您的直接代数相似的标准代数规则的示例问题.

Our DMS Software Reengineering Toolkit can do case C nicely. You can see an example of applying standard algebra rules that is a direct analog to your problem.

真正难以解决的问题之一是在代数中处理关联性和可交换性，例如，知道A * B * A'为"false"是代数规则X * X'=>的结果否，但是您不能只直接检查代数规则中的模式.您必须应用考虑交换性的代数规则.关联性的论点相同.如果您声明适当的运算符具有这些属性，DMS可以很好地完成其中一项工作.您可以在示例中看到这一点.

One of the issues that is really hard to get right is handling associativity and commutativity in the algebra, e.g., knowing that A*B*A' is "false" is a consequence of the algebra rule X*X'=> false, but you can't just check for the pattern in the algebra rule directly. You have to apply the algebra rules accounting for commutivity. Same argument for associativity. One of the things that DMS does nicely is handle that for you, if you declare the appropriate operators to have those properties. You can see this in the example.

A，不是用Java编写的代码.

Alas, not coded in Java.

这篇关于将非标准格式解析为Java中的标准格式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！