呵呵，我又来了~~
看看上次写编译原理学习日记的日期，2月2日。汗~~~已经一个月了……不过，这一个月我可没闲着。我真没想到，做这么一个小玩意居然也要很多数学知识，可能是我想把它做的完善些，为它添加了很多三角函数指令。可是，C标准库里的数学运算函数十分有限，因此，我不得不用一些数学方法来用有限的这些函数实现所有期望的运算。而我的学习……
不过幸运的是，在好多哥们的鼓励和一些热情的高手的指点下，我现在已经学会了这些数学方法，也完成了这个虚拟机！
首先，我对指令系统进行了完善，主要是添加了很多三角函数指令，尤其是双曲函数。还有，我修改了操作数和指令的数据类型，通过使用typedef语句，我将操作数类型声明为double、将指令类型声明为unsigned char。这主要体现在inst.h的改动中，我在其中添加了如下声明：
/* type of instructions: */
typedef unsigned char inst_t;
/* type of operands: */
typedef double operand_t;
这使得我的程序更具伸缩性。当然，这些改动使得我同时改动了汇编编译器和反汇编编译器。如果大家真的感兴趣，而且需要“新版”的计算器，呵呵，老规矩，给我发邮件，我悄悄地告诉你。
另外还有一件值得高兴的事我要在这里说，我的大学英语四级（国家）考试居然过了！我还是上上次（非典刚过，9月份那次）考的试，都没指望了，也没查过分，而且上次（大概是1月份的吧）都没报名。前两天居然接到通知，60.5！哈哈哈~~~
好了，这也不是什么光彩的事，不过觉得很有意思而已。我这种人四级居然能过，中国的教育……
现在就说说我这个虚拟的计算器的实现吧。程序方面没什么新鲜的，主要是一些想法和其中的数学原理。
首先，以前已经说过，这个计算器是基于堆栈的。不过，我没有在其中使用任何显式的堆栈数据结构，也没有特地为此建立函数库。原因很简单——效率。我在程序中声明了一个全局数组opStack，类型为operand_t，作为运算栈；以及一个全局变量opSP，类型为unsigned int，作为堆栈指针。堆栈指针的初值为零（因为使用了无符号整型），这可能与一些用数组实现堆栈的程序不太一样；这样，出栈操作类似于：
operand_t operand = opStack[--opSp];
而入栈操作类似于：
opStack[opSp++] = operand;
也就是说，我的堆栈指针并未指向栈顶元素，而是指向了栈顶元素上面的位置。不过，我在程序中并没有使用这样的操作，稍后将作说明。
由于使用了固定大小的运算栈，对堆栈的空满状态的检查就显得尤为重要。因为几乎所有的指令都要涉及到出入栈操作，因此，我为栈状态的检查编写了两个宏：
/* check the stack status(overflow): */
#define check_overflow() \
if(opSp >= MAX_STACK_SIZE - 1) { \
fprintf(stderr, "Operate stack overflow!\n"); \
exit(0); \
}
/* check the stack statuc(underflow)
* n means how many operands are required:
*/
#define check_underflow(n) \
if(opSp <= n - 1) { \
fprintf(stderr, "Operate stack underflow!\n"); \
exit(0); \
}
其中，check_overflow()用于检查运算栈是否上溢出，用于所有入栈操作之前；check_underflow()用于检查运算栈是否下溢出，用于所有出栈操作之前。由于所有的指令最多只会将一个操作数压入堆栈，check_overflow()宏是没有参数的，只要检查运算栈中是否有一个空位即可；但是，有的指令需要弹出一个操作数，有的需要两个，所以我为check_underflow()宏添加了一个参数，用来表示需要的检查的最小空间。下面的示意图显示了堆栈的结构和堆栈指针在不同情况下的位置，可以帮助你理解如果获取栈顶操作数（后面会遇到）以及上、下溢出检查的依据。
在这里，我使用了宏。这是因为检查堆栈状态的代码很短，不值得编写一个函数；而几乎执行每一条指令时都要对堆栈进行检查，所以又不好将他们写到每条指令的执行体中。
现在来看看具体的实现，也就是指令的处理代码。指令的处理集中在一个while循环中，每次循环读出一条指令，然后在一个巨大的switch分支语句中进行判断和处理。现在介绍几个比较有代表性的语句的处理，看看出栈和入栈操作是如何体现的。
首先是DUP指令，该指令用于复制栈顶操作数，并将一个副本压入运算栈。
case DUP:
check_overflow();
check_underflow(1);
opStack[opSp] = opStack[opSp - 1];
opSp++;
break;
这条指令同时涉及了出栈和入栈操作，其逻辑上的执行顺序为：出栈一个操作数->压入堆栈->压入堆栈。但稍加分析（见下面的运算栈状态示意图）即可知道：该指令的执行结果为堆栈内的操作数数量加一，原栈顶操作数不变，但已不再是栈顶操作数，新的栈顶操作数等于原栈顶操作数。因此，我们只要简单地将原栈顶操作数复制到栈顶的上一个空间中，并将堆栈指针加一即可。也就是opStack[opSp] = opStack[opSp - 1]。注意，opStack[opSp - 1]是原栈顶操作数（因为堆栈指针基-0的缘故）。
再看一个ADD指令，该指令从运算栈中弹出两个操作数，求和后将结果压入运算栈。他的逻辑执行顺序为：出栈第二个个操作数->出栈地一个操作数->计算两个操作数之和->将结果压入运算栈。
case ADD:
check_underflow(2);
opStack[opSp - 2] += opStack[opSp - 1];
opSp -= 1;
break;
原则上，由于这条指令同时涉及了出栈和入栈操作，应当同时进行上溢出和下溢出的检查。但是，如果我们稍作分析（见下面的运算栈状态示意图），即可知道：由于出栈了两个操作数而只压入一个运算结果，上溢出时不会发生的，因此我们只要进行下溢出检查即可。另外，该指令执行的结果是，原来存放第一个操作数的堆栈单元（栈顶下面的一个单元）内的操作数变成运算结果，而第二个操作数（原栈顶操作数）被抛弃，堆栈指针减一。因此我们写作opStack[opSp - 2] += opStack[opSp - 1]; opSp -= 1;。
再来一个SIN指令，该指令计算栈顶元素的三角正弦值，并将计算结果压入运算栈。其逻辑运算顺序为：出栈一个操作数->计算三角正弦值->将结果压入运算栈。它的实现代码为：
case SIN:
check_underflow(1);
opStack[opSp - 1] = sin(opStack[opSp - 1]);
break;
同样，我们只需进行下溢出检查即可。另外opStack[opSp - 1] = sin(opStack[opSp - 1]);一行也是仅表示入栈与出栈操作后的结果（见下面的运算栈示意图），运算执行后堆栈指针不会发生改变。
最后，我们再来看看其中涉及的数学知识。
首先是LOG指令的实现。我们希望对于两个操作数op1、op2，LOG指令能够计算以op1为底op2的对数，即：
但是，C标准库中的数学函数中只提供了log()函数log10()函数，分别用于计算已2和10为底的对数。那么，我们就要用到换底公式，即：
因此，我们可以这样实现LOG指令：
case LOG:
check_underflow(2);
opStack[opSp - 2] = log(opStack[opSp - 2])
/ log(opStack[opSp - 1]);
opSp -= 1;
break;
再来看看三角函数的实现。C标准库中只提供了有限的三角函数，但是，通过这些三角函数，我们可以得到任何三角函数的值。现仅举两个例子表示说明：
首先是SEC指令，我们知道，在数学中有：
想到了吧？很简单：
case SEC:
check_underflow(1);
opStack[opSp - 1] = 1 / cos(opStack[opSp - 1]);
break;
呵呵，来一个复杂一点的。ASECH指令，该指令用于计算：
但C标准库中并未提供相应的函数，所以我们必须进行一些数学推导。我们已知的条件有：
以及C标准库中提供的acos()函数。因此，我们令
则有
即
因此
即
这时，我们就可以通过使用C标准库中提供的acos()函数来完成计算了：
case ASEC:
check_underflow(1);
opStack[opSp - 1] = acos(1 / opStack[opSp - 1]);
break;
看到了吧？真正用于计算的只有一行代码，但为了这行代码，我补习了近一个月的数学知识。
好了，这个计算器就是这样了，其他的指令的实现类似。如果你看到了源代码，你可以从中找到最终推导出来的计算公式，至于其中的数学依据和推导过程，我就不讲了。如果你和我一样有过厌学情绪，现在是不是考虑改一改了？
本文地址：http://com.8s8s.com/it/it37240.htm