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

1、课 程 设 计 报 告 设计题目：简单文法的编译器的设计与实现班 级：XX组长学号：XXX组长姓名：XX指导教师：XX设计时间：2017年1月设计分工组长学号及姓名： 20143710 李万分工：语法分析，生成符号表，语义分析，中间代码生成(四元式)，汇编代码生成组员1学号及姓名：20143724张太分工：部分语法分析组员2学号及姓名：20143725 张天宝分工：部分语义分析组员3学号及姓名：20143722张俊杰 摘 要 编译原理是计算机科学与技术专业一门重要的专业课,它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计

2、算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。 本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。关键词：编译原理，前端，目标代码，后端61 目 录摘要.3 1. 概述.6 2. 课程设计任务及要求.7 2.1 设计任务.7 2.2 设计要求.8 3. 算法及数据结构.9 3.1算法的总体思想.10 3.2 词法分析器模块.11 3.

3、2.1 功能.11 3.2.2 数据结构.11 3.2.3 算法.12 3.3 语法分析器模块.14 3.3.1功能.14 3.3.2 数据结构.14 3.3.3算法.15 3.4 语义分析中间代码生成.18 3.4.1 功能.18 3.4.2 数据结构.18 3.4.3 算法.203.5 目标代码生成器模块.23 3.5.1功能.23 3.5.2 数据结构.23 3.5.3 算法.25 4. 程序设计与实现.26 4.1 程序流程图.26 4.2 程序说明.27 4.3 实验结果.325. 结论.596. 参考文献.60 7. 收获、体会和建议.61 1 概述 编译程序(compiler)是

4、把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。几乎所有形式的计算都要用到编译器。程序运行的过程图如下图所示：高级语言程序机器语言程序编译程序翻译运行结果程序运行过程编译程序的工作一般分为以下几个阶段:词法分析、语法分析、语义分析、中间代码产生、代码优化、目标代码产生。语法分析器语义分析与中间代码生成器优化段目标代码生成器词法分析器语法单位四元式四元式目标代码单词符号 2 课程设计任务及要求2.1 设计任务任务内容：1.定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；If语句、While语句等）支持函数调用，函数递归，支持传参和传

5、值2.扫描器设计实现；3.语法分析器设计实现；4.中间代码设计；5.中间代码生成器设计实现；6.生成目标代码。 文法：给出的文法具有左递归，消除左递归后得到的文法如下所示：1. p ro g r a m d e c l a r a t i o n - l i s t2. d e c l a r a t i o n - l i s t d e c l a r a t i o n d e c l a r a t i o n3. d e c l a r a t i o n v a r- d e c l a r a t i o n | f u n - d e c l a r a t i o n4. v

6、 a r- d e c l a r a t i o n t y p e - s p e c i f i e r I DNUM 5. t y p e - s p e c i f i e r i n t | v o i d6. f u n - d e c l a r a t i o n t y p e - s p e c i f i e r I D( p a r a m s ) | c o m p o u n d - s t m t7. p a r a m s p a r a m s-l i s t | v o i d8. p a r a m - l i s t p a r a m, p a r

7、a m9. p a r a m t y p e - s p e c i f i e r I D 10. compound - s t m t l o c a l-d e c l a r a t i o ns s t a t e m e n t-l i s t 11. l o c a l-d e c l a r a t i o ns empty v a r- d e c l a r a t i o n 12. s t a t e m e n t-l i s t emptys t a t e m e n t 13. s t a t e m e n t e x p re s s i o n-s t

8、m t | c o m p o u n d - s t m t | s e l e c t i o n - s t m t| i t e r a t i o n-s t m t | re t u r n-s t m t14. e x p re s s i o n-s t m t e x p re s s i o n ;15. s e l e c t i o n - s t m t i f ( e x p re s s i o n ) s t a t e m e n t e l s e s t a t e m e n t16. i t e r a t i o n -s t m t w h i l

9、 e ( e x p re s s i o n ) s t a t e m e n t17. re t u r n -s t m t r e t u r n e x p re s s i o n;18. e x p re s s i o n v a r = e x p re s s i o n | s i m p l e-e x p re s s i o n19. v a r I D e x p re s s i o n 20. s i m p l e-e x p re s s i o n a d d i t i v e-e x p re s s i o n re l o p a d d i

10、t i v e-e x p re s s i o n21. re l o p = | | = | = = | ! =22. add i t i v e-e x p re s s i o n termaddop te r m23. add p + | -24. t erm f a c t o r m u l o p f a c t o r25. mulop * | /26. f a c t o r ( e x p re s s i o n ) | v a r | c a l l | N U M27. c a l l I D ( a rg s )28. a rg s a rg - l i s t

11、| e m p t y29. a rg-l i s t e x p re s s i o n , e x p re s s i o n 2.2 设计要求 通过设计C-语言的编译器，了解编译器在程序设计中的功能，以及编译过程中的翻译步骤，对编译原理的各个部分有一个深入的了解和学习。 3 算法及数据结构 3.1 算法的总体思想 如下流程图： 出 错 处 理 符 号 表 词法分析器 源程序 语法分析器 单词符号 语义分析及中间代码产生器 语法单位 中间代码 目标代码生成器 中间代码 目标代码3.2 词法分析器模块 3.2.1 功能根据给出的C-语言词法、语法和语义，设计一个编译器。1. 下面是语言的

12、关键字：else if int return void while ，write,read.所有的关键字都是保留字，并且必须是小写。2. 下面是专用符号：+ - * / = = != = ; , ( ) /* */3. 其他标记是I D和N U M，通过下列正则表达式定义：ID = letter letter*NUM = digit digit*letter = a|.|z|A|.|Zdigit = 0|.|9小写和大写字母是有区别的。4. 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开I D、N U M关键字。5. 注释用通常的C语言符号/ * . . . * /围起来。注释

13、可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。 3.2.2 数据结构 定义了一个枚举类型TokenType,枚举了一些关键字和其他一些词法中的符号。typedef enum TokenType IF,ELSE,ID,NUM,PLUS,MINUS,.TokenType;记号有若干种，其中包括保留字，如IF 和THEN；特殊符号，如算术符号加（PLUS）和减（MINUS）；多字符串的记号，如NUM和ID。作为逻辑项的记号必须与它们所表示的字符串完全区分开来。函数getToken()：它消耗输入字符并根据构造的DFA返回下一个被识别的记号。这个实现利用了双重嵌套

14、情况分析，以及一个有关状态的大型情况列表。在大列表中的是基于当前输入字符的单独列表。扫描程序的状态也被定义为一个枚举类型StateType。扫描程序还需总地计算出每个符号的特性，并且有时会采取其他动作。在此扫描程序中，所需计算的唯一特性是词法或是被识别的记号的串值，它位于变量tokenString之中，并一同提供给编译器其他部分。reservedLookup():实现识别的标识符之后保留字的查找。标志变量save用来指示是否将一个字符增加到tokenString之上。getNextChar(): 读取程序中的下一个字符。printToken():根据此法分析的token，把结果输入到文件里。数

15、与标识符的识别要求从INNUM和INID到最终状态的转换应该是非消耗的，通过提供一个ungetNextchar过程，在输入缓冲区中反填一个字符来完成这一任务。 3.2.3 算法对源程序字符流进行扫描和分解，识别出一个个单词符号。描述工具：有限自动机基本字识别: 需要超前搜索才能确定哪些是基本字标识符识别:字母开头的字母数字串，后跟界符或算符常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索算符和界符的识别:把多个字符符合而成的算符和界符拼合成一个单一单词符号。对于正则表达式ID = letter letter*，其有限自动机如下所示：1Letter2Letter对于词法分析过

16、程，均可以把词法的规则构造成如上所示的。根据给出的词法定义，得到如下图所示的DFA:DFA状态图由此DFA图，得到该词法分析的伪代码： state := START;ch : = next input character;while not Acceptstate and not error（state) donewstate:=Tstate,ch;if Advancestate,ch then ch:=next input char;state:= newstate;end while;if Acceptstate then accept;3.3语法分析器模块 3.3.1功能:在词法分析的基

17、础上，根据语言的语法规则把单词符号串分解成各类语法单位。3.3.2 数据结构必须将树节点的属性保留如下：每一种表达式节点都需要一个特殊的属性。常数节点需要它所代表的整型常数的域；标识符节点应该包括了标识符名称的域；而算符节点则需要包括了算符名称的域。定义了树节点TreeNode的结构体：typedef struct treeNode struct treeNode * childMAXCHILDREN; struct treeNode * father; struct treeNode * sibling; int lineno; NodeKind nodekind; union StmtKi

18、nd stmt; ExpKind exp; kind; union TokenType op; int val; char * name; attr; TokenType type;int iArraySize; / arrary size;int bArr;char *szScope;TreeNode;newNode():新建一个树节点。newStmtNode():新建一个语句节点。newExpNode():新建一个表达式节点。PushBack():回退函数，当得到的词不是想要的而下一次又要用到的时候就调用PushBack（）过程，使下一次getToken还是得到这个Token。PrintT

19、ree():对建立的语法树进行遍历，通过缩进显示子树的方法打印一颗语法分析树。parse():根据文法规则对程序进行分析，并返回最新构造的分析树。通过相互递归调用declaration_list、declaration、var_declaration、fun_declaration、params、compound_stmt、local_declarations()、expression_stmt()、if_stmt()、expression()、term()等函数来实现语法树的构造。match()过程，它匹配指定的记号，匹配成功则调用getToken()读入下一个记号；匹配失败则调用synta

20、xError()指出发生错误的位置。3.3.3 算法自下而上分析法(Bottom-up)：基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。构造不带回溯的自上而下分析算法，需要消除文法的左递归性、克服回溯。主控程序：给出的文法具有左递归，消除左递归后得到的文法如下所示：1. p ro g r a m d e c l a r a t i o

21、n - l i s t2. d e c l a r a t i o n - l i s t d e c l a r a t i o n d e c l a r a t i o n3. d e c l a r a t i o n v a r- d e c l a r a t i o n | f u n - d e c l a r a t i o n4. v a r- d e c l a r a t i o n t y p e - s p e c i f i e r I DNUM 5. t y p e - s p e c i f i e r i n t | v o i d6. f u n - d

22、e c l a r a t i o n t y p e - s p e c i f i e r I D( p a r a m s ) | c o m p o u n d - s t m t7. p a r a m s p a r a m s-l i s t | v o i d8. p a r a m - l i s t p a r a m, p a r a m9. p a r a m t y p e - s p e c i f i e r I D 10. compound - s t m t l o c a l-d e c l a r a t i o ns s t a t e m e n t-

23、l i s t 11. l o c a l-d e c l a r a t i o ns empty v a r- d e c l a r a t i o n 12. s t a t e m e n t-l i s t emptys t a t e m e n t 13. s t a t e m e n t e x p re s s i o n-s t m t | c o m p o u n d - s t m t | s e l e c t i o n - s t m t| i t e r a t i o n-s t m t | re t u r n-s t m t14. e x p re

24、s s i o n-s t m t e x p re s s i o n ;15. s e l e c t i o n - s t m t i f ( e x p re s s i o n ) s t a t e m e n t e l s e s t a t e m e n t16. i t e r a t i o n -s t m t w h i l e ( e x p re s s i o n ) s t a t e m e n t17. re t u r n -s t m t r e t u r n e x p re s s i o n;18. e x p re s s i o n v

25、 a r = e x p re s s i o n | s i m p l e-e x p re s s i o n19. v a r I D e x p re s s i o n 20. s i m p l e-e x p re s s i o n a d d i t i v e-e x p re s s i o n re l o p a d d i t i v e-e x p re s s i o n21. re l o p = | | = | = = | ! =22. add i t i v e-e x p re s s i o n termaddop te r m23. add p +

26、 | -24. t erm f a c t o r m u l o p f a c t o r25. mulop * | /26. f a c t o r ( e x p re s s i o n ) | v a r | c a l l | N U M27. c a l l I D ( a rg s )28. a rg s a rg - l i s t | e m p t y29. a rg-l i s t e x p re s s i o n , e x p re s s i o n 将程序中的词法经过语法分析，得到一颗相关的语法树。基本树形结构：if语句： while语句：if语句表达式语

27、句语句while语句表达式语句 语句复合语句语句语句声明复合语句： 3.4 语义分析中间代码生成 3.4.1 功能 检查源程序的语义错误，并收集代码生成阶段要用到的类型信息。主要是构造符号表和类型检查 3.4.2 数据结构实现buildSymtab和typeCheck使用了相同的通用遍历函数traverse，它接受两个作为参数的过程(和语法树)，一个完成每个节点的前序处理，一个进行后序处理。前序处理器称作insertNode，因为它完成插入到符号表的操作。“空”的过程称作nullProc，它用一个空的过程体说明。insertNode过程通过参数(指向语法树节点的指针)接受的语法树节点的种类，确

28、定何时把一个标识符(与行号和地址一起)插入到符号表中。对于语句节点的情况，包含变量引用的节点是赋值节点和读节点，被赋值或读出的变量名包含在节点的字段中。对表达式节点的情况，标识符节点的名字也存储在中。如果符号表中没有变量，则加入变量和它的行号和地址：st_insert(,t-lineno, location+)；如果变量已经在符号表中，则只存储行号：st_insert(,t-lineno,0);类型检查遍的checkNode过程有两个任务。首先，它必须确定是否出现了类型错误。其次，它必须为当前节点推断一个类型并且在

29、树节点中为这个类型分配一个新的字段。类型检查中还调用了fa_check函数，用以检查函数的参数是否一样。第1个过程完成语法树的前序遍历，当它遇到树中的变量标识符时，调用符号表st_insert过程，遍历完成后，它调用printSymTab打印列表文件中存储的信息。第2个过程完成语法树的后序遍历，在计算数据类型时把它们插入到树节点，并把任意的类型检查错误记录到列表文件中。还定义了一些结构体用来描述变量在符号表中的一些信息，像作用域szScope、类型type、相对储存位置memloc、变量所处的行lines。 typedef struct QUAT char *operational;/操作符

30、char *figure1;/操作数1 char *figure2;/操作数2 char *result;/结果QUAT;四元式的存储结构QUAT Quat1000;/四元式结构体数组3.4.3算法符号表符号表：将名字映射到编译器已知的有关信息的一个字典。符号表的作用:一致性检查和作用域分析;辅助代码生成.符号表的每一项(入口)包含两大栏:名字栏；信息栏，记录相应的不同属性，如：地址、值、作用域等符号表的操作:填入名称（insert）、查找名字（lookup）、访问信息、填写修改信息、删除。符号表的查找：线性查找、二分查找、杂凑查找。杂凑查找(HASH技术)在符号表中使用的杂凑函数将字符串(标

31、识符名字)转换成0.size-1范围内的一个整数，一般分3步进行:将字符串中的每个字符转换成一个非负整数；将这些整数用一定的方法组合成一个整数；把结果调到0.size-1范围。类型检查给定语言可能的类型表达式，类型检查器需要知道两个类型表达式是否表示相同的类型。这就是类型等价(type equivalence)问题。名等价(name equivalence)：两个类型表达式是等价的，当且仅当它们是相同的简单类型或有相同的类型名。对赋值语句，要求被赋值的变量和其接受的值的表达式有相同的类型。常量表达式，像数字及布尔值true和false，隐含地说明了integer和boolean类型。变量名在符

32、号表中通过lookup操作确定它们的类型。其他表达式通过操作符构成，如算术操作符+、布尔操作符or、以及下标操作符。对每种情况子表达式都必须是指定操作的正确类型。符号表可以通过对语法树的前序遍历建立，类型检查通过后序遍历完成。虽然这两个遍历能容易地组合成一个遍历，为使两个处理步骤操作的不同之处更加清楚，仍把它们分成语法树上两个独立的遍。四元式算法流程图： - NEXT (w) NEXT (w) 出口 GEQ(-) TGEQ(+) T + T 入口 结束 结果输出errorNEXT (w) E # 开始 初始化nnyyyn 入口 入口nn ( i Fyynn / * NEXT (w) PUSH(

33、i)yn ) 出口error1error2E NEXT (w)yyGEQ(*) F NEXT (w) 出口 GEQ(/) F NEXT (w) 3.5目标代码生成器模块 3.5.1 功能 代码生成器的主要任务：指令选择、寄存器分配和指派、指令排序代码生成器的输入 ：代码生成器的输入包括源程序的中间表示，以及符号表中的信息。符号表信息用来决定中间表示中名字所代表的数据对象的运行时地址。假定中间表示足够详细，这样，中间语言中名字的值可以表示为目标机器能够直接操作的量(位、整数、实数、指针等)。类型检查：假定已经作过必要的类型检查，所以在必要的地方已经加入了类型转换操作，并且已检测出一些明显的语义错

34、误。这样代码生成阶段就可以假设它的输入是没有错误的。函数调用的中间代码表示，有两个实际的机制需要说明函数过程的定义(definition) (也叫声明(declaration)：定义产生了函数名、参数和代码，但函数却不在那点执行。函数过程的调用(call)：调用产生了参数的实际值，并且执行一个到函 数代码的转移。函数代码被执行和返回。 3.5.2 数据结构 C o d e G e n，其主要工作如下：产生一些注释和指令、设置启动时的运行时环境，然后在语法树上调用 genPreSeg()、genCodeSeg();genPreSeg()负责完成遍历并以修改过的顺序产生代码的语法树，检测节点是函数

35、的参数或者是main函数中的变量定义的节点。调用genData函数来生生成分配数据空间的指令。genCodeSeg()负责完成遍历并以修改过的顺序产生代码的语法树，检测节点是不是函数节点，以main函数为入口，通过递归调用genFunc、genLocal、genStmt等函数，依次来生成在源程序中定义的各个函数的指令代码。genStmt检测节点是句子或表达式节点(或空)，然后在同属上递归调用自身。判断出是句子或者表达式之后，再进一步细化但是那种类型的句子，当前表达式含有哪些操作符和变量进一步生成指令代码。typedef struct treeNode/语法分析器，构造语法树 struct tr

36、eeNode * childMAXCHILDREN;/语法树子节点个数最多为3 struct treeNode * father;/父节点 struct treeNode * sibling;/兄弟节点 int lineno;/所在的行数 NodeKind nodekind;/节点类型 union StmtKind stmt; ExpKind exp; kind;/节点类型，表达式类型或块的声明 /*表达式*/ union TokenType op;/表达式的操作符+，-，*，/ int val;/表达式值 char * name; /表达式名 attr; /*Token类型*/ TokenT

37、ype type; /*数组*/int iArraySize;/数组大小int bArr;/数组标记是否为TRUE? /*变量的作用域*/char *szScope; TreeNode; 3.5.3 算法genPreSeg()负责完成遍历并以修改过的顺序产生代码的语法树，检测节点是函数的参数或者是main函数中的变量定义的节点。调用genData函数来生生成分配数据空间的指令。genCodeSeg()负责完成遍历并以修改过的顺序产生代码的语法树，检测节点是不是函数节点，以main函数为入口，通过递归调用genFunc、genLocal、genStmt等函数，依次来生成在源程序中定义的各个函数的

38、指令代码。genStmt检测节点是句子或表达式节点(或空)，然后在同属上递归调用自身。判断出是句子或者表达式之后，再进一步细化但是那种类型的句子，当前表达式含有哪些操作符和变量进一步生成指令代码。 4 程序设计与实现4.1程序流程图中间代码产生器有错误 语法分析器 词法分析器 开始 程序的总体流程图如下： y n 错误输出 目标代码生成器 结束各个模块的程序具体流程图参考第3节。4.2 程序说明main()： 调用子模块的功能TokenType getToken(void);/词法扫描器/构造hash表语法模块的函数：static int hash ( char * key )/find ID

39、 functionname.static TreeNode * program(void);static TreeNode * declaration_list(void);static TreeNode * declaration(void);static TreeNode * var_declaration(void);/变量声明static TreeNode * fun_declaration(void);/函数声明static TreeNode * params(void);static TreeNode * compound_stmt(void);static TreeNode *

40、local_declarations(void);static TreeNode * expression_stmt(void);static TreeNode * if_stmt(void);/if语句块static TreeNode * while_stmt(void);/while语句块static TreeNode * return_stmt(void);/return 语句块static TreeNode * read_stmt(void);/read语句块static TreeNode * write_stmt(void);/write语句块static TreeNode * ex

41、pression(void);/表达式static TreeNode * simple_expression(void);/static TreeNode * additive_expression(void);static TreeNode * term(void);static TreeNode * factor(void);static TreeNode * var(void);static TreeNode * call(void);static TreeNode * args(void);static TreeNode * subcompound_stmt(void);语义部分的函数

42、：static void traverse( TreeNode * t, /preProcinsertNode void (* preProc) (TreeNode *),/函数指针insertNode /postProcnullProc void (* postProc) (TreeNode *) )/nullProc遍历整个语法树static void insertNode(TreeNode *t)* Function buildSymtab constructs the symbol /通过前序遍历语法树 * table by preorder traversal of the synt

43、ax tree */void buildSymtab(TreeNode * syntaxTree)static void typeError(TreeNode * t, char * message)/错误处理static void checkNode(TreeNode *pNode)/ assign the type to the node. void typeCheck(TreeNode * syntaxTree)/类型检查语义动作，语法制导函数：void fa_insert( TreeNode* pNode )/插入函数参数int fa_check( TreeNode* pNode )/检查函数的参数个数，参数类型是否匹配TreeNode * newExpNode(ExpKind kind)/建立表达式节点 treekind.exp=OpK,ConstK,IDK.TreeNode * newNode (NodeKind node)/建立新节点(函数.TreeNode * newStmtNode(StmtKind kind)目标代码：static void emitCode(char *c)/wite the codestatic void emitCode1(char *c) /only write a line 写入不换行sta