TINY-C编译器的设计与实现-词法分析器的设计与实现.doc

目 录摘 要：1一 前 言31.1编译系统概述31.2编译器的概述31.3TINY语言的概述4二 需求分析62.1 词法分析目的62.2 词法分析中的定义62.3 词法分析概述62.4 词法分析功能62.5词法分析的要求72.6 外部接口要求72.7 数据流程图72.7.1 顶层数据流程图72.7.2 第二层数据流程图7三 概要设计93.1概要设计分析93.1.1 目的93.1.2 定义93.1.3 参考资料93.2 任务概述93.2.1 目标93.2.2 需求概述103.3 总体设计103.3.1 词法分析的目标和作用103.3.2词法分析的数学基础和算法：103.3.3 TINY编译器的词法分析的实现：123.3.4词法分析器的总体结构和外部模块14四 详细设计与编码154.1 引言154.1.1 根本目的154.1.2 要求154.1.3 参考资料154.2 任务概述154.2.1 目标154.2.2 需求概述154.3 总体设计154.3.1 需求概述154.3.2 词法分析器的结构154.4 程序设计说明164.4.1 全局模块194.4.2 词法分析模块22五 测试分析315.1 引言315.1.1编写目的：315.1.2项目背景：315.1.3定义：315.2 任务概述315.2.1目标：315.2.2运行环境：315.2.3需求概述：325.2.4条件与限制：325.3 计划325.3.1测试方案：325.3.2测试项目325.4 测试项目说明325.4.1 测试项目名称及测试内容(1)325.4.2测试项目名称及测试内容(2)335.5 评价345.5.1 软件能力345.5.2 缺陷和限制345.6 测试结论34六 总结与心得35参 考 文 献36致 谢37附 录38 ContentsAbsrtact：1 1preface21.1 Summary of compile system21.2 Summary of compiler21.3 Summary of TINY language32. Requirement Analysis42.1 The purpose of Lexical analysis42.2 In lexical analysis definition 52.3 Summary of Lexical analysis 52.4 Function of scanner52.5 Lexical analysiss request52.6 Exterior interface request52.7 Data flow chart62.7.1 top layer data flow chart 62.7.2 second layer data flow chart 63.Outline design73.1 Outline design analysis73.1.1 Purpose73.1.2 Definition73.1.3 Biliography73.2 Summary of task73.2.1 Purpose73.2.2 Summary of requirement83.3 System design83.3.1 Purpose and function of lexical analysis83.3.2 Lexical analysiss algorithms：8 3.3.3The realizition of scanner：103.3.4System structure and Exterior module124 Detailed design and code realization124.1 Introduce124.1.1 Basic purpose124.1.2 Requirement124.1.3 Biliography134.2 Summary of task134.2.1 purpose134.2.2 Summary of requirement134.3 System design134.3.1 Summary of requirement134.3.2 Scanners structure134.4 Program design explanation134.4.1 Extern module174.4.2 Lexical analysis module205 Testing scanner275.1 Introduce285.1.1Purpose：285.1.2Project background：285.1.3Definition：295.2 Summary of task295.2.1Purpose：295.2.2Commit environment：295.2.3Summary of requirement：295.2.4Condition and limitation：295.3 Plan305.3.1Testing plan：305.3.2Testing items305.4 Explanation of testing item305.4.1 Testing items and details(1)305.4.2Testing items and details(2)315.5appraise325.5.1 Software ability325.5.2 Flaw and limitation325.6 Conclusion of testing325.Conclusion and what one has learned32Bibliography33Thanks34Appendix34 37TINY-C编译器的设计与实现词法分析器的设计与实现摘 要：这个编译器采用TINY 语言作为源语言，构造TINY语言的编译器。项目由三人共同完成，我的工作主要是完成了词法分析器的构造，为语法分析和语义分析做准备。主要工作如下：词法分析器的设计原理，以及所使用的算法和数据结构的实现。同时还负责编译器的总体设计。词法分析的核心就是DFA的设计和实现，这是在设计词法分析器中的主要工作。 关键词TINY，词法分析器, 状态转换图，超前搜索 ，DFA Tiny-C Complier design and realization Lexical analysis design and realizationThis compiler uses the TINY language to take the source language, the structure TINY language compiler. The project completes together by three people, my work mainly has completed the lexical analysis structure, prepared for the grammar analysis and the semantic analysis. Main work as follows: The lexical analyzer principle of design, as well as uses the algorithm and the data structure and realize. Simultaneously also is responsible for the compiler the system design. The lexical analysis core is the DFA design and the realization, this is in the design lexical analyzer main work.KeywordsTINY ，Scanner, Appearance conversion diagram, searching forward， DFA一 前 言1.1编译系统概述编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。编译过程划分成词法分析、语法分析、语义分析与中间代码生成，代码优化和目标代码生成五个阶段。另外两个重要的工作：表格管理和出错处理与上述五个阶段都有联系。其中各阶段功能如下：词法分析器,又称扫描器,输入源程序,进行词法分析,输出单词符号。语法分析器,简称分析器,对单词符号串进行语法分析(根据语法规则进行推导或规约),识别除各类语法单位,最终判断输入串是否构成语法上的正确的”程序”。语义分析与中间代码产生器,按照语义规则对语法分析器规约出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器,对中间代码进行优化处理。目标代码生成器,把中间代码翻译成目标程序。1.2编译器的概述编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序编写的程序作为输入，而产生用目标语言编写的等价程序。通常地，源程序为高级语言，如C或C + +，而目标语言则是目标机器的目标代码（，也就是写在计算机机器指令中的用于运行的代码。几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应掌握编译器的基本结构和操作。编译器的过程：源代码扫描程序 文字表 记号语法分析程序 符号表语义分析程序 语法树 错误处理器 注释树代码优化 中间代码代码生成目标代码 目标代码 图1-1编译器的过程1.3TINY语言的概述 TINY的程序结构很简单，它在语法上和Pascal的语法相似。仅是一个由分号分隔开的语句序列。它既无过程也无声明。所有的变量都是整型变量。它只有两个控制语句： if语句和repeat语句，这两个控制语句本身也可包含语句序列。If语句有一个可选的else部分且必须由关键字end结束。read语句和write语句完成输入/输出。在花括号中可以有注释，但注释不能嵌套。TINY的表达式也局限于布尔表达式和整型算术表达式。TINY语言的记号: 表1-1 TINY语言的记号保留字特殊符号其他i f+数（1个或更多的数字）t h e n- e l s e*e n d/r e p e a t=u n t i l = 和。在各种情况中，记号都表示由扫描程序从剩余的输入字符的开头识别或匹配的某种字符格式。将源程序中的空格、回车、换行等编辑符号排除，从而要构造一个预处理程序。进一步进行单词符号的识别，常用超前搜索的方法来完成。词法分析器的另一种方法是使用状态转换图。状态转换图是一种有限方向图。该图中只包含有限个状态，结点代表状态，用圆圈表示，状态之间用箭弧连结，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类。通常，一个状态图可有多个开始状态，也可有不止一个终止状态。3.3.2词法分析的数学基础和算法： 正规表达式与有限自动机（DFA）（1）正规表达式与正规集设有字母表，上的正规表达式及其值 -下规集的递归定义为：和都是上的正规表达式，它们所表示的正规集分别为 和；任何a，a是上的一个正规工，它所表示的正规集为a；假定U和V都是上的正规式，它们所表示的正规集分别记为L（U）和L（V），那么，（U|V）、（UV）和（U）*也都是正规式，它们所表示的正规集分别为L（U）L（V）、L（U）L（V）（连接积）和（L（U）*（闭包）。（2）确定有限自动机（DFA）一个确定有限自动机M是一个五元式M=（S,s0,F）其中：S是一个有限集，它的每个元素称为一个状态是一个有穷字母表，它的每个元素称为一个输入字符是一个从S至S的单值部分映射。(s,a)=s意味着：当现行状态为s、输入字符为a时，将转换到下一状态s。称s为s的一个后继状态。FS是一个终态集（可为空）。（3）非确定有限自动机（NFA）一个非确定有限自动机M是一个五元式M=（S,s0,F）其中：S是一个有限集，它的每个元素称为一个状态是一个有穷字母表，它的每个元素称为一个输入字符是一个从S*到S的子集映照，即：S*2SFS是一个终态集（可为空）。TINY语言记号的正则表达式数的正则表达式： nat = 0-9+signedNat = (+|-)? n a tnumber = signedNat (. nat ) ? (s i g n e d N a t) ?保留字正则表达式reserved = if | while | .do | 标识符的正则表达式letter = a z,A - Z digit = 0 - 9 identifier = letter (letter | d i g i t) * 注释的正则表达式 () * （4）词法分析程序的自动生成由专门的构造程序对用正规表达式组成的程序设计语言的符号说明书进行处理，生成一些表，由一个通用扫描算法使用这些表，就能实现某特定语言的词法分析程度的功能。（5）超前搜索当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后,它又调用预处理程序装入新串。 词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。像FORTRAN这样的语言,关键字不加特殊保护,关键字和其他记号就是数了，它们是一个或多个数字以及标识符的序列，而标识符又是（为了简便）一个或多个字母的序列。除了记号之外，T I N Y还要遵循以下的词法惯例：注释应放在花括号 . . . 中，且不可嵌套；代码应是自由格式；空白格由空格、制表位和新行组成；最长子串原则后须接识别记号。3.3.3 TINY编译器的词法分析的实现：现在的任务是完整地指出T I N Y的词法结构，也就是：定义记号和它们的特性。T I N Y的记号和记号类都列在表3- 1中。T I N Y的记号分为3个典型类型：保留字、特殊符号和“其他”记号。保留字一共有8个，它们的含义类似（尽管直到很后面才需知道它们的语义）。特殊符号共有1 0种：分别是4种基本的整数运算符号、2种比较符号（等号和小于），以及括号、分号和赋值符号。除了赋值符号是两个字符的长度之外，其余均为一个字符。 表3-1 TINY语言的记号 保留字特殊符号其他i f+数（1个或更多的数字）t h e n-e l s e*e n d/r e p e a t=u n t i l标识符( 1个或更多的字母)r e a d(w r i t e);: = 其他记号就是数了，它们是一个或多个数字以及标识符的序列，而标识符又是（为了简便）一个或多个字母的序列。除了记号之外，T I N Y还要遵循以下的词法惯例：注释应放在花括号 . . . 中，且不可嵌套；代码应是自由格式；空白格由空格、制表位和新行组成；最长子串原则后须接识别记号。TINY扫描程序的DFA: digitINNUM white space other digit START letterDONEINID letter other : =INASSIGN otherINCOMMENT otherother 图3-1词法分析的DFA3.3.4词法分析器的总体结构和外部模块 globals.h(包含记号) main.c（主程序源代码）util.h（工具集的接口） util.c（工具集）scan.h（TINY编译器的扫描器接口） scan.c（扫描程序源代码） 词法分析程序主要的函数： tokenType getToken(void)；/* 返回源文件中的下个记号*/static int getNextChar(void)；/* 扫描程序的的字符输入提供函数 */ /* getNextCharlineBuf取得下一个非空格的字符。如果读完了缓存中的全部字符，就把新的一行读入缓存。*/static void ungetNextChar(void); /* 返填字符函数*/ /* ungetNextChar把一个字符退回到lineBuf缓存中*/static TokenType reservedLookup(char); /*记号集查询函数*/另外还有1个重要函数：显示出错信息static void syntaxError(char * message)补充说明： T I N Y对保留字的识别是通过首先将它们看作是标识符，之后再在保留字表中查找它们来完成的。我们的扫描程序使用了一种非常简便的方法线性搜索， 即按顺序从开头到结尾搜索表格。这对于小型表格不成问题四 详细设计与编码4.1 引言4.1.1 根本目的 我们在TINY编译器的详细设计阶段就是实现词法分析的算法和主要的函数，编制一个能独立运行的词法分析子程序。4.1.2 要求在实现算法的基础上对程序进一步完善，提高程序的运行效率，使之简洁。4.1.3 参考资料 需求分析说明书，概要设计说明书 1Kenneth C.Louden . Compiler Construction Principles and Practice(编译原理及实践) M . 机械工业出版社 . 2000-01-11 2 陈火旺，刘春林 .程序设计语言-编译原理（第3版）M . 国防工业出版社.2000-01-124.2 任务概述4.2.1 目标保证软件的可靠性之外，使将来编写出的程序可读性好，容易理解，容易测试，容易修改和维护，这就是详细设计阶段最重要的目标。4.2.2 需求概述 本系统的核心是针对TINY语言的编译过程中的源程序进行词法分析并能显示出分析结果。4.3 总体设计4.3.1 需求概述扫描程序执行词法分析（Lexical analysis），类似于拼写检查。将字符序列收集成token，将标识符输入到符号表中，将文字（literal）输入到文字表中类型注释。4.3.2 词法分析器的结构输入源代码编译输出记号集 图4-1词法分析器结构图4.4 程序设计说明 TINY编译器源代码结构 globals.h main.cutil.h util.c （工具集）scan.h scan.c （扫描程序，即词法分析） TINY编译器用C语言实现，用BorlandDelphi7做脱离DOS的界面。 程序界面（如图4-2，图4-3）： 图4-2 主界面 （1） 图4-2 主界面 （2） 词法分析界面： 图4-3 词法分析界面词法分析中的数据结构： /* 扫描程序有限自动机的状态 */typedef enum START,INASSIGN,INCOMMENT,INNUM,INID,DONE StateType;/* 用来保存当前保留字或者标识符 */char tokenStringMAXTOKENLEN+1;/* BUFLEN定义源文件行中的最大字符数 */#define BUFLEN 256static char lineBufBUFLEN; /* 保留当前行 */static int linepos = 0; /* 保存LineBuf中的当前位置 */static int bufsize = 0; /* 当前缓存中保存的字符数 */static int EOF_flag = FALSE; /* 当遇到EOF（文件结束符）调整ungetNextChar的操作 */* getNextCharlineBuf取得下一个非空格的字符。如果读完了缓存中的全部字符，就把新的一行读入缓存 */* 一个记号的最大的长度 */#define MAXTOKENLEN 40/* tokenString数组用来存储每个记号 */extern char tokenStringMAXTOKENLEN+1;/* getToken函数返回源文件中的下个记号 */TokenType getToken(void);/*要用到的全局变量*/extern FILE* source; extern FILE* listing; extern int lineno; extern int EchoSource;extern int TraceScan;4.4.1 全局模块 TINY编译器的遍（pass）第1遍由构造语法树的扫描程序和分析程序组成；第2遍和第3遍执行语义分析，其中第2遍构造符号表而第3遍完成类型检查；原代码主要包括： globals.h，main.c ，util.h和util.c（工具集）/*/* 文件： globals.h */* TINY编译器的全局头文件 */*/* 只列出与词法分析器相关的部分 */#ifndef _GLOBALS_H_#define _GLOBALS_H_#include #include #include #include #ifndef FALSE#define FALSE 0#endif#ifndef TRUE#define TRUE 1#endif#define MAXRESERVED 8typedef enum ENDFILE,ERROR, IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE, ID,NUM, ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI TokenType;extern FILE* source; extern FILE* listing; extern int lineno; #define MAXCHILDREN 3extern int EchoSource;extern int TraceScan;#endif/*/* 文件： main.c */* TINY编译器的Main */*/#include globals.h#define NO_PARSE FALSE#include util.h#if NO_PARSE#include scan.h#endifint lineno = 0;FILE * source;FILE * listing;FILE * errorout;int EchoSource = TRUE;int TraceScan = TRUE;int Error = FALSE;/*/main( int argc, char * argv ) TreeNode * syntaxTree; char pgm120; if (argc != 2) fprintf(stderr,usage: %s n,argv0); exit(1); strcpy(pgm,argv1) ; if (strchr (pgm, .) = NULL) strcat(pgm,.tny); source = fopen(pgm,r); if (source=NULL) fprintf(stderr,File %s not foundn,pgm); exit(1); if(!(listing=fopen(Lexical.txt,w) exit(1); if(!(errorout=fopen(Error.txt,w) exit(1); fclose(source); fclose(errorout); return 0;/*/* 文件： util.c */* TINY编译器的全局头文件 */*/#include globals.h#include util.hvoid printToken( TokenType token, const char* tokenString ) switch (token) case IF: case THEN: case ELSE: case END: case REPEAT: case UNTIL: case READ: case WRITE: fprintf(listing, reserved word: %sn,tokenString); break; case ASSIGN: fprintf(listing,:=n); break; case LT: fprintf(listing,n); break; case EQ: fprintf(listing,=n); break; case LPAREN: fprintf(listing,(n); break; case RPAREN: fprintf(listing,)n); break; case SEMI: fprintf(listing,;n); break; case PLUS: fprintf(listing,+n); break; case MINUS: fprintf(listing,-n); break; case TIMES: fprintf(listing,*n); break; case OVER: fprintf(listing,/n); break; case ENDFILE: fprintf(listing,EOFn); break; case NUM: fprintf(listing, NUM, val= %sn,tokenString); break; case ID: fprintf(listing, ID, name= %sn,tokenString); break; case ERROR: fprintf(listing, Error: %sn,tokenString); break; default: fprintf(listing,Unknown token: %dn,token); /*/char * copyString(char * s) int n; char * t; if (s=NULL) return NULL; n = strlen(s)+1; t = malloc(n); if (t=NULL) fprintf(listing,Out of memory error at line %dn,lineno); else strcpy(t,s); return t;/* 退回到缓存中 */4.4.2 词法分析模块功能：对源程序进行扫描，产生记号集，为语法分析做准备。输入项目：源程序。输出项目：扫描程序产生的记号界面： 图4-4词法分析结果原代码主要包括scan.h 和scan.c：/*/* 文件： scan.h */* TINY编译器的扫描器接口 */*/#ifndef _SCAN_H_#define _SCAN_H_/* 一个记号的最大的长度 */#define MAXTOKENLEN 40/* tokenString数组用来存储每个记号 */extern char tokenStringMAXTOKENLEN+1;/* getToken函数返回源文件中的下个记号*/ TokenType getToken(void);#endif /*/* 文件：scan.c */* TINY扫描程序的执行代码*/*/#include globals.h#include util.h#include scan.h/* 扫描程序有限自动机的状态 */typedef enum START,INASSIGN,INCOMMENT,INNUM,INID,DONE StateType;/* 用来保存当前保留字或者标识符 */char tokenStringMAXTOKENLEN+1;/* BUFLEN定义源文件行中的最大字符数 */#define BUFLEN 256static char lineBufBUFLEN; /* 保留当前行 */static int linepos = 0; /* 保存LineBuf中的当前位置 */static int bufsize