[计算机软件及应用]编译原理课设实验报告.doc

编译技术课程设计报告编译技术课程设计报告实验名称 编译器设计 姓名 学号 班级 本课设的任务是完成一个完整的编译器，处理用户提交的符合所定文法的源程序代码，生成四元式中间代码，进而翻译成等价的X86平台上汇编语言的目标程序。编译程序的工作过程划分为下列5个过程：词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码生成。其中，词法分析阶段的基本任务是从以字符串表示的源程序中识别出具有独立意义的单词符号，并以二元组的形式输出，以作为语法分析阶段的输入。语法分析阶段的基本任务是将词法分析阶段产生的二元组作为输入，根据语言的语法规则，识别出各种语法成分，并判断该单词符号序列是否是该语言的一个句子。语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式 (本课设采用四元式) 来描述这种语义。代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码（本课设生成汇编指令代码）。在词法分析阶段，通过DOS环境手动输入字符串序列（以#作为结束标志）作为带分析的源程序，调用词法扫描子程序将字符串以二元组的形式输出（若有不属于该语言单词符号出现，则进行出错处理），词法扫描子程序包括了对源程序的预处理（忽略多余空格、回车换行符等空白字符），以及对单词的识别和分类，以形成（单词种别，单词自身的值）形式的二元组，并将用户自定义变量信息存入程序变量信息表。在语法分析阶段，采用自上而下的递归下降分析法，从文法的开始符号出发，根据文法规则正向推导出给定句子。根据递归下降分析函数编写规则来编写相应的函数，在各个函数的分析过程中调用词法分析程序中的扫描程序，发出“取下一个单词符号”的命令，以取得下一个单词符号作语法分析。在语义分析和中间代码生成阶段，采用语法制导翻译法,使用属性文法为工具来描述程序设计语言的语义。首先审查词法分析得到的每个语法结构的静态语义，如果静态语义正确再生成中间代码（本课设中采用四元式）。使用属性文法作为描述程序设计语言语义的工具，采用语法制导翻译法完成对语法成分的翻译工作，即在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译。目标代码生成是编译程序的最后一个阶段，根据符号表等信息，将中间代码转化为等价的目标代码。为减少访问计算机内存的次数，应尽可能把基本块内还要被引用的变量放到寄存器中，而把基本块内不用的变量所占的寄存器释放。为了随时掌握寄存器的使用情况和变量的存放情况，以便生成适当地目标代码，可以建立寄存器描述表和变量地址描述表。在编译程序的各个阶段中都要涉及到表格管理和错误处理。编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息（本课设中建立了程序变量信息表，变量地址描述表，寄存器描述表）。一个好的编译程序在编译过程中，应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正，因此，在编译程序中还必须有一个出错处理程序。实验的整体设计思想可由以下图示表示： 编译器基本模块设计词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，根据语言 的词法规则识别出一个一个具有独立意义的单词符号，包括关键字，标识符，常数，运算符，分界符。词法分析程序所输出的单词符号表示成如下的二元式：（单词种别整数码，单词自身的值）其中，基本字、运算符和界符都是一符一种，标识符自身的值用自身的字符串表示，常数自身的值用常数本身的值表示；构造出识别语言单词符号的有穷自动机,根据单词符号的状态转换图就可构造出识别语言单词符号的词法分析程序。 词法分析程序中涉及的两个正规式： l ( l | d ) * ( +|-| ) dd*(.dd* | )( e ( +|-| ) dd*|) 词法分析程序状态转换图：l|d非l非d其他=！31129301；，281271261251)(*24123221211非=非=1611711514113112dd-+eedd.dd-+1011198765432l10a) 语法分析器（递归下降法） 采用自上而下的递归下降分析法，从文法的开始符号出发，根据文法规则正向推导出给定句子。对文法中的每个非终结符编写一个函数 (或子程序), 每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用。 为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写，完成相应非终结符匹配，通过所有子程序的相互调用，完成整个终结符号串的分析。(1) 当遇到终结符a时，则编写语句 if (当前读来的输入符号=a) 读下一个输入符号； (2) 当遇到非终结符A时，则编写语句调用 A( )；(3) 当遇到规则A 时，则编写语句if (当前读来的输入符号FOLLOW(A) error( )；递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。语法结构定义采用扩充的BNF表示法,避免了直接左递归规则，并且也没有公共左因子。对于非终结符E T +T ，函数T( )用while语句描述如下：T ( ) F ( ); while ( sym = =*) Scanner ( ); F ( ); b) 语义分析和中间代码生成器（语法制导翻译法）1 语义分析的任务：1)静态语义审查：审查每个语法结构的静态语义,即验证语法结构合法的程序,是否真正有意义。2)执行真正的翻译：如果静态语义正确, 语义处理则要执行真正的翻译, 即生成程序的某种中间代 码的形式或直接生成目标代码。2语法制导翻译法的基本思想为文法的每个产生式都配备一个语义动作或语义子程序。 在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作, 从而实现语义处理。在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译。3 属性文法和语义规则语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。属性文法包含一个上下文无关文法和一系列语义规则（为文法的每一个规则配备的计算属性的计算规则）。这些语义规则附在文法的每个产生式上,在语法分析过程中, 执行语义规则描述的动作, 从而实现语义处理。也就是说, 附在文法的每个产生式上语义规则描述了语义处理的加工动作。4 四元式中间代码结构四元式主要由四部分组成：（OP，arg1, arg2, result）其中OP是运算符；arg1,arg2分别是第一和第二两个运算对象（当OP是一目运算时，常常将运算对象定义为arg1）；result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。 5 采用自下而上的语法制导翻译法语义动作的设计 (1)自下而上的语法制导翻译特点：栈顶形成句柄，归约时执行相应语义动作文法翻译到四元式的语义描述： 1) 语义变量 place 表示存放非终结符E值的变量名或其数值。 2) 语义函数 gen(op,argv1,argv2,result)功能是生成一个四元式。 3) 语义函数 NewTemp()功能是产生一个新的临时变量名字，如T1，T2等。 4) 语义变量 index 为四元式序列指针。 5) 语义变量 真出口etc和假出口efc真(假)出口表示布尔表达式C为真(假)时控制流向的转移目标，布尔表达式的真(假)出口不能在产生其四元式的同时得知，因此设置两个语义变量C.etc:记录表达式 C 所对应的四元式需回填真出口的四元式的地址所构成的链C.efc:记录表达式 C 所对应的四元式需回填假出口的四元式的地址所构成的链 6) 语义变量 语句出口chain 在翻译语句时，其出口的转向点通常不能确定，用链表记录这些出口的位置，以便在适当的时机回填。S.chain表示语句S全部出口组成的链即出口链，以待一次性回填。 7) 语义变量 语句入口head 使用语义变量 LS.head 记录while语句首地址，即对应的第一个四元式语句序号，以回填转移地址,。 8) 链接函数 merg(p1,p2) 功能是把以 p1, p2为链首的两条链合并为一, 返回合并后的链首； 9) 回填函数 bp(p,t)功能是将 p 所链结的每个四元式的第四区分量都回填 t ; (2) 非终结符语义动作：1) := *|/即TF|T*F|T/FTF T.place=F.placeTT*F T.place=NewTemp();gen(*,T1.place,F.place,T.place)TT/FT.place=NewTemp();gen(/,T1.place,F.place,T.place)2) := +|-即ET|E+T|E+T同1)3) :=， := |=|=|!= 即CE op E,op|=|=|!= C.etc=index; C.efc=index+1; gen(goto +op,E1.place1,E2.place2,0); gen(goto,0);4) :=ID=即ASID=Egen(=,E.place,ID); bp(AS.chain,index);5) :=ifelse 即CSif C B |if C B else Bbp(C.etc,index);CS.Chain=C.efc;.(B()CS.chain=merge(B1.chain,index);gen(goto,0);bp(C.efc,index);.(B()CS.chain=merge(B2.chain,CS.chain)6) :=do while 即LSdo B while CLS.head=index;.(B().(C()bp(C.etc,LS.head);bp(C.efc,index);CS.chain=merge(B.chain,C.efc)bp(CS.chain,index);c) 目标代码生成 采用汇编语言代码作为目标代码生成器的输出，在四元式序列中有3类量，常量，程序变量和临时变量。一般地，常量对应立即数出现在目标指令中；程序变量是程序中用户自定义变量，通常是存放在存储单元中的存储器变量，在数据段定义为同名字变量（使用伪指令DW）；而临时变量则是在生成四元式时由编译程序引进的，因为寄存器变量的存取比存储变量的存取快得多，因此，为临时变量安排寄存器。1 寄存器描述表和地址描述表为了反映寄存器使用情况及变量值的存放情况，引进寄存器描述表registerStatus与地址描述表registerT。寄存器描述表动态反映了寄存器的使用状态，即寄存器是处于空闲状态还是被临时变量占用，以便分配寄存器给临时变量。由于本课设中程序变量存储在内存中，源代码单语句内所有临时变量都为语句出口后的非活跃变量，因此，每执行完一条源代码语句，可视作寄存器中内容不再使用，描述符清零。地址描述表指明临时变量所在的寄存器，寄存器描述符为字符串数组，索引为临时变量编号，可能多个临时变量同存在一寄存器。2 目标指令与四元式编号对照表控制转移指令分两种:条件控制转移(goto +op,argv1,argv2,Lable)和无条件控制转移(goto,Lable)。往往在生成目标代码的时候还不了解控制转移到的目标指令的编号，因此需要回填。为此，引进目标指令与四元式编号对照表lable，lablei反应了四元式i对应的若干目标指令中第一条的编号，在生成目标代码时在第四分量中只填入四元式编号i，待所有目标指令完全生成后再统一回填lablei。3 寄存器分配函数 寄存器的分配由函数char* GetfreeR() 实现。为当前值不在寄存器的临时变量分配空闲寄存器。4 四元式对应目标代码根据四元式生成规则,1中argv2为程序变量，2,3,4,5中res为首次出现的临时变量Ti，6,7中label为语句标号Li。序号四元式目标代码备注1(=,argv1,argv2)(1)MOV R,argv1 MOV argv2,R(2)MOV argv2,R(1) argv1为现行值不在寄存器的临时变量，R是新分配给argv1的寄存器(2) argv1 为立即数或现行值在寄存器R的临时变量2(+,argv1,argv2,res)(1)MOV R,argv1 ADD R,argv2(2)ADD R,argv2(1)argv1 现行值不在寄存器，R是新分配给argv1的寄存器,对res=Ti置registerTi=R(2)argv1 现行值在寄存器R,对res=Ti置registerTi=R3(-,argv1,argv2,res)(1)MOV R,argv1 SUB R,argv2(2)SUB R,argv2(1)argv1 现行值不在寄存器，R是新分配给argv1的寄存器,对res=Ti置registerTi=R(2)argv1 现行值在寄存器R,对res=Ti置registerTi=R4(*,argv1,argv2,res)(1)MOV R,argv1 IMUL R,argv2(2)IMUL R,argv2(1)argv1 现行值不在寄存器，R是新分配给argv1的寄存器,对res=Ti置registerTi=R(2)argv1 现行值在寄存器R,对res=Ti置registerTi=R5(/,argv1,argv2,res)(1)PUSH AX(2)PUSH DX(1)MOV AX,argv1 CWD(3)MOV R,argv2(3)IDIV R(4)IDIV argv2(2)POP DX(1)POP AX(1)argv1 现行值不在AX且AX被占用(2)DX被占用(3)argv2 为立即数（常量）(4)argv2为临时变量（寄存器变量）或程序变量（存储器变量）对res=Ti置registerTi=R6(goto,label)JMP Label对于label=LiLabel=L+atoi(labeli)7(goto op,argv1,argv2,label)(1)MOV R,argv1 CMP R,argv2(2) CMP R,argv2(3) CMP argv1,argv2 JX Label(1)argv1为立即数(常量)或argv1,argv2同为存储器操作数(程序变量)(2)argv1 现行值在寄存器R(Op,JX)=(=,JE)|(!=,JNE)|(=,JGE)|(,JG)|(=,JLE)|(,JL)说明：使用到的80X86宏汇编指令：一般传送指令MOV OPD,OPS将字转换成双字指令(将AX中的符号扩展至DX中)：CBW加指令：ADD OPD,OPS减指令：SUB OPD,OPS有符号乘指令：IMUL OPD,OPS有符号除指令：IDIV OPS（字除法：（DX,AX）/(OPS)AX(商),DX(余数)）比较指令：CMP OPD,OPS转移指令： JE 相等转移JNE 不相等转移JG 大于转移JGE 大于或等于转移JL 小于转移JLE 小于或等于转移JMP 无条件转移指令限制：(1)目的操作数不能是立即操作数；(2)操作结束后，运算结果送人目的地址中；(3)源操作数和目的操作数不能同时为存储器操作数；(4)IMUL OPD,OPS中OPD为寄存器(5)IDIV OPS中OPS不能是立即操作数1. 流程框图1) 词法分析器变量初始化忽略空白符返回 是否“#”拼字符串拼数对不同符号给出相应的syn值Syn=10Syn=20是否关键字Syn为对应关键字的种别码报错返回是字母数字其他符号运算符、界符等是否否 scaner()函数流程图2) 语法分析器 （递归下降法） P()函数流程图 B()函数流程图 SS()函数流程图 3) 语义分析及中间代码生成初始化:flag,nVar,index,nSuffix置0 Parse()函数流程图4) 目标代码生成2. 函数相关说明1) 词法分析部分函数 Scaner( );识别源程序的一个单词符号词法分析程序所用的全局变量如下：rwtab 关键字对应到编码值的映射表。prog 字符数组，存放源程序ch 字符变量，存放当前读进的源程序字符。syn 整型，当前单词种别编码token 字符数组, 存放当前构成单词符号的字符串。sum 双精度型，存放当前常量的数值。variable 用户自定义变量信息表。flag 1表示刚读取一个变量或常数，+/-为运算符; 0反之，+/-可能为数值符号将从键盘输入的字符串存储到prog数组，用scaner()函数从prog中取出有独立意义的字符串存到token中：1、 首字符为字母，且其后为字母与数字的组合，syn对应到码值10，进一步检查此组合字符串是否在关键字表中，若在其中，则修改syn对应到相应码值；2、 数字串的组合中：整数数字串、小数数字串码值、（含有字母e）指数数字串，将其二进制数值存入sum；3、 其他符号先判断是否为符号组合一部分，若为符号组合，则继续扫描，syn应到相应码值；若为单个符号，则回退，syn对应到相应码值。main()：先从键盘输入待编码字符串，存入prog中，用#判断是否输入结束，然后调用scaner()函数，得到对应码值，有print函数显示输出。d) 语法分析部分 （递归下降法）(1)函数 Scaner( ) 功能: 读进源程序的下一个单词符号 并将它放在全程变量sym。(2) 函数 error( ) 功能: 出错处理程序。 数组prog、token、rwtab，函数scanner()作用同上。 递归下降算法分析：调用scaner()函数，对应出码值若不为0，则报错；然后调用语句串分析函数；判断是否含有end；若含有则再次调用scaner()函数，对应得相应码值；判断是否由#提示结束；若是，则打印分析成功，若否则转报错处理。3. 输入与输出（包括出错处理）a) 词法分析程序词法分析程序的输入是字符串形式的源程序，词和词之间可以用空白字符（空格、回车、制表符）隔开。词法分析程序的输入是一个二元组，形式为：（单词种别码，单词自身的值）。若输入的字符串带有不合法的字符，则对应的字符（串）在输出中不以二元组的形式显示，而以“error!”表示出错。例如：输入main while if 123.455e+123#输出：（1,main） (9,while) (6,if) (20,1.23455e+125)(0,#)b) 语法分析程序语法分析程序的输入与词法分析的输入一致，即字符串形式的源程序，词和词之间可以用空白字符（空格、回车、制表符）隔开。语法程序的输出是判断所输入字符串是否是该语言的句子的结果，也即“success！”或者“fail！”，分别表示所输入的字符串是该语言的一个句子和字符串不是该语言的一个句子。出错时结果为“fail！”。例如：输入123.345e+123+(1*3+(2+4)/212)+12# 结果为“success！”4. 程序运行结果（屏幕截图）5. 编译器使用说明语法分析器的输入为字符串形式的源程序，词与词之间可以用空白字符（空格、回车、制表符）隔开；语法程序的输出是判断所输入字符串是否是该语言的句子的结果，也即“success！”或者“fail！”，分别表示所输入的字符串是该语言的一个句子和字符串不是该语言的一个句子。是则输出“success”,出错则输出“fail”。6. 心得与体会大部分系统软件和应用软件的开发，通常要用到编译的原理和技术。设计词法分析器的串匹配技术已用于正文编辑器、信息检索系统和模式识别程序; 上下文无关文法和语法制导定义已用于创建诸如排版、绘图系统和语言结构化编辑器中，代码优化技术已用于程序验证器和从非结构化的程序产生结构化程序的编程之中。通过动手编写程序对词法语法的分析有了更加深入的体会，巩固了编译原理的基本知识，亲自动手实践编译程序，使我对编译更加感兴趣。此次实验只是实现了编译器最基本的功能，不由得感叹实际的编译器实在太强大了！继续认真学习，勤于思考，学习编译中的精妙思想，做好课设！7. 源程序清单#include stdafx.h#include #include #include #include #include #include /*/* 词法分析 */*/#define max 10char *rwtab9 = main,int,float,double,char,if,else,do,while;char prog100;/源程序int p;/当前处理字符位置char ch; /当前处理字符int flag; /1表示刚读取一个变量或常数，+/-为运算符;0反之，+/-可能为数值符号int syn; /种别编码char tokenmax; /保留字、内部字符串或操作符double sum; /数值char* variable;/变量信息表int nVar;/*/void scaner() int i; for(i=0;imax;i+) tokeni=0; sum=0; int m=0; int e=0;/数值指数 ch=progp+; while(isspace(ch) ch=progp+;/预处理，去除注释、多余空格、回车换行符等 if(isalpha(ch)/保留字、内部字符串 while(isalnum(ch) tokenm+=ch; ch=progp+; tokenm+=0; p-; syn=10; for(i=0;i9;i+) if(strcmp(token,rwtabi)=0) syn=i+1; flag=0; break; if(syn=10) flag=1; for (i=1;i=nVar;i+) if (!strcmp(token,variablei) return; strcpy(variable+nVar,token); else if (ch = +| ch = - | isdigit(ch)/数值、+、- if (!isdigit(ch)&(flag = 1|!isdigit(progp) tokenm+=ch; if (ch = +) syn =22; else syn = 23; flag = 0; else int flag1 = 0; int flag2 = 0; if(ch = +| ch = -) ch=progp+; if(ch = -) flag1=1; while(isdigit(ch) sum=sum*10+ch-0; ch=progp+; int k=10; if(ch=. & isdigit(progp) ch=progp+; while(isdigit(ch) double d=ch-0; sum=sum+d/k; k=k*10; ch=progp+; if(ch=e | ch=E) char ch_tmp=progp; if(ch_tmp=+ | ch_tmp=-) & isdigit(progp+1) | isdigit(ch_tmp) ch=progp+; if(!isdigit(ch) if(ch=+) flag2=0; else flag2=1; ch=progp+; while(isdigit(ch) e=e*10+ch-0; ch=progp+; if(flag2) sum=sum*pow(10.0,-e); else sum=sum*pow(10.0,e); if(flag1) sum*=(-1); p-; syn=20; flag=1; else/运算符、分隔符 flag = 0; m=0; switch(ch) case : tokenm+=ch; ch=progp+; if(ch=) syn=33; tokenm+=ch; else syn=32; p-; break; case =: tokenm+=ch; ch=progp+; if(ch=) syn=36; tokenm+=ch; else syn=21; p-; break; case !: tokenm+=ch; ch=progp+; if(ch=) syn=37; tokenm+=ch; else syn=-1; break; case *: syn=24; token0=ch; break; case /: syn=25; token0=ch; break; case (: syn=26; token0=ch; break; case ): syn=27; token0=ch; break; case : syn=28; token0=ch; break; case : syn=29; token0=ch; break; case ,: syn=30; token0=ch; break; case ;: syn=31; token0=ch; break; case #: syn=0; token0=ch; break; default: syn=-1; printf(illegal character %c/n,ch); return ;/*/* 语法语义分析 */*/ 递归下降法 /void P (); /程序void B (int *nChain); /语句块void SS(int *nChain); /语句串void S (int *nChain); /语句void AS(int *nChain); /赋值语句void CS(int *nChain); /条件语句void LS(int *nChain); /循环语句void C (int *etc,int *efc); /条件char * E (); /表达式char * T (); /项char * F (); /因子void error(); /出错处理/ 语法制导翻译 /typedef struct quaternion char opmax; char argv1max; char argv2max; char resmax;quad;/四元式quad *pQuad;/四元式组指针int index,nSuffix;/四元式编号,临时变量编号/*/void gen(char *op,char *argv1,char *argv2,char *result);char *NewTemp();int merg(int p1,int p2);void bp(int p,int t);void printQuad();void Parse();/*/void error() if (syn=20) printf(Syntax error before %g,sum); else printf(Syntax error before %g,token); syn=50;/ := main() void P() int nChain; scaner(); if (syn = 1) scaner(); if(syn = 26) scaner(); if (syn = 27) scaner(); B(&nChain); else error(); else error(); else error(); / := void B(int *nChain) if (syn=28) scaner(); SS(nChain); if (syn = 29) scaner(); else error()