Home › Default › 关于图灵机、汇编、编译器、模拟器（解释器）的一些思考

关于图灵机、汇编、编译器、模拟器（解释器）的一些思考

发表于 发表于 Default

我们可以定义一些最基本的计算，比如加减乘除、移位等，然后通过对基本计算进行高阶组合，形成更复杂的计算，比如幂、开方、阶乘等等

而计算机中除了基本的计算，还有基本的控制指令，比如循环、判断、递归、函数调用等

当具备这些特性后，我们就可以用他们进行组合，模拟出一个高阶的机器

比如我们可以使用c语言对内存的控制，对计算的调用，以模拟一个另一个（类）cpu的执行

一个简单的案例如下：

假设我们定义了一个处理器，有以下指令：

“ldc”, “adc”, “ldl”, “stl”, “ldnl”, “stnl”,
“add”, “sub”, “shl”, “shr”, “adj”, “a2sp”, “sp2a”, “call”, “return”,
“brz”, “brlz”, “br”, “HALT”

每个指令都以特定方式操作寄存器

那么我们可以很容易实现一个模拟器

#include "inc.h"

void run() {
	switch ((char) ALU) {
	case 0:
		ldc(ALU >> 8);
		break;
	case 1:
		adc(ALU >> 8);
		break;
	case 2:
		ldl(ALU >> 8);
		break;
	case 3:
		stl(ALU >> 8);
		break;
	case 4:
		ldnl(ALU >> 8);
		break;
	case 5:
		stnl(ALU >> 8);
		break;
	case 6:
		add();
		break;
	case 7:
		sub();
		break;
	case 8:
		shl();
		break;
	case 9:
		shr();
		break;
	case 10:
		adj(ALU >> 8);
		break;
	case 11:
		a2sp();
		break;
	case 12:
		sp2a();
		break;
	case 13:
		call(ALU >> 8);
		break;
	case 14:
		_return();
		break;
	case 15:
		brz(ALU >> 8);
		break;
	case 16:
		brlz(ALU >> 8);
		break;
	case 17:
		br(ALU >> 8);
		break;
	case 18:
		HALT();
		break;
	default:
		printf("invalid opcode: %d\n", (char) ALU);
		exit(EXIT_FAILURE);
		break;
	}
}
void ldc(int param) {
	check_pc();
	B = A;
	A = param;
	ALU = *(array + PC++);
}
void adc(int param) {
	check_pc();
	A += param;
	ALU = *(array + PC++);
}
void ldl(int param) {
	check_pc();
	check_offset(SP + param);
	B = A;
	A = *(array + SP + param);
	ALU = *(array + PC++);
}
void stl(int param) {
	check_pc();
	check_offset(SP + param);
	*(array + SP + param) = A;
	A = B;
	ALU = *(array + PC++);
}
void ldnl(int param) {
	check_pc();
	check_offset(A + param);
	A = *(array + A + param);
	ALU = *(array + PC++);
}
void stnl(int param) {
	check_pc();
	check_offset(A + param);
	*(array + A + param) = B;
	ALU = *(array + PC++);
}
void add() {
	check_pc();
	A += B;
	ALU = *(array + PC++);
}
void sub() {
	check_pc();
	A = B - A;
	ALU = *(array + PC++);
}
void shl() {
	check_pc();
	A = B << A;
	ALU = *(array + PC++);
}
void shr() {
	check_pc();
	A = B >> A;
	ALU = *(array + PC++);
}
void adj(int param) {
	check_pc();
	SP += param;
	ALU = *(array + PC++);
}
void a2sp() {
	check_pc();
	SP = A;
	A = B;
	ALU = *(array + PC++);
}
void sp2a() {
	check_pc();
	B = A;
	A = SP;
	ALU = *(array + PC++);
}
void call(int param) {
	check_pc();
	B = A;
	A = PC;
	PC += param;
	ALU = *(array + PC++);
}
void _return() {
	check_pc();
	PC = A;
	A = B;
	ALU = *(array + PC++);
}
void brz(int param) {
	check_pc();
	if (!A)
		PC += param;
	ALU = *(array + PC++);
}
void brlz(int param) {
	check_pc();
	if (A < 0)
		PC += param;
	ALU = *(array + PC++);
}
void br(int param) {
	check_pc();
	PC += param;
	ALU = *(array + PC++);
}
void HALT() {
	check_pc();
	ALU = *(array + PC++);
}

以下是模拟环境运行时

#include "inc.h"

int main(int argc, char** argv) {
	int exe_count = 0;
	if (!load_obj(*(argv + 1)))
		return 0;
	A = B = PC = SP = 0;
	ALU = *array;
	reg_status("initial status");
	while ((char) ALU != 18) {
		run();
		++exe_count;
	}
	reg_status("final status");
	printf("execution complete without errors. %d instructions executed\n",
			exe_count);
	return 0;
}
int load_obj(const char *filename) {
	FILE *obj_file;
	if (NULL == (obj_file = fopen(filename, "r"))) {
		printf("cannot open file '%s'\n", filename);
		return 0;
	}
	leng = fread(array, sizeof(int), MAX_MEM, obj_file);
	return 1;
}
void out_of_mem() {
	reg_status("out of memory! exit failure with register status");
	exit(EXIT_FAILURE);
}
void reg_status(const char *title) {
	printf("%s:\nA=0X%08X,B=0X%08X,PC=0X%08X,SP=0X%08X\n", title, A, B, PC, SP);
}
void check_pc() {
	check_offset(PC);
}
void check_offset(int offset) {
	if (offset < 0 || offset >= MAX_MEM)
		out_of_mem();
}

这样我们就可以用C语言这个机器去实现另一个“虚构”的机器

而这个“虚构”的机器我们是可以用电路将它实现的，而实现之前用C语言模拟以验证这个虚拟的机器是否完善，这只是图灵机的一个用途

而我想表达的重点是，C语言本身是一种抽象，也是一个机器，C语言底层的汇编又是一个抽象，更底层的机器，更加底层的机器指令同样是一个机器。我们可以用一个图灵完备的机器去构造另一个图灵完备的机器，而这背后考的是可计算理论来支撑

相对来说编译器是比模拟器更加容易理解的东西，虽然编译器技术难点也许更多，但是它没有什么神奇的地方，它只负责将一种语言“翻译”成另一种语言