Существует ли библиотека C / C ++, которая позволяет выяснить, являются ли набор выражений взаимоисключающими? - PullRequest
Новая
       30

Существует ли библиотека C / C ++, которая позволяет выяснить, являются ли набор выражений взаимоисключающими?

4 голосов
/ 27 августа 2010

Я пишу компилятор для языка программирования потока данных, который я разработал. Одна из особенностей, которая мне действительно нравится в этом, заключается в том, что вы можете выразить следующее:

x <- a + 1, если b> 3;

x <- a - 1, если b <= 3; </p>

Что подразумевает что-то вроде:

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

Чтобы осуществить это, хотя компилятор должен знать, что:

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

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

Существуют ли какие-либо библиотеки C / C ++, о которых кто-либо знает, которые могли бы проверить эти 2 утверждения (а также гораздо более сложные)? Или есть какие-либо документы, доступные через Интернет, которые кто-нибудь знает об этой детали подобной системы? Или кто-то может описать возможный подход?

Спасибо

Daniel

1 Ответ

3 голосов
/ 27 августа 2010

Я думаю, вам нужен небольшой набор простых правил, которые сообщают вам, равны ли два выражения или они совершенно разные.

Давайте начнем с самых простых: b> 3 и b <= 3 </p>

Проверить, равны ли они, легко: b>3 и b>3 равны, b>3 и b<=3 явно не равны.

Чтобы увидеть, являются ли они совершенно разными, нам нужно сравнить b>3 и NOT (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 перед одним из выражений
  • Распределите НЕ по самым элементарным частям выражения, используя закон Моргана.
  • Затем сравните все элементы

например. Предположим, мы хотим знать, являются ли следующие выражения совершенно разными: 

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

Сначала поставьте большое НЕ перед вторым: 

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

Затем распределите НЕ: 

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

Теперь удалите NOTS из обоих выражений, используя первое правило: 

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

Затем найдите одинаковые элементы между двумя выражениями. В этом случае все элементы из первого выражения могут быть найдены во втором и наоборот. Это означает, что исходные выражения полностью различны.

...