На самом деле вам нужно построить Абстрактное синтаксическое дерево (AST) .
Это представление исходного кода в виде дерева, с которым гораздо проще работать, особенно для преобразования и оптимизации.
Этот код, представленный в виде дерева, будет выглядеть примерно так:
(+
(+
x
(U f))
(+
(V f)
y))
Затем вы можете попытаться сделать некоторые преобразования: сумма сумм - это сумма всех слагаемых:
(+
x
(U f)
(V f)
y)
Тогда вы можете сканировать дерево и иметь следующие правила:
- (+ (U x) (V x)) = 0, для всех x
- (+ 0 x1 x2 ...) = x, для всех x1, x2, ...
Тогда вы получите то, что ищете:
(+ x y)
В любой хорошей книге по написанию компиляторов будет много обсуждаться об AST. Функциональные языки программирования особенно подходят для этой задачи, поскольку в общем случае легко представлять деревья и сопоставлять шаблоны для анализа и преобразования дерева.
Обычно для этой задачи следует избегать использования регулярных выражений . Регулярные выражения определяют то, что математики называют регулярными языками . Любой обычный язык может быть проанализирован с помощью набора регулярных выражений. Тем не менее, я думаю, что ваш язык не является регулярным, поэтому он не может быть правильно проанализирован регулярным выражением.
Люди пытаются, и пытаются, и пытаются анализировать такие языки, как HTML, используя регулярные выражения. Это подробно обсуждалось здесь в SO, и вы не можете анализировать HTML с помощью регулярных выражений. Всегда будет исключительный случай, когда ваши регулярные выражения потерпят неудачу, и вам придется его адаптировать.
С вашим языком может быть то же самое: если он не регулярный, вам следует избегать множества головных болей и не пытаться его анализировать (и особенно "преобразовывать") с помощью регулярных выражений.