我用 C 语言设计了一个能够生成 AST 的解析器，但是当我开始实现简化时，它真的搞砸了。我已经成功实施了以下汇总规则；
x + 0 -> x
x + x -> 2 * x
等等
但它需要大量的努力和代码来做到这一点。我所做的是搜索整个树并尝试找到我可以使用的模式（大量递归）然后如果有级联的 PLUS 节点，我将它们添加到列表中，然后在该列表上工作（求和数字并组合变量等）然后我从该列表中创建了另一棵树，并将其合并到现有的树中。这是我用来实现它的这篇论文。简而言之，鉴于2*x+1+1+x+0我得到的表达3*x+2。只是总结让我陷入了如此多的麻烦，我什至可以想象高级的东西。所以我意识到我错了。
我读过这个线程，但我真的对术语重写系统感到困惑（它到底是什么，如何在 C 中实现）。
有没有更通用和有效的方法来简化 AST？或者如何用 C 编写一个术语重写系统
术语重写（简单来说）就像您提供的 2 个示例一样。（如何转换x + 0为xAST？）。它是关于 AST 上的模式匹配，一旦匹配，等效表达式的转换。它也称为术语重写规则。
请注意，具有项重写规则不是代数简化的绝对或一般解决方案。一般的解决方案包括有许多重写规则（你展示了其中的两个），并在给定的 AST 中重复应用它们，直到没有一个成功。
然后，一般的解决方案涉及重写规则应用的过程或协调。例如，为了避免重新应用以前失败的规则。
没有一种独特的方法可以做到这一点。有几个系统。对于专有系统，它不为人所知，因为它们保密，但也有开源系统，例如Mathomatica是用 C 编写的。
我建议您检查开放系统Fōrmulæ。在这方面，重写规则（称为“归约引擎”）的协调过程相对简单。它是用 Java 编写的。该系统的优点是重写规则不是在系统或归约引擎中硬连线/硬编码（它们是可热插拔的）。编写重写规则涉及模式匹配和转换的过程，但不知道何时或如何调用它（它遵循好莱坞原则）。
在Fōrmulæ的具体情况下：
归约引擎（一般而言）基于后序树遍历算法。所以当一个节点被“访问”时，它的子节点已经被访问过并且（可能）被转换了，但是可以改变这样的流程（即解决分配中不需要的变量引用x <- 5）。请注意，这不仅仅是一个树遍历，AST 在此过程中实际上正在更改。
为了有效地管理（可能成百上千的）重写规则，每个规则都有一种适用的表达式类型，并且当“访问”单个节点时，仅检查关联的规则是否匹配。例如，您的 2 条规则只能应用于 AST 的“添加”节点。
重写规则不仅限于代数简化，它们还可以用于许多其他领域，例如编程（Fōrmulæ也是它的编程语言，请参阅Fōrmulæ 程序示例，或用于自动或辅助定理证明。