根据穆尼克的说法重新关联

Question

I\xe2\x80\x99m 阅读 Muchnick\xe2\x80\x99s \xe2\x80\x9cAdvanced Compiler Design & Implement\xe2\x80\x9d，其中图 12.6 列出了 20 个转换规则，如果按顺序应用，这些规则会进行常量折叠和重新关联将常量移动到一起。规则（不考虑分布性规则）是（我的语法：c文字、t术语、带有空格的运算符都在源代码中，而没有空格的运算符表示涉及文字的编译时计算）：

\n\n

\nR1: c1 + c2 = c1+c2\nR3: c1 * c2 = c1*c2\nR5: c1 - c2 = c1-c2\n\nR2: t + c = c + t\nR4: t * c = c * t\nR6: t - c = (-c) + t\n\nR7: t1 + (t2 + t3) = (t1 + t2) + t3\nR8: t1 * (t2 * t3) = (t1 * t2 ) * t3 \n\nR9: (c1 + t) + c2 = (c1+c2) + t\nR10: (c1 * t) * c2 = (c1*c2) * t\n

\n\n

他写道 \xe2\x80\x9c 按照给定的 \xe2\x80\x9c 的顺序递归地应用树转换规则 [..]，但我看不出这是如何实现的。鉴于((c1 + t1) + t2) + c2，我将如何应用规则才能到达(c1+c2 + t1) + t2或类似的地方？

\n\n

（我可以想出一套不同的有效规则，但我\xe2\x80\x99d想了解书中的\xe2\x80\x99s，以防我\xe2\x80\x99m读错）。

\n

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