欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

编译原理 简单计算器的编译器的设计与实现(附源码)

程序员文章站 2022-07-14 13:14:33
...

简单计算器的编译器的设计与实现
通过设计、编制、调试一个算术表达式编译器,进一步加深对编译器的词法分析、语法分析、错误处理及输出等环节的理解,获得对实际编译器的构造原理、过程和方法的感性认识,系统掌握语法制导翻译技术。

已知有如下的布尔表达式文法:
E→E+T|E-T|T
T→T*F|T/F|F
F→ +(E)|id
利用LR分析法编制、调试其语法分析程序,生成的中间代码为后缀表达式,通过语法制导定义和后缀表达式进行计算。编制好分析程序后计若干用例,上机
测试并通过所设计的分析程序。算术表达式的LR分析分为扩展文法,构遣识别活动前缀的DFA图,判断是否有冲突,若有冲突,则消除冲突和构遣LR分析表等步骤。
构造项目集规范族

编译原理 简单计算器的编译器的设计与实现(附源码)
编译原理 简单计算器的编译器的设计与实现(附源码)
编译原理 简单计算器的编译器的设计与实现(附源码)
构造识别活前缀的DFA
编译原理 简单计算器的编译器的设计与实现(附源码)
通过DFA可以构造出SLR分析表,这是编译原理需要掌握的技术,此处不再给出。

设计需要完成的内容有:
编译器设计的编译程序涉及到编译五个阶段中的三个阶段,即词法分析、语法分析和中间代码生成。编译程序的输出结果为符号表、分析器对于输入的格局
变化和相应动作、中间代码即后缀表达式。整个编译程序分为五部分:词法分析部分、语法分析并计算部分、中间代码生成部分、输出显示部分。
编译程序需要在符号级别上来分析和翻译源程序,所以首先要识别出符号,而词法分析部分的任务是:从左至右扫描源程序的字符串,按照词法规则(当出现空格,则无操作,过滤空格;当一个数字后面还是数字,则把数字都连接起来,防止二位及以上位数的数字出现分离;当出现符号时,单独识别“)”,识别出正确的符号,并转换成该符号相应的二元组<记号名、属性值>交给语法分析使用。因此,词法分析是编译的基础。执行词法分析的程序称为词法分析器。
语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误,报告错误的位置和性质,并进行适当的纠错工作。
语法分析是以词法分析的结果二元组作为输入,通过LR分析表对语法进行分析处理。采用语法制导定义,由于LR分析表的控制,使得语法制导定义能有条不紊的进行,边分析边计算.最后输出LR分析器对于输入串的格局变化与相应动作以及最后的计算结果。
结果计算可以在语法分析阶段完成,也可以在中间代码生成后进行计算。生成中间代码(即后綴表达式)后,使用栈即可进行计算。

先给出实现界面

首页面
编译原理 简单计算器的编译器的设计与实现(附源码)
词法分析结果:
编译原理 简单计算器的编译器的设计与实现(附源码)
语法分析结果:
编译原理 简单计算器的编译器的设计与实现(附源码)
中间代码生成:
编译原理 简单计算器的编译器的设计与实现(附源码)

本程序还对错误输入等进行处理,较为完整,此处仅给出部分代码
词法分析部分:

bool IsOperator(char ch){
	for (int i = 0; i<5; i++){
		if (OPERATOR[i] == ch){
			return true;
		}
	}
	return false;
}
/**词法分析**/
vector<string> analyse(string expression){
	vector<string> vec;
	char ch = ' ';
	for (int i = 0; i < expression.length(); i++)
	{
		string arr = "";
		ch = expression[i];
		if (IsFilter(ch)){}              //判断是否为过滤符
		else if (IsDigit(ch)){           //判断是否为数字
			while (IsDigit(ch) || IsFilter(ch)){
				if (IsDigit(ch))
					arr += ch;
				i++;
				ch = expression[i];
			}
			i--;
			//printf("%3d    ", CONSTANT);
			cout << "\t\t\t< 整形数 , " << arr <<">"<< endl;
			vec.push_back(arr);	
//将一个新的元素加到vector后面,位置为当前最后一个元素的下一个元素
		}
		else if (IsOperator(ch))
		{
			arr += ch;
			//printf("%3d    ", value(OPERATOR, 8, *arr.data()));
			cout << "\t\t\t< 运算符 , " <<  arr << ">" << endl;
			vec.push_back(arr);
		}
		else if (IsSeparater(ch))
		{
			arr += ch;
			//printf("%3d    ", value(SEPARATER, 8, *arr.data()));
			cout << "\t\t\t< 分隔符 , " << arr << ">" << endl;
			vec.push_back(arr);
		}
		else
		{
			cout << "\t\t\t\"" << ch << "\":无法识别的字符!" << endl;
			vec.clear();
			return vec;
		}
	}
	return vec;
}

中间代码部分:

string InversePolish(string s_mid)
{
	string s_beh = "";
	stack<char> stk;

	map<char, int> op;//利用map来实现运算符对应其优先级
	op['('] = 0;
	op[')'] = 0;
	op['+'] = 1;
	op['-'] = 1;
	op['*'] = 2;
	op['/'] = 2;
	string::iterator it = s_mid.begin();	
	//迭代器,遍历并选择序列中的对象,他提供了一种访问一个容器对象的中各个元素,而又不必保留该对象内部细节的方法。
	while (it != s_mid.end())
	{
		if (op.count(*it))//判断该元素是否为运算符
		{
			if (*it == ')')
//若为’)‘,把栈中的运算符依次加入后缀表达式,直到出现'(',’(‘出栈,退出该次循环
			{
				while (stk.top() != '(')
				{
					s_beh += stk.top();		//取出栈顶元素
					s_beh += " ";
					stk.pop();
				}
				stk.pop();		//弹出栈顶元素
			}
			else if (stk.empty() || *it == '(' || op[*it]>op[stk.top()])
//若为‘(’,入栈 ; 要入栈的运算符优先级大于等于栈顶的运算符的优先级,直接入栈
			{
				stk.push(*it);	//在栈顶增加元素
			}
			else if (op[*it] <= op[stk.top()])
// 入栈的运算符优先级小于等于栈顶的运算符的优先级,栈顶运算符出栈,再次比较,直到出现优先级低的运算符,或者栈为空,退出
			{
				while (op[*it] <= op[stk.top()] && (!stk.empty()))
				{
					s_beh += stk.top();
					s_beh += " ";
					stk.pop();
					if (stk.empty()) break;
				}
				stk.push(*it);
			}
		}
		else
		{
			s_beh += *it;
			it++;
			if (it != s_mid.end() && op.count(*it))
//count,返回被查找元素个数,返回1/0,有/无;find 返回被查找元素的位置,没有返回map.end()
				s_beh += " ";
			it--;
		}
		it++;

		if (it == s_mid.end())//当中缀表达式输出完成,所有元素出栈
		{
			while (!stk.empty())
			{
				s_beh += " ";
				s_beh += stk.top();
				stk.pop();
			}
			break;
		}
	}
	cout <<"逆波兰表达式:"<< s_beh << endl;
	return s_beh;
}

后缀表达式计算:

int Op(int a, char op, int b)
{
	switch (op)
	{
	case '+':return a + b; break;
	case '-':return a - b; break;
	case '*':return a*b; break;
	case '/':return a / b; break;
	}
}

int calculate(char *str)
{
	stack<int> s;//暂存操作数
	int i = 0;
	int offset = 0;
	int flag = 0;
	int Length = strlen(str);
	int Result;
	while (i < Length)
	{
		string One = "";
		for (i; i < Length; i++)
		{

			One += str[i];
			if (((str[i] == ' ')&&(str[i+1]!=' ')) || (i == Length - 1))
			{
				char* OneNumber = (char*)One.data();
				int Number = atoi(One.c_str());  
//atoi字符串转整数,c_str返回一个指向正规c字符串的指针常量,内容与其中string同。(为了与c语言兼容)

				if (IsOperator(*OneNumber))
				{
					Number = 0;
				}
				s.push(Number);

				if (IsOperator(*OneNumber))
				{
					s.pop();
					int x = s.top();
					s.pop();
					int y = s.top();
					s.pop();
					Result = Op(y, *OneNumber, x);
					s.push(Result);
				}
				offset = i + 1;
				break;
			}
		}
		i = offset;
	}
	return s.top();
}

完整代码从此处下载
编译原理 简单计算器的设计与实现