通过编程解决《离散数学》“真值表”类问题

通过编程解决《离散数学》“真值表”类问题2011-09-30 博客园邓勖帆问题引入：真值表是数理逻辑中较为常用的基本工具之一，但这东西若要人手计算还是有点麻烦，而且必须非常仔细才行。现在我们通过编写程序解决这个问题。

一、基本思路

假定表达式中字母个数为n，那么一个最自然的想法就是让i:0->2^n（取其k:0~n-1位分别作为字母 k的赋值），将{^,&,|,->,<->}中的操作符从字符形式转换成Token存储在栈中，然后程序根据栈中信息模拟运算。但这样的缺点是明显的，就是需要对表达式进行2^n次扫描；而一个基本事实是，无论i的值为多少，表达式的结构总是相同的。因此首先可以考虑的优化是将表达式缓存为表达式树，那么运算时就根据表达式树进行栈的生成。

但既便如此，根据表达式树生成栈作为中间状态存储并且进行模拟运算的过程中还是做了大量无谓的判断（例如Token的判断、优先级的判断等）和跳转。干脆狠下心来，不走“解释-模拟运算”的路线，我们直接把表达式编译出来。

二、第一次扫描（1st-Pass）：清理空白字符、语法检查、符号表的建立

为了减少后续操作的复杂度的同时减少意外情况的发生可能，我们先对表达式进行第一次扫描：清除空白字符、检查语法并建立符号表。下面是语法规则的描述：

若S是合法的，则（S）、^S是合法的

若S1,S2是合法的，则S1&S2、S1|S2、S1->S2、S1<->S2是合法的

若S以{a~z,A~Z,_,0~9}中的元素经过有限次连接而成且S不以数字作为起始，则S是合法的

只有有限次地应用（1）~（3）形成的符号串才是合法的表达式

三、第二次扫描（2nd-Pass）：联结词的运算表达、运算符优先级的确定、机器码的生成

这里我重点讲机器码的生成部分。

^、&、|在机器指令中分别以NOT、AND及OR对应，而->、和<->则没有相应的指令。不过我们知道{^,&,|}也是一个完备集，因此以{^,&,|}表示{->,<->}就可以了。我们不准备使用“在程序中生成汇编代码然后交由第三方编译器（如MASM）编译成机器代码”的方法，而是做成一个JIT引擎，将机器码直接写入内存并执行。（这样更加好玩嘛~）那么一个问题就是，怎么得知这些指令的代码字节呢？（也就是说，如“NOT EAX”这条指令对应的二进制或者16进制值为多少）有三个方法解决这个问题：查Intel的CPU指令手册、自己到C/C++中写一段小代码编译出来然后将其反编译检查其代码字节，或者——我们知道，CPU指令对应的字节序列是有一定规律的，如果知道这个规律，我们就可以用填表法将其填写出来了。下面举几个例子：

NOT EAX：0xF7,0xD1

AND EAX,1：0x83,0xE0,0x01