栈式计算机Stack的结构

• 内存，用于存放程序中声明的所有变量。
• 栈，用于进行运算的空间。
• 执行引擎，指令的执行。

栈计算机的指令集（ISA）

指令的语法

s ->  push NUM        栈操作

   ->  load x               访存

   ->  store x              访存

   ->  add                   算术运算

   ->  sub                   算术运算

   -> times                 算术运算

   ->  div                    算术运算

注：我们可以看到这样的7条指令分成了四类， 上述的指令其实就是Java字节码的一个子集，Java字节码是用一个字节来表示字节码中的操作符，所以一个字节的话，Java字节码的指令原则上有256条，但是现在还没完全用完。

指令的语义：push

把整形常量压到栈顶上，栈的规模增加1 

push NUM:top ++;stack[top] = NUM;

指令的语义：load  x

把x从内存读到栈顶上 

load x:top ++;stack[top] = x;

指令的语义：store  x

把栈顶元素弹出去，并且赋值给内存中的x这个变量

store x:x = stack[top];top --;

指令的语义：add

add:temp = stack[top - 1] + stack[top];top -= 2;push temp;

 指令的语义：sub

add:temp = stack[top - 1] - stack[top];top -= 2;push temp;

 指令的语义：times

add:temp = stack[top - 1] * stack[top];top -= 2;push temp;

 指令的语义：div

add:temp = stack[top - 1] / stack[top];top -= 2;push temp;

变量的内存分配伪指令

Stack机器只支持一种数据类型int，并且给变量分配内存的伪指令是：

.int x

伪指令并不会真正的被ALU那样的执行单元来执行，而是Stack机器在装载一个程序时，就会读取伪指令，并且给相关变量分配内存空间

递归下降代码生成算法

从C--到Stack

表达式的代码生成

不变式：表达式的值总在栈顶（注：不变式是在所有可能的情况中都会成立的一个状况）

Gen_E(E e)
{switch (e){case n:emit("push n");break;case id:emit("load id");break;case true:emit("push 1");break;case false:emit("push 0");break;case e1 + e2:Gen_E(e1);Gen_E(e2);emit("add");break;case e1 && e2:Gen_E(e1);Gen_E(e2);emit("times");break;default:break;}
}

语句的代码生成

不变式：栈的规模不变

Gen_S(S s)
{switch (s){case id = e:Gen_E(e);emit("store id");break;case printi(e):Gen_E(e);emit("printi");  // 从栈上拿一个元素弹出来，然后打印到屏幕上break;case printb(e):Gen_E(e);emit("printb");break;default:break;}
}

类型的代码生成

不变式：只生成.int 类型

Gen_T(T t)
{switch (t){case int:emit(".int");break;// 目标机器上只支持整形数，所以我们把布尔类型也翻译成整形case bool:emit(".int");break;default:break;}
}

变量声明的代码生成

不变式：只生成.int 类型

Gen_D(T id; D)Gen_T(T);emit(" id");Gen_D(D);

程序的代码生成

不变式：只生成.int 类型

Gen_P(D S)Gen_D(D);Gen_S(S);

如何运行生成的代码？

1、找一台真实的物理机

2、写一个虚拟机（解释器），类似于JVM，虚拟机可以根据自己定义的Stack指令集做一个定制，并不拘泥于真实的物理机上有没有这条指令，只要虚拟机里支持，那么Stack就可以设置这样一条指令进去。

3、在非栈式计算机上进行模拟，例如，可以在X86上模拟栈式计算机的行为，用X86的调用栈模拟栈，通过操作ebp、esp显式地操作这个栈，所以我们可以把它当做Stack机器上的一个栈，然后用push、pop等操作来模拟执行Stack机器上的指令。注：JVM中的JIT（即时编译）就是采用此种方式，JVM在执行Java字节码的时候，把它动态的翻译成一个底层机器上的代码，比如，底层机器为X86，JIT就会把Java字节码动态的翻译成X86代码，然后用X86代码来模拟字节码指令的行为。