ExpressionUnification.md

Expression Unification

Overview

This transformation standardizes binary expressions with commutative integer operands.

To standardize the binary expression we can swap operands using special rule.

Restrictions

We need to transform the expression saving its meaning. So we are using only integer operands and commutative operators.

• operands are only integer
• operators are only [*, +, |, &, ^]

Algorithm

Recursively unify operands of binary expression.

Base case. Binary expression in the form of lhs (*+|&^) rhs swap lhs and rhs if lhs < rhs lexicographically.

Then after these binary expression transformations we need to correct the expression associativity. The swap operations can ruin the left operator associativity, so we have to collect all incorrect associativity vertices and recreate the subtree with left associativity.

Examples

Before:

3 * x * 2 * 1

After:

1 * 2 * 3 * x

---

Before:

'h' + (4 + 9 * 1)

After:

'h' + (1 * 9 + 4)

---

Before (a, b, c can be inferred as integer):

c + a + b

After:

a + b + c