德摩根定律与yacc

Question

有一个用yacc编写的简单语法，它从逻辑表达式构建一个树，由子表达式、and (&&)、OR (||)和NOT (!)运算符。我不会在这里提供语法本身，因为它没有什么特别之处，而且它类似于无数的YACC教程示例。

但是，我需要解析这些逻辑表达式，以便根据德摩根定律扩展NOT运算符的所有括号。例如，我需要处理表达式

!( ( A && B ) || C ) ) 

作为

( !A || !B ) && !C

是否可以通过修改现有的yacc语法来实现这一点？

Answer 1

可以在YACC的而不是 (!)的reduction操作中做到这一点。运算符，同时构建AST。您可以在语义操作中编写任何您想要的代码。您可以编写代码来检查子节点是否具有所需的形状，如果具有所需的形状，则可以编写代码来检查每个子节点是否具有所需的形状，如果具有所需的形状，则构建每个子节点的de 等效树，而不是“盲目”地从它的子节点组装的树节点(您可以在此类缩减操作中找到常见代码)。这样做的代码有点凌乱，因为它必须在树上爬上爬下，匹配节点和重新排列子树，但它就是讨厌，而且还不错。请注意，德摩根定律可能适用于形状类似于(A&B) || C)和(A || B& C))的孩子，因此您需要处理两个主要的子案例。

我同意Len的观点；在解析器中通常不会这样做。它的目的是让您为更复杂的活动做好准备，除非DeMorganizing是唯一的目的，否则在解析完成后，您将需要其他代码来处理各种was中的AST，所以为什么不把所有的处理留到那里呢？

遵循这一思想，我的recent SO answer on eliminating configured-dead code简化了符号布尔逻辑；它展示了一种使用模式匹配的源到源转换来转换布尔逻辑AST的方法。这种方法避免了令人讨厌的树检查/黑客代码。应该很明显的是，如何编写可读的转换，用这种技术来实现德摩根定律(实际上我们在过去已经完成了son )。

Answer 2

这不是在yacc语法本身中应该做的事情；您应该对语法构造的AST进行后处理，以执行这样的缩减。

您的语法应该生成某种类型的AST -您希望遍历结构，查找与!((A && B)|| C)形状匹配的内容，并将其就地转换为(!A || !B) && C。

如果您需要更多指导，添加更多信息或询问更多问题可能会很有用。

编辑：如果你需要任何帮助，你应该提供你的语法。这听起来像是一个家庭作业，所以我希望这不是您不提供代码的唯一原因。帮助我们帮助你。我们不知道你在语法中做了什么，所以我们怎么能猜测我们能为你做些什么呢？