Реассоциация по Мучнику

Question

Я читаю "Расширенное проектирование и реализацию компилятора" Мучника, где на рис. 12.6 перечислены 20 правил преобразования, которые, если они применяются по порядку, выполняют свертывание и повторное связывание констант для перемещения констант. Правила (без учета правил распространения): (мой синтаксис: c литералы, t термины, операторы с пробелами находятся в источнике, тогда как операторы без пробелов указывают вычисление времени компиляции с использованием литералов):

R1: c1 + c2 = c1 + c2
R3: c1 * c2 = c1 * c2
R5: c1 - c2 = c1-c2

R2: t + c = c + t
R4: т * с = с * т
R6:  t - c  = (-c) + t

R7:  t1 + (t2 + t3) = (t1 + t2) + t3
R8:  t1 * (t2 * t3) = (t1 * t2) * t3 

R9:  (c1 + t) + c2 = (c1+c2) + t
R10: (c1 * t) * c2 = (c1*c2) * t

Он пишет "рекурсивно применять правила преобразования дерева [..] в указанном порядке", но я не вижу, как это работает. Дано ((c1 + t1) + t2) + c2как бы мне применить правила, чтобы добраться до (c1+c2 + t1) + t2 или что-то подобное?

(Я мог бы придумать другой набор правил, который работал бы, но я хотел бы понять, что в книге, на случай, если я просто читаю это неправильно).

Answer 1

У меня нет книги, но я попробую. Начальное выражение:

((c1 + t1) + t2) + c2

Применить R2:

c2 + ((c1 + t1) + t2)

Рекурсивное применение правил для подвыражения справа не дает никаких совпадений. Продолжаем, применяя R7 ко всему выражению (литералы также являются терминами):

(c2 + (c1 + t1)) + t2

Рекурсия. Примените R7 к левому подвыражению.

(c2 + c1) + t1

Рекурсия. Примените R1 к левому подвыражению:

c2+c1

Конечный результат: (c2+c1 + t1) + t2