parsing - yacc 的德摩根定律

Question

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

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

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

作为

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

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

Answer 1

在构建 AST 时，可以在 YACC 的not (!) 运算符的归约操作中执行此操作。您可以在语义操作中编写任何您想要的代码。您可以编写代码检查子节点是否具有所需的形状，如果是，则可以编写代码来检查子节点，而不是“盲目地”组装树节点而不是来自其子节点（您会在此类缩减操作中找到的常用代码），构造每个的德摩根等效树。执行此操作的代码有点混乱，因为它必须在树上爬上爬下，匹配节点并重新排列子树，但它只是很糟糕而且还不错。请注意，德摩根定律可以说适用于形状都像 ( A && B ) || C ) 和 ( A || B && C))，所以你要处理两个主要的子情况。

我同意伦的观点；您通常不会在解析器中执行此操作。它的目的是让您为更复杂的活动进行设置，除非 DeMorganizing 是唯一目的，否则在解析完成后您将需要其他代码来处理各种不同的 AST，那么为什么不将所有处理留到那里呢？

按照这个想法，我最近关于消除配置死代码的 SO 答案简化了符号布尔逻辑；它展示了一种使用模式匹配源到源转换来转换布尔逻辑 AST 的方法。这种方法避免了讨厌的树检查/黑客代码。如何使用该技术编写实现德摩根定律的可读转换应该是显而易见的（事实上我们过去曾做过儿子）。

Answer 2

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

你的语法应该产生某种形式的AST——你想遍历结构并寻找与形状匹配的东西!((A && B)|| C)并将其就地转换为(!A || !B) && C.

如果您需要有关此方面的更多指导，添加更多信息或提出更多问题可能会很有用。

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