编译器实现-1

这几周一直在研究怎么写编译器，算是这一年学花指令的最后学习了吧。这个写完之后，就专心学Win内核QAQ

目前还没有把编译器写完，所以现在只是先总结一下流程。

目前我遵循的流程是：

• 输入文本
• token流：将输入的文本解析为token字，它是最小的基本词汇，比如把+=视为1个符号，把abcd视为标识符。此处会进行词法检查。
• 抽象语法树(AST)：将token流解析为抽象语法树，以语句块(节点)为基本单位，装载在不同函数块(节点)中。生成结束后，再进行语法检查。
• 三地址码：将抽象语法树按自顶向下的(从块到句)解析为三地址码，三地址码类似汇编，比如：a += b + c这个AST，会变为tmp = b+c，a = a + tmp，这种方式可以很方便地在下一步映射中间变量为寄存器。
• 汇编代码：三地址码转化为汇编基本只用实现寄存器初始化，使用和销毁。这一步可以和三地址码一起使用，也就是说可以省略三地址码，直接从抽象语法树转换为汇编。

生成token流

这一步需要通过读取文本，解析文本结构来实现输出token流，可以先对输入的内容分类：

字符:''
字符串：""
数字：数字开头纯数字，0x开头且字母小于F的hex值
关键字：控制流关键字(main,if,continue,break,return,等),类型关键字(void,int,dword,byte,proc,struct,等)
符号：运算符：(+,-,*,%,/,等)，间隔符：((),{},[],;)
标识符：字母开头的不含运算符和间隔符的任意内容。且不与关键字重复。

那么就可以对以上内容进行顺序判断实现生成token流，因为是第一次写，所以类型写的比较混乱，QAQ之后有机会改一改

class Token
{
public:
	std::string originaldata;
	ttoken tokenData;
	TYPE tokenType;
	Token(std::string data, ttoken type, TYPE type_)
		: originaldata(data), tokenData(type), tokenType(type_) {
	}
	ttoken type() const
	{
		return tokenData;
	}
	bool isType(ttoken type) const
	{
		return tokenData == type;
	}
	bool operator==(Token a) const
	{
		return tokenData == a.tokenData;
	}
};
class Parser
{
private:
	std::vector<char> origalCode;
	std::vector<Token> TokenList;

public:
	Parser(std::string soureCodePath)
	{
		std::ifstream file(soureCodePath, std::ios::binary);
		if (!file.is_open())
			throw std::runtime_error("文件打开失败");
		file.seekg(0, std::ios::end);
		std::streamsize dataSize = file.tellg();
		file.seekg(0, std::ios::beg);
		origalCode.resize(dataSize);
		if (!file.read(origalCode.data(), dataSize))
			throw std::runtime_error("拷贝文件至缓冲区失败");
	}

	void lexicalAnalysis();//词法分析

};

namespace pomnet
{
	namespace inner {
		//获得下一个值,不递增pdata
		char getNext(char*& pdata)
		{
			return pdata[1];
		}

		//判断字符是否为数字
		bool isDigit(char data)
		{
			if (data >= '0' && data <= '9')
				return true;
			return false;
		}
		bool isHex(char data)
		{
			if (isDigit(data))
				return true;
			if (data >= 'a' && data <= 'f' || data >= 'A' && data <= 'F')
				return true;
			return false;
		}

		//判断字符是否为字母
		bool isAlpha(char data)
		{
			if (data >= 'a' && data <= 'z' || data >= 'A' && data <= 'Z')
				return true;
			return false;
		}

		//判断是否为非字母和数字
		bool notDigitAlpha(char data)
		{
			if (isAlpha(data) || isDigit(data))
				return false;
			return true;
		}
		bool notDigitAlpha_(char data)
		{
			if (data == '_' || isAlpha(data) || isDigit(data))
				return false;
			return true;
		}

		//判断结束
		bool isEndSentence(char data)
		{
			return data == ';';
		}
		//判断块开始或结束
		bool isBlockStart(char data)
		{
			return data == '{';
		}
		bool isBlockEnd(char data)
		{
			return data == '}';
		}


		//判断数字是否正确闭合，当存在一个值是字母但是不是hex时说明数字输入错误
		bool isNumberEndHex(char data)
		{
			if (!isHex(data) && (isAlpha(data) || data == '_'))
			{
				return false;
			}
			return true;
		}
		//判断数字是否正确闭合，当存在一个值是字母时说明数字输入错误
		bool isNumberEnd(char data)
		{
			if (isAlpha(data) || data == '_')
			{
				return false;
			}
			return true;
		}
	}

	//获取最长可能串，字母开头,除了下划线和数字和字母以外的最长字符串,同时偏移到字符串结尾,如果是空，说明没有找到
	std::string getMostData(char*& pdata)
	{
		using namespace inner;
		if (!isAlpha(*pdata))
			return std::string();
		std::string result;
		while (!notDigitAlpha_(*pdata))
		{
			result += *pdata;
			pdata++;
		}
		return result;
	}
	//获取最长可能串，数字，如果是空，说明没有找到
	std::string getMostNumber(char*& pdata)
	{
		using namespace inner;

		if (!isDigit(*pdata))
			return std::string();
		std::string result;

		//如果是0x开头
		if (pdata[0] == '0' && getNext(pdata) == 'x')
		{
			pdata += 2;
			result += "0x";
			while (isHex(*pdata))
			{
				result += *pdata;
				pdata++;
			}
			if (!isNumberEndHex(*pdata))
			{
				throw std::runtime_error("数字未闭合");
			}
			return result;
		}
		//标准数字
		if (pdata[0] != '0')
		{
			while (isDigit(*pdata))
			{
				result += *pdata;
				pdata++;
			}
			if (!isNumberEnd(*pdata))
			{
				throw std::runtime_error("数字未闭合");
			}
			return result;
		}
		//字符串为0
		pdata++;
		return result = "0";
	}

	//获取最长可能字符串
	std::string getMostString(char*& pdata)
	{
		using namespace inner;
		std::string result;
		if (*pdata == '"')
		{
			pdata++;
			result += '"';
			while (*pdata != '"')
			{
				if (*pdata == '\\' && getNext(pdata) == '"')
				{
					pdata++;
					result += *pdata;
					pdata++;
					continue;
				}
				if (*pdata == '\\' && getNext(pdata) == '\\')
				{
					pdata++;
					result += *pdata;
					pdata++;
					continue;
				}
				result += *pdata;
				pdata++;
			}
			if (*pdata == '"')
			{
				result += '"';
				pdata++;
				return result;
			}
			else
			{
				return std::string();
			}
		}
	}

	//获取字符
	std::string getChar(char*& pdata)
	{
		using namespace inner;
		std::string result;
		if (*pdata == '\'')
		{
			pdata++;
			result += '\'';
			if (*pdata == '\\')
			{
				pdata++;
				result += *pdata;
				pdata++;
			}
			else
			{
				result += *pdata;
				pdata++;
			}
			if (*pdata != '\'')
			{
				return std::string();
			}
			result += *pdata;
			pdata++;
			return result;
		}
	}


	//获取符号，如果是空，说明没有找到
	std::string getMostSymbol(char*& pdata)
	{
		using namespace inner;
		std::string result;
		auto targetKey = symbolMap.find(result + *pdata);
		if (targetKey == symbolMap.end())
			return result;
		auto targetKey2 = symbolMap.find(result + *pdata + getNext(pdata));
		if (targetKey2 == symbolMap.end())//长度为1
		{
			result += *pdata;
			pdata++;
			return result;
		}
		//长度为2
		result += *pdata + getNext(pdata);
		pdata += 2;
		return result;
	}


	//直接返回对应类型对应源数据的Token类实例
	Token generateToken(std::string data, TYPE type_)
	{
		switch (type_)
		{
		case identifier:
		{
			return Token(data, ID_TOKEN, identifier);
		}
		case keyword:
		{
			auto targetKey = keyWordMap.find(data);
			if (targetKey != keyWordMap.end())
			{
				return Token(data, targetKey->second, keyword);

			}
			return Token(data, BAD_TOKEN, keyword);
		}
		case type:
		{
			auto targetKey = typeMap.find(data);
			if (targetKey != typeMap.end())
			{
				return Token(data, targetKey->second, type);
			}
			return Token(data, BAD_TOKEN, type);
		}
		case number:
		{
			return Token(data, NUM_TOKEN, number);
		}
		case string:
		{
			return Token(data, STR_TOKEN, string);
		}
		case character:
		{
			return Token(data, CHR_TOKEN, character);
		}
		case symbol:
		{
			auto targetKey = symbolMap.find(data);
			if (targetKey != symbolMap.end())
			{
				return Token(data, targetKey->second, symbol);
			}
			return Token(data, BAD_TOKEN, symbol);

		}
		case separator:
		{
			if (data == ";")
				return Token(data, SY_SEMI, separator);
			if (data == "{")
				return Token(data, SY_LBRACE, separator);
			if (data == "}")
				return Token(data, SY_RBRACE, separator);
		}
		}


	}
}


void Parser::lexicalAnalysis()
{
	char* pdata = origalCode.data();
	auto dataSize = origalCode.size();
	if (dataSize == 0)
	{
		throw std::runtime_error("源文件为空");
	}
	using namespace pomnet;
	while (pdata < origalCode.data() + dataSize)
	{
		//如果是数字
		if (inner::isDigit(*pdata))
		{
			std::string number = getMostNumber(pdata);
			if (number.empty())
			{
				throw std::runtime_error("数字未闭合");
			}
			TokenList.push_back(generateToken(number, TYPE::number));
			continue;
		}
		//如果是字母开头，两种可能，标识符和关键字
		if (inner::isAlpha(*pdata))
		{

			std::string str = getMostData(pdata);
			//如果字符串在map中，说明是关键字
			if (keyWordMap.find(str) != keyWordMap.end())
			{
				TokenList.push_back(generateToken(str, TYPE::keyword));
				continue;
			}
			if (typeMap.find(str) != typeMap.end())
			{
				TokenList.push_back(generateToken(str, TYPE::type));
				continue;
			}
			//如果不是关键字，说明是标识符
			TokenList.push_back(generateToken(str, TYPE::identifier));
			continue;
		}
		//如果是符号开头，分隔符，运算符，字符串或字符
		if (inner::notDigitAlpha(*pdata))
		{
			//如果是空格
			if (*pdata == ' ' || *pdata == '\t' || *pdata == '\n' || *pdata == '\r')
			{
				pdata++;
				continue;
			}

			//如果是字符或字符串
			if (*pdata == '\'')
			{
				std::string chr = getChar(pdata);
				if (!chr.empty())
				{
					TokenList.push_back(generateToken(chr, TYPE::character));
					continue;
				}
			}
			if (*pdata == '"')
			{
				std::string str = getMostString(pdata);
				if (!str.empty())
				{
					TokenList.push_back(generateToken(str, TYPE::string));
					continue;
				}
			}
			//如果是分割符
			if (inner::isEndSentence(*pdata))
			{
				TokenList.push_back(generateToken(";", TYPE::separator));
				pdata++;
				continue;
			}
			if (inner::isBlockEnd(*pdata))
			{
				TokenList.push_back(generateToken("}", TYPE::separator));
				pdata++;
				continue;
			}
			if (inner::isBlockStart(*pdata))
			{
				TokenList.push_back(generateToken("{", TYPE::separator));
				pdata++;
				continue;
			}

			//如果是符号
			std::string symbol = getMostSymbol(pdata);
			if (symbol.empty())
			{
				throw std::runtime_error("非符号");
			}
			TokenList.push_back(generateToken(symbol, TYPE::symbol));
			continue;
		}
	}
}

通过以上内容，就可以生成token list

生成AST

这一步主要进行语法解析，所以是要对每个函数块的内容实现抽象描述。

从最基本的抽象开始：表达式

这里使用partt表达式解析方法。

在一次解析中，先解析符号是否是前缀运算符，再解析符号是否是中缀运算符，最后判断是否是后缀运算符。

解析符号生成AST时，使用固定的getGenerateFunc解析函数传入不同的token类型返回生成对应节点的函数

因此只需要递归调用主函数并在getGenerateFunc返回的函数中实现生成AST即可。

[未完待续]