16

我正在寻找将真值表生成器作为个人项目编写。

这里和这里有几个基于网络的在线网站。

替代文字
(Example screenshot of an existing Truth Table Generator)

我有以下问题：

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

谁能向我提供有关解析这些任意表达式并最终评估解析表达式的提示？

4

5 回答 5

24

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

这种系统的工作方式是我们如何理解自然语言的形式化。如果我给你一句话：“这只狗，Rover，吃了他的食物。”，你要做的第一件事就是把它分解成单词和标点符号。“The”、“SPACE”、“dog”、“COMMA”、“SPACE”、“Rover”……那是“tokenizing”或“lexing”。

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

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

然后编译器有一个人类没有的第四阶段，即他们生成代表语言中描述的动作的代码。

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

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

然后编写一个分析器，查看那棵树并计算出一些东西，比如“我有多少不同的自由变量？”

然后编写一个代码生成器，生成评估真值表所需的代码。吐IL似乎有点过头了，但如果你想成为真正的爱好者，你可以。让表达式树库为您做这件事可能更容易；您可以将解析树转换为表达式树，然后将表达式树转换为委托，并评估委托。

祝你好运！

于 2009-07-05T22:34:17.117 回答
2

我认为解析器生成器太过分了。您可以使用将表达式转换为后缀并评估后缀表达式的想法（或直接从中缀表达式构建表达式树并使用它来生成真值表）来解决此问题。

于 2009-07-05T21:44:49.603 回答
1

正如 Mehrdad 提到的，您应该能够在学习词法分析器/解析器的语法的同时手动进行解析。您想要的最终结果是您给出的表达式的一些抽象语法树 (AST)。

然后，您需要构建一些输入生成器，为表达式中定义的符号创建输入组合。

然后遍历输入集，为每个输入组合生成结果，给定您在第一步中解析的规则 (AST)。

我会怎么做：

我可以想象在解析树时使用 lambda 函数来表达 AST/规则，并在解析时构建符号表，然后您可以构建输入集，将符号表解析为 lambda 表达式树，以计算结果。

于 2009-07-05T22:39:39.853 回答
1

如果您的目标是处理布尔表达式，那么解析器生成器和所有附带的机器都是浪费时间，除非您想了解它们是如何工作的（那么它们中的任何一个都可以）。

但是很容易为布尔表达式手动构建一个递归下降解析器，它计算并返回“评估”表达式的结果。这样的解析器可以在第一遍中用于确定唯一变量的数量，其中“评估”表示“每个新变量名称的计数 1”。编写一个生成器来为 N 个变量生成所有可能的真值是微不足道的；对于每组值，只需再次调用解析器并使用它来评估表达式，其中评估的意思是“根据运算符组合子表达式的值”。

你需要一个语法：

formula = disjunction ;
disjunction = conjunction 
              | disjunction "or" conjunction ;
conjunction = term 
              | conjunction "and" term ;
term = variable 
       | "not" term 
       |  "(" formula ")" ;

你的可能更复杂，但对于布尔表达式，它不可能更复杂。

对于每个语法规则，将 1 个使用全局“扫描”索引的子例程写入正在解析的字符串中：

  int disjunction()
 // returns "-1"==> "not a disjunction"
 // in mode 1:
 // returns "0" if disjunction is false
 // return  "1" if disjunction is true
 { skipblanks(); // advance scan past blanks (duh)
   temp1=conjunction();
   if (temp1==-1) return -1; // syntax error
   while (true)
     { skipblanks();
       if (matchinput("or")==false) return temp1;
       temp2= conjunction();
       if (temp2==-1) return temp1;
       temp1=temp1 or temp2;
     }
  end

  int term()
  { skipblanks();
    if (inputmatchesvariablename())
       { variablename = getvariablenamefrominput();
         if unique(variablename) then += numberofvariables;
         return lookupvariablename(variablename); // get truthtable value for name
       }
     ...
  }

您的每个解析例程都将如此复杂。严重地。

于 2009-08-22T11:57:55.027 回答
0

您可以在http://code.google.com/p/pyttgen/source/browse/#hg/src获得 pyttgen 程序的源代码它为逻辑表达式生成真值表。基于 ply 库的代码，所以非常简单:)

于 2010-05-14T20:19:25.447 回答