TINY部分源码分析报告书

1、word 格式文档TINY 源码分析一、文件概述MAIN.C: 主函数GLOBALS.H:全局定义的文件SCAN.C/SCAN.H: 词法分析PARSE.C/PARSE.H:语法分析UTIL.C/UTIL.H:构造树SYMTAB.C/SYMTAB.H:符号表CGEN.C/CGEN.H:生成 " 汇编代码 "CODE.C/CODE.H:这个只是用来把分析过程输出到屏幕的.二、各个文件的分析主要有三个FILE* 句柄 :source-源代码文件。listing-显示分析过程的文件，这里重定向到stdout 。code- 目标汇编代码文件。从该文件中可知程序运行的流程：检查参数正

2、确否(tiny.exe filename)->构造语法树（调用parse 函数） -> 根据语法树生成代码（调用codeGen 函数，该函数又调用cGen 函数。定义了关键字个数8 个。定义了关键字，运算符等内容的枚举值。定义了语句类型的枚举值，这个决定树的结点。专业整理word 格式文档定义了变量类型（也就三种，void, integer, boolean）。定义了树的节点- 这个最重要了！ ！其结构如下所示：typedef struct treeNodestruct treeNode * childMAXCHILDREN;struct treeNode * sibling;in

3、t lineno;NodeKind nodekind;union StmtKind stmt; ExpKind exp; kind;union TokenType op;int val;char * name; attr;ExpType type; /* for type checking of exps */ TreeNode;主要函数TreeNode * newStmtNode(StmtKind kind)此函数创建一个有关语法树的声明节点TreeNode * newExpNode(ExpKind kind)此函数创建一个有关语法树的表述节点char * copyString(char *

4、 s)此函数分配和创建一个新的已存在树的复制void printTree( TreeNode * tree )输出一个语法树这两个文件主要是关于语法树的创建和输出主要有这么几个函数：专业整理word 格式文档static int getNextChar(void);static void ungetNextChar(void);static TokenType reservedLookup (char * s);TokenType getToken(void);reservedLookup 函数是查找关键字的，在符号表中找。这里还定义了一个保存关键字的结构：static struct char

5、* str; TokenType tok; reservedWordsMAXRESERVED="if",IF,"then",THEN,"else",ELSE,"end",END,"repeat",REPEAT,"until",UNTIL,"read",READ,"write",WRITE;最重要的是 getToken(void) 函数。这个相当于 lex 的功能，进行词法分析。 也就是一个 DFA， switch 后面跟了一堆的 cas

6、e 。其中 getNextChar(void)函数的思路，以下列出：static int getNextChar(void)if (!(linepos < bufsize)lineno+;if (fgets(lineBuf,BUFLEN-1,source)专业整理word 格式文档if (EchoSource) fprintf(listing,"%4d: %s",lineno,lineBuf);bufsize = strlen(lineBuf);linepos = 0;return lineBuflinepos+;elseEOF_flag = TRUE;return

7、EOF;else return lineBuflinepos+;有这么几个函数：TreeNode * parse(void)static TreeNode * stmt_sequence(void);static TreeNode * statement(void);static TreeNode * if_stmt(void);static TreeNode * repeat_stmt(void);static TreeNode * assign_stmt(void);专业整理word 格式文档static TreeNode * read_stmt(void);static TreeNode

8、 * write_stmt(void);static TreeNode * exp(void);static TreeNode * simple_exp(void);static TreeNode * term(void);static TreeNode * factor(void);最重要的是 parse 这个函数， 就是用来构造整个程序的语法树的。 下面的一堆私有函数构造相应语法的语法树，然后 parse 最后把它们这些子树整合成一个大树。这个是符号表操作的， 也就是词法分析的时候查找表， 看该 token 是不是关键字。 如果不是，就当作表识符添加进去。在语法分析的时候也要用到，看变量有

9、没有声明的时候用的。三、实验心得：通过这次实验，仔细地去查看和分析了TINY 编译器的部分源码。了解到了编译器的运行：检查参数正确否(tiny.exe filename)->构造语法树（调用parse 函数） -> 根据语法树生成代码（调用codeGen 函数），同时熟悉了编译器是如何使用prase 函数进行语法树的构建以及语法树生成代码的转化，最主要的是进一步清晰了解到编译器的构造和运行原理，加深了对课本知识的运用和拓展，感觉收获很大！Main.c/*/* File: main.c*/* Main program for TINY compiler*/* Compiler Con

10、struction: Principles and Practice*/* Kenneth C. Louden*/*/#include "globals.h"/* set NO_PARSE to TRUE to get a scanner-only compiler， NO_PARSE为 true时创建一个只扫描的编译器*/#define NO_PARSE FALSE/* set NO_ANALYZE to TRUE to get a parser-only compiler， NO_ANALYZE为 true 时创建一个只分析和扫描的编译器*/#define NO_ANA

11、LYZE FALSE专业整理word 格式文档/* set NO_CODE to TRUE to get a compiler that does not* generate code NO_CODE为 true时创建一个执行语义分析，但不生成代码的编译器*/#define NO_CODE FALSE#include "util.h"#if NO_PARSE#include "scan.h" /如果 NO_PARSE为 true, 调用头文件 scan.h#else#include "parse.h"/否则调用头文件 prase.h#

12、if !NO_ANALYZE#include "analyze.h" /如果 NO_ANALYZE为 true,调用头文件 analyze.h#if !NO_CODE#include "cgen.h"/如果 NO_CODE为 true, 调用头文件 cgen.h#endif#endif#endif /结束预处理语句符号/* allocate global variables分配全局变量 */int lineno = 0;FILE * source; /指针指向源代码文件地址FILE * listing;/指针指向显示分析过程的文件的地址FILE * co

13、de;/指针指向目标汇编代码文件的地址/* allocate and set tracing flags分配和设置跟踪标志*/int EchoSource = FALSE;int TraceScan = FALSE;int TraceParse = FALSE;int TraceAnalyze = FALSE;int TraceCode = FALSE;int Error = FALSE;/跟踪标志全部初始化为falsemain( int argc, char * argv ) TreeNode * syntaxTree;char pgm120; /* source code file nam

14、e */ if (argc != 2) fprintf(stderr,"usage: %s <filename>n",argv0);exit(1); /如果 argv 不为 2，打印显示信息并退出strcpy(pgm,argv1) ; / 复制 argv1 地址以 null 为退出字符的存储器区块到另一个存储器区块品 pgm 内if (strchr (pgm, '.') = NULL)专业整理word 格式文档strcat(pgm,".tny"); /把 .tyn文件所指字符串添加到pgm结尾处并添加'0'。s

15、ource= fopen(pgm,"r");/以只读的方式打开pgm文件，并将指向pgm文件的指针返回给 sourceif (source=NULL) fprintf(stderr,"File %s not foundn",pgm);exit(1); /如果源代码文件为空，打印显示信息并退出listing = stdout; /* send listing to screen清单发送到屏幕*/fprintf(listing,"nTINY COMPILATION: %sn",pgm); /答应显示语句#if NO_PARSEwhile

16、(getToken()!=ENDFILE); /如果输入流没有结束就继续进行循环，直至结束#elsesyntaxTree = parse();/调用 prase()函数构造语法树if (TraceParse) fprintf(listing,"nSyntax tree:n");printTree(syntaxTree);/如果语法分析追踪标志为TRUE且没有语法错误, 则将生成的语法树输出到屏幕#if !NO_ANALYZEif (! Error) if (TraceAnalyze) fprintf(listing,"nBuilding Symbol Table.

17、n");buildSymtab(syntaxTree); /输出含符号表信息的语法树if (TraceAnalyze) fprintf(listing,"nChecking Types.n");typeCheck(syntaxTree);/输出含类型检查的语法树if (TraceAnalyze) fprintf(listing,"nTypeChecking Finishedn");/打印结束信息#if !NO_CODEif (! Error) char * codefile;int fnlen = strcspn(pgm,".&quo

18、t;);codefile = (char *) calloc(fnlen+4, sizeof(char); strncpy(codefile,pgm,fnlen);strcat(codefile,".tm");/将源文件名，去掉扩展名，添加扩展名.tmcode = fopen(codefile,"w");/以只写的方式打开目标汇编代码文件，并返回地址给codez 指针if (code = NULL) printf("Unable to open %sn",codefile);exit(1); /如果 code 指针为空，打印显示信息并

19、退出codeGen(syntaxTree,codefile);/目标代码生成fclose(code);#endif专业整理word 格式文档#endif#endif/结束之前对应的条件编译fclose(source); /关闭源代码文件return 0;GLOBALS.H/*/* File: globals.h*/* Global types and vars for TINY compiler*/* must come before other include files*/* Compiler Construction: Principles and Practice*/* Kenneth

20、 C. Louden*/*/#ifndef _GLOBALS_H_#define _GLOBALS_H_/宏定义#include <stdio.h>#include <stdlib.h>#include <ctype.h>#include <string.h> /头文件引用#ifndef FALSE#define FALSE 0 /定义 FALSE为 0#endif#ifndef TRUE#define TRUE 1 /定义 TRUE为 1#endif/* MAXRESERVED = the number of reserved words */

21、#define MAXRESERVED 8 / 定义了关键字个数8 个typedef enum/* book-keeping tokens */ENDFILE,ERROR,/* reserved words */IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE,/* multicharacter tokens */ID,NUM,/* special symbols */ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI专业整理word 格式文档 TokenType; /定义了关键字，运算符等内容的枚举值ex

22、tern FILE* source; /* source code text file源代码地址*/extern FILE* listing; /* listing output text file显示分析过程的文件的地址*/extern FILE* code; /* code text file for TM simulator目标汇编代码文件的地址*/extern int lineno; /* source line number for listing */*/*Syntax tree for parsing */*/typedef enum StmtK,ExpK NodeKind;/

23、定义了语句类型的枚举值，这个决定树的节点 typedef enum IfK,RepeatK,AssignK,ReadK,WriteK StmtKind;typedef enum OpK,ConstK,IdK ExpKind;/* ExpType is used for type checking */typedef enum Void,Integer,Boolean ExpType;/定义了变量类型#define MAXCHILDREN 3/定义了最大子节点typedef struct treeNode/定义了树的节点 struct treeNode * childMAXCHILDREN;st

24、ruct treeNode * sibling; int lineno;NodeKind nodekind;union StmtKind stmt; ExpKind exp; kind;union TokenType op;int val;char * name; attr;ExpType type; /* for type checking of exps */ TreeNode;/*/*Flags for tracing*/*/* EchoSource = TRUE causes the source program to* be echoed to the listing file wi

25、th line numbers* during parsing*/extern int EchoSource;/* TraceScan = TRUE causes token information to be专业整理word 格式文档* printed to the listing file as each token is* recognized by the scanner*/extern int TraceScan;/* TraceParse = TRUE causes the syntax tree to be* printed to the listing file in line

26、arized form* (using indents for children)*/extern int TraceParse;/* TraceAnalyze = TRUE causes symbol table inserts* and lookups to be reported to the listing file*/extern int TraceAnalyze;/* TraceCode = TRUE causes comments to be written* to the TM code file as code is generated*/extern int TraceCo

27、de;/* Error = TRUE prevents further passes if an error occurs */extern int Error;#endifSCAN.C/*词法扫描程序*/#include "globals.h"#include "util.h"#include "scan.h"/* 定义的状态 */typedef enumSTART,/*初始状态 */INASSIGN, /*进入到赋值状态 */INCOMMENT, /* 进入到注释状态 */INNUM,/*进入到数字状态 */INID,/*进入到标

28、志符状态 */DONE/*状态结束 */StateType;/*每当语法分析程序需要一个单词时, 就调用该子程序 , 得到 ( 类别码 , 单词的值 )*/*语义标识符和保留字 */char tokenStringMAXTOKENLEN+1;专业整理word 格式文档/* BUFLEN =源代码的输入缓冲长度*/#define BUFLEN 256static char lineBufBUFLEN; /*当前行 */static int linepos = 0; /*在 linebuf中的当前位置 */static int bufsize = 0; /*缓冲区的字符串当前大小*/static

29、int EOF_flag = FALSE; /*如果读入下一个字符出错，设置EOF_flag 为假。 */*从 linebuffer中读取下一个非空白字符，如果读完，则读入新行。*/static int getNextChar(void) if (!(linepos < bufsize) lineno+;if (fgets(lineBuf,BUFLEN-1,source) if (EchoSource) fprintf(listing,"%4d: %s",lineno,lineBuf); bufsize = strlen(lineBuf);linepos = 0;re

30、turn lineBuflinepos+;else EOF_flag = TRUE; return EOF;else return lineBuflinepos+;/* 如果读入下一个字符出错，在 linebuf 中回退一个字符 。 */ static void ungetNextChar(void) if (!EOF_flag) linepos- ; /* 保留字的查找表 */ static struct char* str; TokenType tok; reservedWordsMAXRESERVED= "if",IF,"then",THEN,&q

31、uot;else",ELSE,"end",END,"repeat",REPEAT,"until",UNTIL,"read",READ,"write",WRITE;/*标识符是否是保留字*/static TokenType reservedLookup (char * s) int i;for (i=0;i<MAXRESERVED;i+)if (!strcmp(s,reservedWordsi.str) return reservedWordsi.tok;return ID;/*扫

32、描仪的主要功能函数 gettoken返回源文件中下一个标记*/专业整理word 格式文档TokenType getToken(void)/*存入 tokenstring的位置 */int tokenStringIndex = 0;/*保存当前要返回的token ； */TokenType currentToken;当前状态StateType state = START;/*表示保存到tokenstring的 flag */int save;while (state != DONE)int c = getNextChar(); /*从输入 buf 中读入一个字符*/save = TRUE;swi

33、tch (state)case START:if (isdigit(c)state = INNUM;else if (isalpha(c) /*判断字母 */state = INID;else if (c = ':')state = INASSIGN;else if (c = ' ') | (c = '/t') | (c = '/n')save = FALSE;else if (c = '')save = FALSE;state = INCOMMENT;elsestate = DONE;switch (c)case

34、 EOF:save = FALSE;currentToken = ENDFILE;break;case '=':currentToken = EQ;break;case '<':专业整理word 格式文档currentToken = LT;break;case '+':currentToken = PLUS;break;case '-':currentToken = MINUS;break;case '*':currentToken = TIMES;break;case '/':current

35、Token = OVER;break;case '(':currentToken = LPAREN;break;case ')':currentToken = RPAREN;break;case '':currentToken = SEMI;break;default:currentToken = ERROR;break;break;case INCOMMENT:save = FALSE;if (c = EOF)state = DONE;currentToken = ENDFILE;else if (c = '') state =

36、 START;break;case INASSIGN:state = DONE;if (c = '=')currentToken = ASSIGN;else专业整理word 格式文档/*在输入中备份*/ungetNextChar();save = FALSE;currentToken = ERROR;break;case INNUM:if (!isdigit(c)/*在输入中备份*/ungetNextChar();save = FALSE;state = DONE;currentToken = NUM;break;case INID:if (!isalpha(c)/*在输入中备

37、份*/ungetNextChar();save = FALSE;专业整理word 格式文档state = DONE;currentToken = ID;break;case DONE:default: /*应该不会执行*/fprintf(listing,"Scanner Bug: state= %d/n",state);state = DONE;currentToken = ERROR;break;if (save) && (tokenStringIndex <= MAXTOKENLEN)tokenStringtokenStringIndex+ = (

38、char) c;/*解析单词结束*/if (state = DONE)tokenStringtokenStringIndex = '/0'if (currentToken = ID)currentToken = reservedLookup(tokenString);专业整理word 格式文档if (TraceScan)fprintf(listing,"/t%d: ",lineno);printToken(currentToken,tokenString);return currentToken;SCAN.H/*/*对于 tiny编译器的扫描程序接口*/*/

39、#ifndef _SCAN_H_#define _SCAN_H_/* maxtokenlen是 token 的最大大小 */#define MAXTOKENLEN 40/* tokenString数组保存每个token */extern char tokenStringMAXTOKENLEN+1;/* f函数 getToken 返回源程序中的下一个token*/TokenType getToken(void);#endifUTIL.H/*/* File: util.h*/* Utility functions for the TINY compiler*/* Compiler Construc

40、tion: Principles and Practice*/* Kenneth C. Louden*/*/专业整理word 格式文档#ifndef _UTIL_H_#define _UTIL_H_/* Procedure printToken prints a token* and its lexeme to the listing file*/void printToken( TokenType, const char* );/* Function newStmtNode creates a new statement* node for syntax tree construction*

41、/TreeNode * newStmtNode(StmtKind);/* Function newExpNode creates a new expression* node for syntax tree construction*/TreeNode * newExpNode(ExpKind);/* Function copyString allocates and makes a new* copy of an existing string*/char * copyString( char * );/* procedure printTree prints a syntax tree t

42、o the* listing file using indentation to indicate subtrees*/void printTree( TreeNode * );#endifUTIL.C/*/* File: util.c*/* Utility function implementation*/* for the TINY compiler*/* Compiler Construction: Principles and Practice*/* Kenneth C. Louden*/*/#include "globals.h"#include "ut

43、il.h"专业整理word 格式文档/* Procedure printToken prints a token* and its lexeme to the listing file*/void 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,"re

44、served 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;c

45、ase 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"); b

46、reak; 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: /* should never happen */fprintf(listing,"Unknown token: %dn",

47、token);专业整理word 格式文档/* Function newStmtNode creates a new statement* node for syntax tree construction*/TreeNode * newStmtNode(StmtKind kind)/此函数创建一个有关此法树的声明节点 TreeNode * t = (TreeNode *) malloc(sizeof(TreeNode);int i;if (t=NULL)fprintf(listing,"Out of memory error at line %dn",lineno);else for (i=0;i<MAXCHILDREN;i+) t->childi = NULL;t->sibling = NULL;t->nodekind