有没有 C/C++允许您找出一组表达式是否互斥的库?

发布于 2024-09-16 09:29:00 字数 417 浏览 13 评论 0原文

我正在为我设计的数据流编程语言编写编译器。我真正喜欢它的功能之一是您可以表达以下内容:

x <- a + 1 if b > 3;

如果 b <= 3,则 x <- a - 1;

这意味着:

x <- a - 1 + 2*(b>3);

为了实现这一点,编译器需要知道:

((b > 3) && (b <= 3)) = false

((b > 3) || (b <= 3) )) = true

是否有任何人都知道的 C/C++ 库能够验证这两个语句(以及更复杂的语句)?或者是否有任何人可以通过网络获得有关类似系统详细信息的论文?或者有人可以描述一种可能的方法吗?

谢谢,

丹尼尔

I'm writing a compiler for a dataflow programming language I have designed. One of the features that I really like about it is that you can express the following:

x <- a + 1 if b > 3;

x <- a - 1 if b <= 3;

Which implies something like:

x <- a - 1 + 2*(b>3);

In order to pull this off though the compiler needs to know that:

((b > 3) && (b <= 3)) = false

((b > 3) || (b <= 3)) = true

Are there any C/C++ libraries that anyone knows of that would be able to validate these 2 statements (as well as much more complicated ones)? Or are there any papers available via the web that anyone knows of that detail a similar system? Or could someone describe a possible approach?

Thanks,

Daniel

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

落日海湾 2024-09-23 09:29:00

我认为您需要一小组简单的规则来告诉您两个表达式是否相等或完全不同。

让我们从最简单的开始:b>3 和 b<=3

检查它们是否相等很容易:b>3b>3 相等,b>3b<=3 显然不是。

要查看它们是否完全不同,我们必须比较 b>3NOT (b<=3)。通过简单地在其前面添加 NOT,我们将“不同”比较更改为“相等”比较。

您的软件现在应该具有将 NOT (b<=3) 转换为 (b>3) 的逻辑。由于它们完全相等,因此原始的也完全不同。

如果比较比较困难,您应该开始使用摩根定律。该定律规定以下表达式是相等的:

NOT (A AND B) is equal to NOT A OR NOT B
NOT (A OR B) is equal to NOT A AND NOT B

现在结合这两个规则:

  • 将 NOT 放在表达式之一前面
  • 使用摩根定律将 NOT 分配给表达式的最基本部分。
  • 然后比较所有元素,

例如假设我们想知道以下表达式是否完全不同:

(a<3) and not (b>=7)
(b>=7) or (a>=3)

首先在第二个表达式之前放置一个大的 NOT:

NOT ((b>=7) or (a>=3))

然后分发 NOT:

(NOT (b>=7)) and (NOT (a>=3))

现在使用第一个规则从两个表达式中删除 NOT:

(a<3) and (b<7)
(b<7) and (a<3)

然后在两个表达式之间找到相同的元素。在这种情况下,第一个表达式中的所有元素都可以在第二个表达式中找到,反之亦然。这意味着原始表达是完全不同的。

I think you need a small set of simple rules that tell you whether two expressions are equal, or are totally different.

Let's start with the easiest ones: b>3 and b<=3

Checking whether they're equal is easy: b>3 and b>3 are equal, b>3 and b<=3 clearly aren't.

To see whether they are completely different, we would have to compare b>3 and NOT (b<=3). By simply adding the NOT in front of it, we changed the "distinct" to an "equal" comparison.

Your software should now have the logic to transform NOT (b<=3) to (b>3). And since these are completely equal, the original ones are completely distinct.

If the comparisons are more difficult, you should start to use Morgans Law. This law states that the following expressions are equal:

NOT (A AND B) is equal to NOT A OR NOT B
NOT (A OR B) is equal to NOT A AND NOT B

Now combine both rules:

  • Put NOT in front of one of the expressions
  • Distribute NOT to the most elemental parts of the expression using Morgans law.
  • Then compare all the elements

e.g. suppose we want to know if the following expressions are completely distinct:

(a<3) and not (b>=7)
(b>=7) or (a>=3)

First put a big NOT before the second one:

NOT ((b>=7) or (a>=3))

Then distribute the NOT:

(NOT (b>=7)) and (NOT (a>=3))

Now remove the NOTS from both expressions using the first rule:

(a<3) and (b<7)
(b<7) and (a<3)

Then find the same elements between the two expressions. In this case all the elements from the first expression can be found in the second one and vice versa. This means that the original expressions are completely distinct.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文