将算术表达式转换成四元式的程序实现

第一部分：实验内容描述

29． 题目：将算术表达式转换成四元式的程序实现

设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成四元式。要求：

先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。

实验原理：四元式是一个带有四个域的记录结构，这四个域分别为op，arg1，arg2及result。域op包含一个代表运算符的内部码。

由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。具体的形式为：（op，arg1，arg2，result） 。

例如，语句 a=b+(c-d)*e+f/g*(h-i+j/(k+l*m-n)) 的四元式表示如下：

（1） (-，c,d,t1)

（2） (*,t1,e,t2)

（3） (+,b,t2,t3)

（4） (/,f,g,t4)

（5） (+,t3,t4,t5)

（6）(-,h,i,t6)

（7）(*,l,m,t7)

（8）(+,k,t4,t7)

（9）(-,t7,n,t8)

（10）(/,j,t8,t9)

（11）(+,t6,t9,t10)

（12）(=,t10,-,a)

1).检查输入的元素；

2).如果是一个操作数，则进栈；

3).如果是操作符，则

i). 如果符号栈不为空或者此操作符的优先级大于符号栈栈顶的优先级，则将此运算符压栈；

ii).如果符号栈不为空或者此操作符的优先级小于符号栈栈顶的优先级，栈顶操作符出栈并进行相应的操作；

4).假定输入完毕，栈中剩余的所有操作符出栈并进行相应操作。

第二部分：实验过程与结果分析

一、实验过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）

按照顺序将任意一个正确的算术表达式拆分成操作符和操作数部分并入栈，而后比较优先级按照优先级高低出栈，执行操作：将算术表达式转换成四元式输出。本程序共有两个函数，一个将算术表达式翻译成四元式的函数 int translate(string s)，是本程序的主要函数；另一个是主函数，负责调用翻译函数和输入输出处理。

具体如下：

先定义两个栈结构用来存储运算符号和字符，扫描整个算术表达式时，如果是字母则代表碰到一个变量，就无条件入栈，如果为”(”则表示下面会是一个在括号内进行的运算，且应该先运算，所以要不处理符号栈顶的符号，如果不是括号里为负数的形式，将“(”进栈，否则先执行将负值赋给一个临时变量，同时临时变量入字符栈，并向下继续搜索，如果为“)”则一-定会执行完整个括号中的运算式，因此应该在碰到“=”或“(”停止四元式语句的产生，而对于一般的运算符号，则根本先算乘除后算加减，从左到右运算的原则，进行判定，从而确定是将运算符号存入栈还是用来产生四元式。还要注意的是“=”一定是在最后产生，依照这样的法则就会产生四元式。以一个表达式为例:

Y=a+b*(c-(-d))

首先扫描到Y入字符栈，然后“=“入符号栈，然后a入字符栈,“+”入符号栈，b入字符栈，搜索到“*”时，因为*优先级比+大，所以入栈，再向后搜索到“(”判断得下一个不是“-”所以入栈，c入字符栈,再搜索到“(”判断得后面的为“-”,所以产生一个四元式uminus(负数标志) d_ (空值标志) T1 (新产生的临时变量)再把T1 入字符栈，最后扫描到“)”则在栈顶不是“(”时将栈顶出栈同时产生四元式- c T1 T2，然后继续产生四元式*bT2T3，+aT3T4,:=T4一Y，至此产生结束。

核心数据结构如下：

struct TOKEN

{

  char t;

  int i;

} ;

struct TOKEN word, sem[10];

  int i_sem;

 

struct QT

{

  char w;

  struct TOKEN word1;

  struct TOKEN word2;

  struct TOKEN temp;

} ;

编译原理

完整代码见https://download.****.net/download/gyx1549624673/10840211