如何构建真值表生成器？

StackOverflow https://stackoverflow.com/questions/1084873

题

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

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

alt text
(Example screenshot of an existing Truth Table Generator)

我有以下问题：

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

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

有帮助吗？

解决方案

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

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

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

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

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

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

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

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

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

祝你好运！

其他提示

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

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

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

然后，根据您在第一步中解析的规则 (AST)，迭代输入集，生成每个输入组合的结果。

我会怎么做：

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

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

但是，很容易为布尔表达式手动构建递归下降解析器，该解析器计算并返回“评估”表达式的结果。这样的解析器可以在第一遍中使用来确定唯一变量的数量，其中“评估”意味着“每个新变量名称计数 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
       }
     ...
  }

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top