optimization - 根据穆奇尼克的重新关联

Question

我正在阅读 Muchnick 的“高级编译器设计与实现”，其中图 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:t * c = c * t
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