课程设计报告

设计题目：简单文法的编译器的设计与实现班级：XX

组长学号：XXX

组长姓名：XX

指导教师：XX

设计时间：2017年1月

1

设计分工

组长学号及姓名：20143710 李万

分工：语法分析，生成符号表，语义分析，中间代码生成(四元式)，汇编代码生成

组员1学号及姓名：20143724张太

分工：部分语法分析

组员2学号及姓名：20143725 张天宝

分工：部分语义分析

组员3学号及姓名：20143722张俊杰

2

摘要

编译原理是计算机科学与技术专业一门重要的专业课, 它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。

本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。

关键词：编译原理，前端，目标代码，后端

3

目录

摘要 (3)

1. 概述 (6)

2. 课程设计任务及要求 (7)

2.1 设计任务 (7)

2.2 设计要求 (8)

3. 算法及数据结构 (9)

3.1算法的总体思想 (10)

3.2 词法分析器模块 (11)

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 算法 (20)

3.5 目标代码生成器模块 (23)

3.5.1功能 (23)

3.5.2 数据结构 (23)

3.5.3 算法 (25)

4. 程序设计与实现 (26)

4.1 程序流程图 (26)

4.2 程序说明 (27)

4.3 实验结果 (32)

4

5. 结论 (59)

6. 参考文献 (60)

7. 收获、体会和建议 (61)

5

6 1 概述

编译程序(compiler)是把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。几乎所有形式的计算都要用到编译器。程序运行的过程图如下图所示：

程序运行过程

编译程序的工作一般分为以下几个阶段:词法分析、语法分析、语义分析、中间代码产生、代码优化、目标代码产生。

2 课程设计任务及要求

2.1 设计任务

任务内容：1.定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；If语句、While语句等）支持函数调用，函数递归，支持传参和传值2.扫描器设计实现；3.语法分析器设计实现；

4.中间代码设计；

5.中间代码生成器设计实现；

6.生成目标代码。

文法：给出的文法具有左递归，消除左递归后得到的文法如下所示：

1. p r o g r a m → d e c l a r a t i o n - l i s t

2. 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 n}

3. 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 n

4. 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 D[N UM]

5. t y p e-s p e c i f i e r→i n t|v o i d

6. 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 t

7. p a r a m s →p a r a m s-l i s t | v o i d

8. p a r a m-l i s t→ p a r a m{, p a r a m}

9. p a r a m →t y p e - s p e c i f i e r I D[[]]

10. co mp ou nd -s t m t→{ l o c a l-d e c l a r a t i o n s 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 n s→e m p t y{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 → e mp ty{s t a t e m e n t }

13.s t a t e m e n t→e x p r e 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 t

14. e x p r e s s i o n-s t m t→[e x p r e s s i o n] ;

15.s e l e c t i o n-s t m t →i f (e x p r e 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 t]

16.i t e r a t i o n-s t m t → w h i l e (e x p r e s s i o n) s t a t e m e n t

17. r e t u r n -s t m t→ r e t u r n [e x p r e s s i o n];

18.e x p r e s s i o n→v a r=e x p r e s s i o n|s i m p l e-e x p re s s i o n

19. v a r →I D [ e x p r e s s i o n ]

20.s i m p l e-e x p r e s s i o n →a d d i t i v e-e x p r e s s i o n[ r e l o p a

7

d d i t i v e-

e x p r e s s i o n]

21. r e l o p →< = | < | > | > = | = = | ! =

22. a dd i t i v e-e x p r e s s i o n →t er m{a d d o p t e r m}

23. a dd p →+ |-

24. t e rm →f a c t o r{m u l o p f a c t o r}

25. m ul op →* | /

26. f a c t o r →( e x p r e s s i o n ) | v a r | c a l l | N U M

27. c a l l →I D ( a rg s )

28. a r g s → a r g - l i s t|e m p t y

29. a r g-l i s t → e x p r e s s i o n{,e x p r e s s i o n}

2.2 设计要求

通过设计C-语言的编译器，了解编译器在程序设计中的功能，以及编译过程中的翻译步骤，对编译原理的各个部分有一个深入的了解和学习。

8

3 算法及数据结构3.1 算法的总体思想

如下流程图：

目标代码

9

3.2 词法分析器模块

3.2.1 功能

根据给出的C-语言词法、语法和语义，设计一个编译器。

1. 下面是语言的关键字：

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|..|Z

digit = 0|..|9

小写和大写字母是有区别的。

4. 空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开I D、N U M关键字。

5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。

3.2.2 数据结构

定义了一个枚举类型TokenType,枚举了一些关键字和其他一些词法中的符号。

typedef enum TokenType

{IF,ELSE,ID,NUM,PLUS,MINUS,...}

10

TokenType;

记号有若干种，其中包括保留字，如IF 和THEN；特殊符号，如算术符号加（PLUS）和减（MINUS）；多字符串的记号，如NUM和ID。作为逻辑项的记号必须与它们所表示的字符串完全区分开来。

函数getToken()：它消耗输入字符并根据构造的DFA返回下一个被识别的记号。这个实现利用了双重嵌套情况分析，以及一个有关状态的大型情况列表。在大列表中的是基于当前输入字符的单独列表。扫描程序的状态也被定义为一个枚举类型StateType。

扫描程序还需总地计算出每个符号的特性，并且有时会采取其他动作。在此扫描程序中，所需计算的唯一特性是词法或是被识别的记号的串值，它位于变量tokenString之中，并一同提供给编译器其他部分。

reservedLookup():实现识别的标识符之后保留字的查找。标志变量save用来指示是否将一个字符增加到tokenString之上。

getNextChar(): 读取程序中的下一个字符。

printToken():根据此法分析的token，把结果输入到文件里。

数与标识符的识别要求从INNUM和INID到最终状态的转换应该是非消耗的，通过提供一个ungetNextchar过程，在输入缓冲区中反填一个字符来完成这一任务。

3.2.3 算法

对源程序字符流进行扫描和分解，识别出一个个单词符号。

描述工具：有限自动机

11

标识符识别:字母开头的字母数字串，后跟界符或算符

常数识别:识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索

算符和界符的识别:把多个字符符合而成的算符和界符拼合成一个单一单词符号。

对于正则表达式ID = letter letter*，其有限自动机如下所示：

对于词法分析过程，均可以把词法的规则构造成如上所示的ＤＦＡ。根据给出的词法定义，得到如下图所示的DFA:

12

DFA状态图

由此DFA图，得到该词法分析的伪代码：

state := START;

ch : = next input character;

while not Accept[state] and not error（state) do newstate:=T[state,ch];

if Advance[state,ch] then ch:=next input char;

state:= newstate;

end while;

if Accept[state] then accept;

13

3.3语法分析器模块

3.3.1功能

:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。

3.3.2 数据结构

必须将树节点的属性保留如下：每一种表达式节点都需要一个特殊的属性。常数节点需要它所代表的整型常数的域；标识符节点应该包括了标识符名称的域；而算符节点则需要包括了算符名称的域。

定义了树节点TreeNode的结构体：

typedef struct treeNode

{ struct treeNode * child[MAXCHILDREN];

struct treeNode * father;

struct treeNode * sibling;

int lineno;

NodeKind nodekind;

union { StmtKind 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():新建一个表达式节点。

14

PushBack():回退函数，当得到的词不是想要的而下一次又要用到的时候就调用PushBack（）过程，使下一次getToken还是得到这个Token。

PrintTree():对建立的语法树进行遍历，通过缩进显示子树的方法打印一颗语法分析树。

parse():根据文法规则对程序进行分析，并返回最新构造的分析树。通过相互递归调用declaration_list、declaration、

var_declaration、fun_declaration、params、compound_stmt、

local_declarations()、expression_stmt()、if_stmt()、expression()、

term()等函数来实现语法树的构造。

match()过程，它匹配指定的记号，匹配成功则调用getToken()读入下一个记号；匹配失败则调用syntaxError()指出发生错误的位置。

3.3.3 算法

自下而上分析法(Bottom-up)：

基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号

自上而下分析的主旨：

对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。

构造不带回溯的自上而下分析算法，需要消除文法的左递归性、克服回溯。

15