1 实验任务

编写一个中间代码生成程序，能将算术表达式等翻译成逆波兰、三元组或四元组形式（选择其中一种形式即可）。

2 实验内容

（1）实验要求
将算术表达式等翻译成逆波兰、三元组或四元组形式
（2）输入格式
包含各种算术表达式的文本文件。
（3）输出格式
程序能输出生成的逆波兰、三元组或四元组序列。

3 算法描述

人们常用的算术表达式是中序表达式，而逆波兰表达式是后续表达式，在计算机编程中，后续表达式更易于求得表达式结果。

此处实现的算法主要是对栈的应用，主要实现是先给+、-、*、/、(设定优先级，然后读入符号，若是数字则直接压入结果栈，若是左括号则压入符号栈，是右括号则弹结果栈直到遇到左括号。

其他情况则按优先级压入，若当前符号优先级大于栈顶，直接压入符号栈，否则弹出符号栈到结果栈，直到为空或者符号优先级大于栈顶再压入符号栈。
而逆波兰表达式的求值则较为简单，每次从结果栈弹出三个值，分别是两个操作数和一个操作符，然后进行运算后压栈，当栈内只剩一个元素时，那个元素往往就是运算结果。

对于出错处理部分，将它们分成了三个错误：

1. 字符非法：通过遍历字符看起是否合法实现。
2. 操作符连续：维护一个bool的变量记录上个字符是否代表操作符。
3. 括号无法匹配：利用一个栈。若左括号就压栈，右括号时查看是否是左括号处于栈顶，是的话就弹栈，不是的话就出错。最后，如果这个栈有剩余的左括号，说明出错。

4 代码

主要包含四个函数：

• Convert：将输入的中序表达式转化为结果栈的形式（这里用链表模拟栈）。
• GetRes：以Convert的输出做输入，求得后序表达式的值。
• CheckInput：查看输入是否有错误。
• error：输出对应错误。

//将中序表达式转化为后序表达式
//并利用后序表达式计算结果
#include<iostream>
#include<list>
#include<cstdio>
#include<string.h>
#include<string>
#include<map>
using namespace std;

list<string> ope;			//运算符栈
list<string> res;			//结果栈
map<string,int> oper;		//存储算符优先级
list<int> container;		//运算栈
char invalidChar;
bool valid = true;
void error(int x){
	valid = false;
	switch(x){
		case 1://)(()
			cout<<"非法字符"<<invalidChar<<endl;
			break;
		case 2:
			cout<<"连续的操作符"<<invalidChar<<endl;
			break;
		case 3:
			cout<<"无法匹配括号"<<endl;
			break;
	}
	
}

void CheckInput(string s){
	list<char> bracketStack;
	bool lastOp = true;//记录上一个是否为运算符 
	for(int i = 0;i<s.length();i++){
		if(s[i]>='0'&&s[i]<='9'){
			lastOp = false;
		}
		else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'){
			if(lastOp){
				invalidChar=s[i];
				error(2);
			}
			lastOp=true;
		}
		else if(s[i]=='('){
			bracketStack.push_back('(');
			lastOp=true;//左括号后不能直接出现运算符 
		}
		else if(s[i]==')'){
			if(bracketStack.empty()||bracketStack.back()!='('){//不匹配 
				error(3);
			}
			else{
				bracketStack.pop_back();
			}
			
		}
		else{ 
			lastOp = false;
			invalidChar=s[i];
			error(1);
		}
		
	}
	if(!bracketStack.empty())
		error(3);
}

string Convert(char s[])
{
	oper["+"] = 1;		//运算符优先级越低，oper越低
	oper["-"] = 1;
	oper["*"] = 2;
	oper["/"] = 2;
	oper["("] = 0;
	int i = 0;
	while(true)
	{
		if (i >= strlen(s)) 
			break;
		while (s[i]==' '||s[i]=='/t')//去除无效的空格
			++i;
		if(s[i]>='0'&&s[i]<='9')	//若为数字则获取
		{
			string num;
			while (s[i] >= '0'&&s[i] <= '9')
				num.push_back(s[i++]);			
			res.push_back(num);		//数字直接压入结果栈
			continue;
		}
		else if(s[i]=='(')
			ope.push_back("(");
		else if(s[i]==')')			//是右括号则匹配
		{
			while(true)
			{
				if(ope.back()=="(")
				{
					ope.pop_back();
					break;
				}
				res.push_back(ope.back());
				ope.pop_back();
			}
		}
		else
		{
			string num;
			num.push_back(s[i]);
			while(!ope.empty())
			{
				if(oper[num]>oper[ope.back()])//当前符号优先级大于栈顶，直接压入符号栈
				{
				   ope.push_back(num);
				   break;
				}
				res.push_back(ope.back());//否则弹出符号栈到结果栈，直到为空或者符号优先级大于栈顶再压入符号栈。
				ope.pop_back();
			}
			if(ope.empty())
				ope.push_back(num);
		}
		++i;
	}
	while(!ope.empty())//最后把符号栈的全部内容弹到结果栈
	{
		res.push_back(ope.back());
		ope.pop_back();
	}
   string result = "";
   while(!res.empty())//输出后序表达式
   {
      result+=res.front()+" ";
      res.pop_front();
   }
   return result;
}

int GetRes(string s)
{
   int res;
   int i = 0;
   while(true)
   {
		if (i >= s.length()-1) 
		{
			break;
		}
		while (s[i]==' '||s[i]=='/t')//去除无效的空格
			++i;
		if(s[i]>='0'&&s[i]<='9')
		{
			int num=0;
			while (s[i] >= '0'&&s[i] <= '9')
				num = num*10 + s[i++]-'0';
			container.push_back(num);
			continue;
		}
      else
      {
         int b = container.back();
         container.pop_back();
         int a = container.back();
         container.pop_back();
         int c;
         if(s[i]=='+')
            c = a+b;
         else if(s[i]=='-')
            c = a-b;
         else if(s[i]=='*')
            c = a*b;
         else if(s[i]=='/')
            c = a/b;
         container.push_back(c);
      }
	  ++i;
   }
   return container.back();
}

int main()
{
   char s[30];
   while (scanf("%s", &s) != EOF) {
		ope.clear();
		res.clear();			
		container.clear();
		valid = true;
		CheckInput(s);
		if(!valid)
			continue;
	  	string ansStr = Convert(s);				//把中序的算数表达式
      	cout<<ansStr<<endl;						//输出逆波兰表达式
      	cout<<"算数结果："<<GetRes(ansStr)<<endl;	//输出算数结果
   }
}
//56+8130/(2+67)*8
//9+1/1-7*2+123+456/123+(98+87)
//56+(8130/((2+67)-6*5+7)*8)
//56-+8130/(*2+67)*8
//~45+a/5
//5+2)(

5 运行结果

（1）测试一：56+8130/(2+67)8

（2）测试二：9+1/1-72+123+456/123+(98+87)

（3）测试三：56+(8130/((2+67)-6*5+7)*8)

（4）测试四：对三种出错情况进行测试。
56-+8130/(*2+67)*8触发错误：连续的操作符
~45+a/5触发错误：非法字符
5+2)(触发错误：括号不匹配

逆波兰表达式

• 运算对象写在前，运算符写在后(后缀表示形式)
  例如：a+b $\to$ ab+
  　　(a+b)c $\to$ ab+c
  　　a+bc $\to$ abc+
  　　a=bc+bd $\to$ abcbd+=
• 优点：易于计算机处理
  利用栈，将扫描到的运算对象入栈，碰到运算符：
  若是双目运算符，则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈；
  若是单目运算符，对栈顶元素，执行该运算，将运算结果代替该元素进栈，最后结果即栈顶元素。

c++代码：

#include<string>
#include<iostream>
#include<map>
#include<stack>
#include<vector>
using namespace std;
string str; //需要进行分析的算术表达式
stack<char> tem; //当无法确定运算符是否要输出的时候，将运算符进栈
vector<string> exp;//逆波兰表达式序列
map<char,int> opPri;//定义预定义运算符的优先级
bool convert();//将中缀表达式转化成逆波兰表达式，返回值fasle表示表达式存在错误
bool isLet(char c){
    return (c>='A'&&c<='Z')||(c>='a'&&c<='z');
}//判断字符是否为字母
bool isId(char c){
    return isLet(c)||c=='_';
}//判断字符是否为字母或者为下划线，是否为标识符的一部分
bool isDigit(char c){
    return c>='0'&&c<='9';
}//判断字符是否为数字
int main(){
    opPri['(']=opPri[')']=1;
    opPri['+']=opPri['-']=100;
    opPri['*']=opPri['/']=200;
    while(true){
        cout<<"请输入算术表达式\n";getline(cin,str);
        if(convert()){
            cout<<"分析完毕,该表达式的后缀表达式为:\n";
            for(int i=0;i<exp.size();++i)cout<<exp[i]<<" ";cout<<endl;
        }
        cout<<"是否继续进行分析(y)\n";getline(cin,str);
        if(str!="y")break;
    }
}
bool convert(){
    int len=str.length();bool f1=false,f2=false;
    string word;exp.clear();while(!tem.empty())tem.pop();
    for(int i=0;i<len;){
        if(str[i]==' '||str[i]==9){
            i++;continue;
        }//忽略空格、tab
        if(isId(str[i])){   
            word="";
            while(i<len&&(isId(str[i])||isDigit(str[i])))word+=str[i++];
            if(i<len&&str[i]=='('){
                cout<<"表达式错误，’(‘前面应该为运算符"<<endl;return false;
            }else if(f1==true){
                cout<<"表达式错误，标识符(数字)之间应该有运算符"<<endl;return false;
            }
            f1=true;f2=false;
            exp.push_back(word); 
        }else if(isDigit(str[i])){
            word="";
            while(i<len&&isDigit(str[i]))word+=str[i++];
            if(i<len&&str[i]=='.'){
                word+='.';++i;if(i==len||(isDigit(str[i])==false)){
                    cout<<"表达式错误,浮点数表达错误"<<endl;return false;
                }
                while(i<len&&isDigit(str[i]))word+=str[i++];
                if(i<len&&(isId(str[i])||str[i]=='.')){
                    cout<<"表达式错误,浮点数表达错误"<<endl;return false;
                }else if(f1){
                    cout<<"表达式错误，标识符(数字)之间应该有运算符"<<endl;return false;
                }
                f1=true;f2=false;
                exp.push_back(word); 
            }else if(i<len&&isId(str[i])){
                cout<<"表达式错误，数字之间跟字母"<<endl;return false;
            }else if(f1){
                cout<<"表达式错误，标识符(数字)之间应该有运算符"<<endl;return false;
            }else if(i<len&&str[i]=='('){
                cout<<"表达式错误，’(‘前面应该为运算符"<<endl;return false;
            }
            f1=true;f2=false;
            exp.push_back(word); 
        }else if(str[i]=='('){
            tem.push(str[i++]);
        }else if(str[i]==')'){
            while(!tem.empty()&&tem.top()!='('){
                word="";word+=tem.top();tem.pop();exp.push_back(word);
            }
            if(tem.empty()){
                cout<<"表达式错误，')'前面缺少'('。\n";return false;
            }
            tem.pop();
            ++i;
        }else{
            if(opPri.find(str[i])==opPri.end()){
                cout<<"表达式错误，出现非法字符\n";return false;
            }
            if(f2==true){
                cout<<"表达式错误，出现连续的运算符\n";return false;
            }
            while(!tem.empty()&&opPri[str[i]]<=opPri[tem.top()]){
                word="";word+=tem.top();tem.pop();exp.push_back(word);
            }
            tem.push(str[i++]);f1=false,f2=true;
        }
    }
    while(!tem.empty()){
        if(tem.top()=='('){
            cout<<"表达式错误，'('后面缺少')'。\n";return false;
        }
        word="";word+=tem.top();tem.pop();exp.push_back(word);
    }return true;
}

测试

测试数据:

a+4.+
y
a+7+8+(+
y
a + 4 +(sf+d))
y
a33+d3+34f
y
1 e + 4
y
(a+4+(d*4)+5)+8
n

截图：

基本要求:
①掌握中间代码生成的基本方法。
②掌握语法制导翻译模式。
③完成算术表达式的中间代码生成程序。
重点及难点：掌握语法制导翻译模式的核心思想和工作原理，在此基础上完成基于算数表达式的中间代码生成程序的设计和调试运行。

一、 算符优先分析法

算符优先分析法是一种简单且直观的自下而上分析方法，它特别适合于分析程序语言中的各类表达式，并且宜于手工实现。所谓算符优先分析，就是依照算术表达式的四则运算过程来进行语法分析，即这种分析方法要预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，然后借助于这种关系来比较相邻运算符的优先级，以确定句型的“可归约串”来进行归约。因此，算符优先分析法不是一种规范归约，在整个归约过程中起决定性作用的是相继两个终结符的优先关系。
附加语义的方法是采用语法制导翻译的方法，语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。

二.算符优先分析法程序源代码

#include<string.h>
#include<stdio.h>
#include<math.h>

int nxq = 100;
char a[20], optr[10], s, op;
int i, j, k, opond[10], x1, x2, x3;

int operand(char c) {
	if ((c >= 48) && (c <= 57)) {
		return(1);
	}
	else {
		return(0);
	}
}

int f(char c) {
	switch (c) {
	case'+':return(4);
	case'-':return(4);
	case'*':return(6);
	case'/':return(4);
	case'(':return(2);
	case')':return(6);
	case'#':return(0);
	default:printf("error!\n");
	}
}

int g(char c) {
	switch (c) {
	case'+':return(3);
	case'-':return(3);
	case'*':return(5);
	case'/':return(5);
	case'(':return(7);
	case')':return(2);
	case'#':return(0);
	default:printf("error!\n");
	}
}

void get() {
	s = a[i];
	i = i + 1;
}

int main() {
	printf("please input your exoression:\n");
	i = 0;
	do {
		i = i + 1;
		scanf_s("%c", &a[i]);
	} while (a[i] != '#');
	i = 1;
	j = k = 1;
	optr[j] = '#';
	get();
	while (!((optr[j] == '#') && (s == '#'))) {
		if (operand(s)) {
			opond[k] = s - 48;
			k = k + 1;
			get();
		}
		else if (f(optr[j]) > g(s)) {
			op = optr[j];
			j = j - 1;
			x1 = opond[k - 2];
			x2 = opond[k - 1];
			k = k - 2;
			switch (op) {
			case'+':x3 = x1 + x2;break;
			case'*':x3 = x1 * x2;break;
			case'-':x3 = x1 - x2;break;
			case'/':x3 = x1 / x2;break;
			}			
			opond[k] = x3;
			k++;
			printf("%d (%c,%d,%d,%d)\n", nxq++,op, x1, x2, x3);
		}
		else if (f(optr[j]) < g(s)) {
			j = j + 1;
			optr[j] = s;
			get();
		}
		else if (f(optr[j]) == g(s)) {
			if (optr[j] == '(' ||optr[j]== ')') {
				j = j - 1;
				get();
			}
			else {
				printf("error!\n");
			}
		}
		else {
			printf("error!\n");
		}
	}
	return 0;
}