编译原理课程设计报告

1课程设计报告设计题目：简单文法的编译器的设计与实现班级：计算机1206组长学号：20123966组长姓名：苏君君指导教师：李晓华设计时间：2014年12月2设计分工组长学号及姓名：20123966苏君君分工：中间代码，中间代码优化，目标代码，可视化组员1学号及姓名：20123981王奉楠分工：扫描器组员2学号及姓名：20123971王正海分工：语法制导翻译3摘要编译原理是计算机科学与技术专业一门重要的专业课,它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端4目录摘要.....................................................31.概述..................................................62.课程设计任务及要求....................................82.1设计任务..........................................82.2设计要求..........................................93.算法及数据结构.......................................103.1算法的总体思想....................................103.2词法分析器模块....................................113.2.1功能..........................................113.2.2数据结构......................................113.2.3算法..........................................123.3语法分析器模块....................................133.3.1功能..........................................133.3.2数据结构......................................133.3.3算法..........................................143.4中间代码产生器模块................................243.4.1功能..........................................243.4.2数据结构......................................243.4.3算法..........................................253.5优化器模块........................................273.5.1功能..........................................273.5.2数据结构......................................273.5.3算法..........................................283.6目标代码生成器模块................................303.6.1功能...........................................303.6.2数据结构.......................................303.6.3算法...........................................3154.程序设计与实现.........................................324.1程序流程图.........................................324.2程序说明...........................................334.3实验结果...........................................355.结论...................................................426.参考文献...............................................437.收获、体会和建议.......................................4461概述在计算机上执行一个高级语言程序一般要分为两步；第一步，用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。在学习《编译原理》课程过程中，逐渐掌握各章节构造编译程序的基本理论，并能独立完成词法分析器、语法分析器和语义分析器实验，在基本实验完成的基础上，逐步完成课程设计。针对自己的理解和学习，实现一个小编译器括符号表的构造。编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码产生、优化、目标代码生成。第一阶段，词法分析。词法分析的任务是：输入源程序，对构成源程序的字符串进行分解和扫描，识别出一个个的单词或符号。我们设计了符号表，包括名字栏和信息栏，其中名字栏作为关键字，根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针，从符号表中删除给定名字的表项，并且设计了词法分析器，具体实现为设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；，能够拼出语言中的各个单词，将拼出的标识符填入符号表，返回识别单词或符号的种别码和属性值。第二阶段，语法分析。在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。我们实现了语法分析器，能够使用预测分7析法、递归下降分析法、算符优先分析法、SLR分析法实现对表达式、各种说明语句、控制语句进行语法分析。第三阶段，语义分析和中间代码产生。对语法分析所识别的各类语法范畴，分析其含义，并进行初步翻译(产生中间代码）。这一阶段包括两个方面的工作。首先，对每种语法范畴进行静态语义检查。如果语义正确，则依循语言的语义规则进行中间代码的翻译。第四阶段，优化。优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。例如公共子表达式的提取、循环优化、删除无用代码。第五阶段，目标代码生成，把中间代码变换成特定机器上的低级语言代码，有赖于硬件系统结构和机器指令含义来实现最后的翻译。在能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码。通过对编译器的设计实现，一方面再次熟悉了c语言的编程方法及思想，另一方面加深了而对所学编译知识的掌握和理解，也深刻的理解了编译器的思想和实现方法；从词法分析到语法分析，再到语义分析，整个独立而又紧密联系的环节，紧紧相扣，整体的实现理解的更加透彻。不过由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。82课程设计任务及要求2.1设计任务任务内容：①定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；②扫描器设计实现；③语法分析器设计实现；④中间代码设计；⑤中间代码生成器设计实现；⑥中间代码优化；⑦生成目标代码。分析完任务内容，我们制定出一套满足老师要求的语句的文法结构，具体内容如下（其中“？”代表空产生式）：程序--voidmain(){函数体}函数体--变量声明语句函数体|赋值语句函数体|if(表达式){函数体}[else{函数体}]函数体|while(表达式){函数体}函数体|?变量声明语句--类型标识符变量声明语句_1;类型--int|char|bool变量声明语句_1--,标识符变量声明语句_1|=表达式变量声明语句_1|?赋值语句--标识符=表达式;表达式--算数表达式逻辑表达式逻辑表达式--[=]算数表达式|[=]算数表达式|==算数表达式|and算数表达式|or算数表达式|not算数表达式|?（此处的[]代表可选）算数表达式（这个地方直接写出老师上课讲授的形式）：E--TE1E1--+TE1|-TE1|?9T--FT1T1--*FT1|/FT1|?F--标识符[常数]|(E)这个文法满足老师的要求，但是也存在一些不足，比如变量类型中没有处理实数，数组和结构体以及if语句和while语句后必须有大括弧匹配。2.2设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；103算法及数据结构3.1算法的总体思想词法分析器又称为扫描器，它的任务就是对输入的源程序进行词法分析输出单词符号供语法分析使用，语法分析器简称分析器，对单词符号串进行语法分析，根据语法规则进行推导，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析与中间代码产生器，按照语义规则对语法分析器推导出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器就是对中间代码进行优化处理。目标代码生成器，把中间代码翻译成目标程序。符号表用来登记源程序中出现的变量及其属性。另外，如果源程序有错误，编译发现错误，把有关错误信息报告给用户，即出错处理。流程图如下：源程序单词符号语法单位中间代码中间代码目标代码词法分析器语法分析器语义分析及中间代码产生器优化器目标代码生成器符号表出错处理113.2词法分析器模块3.2.1功能词法分析器功能室输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列5种。（1）关键字是由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。（2）标识符用来标示各种名字，如变量名，数组名，函数名等。（3）常数程序中出现用来运算的数值（4）运算符我们所定义的文法包括+，-，*，/算术运算符，还有and，or，not，=，，，=，==逻辑运算符。（5）界符程序中用来分割的符号。3.2.2数据结构一个程序语言的关键字，运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用都不加限制。词法分析器所输出的单词符号常常表示为二元式结构：（单词种别，单词符号的属性值）；相应的数据结构处理为如下表示：char*KeyWords[]={main,bool,int,char,v