编译原理报告三四元式.docx

四元式生成一、 目的和要求1、目的通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法范畴变换为某种中间代码的语义翻译方法。2、要求（1） 选用目前世界上普遍采用的语义分析方法语法制导翻译技术。（2）语义分析对象重点考虑经过语法分析后已是正确的语法范畴，实习重点是语义子程序。（3） 中间代码选用比较常见的形式，例如四元式。二、背景知识属性文法：A=(G，V，F)，其中： G：一个CFG, 属性文法的基础。V：有穷的属性集：每个属性与一个文法符号相关联，这些属性代表与文法符号相关的语义信息，如：类型、地址、值、代码、符号表内容等等。属性与变量一样，可以进行计算和传递，属性加工的过程即是语义处理的过程。属性加工与语法分析同时进行。属性的表示：标始符（或数），写在相应文法的下边，点记法：E.Val,E.Place,E.Type。F：关于属性的属性断言或一组属性的计算规则(称为语义规则)。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。属性有两类：综合属性：归约型属性，用于“自下而上”传递信息。继承属性：推导型属性，用于“自上而下”传递信息。综合属性的例子：非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现。设表达式为35+4，则语义动作打印数值19。L属性文法：一个属性文法称为L属性文法，如果对于每个产生式AX1X2Xn，满足：1、 Xj（1jn）的继承属性仅依赖于下述属性值中的一种：A的继承属性或产生式右部位 v于Xj左边的符号X1，X2，Xj-1的属性。2、A的综合属性，仅依赖于下述属性值中的一种：A的继承属性或产生式右部符号Xj （除自身外）的任意属性。 L属性文法的翻译器通常可借助于LL分析器实现。在L属性文法的基础上， LL分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。需要对LL分析器增加语义栈，以保存与栈中文法符号有关的继承属性值。每当进行推导时，新的属性值就由栈中正在推导的产生式左边符号的属性值来计算。 S属性文法：一个属性文法称为 S属性文法,当且仅当满足如下条件：1、所有非终结符的属性是综合属性；2、同一产生式中相同符号的各综合属性之间无相互依赖关系；3、如果q是某个产生式中文法符号V的继承属性，则属性q的值仅仅依赖于该产生式右部位于V左边的符号的属性。S属性文法的翻译器通常可借助于LR分析器实现。 在S属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。语法制导翻译的基本思想：为每个产生式配上一个语义子程序，（该子程序描述了一个产生式所对应的翻译工作。这些工作包括：生成中间代码，查填有关的符号表，检查和报错，修改编译程序某些工作变量的值等）。在语法分析过程中，每当一个产生或用于匹配式进行归约时，就调用该产生式所对应的语义子程序，以完成即定的翻译任务。基础源文法和基础目标文法：SDTS的基础源文法(输入文法)一个CFG：(VT，VN，P， S)，其中P=A w|Aw，y属于R)。SDTS的基础目标文法(输出文法)一个CFG：(VN，D，P， S)，其中P=A y|Aw，y属于R)。SDTS的形式化定义：SDTS是一个CFG,是一个五元组 T=( VT，VN，D，R，S)，其中：1、 VT是有穷的输入字母表（包含源语言中的符号）； 2、 VN是有穷的非终结符集；3、D是有穷的输出字母表（包含出现在输出串中的符号）；4、 R是形如Aw，y的规则的有穷集合；R中规则形式： Aw，y A VN，w(VTVN)*，y(VND )*且y中那组非终结符是w中那组非终结符的置换。W：规则的源成分y：规则的翻译成分。5、 S VN，是文法的开始符号。主要的中间代码有：逆波兰、四元式、三元式、间接三元式、树。三、实验内容语法制导翻译是在语法分析的基础上增加语义操作来实现翻译的。原则上每个产生式对应一个语义子程序。在语法分析的过程中，当一个产生式获得匹配或进行归约时，相应的语义子程序便开始工作，生成中间代码，查填有关表格，检查并报告源程序中的错误，修改编译程序某些变量的值。高级语言的语法结构类型很多，从实习的角度可分为以下六类： 说明语句。如各种数据类型说明（整型、实型、布尔型、字符型、复型、双精度型、枚举、子界、数组、集合、文件、记录、指针等），各种数据空间特性说明（如公用语句，共名语句，等价语句等），初值语句。实习重点是内存空间的分配方法。 顺序结构语句。典型代表是各类表达式（如算术表达式、布尔表达式、字符表达式、位表达）及相应的赋值语句。实习重点是算术表达式的翻译方法。 控制结构语句。常见的有转移语句、条件语句和各种分叉语句。实习重点是拉链返填的方法。 子程序结构。指子程序、函数、过程这类结构的定义和调用。实习重点是哑实结合的方法。 循环结构。如计数循环、条件循环等。实习重点是循环化简的方法。 格式语句。主要指输入输出语句的格式加工。实习重点是数据编辑的方法。根据教学要求可从以上六类中选择一至三类实习。四、设计思路模块结构：（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。（5）对生成的逆波兰式进行计算。五、注意事项1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；六、相关代码#include#include#includeusingnamespacestd;#defineMAX100intm=0,sum=0;/sum用于计算运算符的个数/m用于标记输入表达式中字符的个数charJG=A;charstrMAX;/用于存输入表达式inttoken=0;/左括号的标志/*用于更改计算后数组中的值*/voidchange(inte)intf=e+2;charch=strf;if(ch=A&ch=Z)for(intl=0;l=A&stre=Z)for(inti=0;im;i+)if(stri=stre)stri=JG;voidchengchuchuli(inti,intm)i+;for(i=m-1;i+)/处理乘除运算if(stri=*|stri=/)cout(stristri-1stri+1JG)endl;change(i-1);stri-1=stri=stri+1=JG;sum-;JG=(char)(int)JG+;voidjiajianchuli(intj,intm)j+;for(j=m-1;j+)/处理加减运算if(strj=+|strj=-)cout(strjstrj-1strj+1JG)endl;change(j-1);strj-1=strj=strj+1=JG;sum-;JG=(char)(int)JG+;/*扫描一遍从文件中读入表达式*/voidscan(FILE*fin)intpMAX;charch=a;intc=-1,q=0;while(ch!=EOF)ch=getc(fin);while(ch=|ch=n|ch=t)ch=getc(fin);/消除空格和换行符strm+=ch;if(ch=|ch=+|ch=-|ch=*|ch=/)sum+;elseif(ch=()p+c=m-1;elseif(ch=)q=m-1;chengchuchuli(pc,q);/从左括号处理到又括号jiajianchuli(pc,q);JG=(char)(int)JG-;strpc=strm-1=JG;c-;JG=(char)(int)JG+;/*对表达是进行处理并输出部分四元式*/voidsiyuanshi()for(inti=0;i=m-1;i+)/处理乘除运算if(stri=*|stri=/)cout(stristri-1stri+1JG)endl;change(i-1);stri-1=stri=stri+1=JG;sum-;JG=(char)(int)JG+;for(intj=0;j=m-1;j+)/处理加减运算if(strj=+|strj=-)cout(strjstrj-1strj+1JG)endl;change(j-1);strj-1=strj=strj+1=JG;sum-;JG=(char)(int)JG+;for(intk=0;k=m-1;k+)/处理赋值运算if(strk=)JG=(char)(int)-JG;cout(strkstrk+1strk-1)endl;sum-;change(k+1);strk-1=JG;/*主函数*/voidmain()charinMAX;/用于接收输入输出文件名FILE*fin;/用于指向输入输出文件的指针coutin;c