高分编译技术课程设计报告.doc

1、编译技术课程设计报告华中科技大学软件学院编译技术课程设计报告实验名称 C/C+语言编译器设计 姓名 学号 班级 指导教师 2010年 11月 22日编译技术课程设计报告一、 实验题目实验概述：用C语言对下述文法和单词表定义的语言设计编制一个编译器。具体要求：1） 单词符号及种别表单词符号种别编码单词值main1int 2float3double4char5if 6else 7do8while9l(l|d)*10内部字符串 ( +|-| ) d*(.dd* | )( e ( +|-| ) dd*|) 20二进制数值表示=21+22- 23* 24/ 25(26)272829,30;3132=33

2、34=35=36!=37单词符号及其种别表 2） 语法结构定义 := main() := :=;:=|:=ID=:=ifelse :=do while := := +|- := *|/ :=ID|num|()num:= ( +|-| ) 数字*(.数字数字* | )( e ( +|-| ) 数字数字*|)ID:=字母(字母|d数字)*字母:=a|b|c|z|A|B|C|Z数字:=0|1|2|9 := |=|=|!=二、 实验目的1) 通过该课程设计,熟练应用编译原理的基本理论和方法2) 学会用C/C+高级程序设计语言设计一个编译器的技术3) 加深对编译原理的分析理论的理解，培养动手实践能力4)

3、 通过设计、编制、调试一个编译器，掌握其设计方法和技术，提高解决实际问题的综合素质三、 实验要求处理用户提交的符合上述文法的源代码序列，生成四元式中间代码或X86平台上的目标代码。四、 实验步骤1) 画出识别上述语言单词的状态转换图2) 用C/C+语言编写词法分析程序（应考虑能被语法分析程序调用）3) 预处理，去除注释、多余空格、回车换行符等4) 设计实现语法分析程序(调用上述词法程序分析单词)5) 设计构造属性文法及中间代码序列结构6) 采用语法制导翻译法，完成语义分析程序设计，生成四元式中间代码7) 或将生成的四元式中间代码转换成X86平台上的目标代码8) 设计若干用例，上机测试并通过所设

4、计实现的编译器五、 实验方案设计实现1. 总体设计思想本课设的任务是完成一个完整的编译器，处理用户提交的符合所定文法的源程序代码，生成四元式中间代码，进而翻译成等价的X86平台上汇编语言的目标程序。编译程序的工作过程划分为下列5个过程：词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码生成。其中，词法分析阶段的基本任务是从以字符串表示的源程序中识别出具有独立意义的单词符号，并以二元组的形式输出，以作为语法分析阶段的输入。语法分析阶段的基本任务是将词法分析阶段产生的二元组作为输入，根据语言的语法规则，识别出各种语法成分，并判断该单词符号序列是否是该语言的一个句子。语义分析的任务是首先

5、对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式 (本课设采用四元式) 来描述这种语义。代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。目标代码生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码（本课设生成汇编指令代码）。在词法分析阶段，通过DOS环境手动输入字符串序列（以#作为结束标志）作为带分析的源程序，调用词法扫描子程序将字符串以二元组的形式输出（若有不属于该语言单词符号出现，则进行出错处理），词法扫描子程序包括了对源程序的预处理（忽略多余空格、回车换行符等空白字符），以及对单词的

6、识别和分类，以形成（单词种别，单词自身的值）形式的二元组，并将用户自定义变量信息存入程序变量信息表。在语法分析阶段，采用自上而下的递归下降分析法，从文法的开始符号出发，根据文法规则正向推导出给定句子。根据递归下降分析函数编写规则来编写相应的函数，在各个函数的分析过程中调用词法分析程序中的扫描程序，发出“取下一个单词符号”的命令，以取得下一个单词符号作语法分析。在语义分析和中间代码生成阶段，采用语法制导翻译法,使用属性文法为工具来描述程序设计语言的语义。首先审查词法分析得到的每个语法结构的静态语义，如果静态语义正确再生成中间代码（本课设中采用四元式）。使用属性文法作为描述程序设计语言语义的工具，

7、采用语法制导翻译法完成对语法成分的翻译工作，即在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译。目标代码生成是编译程序的最后一个阶段，根据符号表等信息，将中间代码转化为等价的目标代码。为减少访问计算机内存的次数，应尽可能把基本块内还要被引用的变量放到寄存器中，而把基本块内不用的变量所占的寄存器释放。为了随时掌握寄存器的使用情况和变量的存放情况，以便生成适当地目标代码，可以建立寄存器描述表和变量地址描述表。在编译程序的各个阶段中都要涉及到表格管理和错误处理。编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所

8、产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息（本课设中建立了程序变量信息表，变量地址描述表，寄存器描述表）。一个好的编译程序在编译过程中，应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正，因此，在编译程序中还必须有一个出错处理程序。实验的整体设计思想可由以下图示表示： 编译器基本模块设计2. 详细算法设计（包括分析表设计）a) 词法分析器词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，根据语言 的词法规则识别出一个一个具有独立意义的单词符号，包括关键字，标识符，常数，运算符，分界符。词法分析程序所输出的单词符号表

9、示成如下的二元式：（单词种别整数码，单词自身的值）其中，基本字、运算符和界符都是一符一种，标识符自身的值用自身的字符串表示，常数自身的值用常数本身的值表示；构造出识别语言单词符号的有穷自动机,根据单词符号的状态转换图就可构造出识别语言单词符号的词法分析程序。 词法分析程序中涉及的两个正规式： l ( l | d ) * ( +|-| ) dd*(.dd* | )( e ( +|-| ) dd*|) 词法分析程序状态转换图：l|d非l非d其他=！31129301；，281271261251)(*24123221211非=非=1611711514113112dd-+eedd.dd-+1011198

10、765432l10b) 语法分析器（递归下降法） 采用自上而下的递归下降分析法，从文法的开始符号出发，根据文法规则正向推导出给定句子。对文法中的每个非终结符编写一个函数 (或子程序), 每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用。 为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写，完成相应非终结符匹配，通过所有子程序的相互调用，完成整个终结符号串的分析。(1) 当遇到终结符a时，则编写语句 if (当前读来的输入符号=a)

11、 读下一个输入符号； (2) 当遇到非终结符A时，则编写语句调用 A( )；(3) 当遇到规则A 时，则编写语句if (当前读来的输入符号FOLLOW(A) error( )；递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。语法结构定义采用扩充的BNF表示法,避免了直接左递归规则，并且也没有公共左因子。对于非终结符E T +T ，函数T( )用while语句描述如下：T ( ) F ( ); while ( sym = =*) Scanner ( ); F ( ); c) 语义分析和中间代码生成器（语法制导翻译法）1 语义分析的任务：1)静态语义审查：审查每个语法结构

12、的静态语义,即验证语法结构合法的程序,是否真正有意义。2)执行真正的翻译：如果静态语义正确, 语义处理则要执行真正的翻译, 即生成程序的某种中间代 码的形式或直接生成目标代码。2语法制导翻译法的基本思想为文法的每个产生式都配备一个语义动作或语义子程序。 在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作, 从而实现语义处理。在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译。3 属性文法和语义规则语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。属性文法包含一个上下文无关文法和一系列语义规则（

13、为文法的每一个规则配备的计算属性的计算规则）。这些语义规则附在文法的每个产生式上,在语法分析过程中, 执行语义规则描述的动作, 从而实现语义处理。也就是说, 附在文法的每个产生式上语义规则描述了语义处理的加工动作。4 四元式中间代码结构四元式主要由四部分组成：（OP，arg1, arg2, result）其中OP是运算符；arg1,arg2分别是第一和第二两个运算对象（当OP是一目运算时，常常将运算对象定义为arg1）；result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。 5 采用自下而上的语法制导翻译法语义动作的设计 (1)自下而上

14、的语法制导翻译特点：栈顶形成句柄，归约时执行相应语义动作文法翻译到四元式的语义描述： 1) 语义变量 place 表示存放非终结符E值的变量名或其数值。 2) 语义函数 gen(op,argv1,argv2,result)功能是生成一个四元式。 3) 语义函数 NewTemp()功能是产生一个新的临时变量名字，如T1，T2等。 4) 语义变量 index 为四元式序列指针。 5) 语义变量 真出口etc和假出口efc真(假)出口表示布尔表达式C为真(假)时控制流向的转移目标，布尔表达式的真(假)出口不能在产生其四元式的同时得知，因此设置两个语义变量C.etc:记录表达式 C 所对应的四元式需回

15、填真出口的四元式的地址所构成的链C.efc:记录表达式 C 所对应的四元式需回填假出口的四元式的地址所构成的链 6) 语义变量 语句出口chain 在翻译语句时，其出口的转向点通常不能确定，用链表记录这些出口的位置，以便在适当的时机回填。S.chain表示语句S全部出口组成的链即出口链，以待一次性回填。 7) 语义变量 语句入口head 使用语义变量 LS.head 记录while语句首地址，即对应的第一个四元式语句序号，以回填转移地址,。 8) 链接函数 merg(p1,p2) 功能是把以 p1, p2为链首的两条链合并为一, 返回合并后的链首； 9) 回填函数 bp(p,t)功能是将 p

16、所链结的每个四元式的第四区分量都回填 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.place

17、2,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.et

18、c,LS.head);bp(C.efc,index);CS.chain=merge(B.chain,C.efc)bp(CS.chain,index);d) 目标代码生成 采用汇编语言代码作为目标代码生成器的输出，在四元式序列中有3类量，常量，程序变量和临时变量。一般地，常量对应立即数出现在目标指令中；程序变量是程序中用户自定义变量，通常是存放在存储单元中的存储器变量，在数据段定义为同名字变量（使用伪指令DW）；而临时变量则是在生成四元式时由编译程序引进的，因为寄存器变量的存取比存储变量的存取快得多，因此，为临时变量安排寄存器。1 寄存器描述表和地址描述表为了反映寄存器使用情况及变量值的存放情况

19、，引进寄存器描述表registerStatus与地址描述表registerT。寄存器描述表动态反映了寄存器的使用状态，即寄存器是处于空闲状态还是被临时变量占用，以便分配寄存器给临时变量。由于本课设中程序变量存储在内存中，源代码单语句内所有临时变量都为语句出口后的非活跃变量，因此，每执行完一条源代码语句，可视作寄存器中内容不再使用，描述符清零。地址描述表指明临时变量所在的寄存器，寄存器描述符为字符串数组，索引为临时变量编号，可能多个临时变量同存在一寄存器。2 目标指令与四元式编号对照表控制转移指令分两种:条件控制转移(goto +op,argv1,argv2,Lable)和无条件控制转移(got

20、o,Lable)。往往在生成目标代码的时候还不了解控制转移到的目标指令的编号，因此需要回填。为此，引进目标指令与四元式编号对照表lable，lablei反应了四元式i对应的若干目标指令中第一条的编号，在生成目标代码时在第四分量中只填入四元式编号i，待所有目标指令完全生成后再统一回填lablei。3 寄存器分配函数 寄存器的分配由函数char* GetfreeR() 实现。为当前值不在寄存器的临时变量分配空闲寄存器。4 四元式对应目标代码根据四元式生成规则,1中argv2为程序变量，2,3,4,5中res为首次出现的临时变量Ti，6,7中label为语句标号Li。序号四元式目标代码备注1(=,a

21、rgv1,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,a

22、rgv1 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)P

23、USH 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) CM

24、P 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

25、(余数)）比较指令：CMP OPD,OPS转移指令： JE 相等转移JNE 不相等转移JG 大于转移JGE 大于或等于转移JL 小于转移JLE 小于或等于转移JMP 无条件转移指令限制：(1)目的操作数不能是立即操作数；(2)操作结束后，运算结果送人目的地址中；(3)源操作数和目的操作数不能同时为存储器操作数；(4)IMUL OPD,OPS中OPD为寄存器(5)IDIV OPS中OPS不能是立即操作数3. 流程框图1) 词法分析器变量初始化忽略空白符返回 是否“#”拼字符串拼数对不同符号给出相应的syn值Syn=10Syn=20是否关键字Syn为对应关键字的种别码报错返回是字母数字其他符号运算

26、符、界符等是否否 scaner()函数流程图2) 语法分析器 （递归下降法） P()函数流程图 B()函数流程图 SS()函数流程图 3) 语义分析及中间代码生成初始化:flag,nVar,index,nSuffix置0 Parse()函数流程图4) 目标代码生成4. 函数相关说明1) 词法分析部分函数 Scaner( );识别源程序的一个单词符号词法分析程序所用的全局变量如下：rwtab 关键字对应到编码值的映射表。prog 字符数组，存放源程序ch 字符变量，存放当前读进的源程序字符。syn 整型，当前单词种别编码token 字符数组, 存放当前构成单词符号的字符串。sum 双精度型，存放当前常量的数值。variable 用户自定义变量信息表。flag 1表示刚读取一个变量或常数，+/-为运算符; 0反之，+/-可能为数值符号将从键盘输入的字符串存储到prog数组，用scaner()函数从prog中取出有独立意义的字符串存到token中：1、 首字符为字母，且其后为字母与数字的组合，syn对应到码值10，进一步检查此组合字符串是否在关键字表