初识编译原理

皇家药学院的信管专业毕竟不是专门的计算机专业。WEB的课程也是基本等于没有，没有开设编译原理课程。为了巩固基础知识，自学编译原理

第一课：sub虚拟机和sub简单编译器。

为了简单，虚拟机只支持两个命令：
push和add
push要带一个数字参数，效果就是把跟的参数压栈
add不用带参数，效果就是从栈顶取两个元素相加，把结果压入栈顶

这里借助二叉树实现语法分析，把加法代码解析为二叉树，对二叉树采用左后遍历（先遍历左节点，再遍历右节点，再遍历父节点）。对节点值不是加号的生成push "节点值"的命令。对节点值为加号的节点，生成add命令。这样整个数遍历完了就生成sub虚拟机的机器码了。

sub虚拟机实现

#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;



/// 
/// 从文件读入到string里
/// 
/// 文件名
/// 文件串
string ReadFileIntoString(char* filename);

/// 
/// 分割字符串
/// 
/// 字符串
/// 分割串
/// 字符串向量
vector SplitString(const string& str, const string& delim);

/// 
/// 浮点类型转换字符串
/// 
/// 
/// 
string DoubleToString(double d);

/// 
/// 字符串转浮点数
/// 
/// 
/// 
double StringToDouble(string str);

/// 
/// 入口函数
/// 
/// 
int main(int argc, char* argv[])
{
	//有参数就按参数传
	if (argc > 1)
	{
		for (int i = 1; i < argc; i++)
		{
			//加载机器代码
			string code = ReadFileIntoString(argv[i]);
			//分割得到每行代码
			vector vecStr = SplitString(code, "n");
			//虚拟机执行栈
			stack machineStack;
			//顺序执行代码
			for (int i = 0; i < vecStr.size(); i++)
			{
				string oneLine = vecStr[i];
				//分割一条命令
				vector vecCode = SplitString(oneLine, " ");
				//是push命令
				if (vecCode[0] == "push")
				{
					machineStack.push(vecCode[1]);
				}
				//执行add命令
				else if (vecCode[0] == "add")
				{
					string oneval = machineStack.top();
					machineStack.pop();
					string towVal = machineStack.top();
					machineStack.pop();
					double res = StringToDouble(oneval)+ StringToDouble(towVal);
					machineStack.push(DoubleToString(res));
				}
			}
			//命令执行完成后取出栈顶元素输出
			if (machineStack.size() > 0)
			{
				string res = machineStack.top();
				cout << "执行结果:" << res<
/// 浮点类型转换字符串
/// 
/// 
/// 
string DoubleToString(double d) {
	ostringstream os;
	if (os << d) return os.str();
	return "invalid conversion";
}

/// 
/// 字符串转浮点数
/// 
/// 
/// 
double StringToDouble(string str) {
	istringstream iss(str);

	double  x;
	if (iss >> x) return x;
	return 0.0;
}

/// 
/// 从文件读入到string里
/// 
/// 文件名
/// 文件串
string ReadFileIntoString(char* filename)
{
	ifstream ifile(filename);
	//将文件读入到ostringstream对象buf中
	ostringstream buf;
	char ch;
	while (buf && ifile.get(ch))
	{
		buf.put(ch);
	}
	//返回与流对象buf关联的字符串
	return buf.str();
}

/// 
/// 分割字符串
/// 
/// 字符串
/// 分割串
/// 字符串向量
vector SplitString(const string& str, const string& delim) {
	vector res;
	if ("" == str) return res;
	//先将要切割的字符串从string类型转换为char*类型  
	//不要忘了  
	char* strs = new char[str.length() + 1];
	strcpy(strs, str.c_str());
	char* d = new char[delim.length() + 1];
	strcpy(d, delim.c_str());
	char* p = strtok(strs, d);
	while (p) {
		string s = p; //分割得到的字符串转换为string类型  
		res.push_back(s); //存入结果数组  
		p = strtok(NULL, d);
	}
	return res;
}

sub编译器实现
头文件

#pragma once
#include 
#include 
using namespace std;
//二叉树数据类型
typedef string TreeElemType;
/// 
/// 定义二叉树结构
/// 
typedef struct BitTreeNode {

	/// 
	/// 存数据的节点
	/// 
	TreeElemType data;

	/// 
	/// 左边节点
	/// 
	struct BitTreeNode* leftChild;

	/// 
	/// 右边节点
	/// 
	struct BitTreeNode* rightChild;
};

实现文件

#include "CompileStudy.h"
#include 
#include 
#include 
#include 



/// 
/// 从文件读入到string里
/// 
/// 文件名
/// 文件串
string ReadFileIntoString(char* filename);

/// 
/// 输出向量字符串到文件
/// 
/// 文件名
/// 文件串
void WriteStrToFile(string filename, vector* codeList);

/// 
/// 分割字符串
/// 
/// 字符串
/// 分割串
/// 字符串向量
vector SplitString(const string& str, const string& delim);

/// 
/// 遍历二叉树生成栈代码
/// 
/// 总节点
/// 栈执行代码
void TraverseMakeCode(const BitTreeNode* node, vector* codeList);

/// 
/// 替换字符串
/// 
/// 源串
/// 老串
/// 新串
/// 
string& ReplaceAllStr(string& str, const  string& old_value, const  string& new_value);


/// 
/// 入口函数
/// 
/// 
int main(int argc, char* argv[])
{
	//有参数就按参数传
	if (argc > 1)
	{
		for (int i = 1; i < argc; i++)
		{
			string code = ReadFileIntoString(argv[i]);
			cout << "读取:" << argv[i] << "代码为:" + code << endl;
			vector vecStr = SplitString(code,"+");
			//1+2+3生成一颗二叉树
			if (vecStr.size() > 0)
			{
				BitTreeNode* mianNode= new BitTreeNode;
				mianNode->data = "+";
				mianNode->leftChild = NULL;
				mianNode->rightChild = NULL;
				for (int i = 0; i < vecStr.size(); i++)
				{
					//树的总节点
					BitTreeNode* oneNode = new BitTreeNode;
					oneNode->data = vecStr[i];
					oneNode->leftChild = NULL;
					oneNode->rightChild = NULL;
					if (mianNode->leftChild == NULL)
					{
						mianNode->leftChild = oneNode;
					}
					else if (mianNode->rightChild == NULL)
					{
						mianNode->rightChild = oneNode;
					}
					else
					{
						BitTreeNode* mianNodeNew = new BitTreeNode;
						mianNodeNew->data = "+";
						mianNodeNew->leftChild = mianNode;
						mianNodeNew->rightChild = oneNode;
						mianNode = mianNodeNew;
					}
				}
				//按二叉树生成代码
				cout << "构造语法二叉树完成"<< endl;
				vector codeList;
				//按二叉树生成栈执行代码
				TraverseMakeCode(mianNode, &codeList);
				string outName = argv[i];
				//输出名字
				outName = ReplaceAllStr(outName,".code",".sub");
				//输出文件
				WriteStrToFile(outName, &codeList);
			}
		}
	}
	else
	{
		cout << "未传入要编译的文件名!" << endl;
	}
	return 0;
}

/// 
/// 替换字符串
/// 
/// 源串
/// 老串
/// 新串
/// 
string& ReplaceAllStr(string& str, const  string& old_value, const  string& new_value)
{
	while (true) {
		string::size_type   pos(0);
		if ((pos = str.find(old_value)) != string::npos)
			str.replace(pos, old_value.length(), new_value);
		else   break;
	}
	return str;
}

/// 
/// 遍历二叉树生成栈代码
/// 
/// 总节点
/// 栈执行代码
void TraverseMakeCode(const BitTreeNode * node, vector* codeList)
{
	if (node != NULL)
	{
		if (node->leftChild == NULL&& node->rightChild == NULL)
		{
			codeList->push_back("push " + node->data);
		}
		if (node->leftChild != NULL)
		{
			TraverseMakeCode(node->leftChild, codeList);
		}
		if (node->rightChild != NULL)
		{
			TraverseMakeCode(node->rightChild, codeList);
		}
		if (node->data =="+")
		{
			codeList->push_back("add");
		}
		
	}
}

/// 
/// 从文件读入到string里
/// 
/// 文件名
/// 文件串
string ReadFileIntoString(char* filename)
{
	ifstream ifile(filename);
	//将文件读入到ostringstream对象buf中
	ostringstream buf;
	char ch;
	while (buf && ifile.get(ch))
	{
		buf.put(ch);
	}
	//返回与流对象buf关联的字符串
	return buf.str();
}

/// 
/// 输出向量字符串到文件
/// 
/// 文件名
/// 文件串
void WriteStrToFile(string filename, vector* codeList)
{
	ofstream outfile(filename.c_str(), ios::trunc);
	cout << "生成add栈代码" << endl;
	for (int j = 0; j < (*codeList).size(); j++)
	{
		cout << (*codeList)[j] << endl;
		outfile << (*codeList)[j] << endl;
	}
	outfile.close();
	cout << "代码生成在:"+ filename<< endl;
}

/// 
/// 分割字符串
/// 
/// 字符串
/// 分割串
/// 字符串向量
vector SplitString(const string& str, const string& delim) {
	vector res;
	if ("" == str) return res;
	//先将要切割的字符串从string类型转换为char*类型  
	//不要忘了  
	char* strs = new char[str.length() + 1]; 
	strcpy(strs, str.c_str());
	char* d = new char[delim.length() + 1];
	strcpy(d, delim.c_str());
	char* p = strtok(strs, d);
	while (p) {
		string s = p; //分割得到的字符串转换为string类型  
		res.push_back(s); //存入结果数组  
		p = strtok(NULL, d);
	}
	return res;
}

源码和编译结果
源码

1+2+3

编译结果

push 1
push 2
add
push 3
add

执行测试

源码

1+2+3+23+64+100+76

编译结果

push 1
push 2
add
push 3
add
push 23
add
push 64
add
push 100
add

执行测试

这次的例子复习了C++二叉树和二叉树的遍历。理解基础栈式虚拟机原理，理解基本的代码编译。如果真的有个芯片支持push和add，那么这就是一个简单的求和语言编译器。避免直接写push和add命令，也就是语言抽象的“高级语言”

初识编译原理

C/C++/C#相关栏目本月热门文章