张瑞编译原理实验报告

黑龙江大学“编译原理课程设计”读书报告学院软件学院年级2012级专业软件工程学号20122515姓名张瑞报告日期2014年6月28日成绩黑龙江大学计算机科学技术学院黑龙江大学软件学院概述“编译原理”课程是计算机专业中一门重要的专业理论课，是一门理论性和实践性都很强的课程。为配合《编译原理》课程的教学，培养学生的实际工作能力，加深对课堂教学内容的理解，通过设计一个小型编译器，更深刻地领会其基本概念、基本工作原理和实现方法，从而具有初步开发系统软件和应用软件的实际能力，特开设此课程设计。通过设计、编制、调试一个对PL/0语言进行词法、语法及中间代码生成的程序，加深对编译原理的理解。掌握对单词序列的词法检查和分析、掌握计算机语言的语法分析的过程。熟练运用一种分析方法（自上而下或自下而上的方法）分析一个给定的文法以及通过思考以及动手制作分析器的过程来锻炼自己的编程能力和逻辑思维能力体会计算机编译器的奥妙之处。一、开发环境简介MicrosoftvisualC++6.0.开发环境:是指在基本硬件和数字软件的基础上,为支持系统软件和应用软件的工程化开发和维护儿使用的一组软件,简称SDE。它有软件工具和环境继承机制构成,前者用以支持软件开发的相关过程、活动和人物,后者为工具集成和软件的开发、维护及管理提供统一的支持。1.支持开发完备模型2.灵活控制二、基本理论阐述、当前理论或实践应用现状《编译原理》理论和实践并重,叙述严谨、简明,富有启发性,且内容深入浅出,便于自学。《编译原理》不仅可以作为高等院校相关专业的教材,也可以作为计算机专业人员的参考用书。编译器的构造工具是根据用户输入的语言的文法,编译器的构造工具可以生成程序来处理以用户输入的文法书写的文本。随着计算机应用范围的扩大,在软件自动生成,文档处理,特定专业的语言等领域,编译器的构造工具这一技术显得越来越重要.在分析语法成分时比较方便直观,更便于操作。运行程序的同时不断修正改进程序,直至的到最优源程序。三、小型编译器系统架构它是一个编译器的架构.通俗的来说,它实现了一个库,在这个库上,可以很容易的实现不同的编译相关的程序,当然,编译器自然是其中最重要的一个.当然其他像编译时间的代码分析也是很容易实现的。构造识别符号串的自动机、词法分析程序的构造、语法分析程序的构造、中间语言的生成程序、编译程序的代码生成。四、小型编译器主要功能模块与实现（1）功能介绍1.词法分析功能：对代码进行分词操作，分出以下5类单词：关键字、标识符、常量、运算符、分隔符。2.算术表达式、关系表达式和逻辑表达式的分析与化简：提取代码中的所有算术表达式，可用LL(1)分析或算符优先分析算术表达式。关系表达式和逻辑表达式也可用算术表达式的程序进行分析。分析成功后进行化简操作，方便语法分析程序分析。3.LL(1)语法分析：自己写的简单C语言的方法，支持赋值语句、判断语句、循环语句，用自顶向下的分析方法，对化简之后的单词流进行分析。4.四元式生成与后缀式。对词法分析分词后的单词流生成中间代码。其中算术表达式先生成后缀式。然后再根据后缀式的结果生成四元式。对多条逻辑表达式采用先计算再跳转的操作。对if语句判断跳转，if中的表达式支持多条逻辑表达式，但不支持嵌套。while和if相同。5.汇编语言生成：根据四元式生成汇编语言。（2）相关理论1.词法分析（英语：lexicalanalysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器，也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。2.LL(1)文法：对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A—α|β满足下列条件：（1）如果α、β均不能推导出ε,则FIRST(α)∩FIRST(β)=Φ。（2）α和β至多有一个能推导出ε。（3）如果β*═ε,则FIRST(α)∩FOLLOW(A)=Φ。将满足上述条件的文法称为LL(1)文法。第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。LL(1)文法既不是二义性的，也不含左递归，对LL(1)文法的所有句子均可进行确定的自顶向下语法分析。并不是所有的语言都可以用LL(1)文法来描述，而且不存在判定某种语言是否是LL(1)文法的算法。也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL(1)文法所产生的语言。另外，在上述LL(1)文法的条件中，要求：ε∈FIRST(α1)，ε∈FIRST(α2)，…ε∈FIRST(αn)中至多有一个成立。3.语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。4.后缀式：即逆波兰式。逆波兰式是波兰逻辑学家卢卡西维奇（Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用械实现求值。对于表达式x:=(a+b)*(c+d)，其后缀式为xab+cd+*:=。原表达式：a*(b*(c+d/e)-f)#/*#为表达式结束符号*/后缀式：abcde/+*f-*#5.四元式：四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。四元式实际上是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)其中，op为一个二元(也可是一元或零元)运算符；arg1,arg2分别为它的两个运算(或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式：result∶=arg1oparg2每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元式构成的序列来表示。例如，表达式A+B*C可写为序列T1∶=B*C,T2∶=A+T1其中，T1，T2是编译系统所产生的临时变量名。当op为一元、零元运算符(如无条件转移)时，arg2甚至arg1应缺省，即result∶=oparg1或opresult；对应的一般形式为：(op,arg1,arg2,result).（3）算法描述1.词法分析器1.Designtheregulargrammar.2.Designtheregularexpression.3.ConstructtheDFA.4.Writetheprogram.数据结构typedefstruct{inttype;chartoken[size];}symbol;Char*keywords[keywordsnum]={auto,break,case,char,const,continue,default,do,double,else,enum,extern,float,for,goto,if,int,long,register,return,short,signed,sizeof,static,struct,switch,typedef,printf,union,unsigned,void,volatile,while,main,include,using,namespace,std,bool,cin,cout,iostream,endl};char*operators[operatorsnum]={+,-,*,/,++,--,%};char*jiefu[jiefunum]={,,;,.,(,),{,},[,],|};char*luoji[luojinum]={,,=,=,=,==,!=,&&,||,!};char*teshu[teshunum]={@,#,$,&,^,~,,};char*zhushi[zhushinum]={//,/*,*/};char*str[8]={关键字,操作符,界符,逻辑运算符,特殊符,注释符,常量,标识符};*通过读文件的形式一个字符一个字符读入进行分析*下面是词法分析的主要函数voidlex(char*filename){interror=0;intflag=0;charch;fp.open(filename);intlinenum=1;inti,j;i=0;intx=0;ch=fp.get();while(!fp.eof()){if(ch==''||ch=='\t'){x=0;ch=fp.get();}elseif(ch=='\n'){x=0;linenum++;ch=fp.get();}elseif(isalpha(ch)==1){table[i].token[x]=ch;ch=fp.get();if(isalpha(ch)==0&&isdigit(ch)==0&&ch!='_'){table[i].token[++x]='\0';i++;flag=0;x=0;}elseif(isdigit(ch)==1||isalpha(ch)==1||ch=='_')x++;}elseif(isdigit(ch)==1){table[i].token[x]=ch;ch=fp.get();if(isdigit(ch)==1)x++;elseif(ch=='.'&&flag==0){table[i].token[++x]=ch;flag=1;x++;ch=fp.get();}elseif(ch=='.'&&flag==1){cout(linenum)errorendl;f(linenum)errorendl;error++;flag=0;}if(isdigit(ch)==0){table[i].token[++x]='\0';i++;x=0;flag=0;}}elseif(ch=='_'){table[i].token[x]=ch;ch=fp.get();if(isalpha(ch)==1||isdigit(ch)==1||ch=='_')x++;else{table[i].token[++x]='\0';i++;}}else{charch2=fp.get();if(ist(ch,ch2)==1){table[i].token[0]=ch;table[i].token[1]=ch2;table[i].token[2]='\0';x=0;i++;ch=fp.get();}else{table[i].token[0]=ch;table[i].token[1]='\0';x=0;i++;ch=ch2;}}}for(j=0;ji;j++){intn=typenum(table[j].token);table[j].type=n;}couterrorerror(s)endl;ferrorerror(s)endl;f----------------endl;cout----------------endl;for(j=0;ji;j++){couttable[j].token\t\t;ftable[j].token\t\t;sf(table[j].type);}}2.语法分析器1).自顶向下的LL（1）分析2).先求first、follow、select集构造分