我期待写真值表发电机作为一个个人项目。
有几个基于网络的在线的人在这里和这里 。
(Example screenshot of an existing Truth Table Generator
)
我有以下问题:
- 我应该如何去解析般的表情:((P => Q)(Q => R))=>(P => R)
- 我应该使用一个解析器生成像ANTLR或者YACC,或使用直正则表达式?
- 有一次,我已经表达分析,我应该怎么去生成真值表? 需要表达的每个部分将被划分成其最小的部件和从左侧表中的向右重新构建的。 我将如何评价这样的事情?
任何人都可以给我提供关于这些技巧任意表达式的分析和评估,最终解析表达式?
这听起来像一个伟大的个人项目。 你会学到很多关于如何编译工作的基本组成部分。 我将跳过试图用一个解析器生成器; 如果这是你自己的熏陶,您将学习从无到有做这一切了。
顺便这种系统的工作是我们如何理解自然语言的形式化。 如果我给你一句:“狗,流浪,吃了他的食物。”,你要做的第一件事就是把它分解成字和标点符号。 “该”,“空间”,“狗”,“逗号”,“空间”,“漫游者”,......这就是“标记化”或“词法”。
你做的下一件事是分析令牌流,看句子语法是。 英语的语法是非常复杂的,但是这句话是非常简单的。 主题同位语谓宾。 这是“解析”。
一旦你知道这句话是语法,你可以分析句子真正得到意思出来。 举例来说,你可以看到有这句话的三个部分 - 主题,同位语,并在“他”的对象 - 全部指的是同一实体,即狗。 你可以弄清楚的是,狗是干什么吃的东西,食物是被吃掉的东西。 这是语义分析阶段。
编译器则有第四个阶段,人类不这样做,这是他们产生代表在语言描述的动作代码。
所以,做了这一切。 通过定义你的语言的令牌启动,定义一个基类令牌和一堆派生类为每个。 (IdentifierToken,OrToken,AndToken,ImpliesToken,RightParenToken ...)。 然后写这需要一个字符串,并返回一个IEnumerable”的方法。 这就是你的词法分析器。
其次,找出你的语言的语法是什么,写一个递归下降解析器,一个IEnumerable分解成代表在你的语言语法的实体的抽象语法树。
然后写一个分析工具,着眼于树和数字的东西出来,像“有多少不同的自由变量做我有吗?”
然后写一个代码生成吐出必要评估真值表的代码。 随地吐痰IL似乎矫枉过正,但如果你想成为真正的buff,你可以。 这可能是更容易让表达式树库为你做的; 您可以将您的分析树成一个表达式树,然后打开表达式树为代表,并评估委托。
祝好运!
我认为一个解析器发电机是矫枉过正。 你可以使用一个表达式转换为后缀和的想法评估后缀表达式 (或者直接建立一个表达式树出缀表达式,并使用产生的真值表)来解决这个问题。
作为迈赫达德提到你应该能够手卷解析在同一时间,因为它会花时间去学习词法分析器/解析器的语法。 你想要的最终结果是你被赋予了表达的一些抽象语法树(AST)。
然后,您需要建立创建表达式定义的符号的输入组合的一些输入法生成器。
然后在输入集迭代,产生每个输入组合的结果,给定的规则(AST)在第一个步骤中解析。
我会怎么做:
我能想象使用lambda函数来表示AST /为您解析树,并建立一个符号表你分析,你则可以构建输入集,解析符号表的lambda表达式树,计算结果的规则。
如果你的目标是处理布尔表达式,解析器发电机和所有的机器,与去是浪费时间,除非你想了解他们是如何工作的(那么任何人就可以了)。
但它很容易建立手工递归下降解析器布尔表达式,计算并返回“评估”表达的结果。 这样的解析器可以在第一次通过用于确定唯一变量,其中“评价”是指“对每个新的变量名couunt 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它为逻辑表达式真值表。 代码基于层库,所以它很简单:)