c# - 如何构建真值表生成器？

Question

我希望将真值表生成器编写为个人项目。

有几个基于网络的在线的here和 here .

(现有真值表生成器的示例屏幕截图)

我有以下问题:

• 我应该如何解析如下表达式:((P => Q) & (Q => R)) => (P => R)
• 我应该使用像 ANTLr 或 YACC 这样的解析器生成器，还是直接使用正则表达式？
• 一旦我解析了表达式，我应该如何生成真值表？表达式的每个部分都需要分成最小的部分，并从表的左侧到右侧重新构建。我会如何评价这样的事情？

任何人都可以向我提供有关解析这些任意表达式并最终评估已解析表达式的提示吗？

Answer 1

这听起来像是一个很棒的个人项目。您将学到很多关于编译器的基本部分如何工作的知识。我会跳过尝试使用解析器生成器；如果这是为了您自己的启蒙，那么您将从头开始学习更多知识。

此类系统的工作方式是我们理解自然语言方式的形式化。如果我给你一个句子:“The dog, Rover, ate his food.”，你做的第一件事就是把它分解成单词和标点符号。 “The”、“SPACE”、“dog”、“COMMA”、“SPACE”、“Rover”……这就是“分词”或“词法分析”。

接下来您要做的是分析标记流，看看句子是否合乎语法。英语的语法非常复杂，但这句话却很简单。主语-同位-动词-宾语。这就是“解析”。

一旦您知道该句子是合乎语法的，您就可以分析该句子以真正了解其含义。例如，您可以看到这句话的三个部分——主语、同位语和宾语中的“他的”——都指代同一个实体，即狗。你可以看出狗是吃东西的东西，食物是被吃的东西。这是语义分析阶段。

然后，编译器进行了人类没有的第四阶段，即它们生成表示语言中描述的操作的代码。

所以，做所有这些。首先定义您的语言的标记是什么，为每个标记定义一个基类 Token 和一堆派生类。 (IdentifierToken、OrToken、AndToken、ImpliesToken、RightParenToken...)。然后编写一个方法，该方法接受一个字符串并返回一个 IEnumerable'。那是你的词法分析器。

其次，弄清楚你的语言的语法是什么，并编写一个递归下降解析器，将 IEnumerable 分解为代表你的语言中的语法实体的抽象语法树。

然后编写一个分析器来查看该树并计算出内容，例如“我有多少个不同的自由变量？”

然后编写一个代码生成器，生成评估真值表所需的代码。 Spitting IL 似乎有点矫枉过正，但如果你想成为真正的 buff，你可以。让表达式树库为您做这件事可能会更容易；您可以将解析树转换为表达式树，然后将表达式树转换为委托(delegate)，并对委托(delegate)求值。

祝你好运!