东北大学编译原理课程设计报告

1课程设计报告设计题目：简单文法的编译器的设计与实现班级：XX组长学号：XXX组长姓名：XX指导教师：XX设计时间：2017年1月2设计分工组长学号及姓名：20143710李万分工：语法分析，生成符号表，语义分析，中间代码生成(四元式)，汇编代码生成组员1学号及姓名：20143724张太分工：部分语法分析组员2学号及姓名：20143725张天宝分工：部分语义分析组员3学号及姓名：20143722张俊杰3摘要编译原理是计算机科学与技术专业一门重要的专业课,它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端4目录摘要.....................................................31.概述..................................................62.课程设计任务及要求....................................72.1设计任务..........................................72.2设计要求..........................................83.算法及数据结构.......................................93.1算法的总体思想....................................103.2词法分析器模块....................................113.2.1功能..........................................113.2.2数据结构......................................113.2.3算法..........................................123.3语法分析器模块....................................143.3.1功能..........................................143.3.2数据结构......................................143.3.3算法..........................................153.4语义分析中间代码生成................................183.4.1功能..........................................183.4.2数据结构......................................183.4.3算法..........................................203.5目标代码生成器模块................................233.5.1功能...........................................233.5.2数据结构.......................................233.5.3算法...........................................254.程序设计与实现.........................................264.1程序流程图.........................................264.2程序说明...........................................274.3实验结果...........................................3255.结论...................................................596.参考文献...............................................607.收获、体会和建议........................................6161概述编译程序(compiler)是把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。几乎所有形式的计算都要用到编译器。程序运行的过程图如下图所示：程序运行过程编译程序的工作一般分为以下几个阶段:词法分析、语法分析、语义分析、中间代码产生、代码优化、目标代码产生。高级语言程序机器语言程序编译程序翻译运行结果语法分析器语义分析与中间代码生成器优化段目标代码生成器词法分析器语法单位四元式四元式目标代码单词符号72课程设计任务及要求2.1设计任务任务内容：1.定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；If语句、While语句等）支持函数调用，函数递归，支持传参和传值2.扫描器设计实现；3.语法分析器设计实现；4.中间代码设计；5.中间代码生成器设计实现；6.生成目标代码。文法：给出的文法具有左递归，消除左递归后得到的文法如下所示：1.program→declaration-list2.declaration-list→declaration{declaration}3.declaration→var-declaration|fun-declaration4.var-declaration→type-specifierID[NUM]5.type-specifier→int|void6.fun-declaration→type-specifierID(params)|compound-stmt7.params→params-list|void8.param-list→param{,param}9.param→type-specifierID[[]]10.compound-stmt→{local-declarationsstatement-list}11.local-declarations→empty{var-declaration}12.statement-list→empty{statement}13.statement→expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt14.expression-stmt→[expression];15.selection-stmt→if(expression)statement[elsestatement]16.iteration-stmt→while(expression)statement17.return-stmt→return[expression];18.expression→var=expression|simple-expression19.var→ID[expression]20.simple-expression→additive-expression[relopa8dditive-expression]21.relop→=|||=|==|!=22.additive-expression→term{addopterm}23.addp→+|-24.term→factor{mulopfactor}25.mulop→*|/26.factor→(expression)|var|call|NUM27.call→ID(args)28.args→arg-list|empty29.arg-list→expression{,expression}2.2设计要求通过设计C-语言的编译器，了解编译器在程序设计中的功能，以及编译过程中的翻译步骤，对编译原理的各个部分有一个深入的了解和学习。93算法及数据结构3.1算法的总体思想如下流程图：源程序单词符号语法单位中间代码中间代码目标代码词法分析器语法分析器语义分析及中间代码产生器目标代码生成器符号表出错处理103.2词法分析器模块3.2.1功能根据给出的C-语言词法、语法和语义，设计一个编译器。1.下面是语言的关键字：elseifintreturnvoidwhile，write,read.所有的关键字都是保留字，并且必须是小写。2.下面是专用符号：+-*/====!==;,()[]{}/**/3.其他标记是ID和NUM，通过下列正则表达式定义：ID=letterletter*NUM=digitdigit*letter=a|..|z|A|..|Zdigit=0|..|9小写和大写字母是有区别的。4.空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。5.注释用通常的C语言符号/*...*/围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。3.2.2数据结构定义了一个枚举类型TokenType,枚举了一些关键字和其他一些词法中的符号。typedefenumTokenType{IF,ELSE,ID,NUM,PLUS,MINUS,...}11TokenType;记号有若干种，其中包括保留字，如IF和THEN；特殊符号，如算术符号加（PLUS）和减（MINUS）；多字符串的记号，如NUM和ID。作为逻辑项的记号必须与它们所表示的字符串完全区分开来。函数getToken()：它消耗输入字符并根据构造的DFA返回下一个被识别的记号。这个实现利用了双重嵌套情况分析，以及一个有关状态的大型情况列表。在大列表中的是基于当前输入字符的单独列表。扫描程序的状态也被定义为一个枚举类型StateType。扫描程序还需总地计算出每个符号的特性，并且有时会采取其他动作。在此扫描程序中，所需计算的唯一特性是词法或是被识别的记号的串值，它位于变量tokenString之中，并一同提供给编译器其他部分。reservedLookup():实现识别的标识符之后保留字的查找。标志变量save用来指示是否将一个字符增加到tokenString之上。getNextChar():读取程序中的下一个字符。printToken():根据此法分析的token，把结果输入到文件里。数与标识符的识别要求从INNUM和INID到最终状态的转换应该是非消耗的，通过提供一个ungetNextchar过程，在输入缓冲区中反填一个字符来完成这一任务。3.2.3算法对源程序字符流进行扫描和分解，识别出一个个单词符号。描述工具：有限自动机12词法分析器的结构预处理子程序扫描器输入缓冲区扫描缓冲区单词符号输入列表2.3.2词法分析器的设计基本字识别:需要超前搜索才能确定哪些是基本字标识符识别:字母开头的字母数字串，后跟界符或算符常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索算符和界符的识别:把多个字符符合而成的算符和界符拼合成一个单一单词符号。对于正则表达式ID=letterletter*，其有限自动机如下所示：对于词法分析过程，均可以把词法的规则构造成如上所示的ＤＦＡ。根据给出的词法定义，得到如下图所示的DFA:1Letter2Letter13DFA状态图由此DFA图，得到该词法分析的伪代码：state:=START;ch:=nextinputcharacter;whilenotAcc