Давайте немного посмотрим строение наших деревьев при различных вводимых данных.
Как мы знаем из курсов математики
1) От перестановки мест слагаемых сумма не меняется
2) От перестановки мест множителей произведение не меняется
но меняется вид дерева... На более всего устраивает то дерево, где суммы чисел сгруппированы как на 2-й диаграмме.
Для того, что бы упорядочить дерево и сгруппировать слагаемые, мы просто при построении новой веточки будем опускать все слагаемые вниз, в итоге дерево у нас автоматически будет группировать слагаемые там где нам и надо.
Но, перед этим, что бы удобнее было работать, сделаем идентификаторы, просто симулируем так, что бы компилятор принимал идентификаторы. Для этого временно переместим поле
name из
MCB.Object_ в
MCB.Item и в процедуру
MCE.Factor добавим:
Код: "OBERON"
IF sym = MCS.lx_ident THEN BEGIN
MCB.MakeConstItem(x,MCB.noType,0);
x.name := MCS.id;
x.clas := MCB.cLit;
MCS.Get(sym);
END ELSE IF sym = MCS.lx_int ...
Как бы идентификаторы все будут у нас константами без типа. Пока мы эксперементируем нам хватит.
Я всё таки разнёс проверку типов и упрощение выражений в разные модули для удобства.
Напишем новую процедуру
MCO.Simplification; И в ней вложеные процедуры
Multiplier и
SummandКод: "OBERON"
PROCEDURE Simplification(VAR x: MCB.Item);
PROCEDURE Multiplier(VAR x: MCB.Item);
PROCEDURE Summand(VAR x: MCB.Item);
...
Они как раз и будет заниматься вышеописаным.
Давайте посмотрим дерево для выражения 1+2+3*a/b*4+5+c+6 (мы уже можем позволить псевдо-переменные
)
Мы видим, что на конечных веточках, иногда остаются непросчитываемые выражения 3*a , остаются свободные константы 5 и 6 ...
Теперь если подключить нашу функцию, то дерево будет выглядеть так
Результат как говорится на лицо.
Теперь есть возможность просчитать суммы и произведения и привести дерево к виду
Наше дерево свернулось до вида 14 + 12*a/b + с
В итоге мы получили довольно не плохой оптимизатор.
Уж на сколько реализация в нём эффективная - не мне судить, делал из собственных соображений, может быть есть алгоритмы более эффективные, если кто о них знает просьба написать!
Вход
FAQ
Поиск
, ...шутка.