编译原理报告四逆波兰式

1、逆波兰式的产生及计算一、 目的与要求1、目的通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法范畴变换为某种中间代码的语义翻译方法。2、要求（1） 选用目前世界上普遍采用的语义分析方法语法制导翻译技术。（2）语义分析对象重点考虑经过语法分析后已是正确的语法范畴，实习重点是语义子程序。（3） 中间代码选用比较常见的形式，例如四元式。二、背景知识属性文法：A=(G，V，F)，其中： G：一个CFG, 属性文法的基础。V：有穷的属性集：每个属性与一个文法符号相关联，这些属性代表与文法符号相关的语义信息，如：类型、地址、值、代码、符号表内容等等。属性与变量一样，可以进行计算和传递，

2、属性加工的过程即是语义处理的过程。属性加工与语法分析同时进行。属性的表示：标始符（或数），写在相应文法的下边，点记法：E.Val,E.Place,E.Type。F：关于属性的属性断言或一组属性的计算规则(称为语义规则)。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。属性有两类：综合属性：归约型属性，用于“自下而上”传递信息。继承属性：推导型属性，用于“自上而下”传递信息。综合属性的例子：非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我

3、们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现。设表达式为35+4，则语义动作打印数值19。 3*5+4的带注释的分析树继承属性的例子：继承属性的自上而下定值（Real id1，id2，id3）： Real id1，id2，id3的分析树L属性文法：一个属性文法称为L属性文法，如果对于每个产生式AX1X2Xn，满足：1、 Xj（1jn）的继承属性仅依赖于下述属性值中的一种：A的继承属性或产生式右部位于Xj左边的符号X1，X2，Xj-1的属性。2、A的综合属性，仅依赖于下述属性值中的一种：A的继承属性或产生式右部符号Xj （除自身外）的任意属性

4、。 L属性文法的翻译器通常可借助于LL分析器实现。在L属性文法的基础上， LL分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。需要对LL分析器增加语义栈，以保存与栈中文法符号有关的继承属性值。每当进行推导时，新的属性值就由栈中正在推导的产生式左边符号的属性值来计算。 S属性文法：一个属性文法称为 S属性文法,当且仅当满足如下条件：1、所有非终结符的属性是综合属性；2、同一产生式中相同符号的各综合属性之间无相互依赖关系；3、如果q是某个产生式中文法符号V的继承属性，则属性q的值仅仅依赖于该产生式右部位于V左边的符号的属性。S属性文法的翻译器通常可借助于LR分析器实现。 在

5、S属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。语法制导翻译的基本思想：为每个产生式配上一个语义子程序，（该子程序描述了一个产生式所对应的翻译工作。这些工作包括：生成中间代码，查填有关的符号表，检查和报错，修改编译程序某些工作变量的值等）。在语法分析过程中，每当一个产生或用于匹配式进行归约时，就调用该产生式所对应的语义子程序，以完成即定的翻译任务。基础源文法和基础目标文法：SDTS的基础源文法(输入文法)一个CFG：(VT，VN，P， S)，其中P=A® w|A®w，y属于R)。SDTS的基础目标文法(输出文法)一个CFG：(

6、VN，D，P， S)，其中P=A® y|A®w，y属于R)。SDTS的形式化定义：SDTS是一个CFG,是一个五元组 T=( VT，VN，D，R，S)，其中：1、 VT是有穷的输入字母表（包含源语言中的符号）； 2、 VN是有穷的非终结符集；3、D是有穷的输出字母表（包含出现在输出串中的符号）；4、 R是形如A®w，y的规则的有穷集合；R中规则形式： A®w，y A VN，w(VTVN)*，y(VND )*且y中那组非终结符是w中那组非终结符的置换。W：规则的源成分y：规则的翻译成分。5、 S VN，是文法的开始符号。主要的中间代码有：逆波兰、四元式、三

7、元式、间接三元式、树。三、 实验内容1、逆波兰式定义将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。2、产生逆波兰式的前提中缀算术表达式3、逆波兰式生成的实验设计思想及算法否出错处理否否是是是是否是否输入一个中缀式表示的简单运算表达式#入栈sym=当前输入符号sym是数字吗?对数字进行处理，形成一个数字串栈顶运算符优先级低于sym吗?将向前看符号入栈栈顶运算符与sym优先级相等吗?将栈顶运算符弹出，且输出栈顶运算符优先级高于sy

8、m吗栈顶是(且sym为）吗栈顶运算符出栈程序结束(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重

9、复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。4、逆波兰式计算的实验设计思想及算法读入一个逆波兰算术表达式sym=当前输入符号sym是运算符吗?将该字符入栈根据运算符的特点从栈顶部取出若干个运算对象进行该运算将运算结果入栈程序结束否是Sym=#否是(1)构造一个栈，存放运算对象。(2)读入一个用逆波兰式表示的简单算术表达式。(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运

10、算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。程序输入/输出示例：输出的格式如下：(1)输入一以#结束的中缀表达式(包括+*/（）数字#)：在此位置输入符号串如(28+68)*2#(2)逆波兰式为：28&68+2*(3)逆波兰式28&68+2*计算结果为192备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔；(2

11、)在此位置输入符号串为用户自行输入的符号串。四、设计思路模块结构：（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。（5）对生成的逆波兰式进行计算。五、注意事项1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，测试用的表达式事

12、先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；六、相关代码 #include<stdio.h> #include<math.h> #define max 100 char exmax;       /*存储后缀表达式*/ void trans()        /*

13、将算术表达式转化为后缀表达式*/ char strmax;   /*存储原算术表达式*/  char stackmax;       /*作为栈使用*/  char ch;  int sum,i,j,t,top=0;  printf("*n");  printf("*输入一个求值的表达式，以#结束。*n");

14、  printf("*n");  printf("算数表达式：");  i=0;                      /*获取用户输入的表达式*/  do   i+; scanf("%c",&a

15、mp;stri);  while(stri!='#' && i!=max);     sum=i;  t=1;i=1;  ch=stri;i+; while(ch!='#')   switch(ch)   case '(':        

16、60;        /*判定为左括号*/   top+;stacktop=ch;        break;         case ')':            &#

17、160;    /*判定为右括号*/   while(stacktop!='(')                 ext=stacktop;top-;t+;        top-;   break;  

18、0;      case '+':                 /*判定为加减号*/   case '-':          while(top!=0&&stackt

19、op!='(') ext=stacktop;top-;t+;        top+;stacktop=ch;    break; case '*':                  /*判定为乘除号*/  

20、0;      case '/':    while(stacktop='*'|stacktop='/')     ext=stacktop;top-;t+;        top+;stacktop=ch;    break;   case

21、 ' ':break;   default:while(ch>='0'&&ch<='9')                 /*判定为数字*/    ext=ch;t+;    ch=stri;i+;  

22、       i-;    ext='#'t+;      ch=stri;i+;    while(top!=0)   ext=stacktop;t+;top-;    ext='#'  printf("nt原来表达式："); 

23、0;for(j=1;j<sum;j+)   printf("%c",strj);     printf("nt后缀表达式：",ex);  for(j=1;j<t;j+)   printf("%c",exj);  void compvalue()          &#

24、160;                      /*计算后缀表达式的值*/  float stackmax,d;                   

25、60;/*作为栈使用*/  char ch;  int t=1,top=0;                  /*t为ex下标，top为stack下标*/  ch=ext;t+;     while(ch!='#')   switch(ch)

26、     case '+':      stacktop-1=stacktop-1+stacktop;      top-;     break;           case '-':  

27、0;   stacktop-1=stacktop-1-stacktop;      top-;     break;           case '*':      stacktop-1=stacktop-1*stacktop;   

28、;   top-;      break;           case '/':            if(stacktop!=0)   stacktop-1=stacktop-1/stacktop; 

29、0;          else             printf("nt除零错误!n");             exit(0);       

30、;            /*异常退出*/           top-;      break;     default:      d=0;    

31、0; while(ch>='0'&&ch<='9')       d=10*d+ch-'0'               /*将数字字符转化为对应的数值*/          ch=ext;t+

32、;            top+;      stacktop=d;      ch=ext;t+;    printf("nt计算结果:%gn",stacktop);   main()  trans();  compvalue

33、();运行结果：#include<stdio.h>#include<math.h>#include<stdafx.h>#include<windows.h>#define max 100char exmax; /*存储后缀表达式*/void trans()/*将算术表达式转化为后缀表达式*/char strmax; /*存储原算术表达式*/char stackmax; /*作为栈使用*/char ch;int sum,i,j,t,top=0;printf("*n");printf("*输入一个求值的表达式，以#结束。

34、*n");printf("*n");printf("算数表达式：");i=0; /*获取用户输入的表达式*/doi+;scanf("%c",&stri);while(stri!='#' && i!=max);sum=i;t=1;i=1;ch=stri;i+;while(ch!='#')switch(ch)case '(': /*判定为左括号*/top+;stacktop=ch;break;case ')': /*判定为右括号*/while(stacktop!='(')ext=stacktop;top-;t+; top-;break;case '+': /*判定为加减号*/ case '-': while(top!=0&&stacktop!='(')ext=stacktop;top-;t+;top+;stacktop=ch;break;c