A 有一个用 yacc 编写的简单语法，它从逻辑表达式构建一棵树，由子表达式以及 AND (&&)、OR (||) 和 NOT (!) 运算符组成。我不会在这里提供语法本身，因为它没有什么特别的，它与无数的 YACC 教程示例类似。
但是，我需要解析这些逻辑表达式，以便根据德摩根定律为 NOT 运算符扩展所有括号。例如，我需要处理表达式
!( ( A && B ) || C ) )
作为
( !A || !B ) && !C
是否可以通过修改现有的 yacc 语法来实现？
最佳答案
在构建 AST 时，可以在 YACC 对 not (!) 运算符的归约操作中执行此操作。您可以在语义操作中编写任何您想要的代码。您可以编写检查子节点以查看是否具有需要形状，如果是这样，则构造每个形状的德摩根等效树。执行此操作的代码有点困惑，因为它必须在树上爬上爬下，匹配节点并重新排列子树，但这只是令人讨厌而且还不错。请注意，德摩根定律可以说适用于形状都类似于 ( A && B ) || 的 child 。 C ) 和 ( A || B && C))，所以你要处理两个主要的子情况。
我同意莱恩的观点；您通常不会在解析器中执行此操作。它的目的是让您为更复杂的事件做好准备，除非 DeMorganizing 是唯一的目的，否则您将需要其他代码来在解析完成后以各种方式处理 AST，所以为什么不将所有处理留到那里呢？
按照这个想法，我的 recent SO answer on eliminating configured-dead code简化符号 bool 逻辑；它展示了一种使用模式匹配源到源转换来转换 bool 逻辑 AST 的方法。这种方法避免了令人讨厌的树检查/黑客代码。如何使用该技术编写可读变换来实现德摩根定律应该是显而易见的(事实上我们过去已经这样做过)。
关于parsing - 德摩根定律与 yacc，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10515272/