Y at-il une bibliothèque C/C++ qui vous permet de savoir si un ensemble d'expressions s'excluent mutuellement?

Question

J'écris un compilateur pour un langage de programmation de flux de données que j'ai conçu. L'une des caractéristiques que j'aime vraiment à ce sujet est que vous pouvez exprimer ce qui suit:

x < - a + 1 si b> 3;

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

Ce qui implique quelque chose comme:

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

Pour retirer ceci bien que le compilateur a besoin de savoir que:

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

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

Y a-t-il des bibliothèques C/C++ connues de tous qui pourraient valider ces 2 instructions (ainsi que des plus compliquées)? Ou y a-t-il des documents disponibles sur le Web que quelqu'un connaît de ce système de détail? Ou pourrait-on décrire une approche possible?

Merci,

Daniel

Answer 1

Je pense que vous avez besoin d'un petit ensemble de règles simples qui vous indiquent si deux expressions sont égales ou sont totalement différents.

Commençons par les plus faciles: b> 3 et b = 3 <

Vérifier si elles sont égales est facile: b>3 et b>3 sont égaux, et b>3b<=3 ne sont manifestement pas. Pour voir s'ils sont complètement différents, il faudrait comparer b>3 et NOT (b<=3). En ajoutant simplement le NOT devant, nous avons changé le "distinct" en une comparaison "égale". Votre logiciel devrait maintenant avoir la logique pour transformer NOT (b<=3) en (b>3). Et puisque ceux-ci sont complètement égaux, les originaux sont complètement distincts.

Si les comparaisons sont plus difficiles, vous devriez commencer à utiliser la loi de Morgans. Cette loi stipule que les expressions suivantes sont égales:

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

maintenant combiner les deux règles:

• met pas en face de l'une des expressions
• distribue pas aux parties les plus élémentaires de l'expression en utilisant la loi de Morgans.
• Ensuite, comparez tous les éléments

par exemplesupposons que nous voulons savoir si les expressions suivantes sont complètement distinctes:

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

d'abord mis un grand pas avant la seconde:

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

redistribuent le PAS:

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

maintenant supprimer les NOTS des deux expressions en utilisant la première règle:

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

Ensuite, trouvez les mêmes éléments entre les deux expressions. Dans ce cas, tous les éléments de la première expression peuvent être trouvés dans le second et vice versa. Cela signifie que les expressions originales sont complètement distinctes.