TINY部分源码分析报告

1、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:这个只是用来把分析过程输出到屏幕的.二、各个文件的分析1.MAIN.C:主要有三个FILE*句柄:source-源代码文件。listing-显示分析过程的文件，这里重定向到stdout。code-目标汇编代码文件。从该文件中可知程序运行的流程：检查参数正确否(tiny.

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

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

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

5、t char* 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后面跟了一堆的case。其中

6、getNextChar(void)函数的思路，以下列出：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;return lineBuflinepos+;elseEOF_flag = TRUE;return EOF;else return lin

7、eBuflinepos+;4.PARSE.C/PARSE.H有这么几个函数：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);static TreeNode * read_stmt(void);static TreeNode * write_stmt(v

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

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

10、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_ANALYZE FALSE

11、/* 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#if !NO_ANALYZE#include &qu

12、ot;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 * code; /指针指向目标汇编代码文件的地址/* allocat

13、e 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 name */ if (argc != 2) fprint

14、f(stderr,"usage: %s <filename>n",argv0); exit(1); /如果argv不为2，打印显示信息并退出 strcpy(pgm,argv1) ; /复制argv1地址以null为退出字符的存储器区块到另一个存储器区块品pgm内 if (strchr (pgm, '.') = NULL) strcat(pgm,".tny"); /把.tyn文件所指字符串添加到pgm结尾处并添加'0'。 source = fopen(pgm,"r"); /以只读的方式打开pg

15、m文件，并将指向pgm文件的指针返回给source if (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_PARSE while (getToken()!=ENDFILE); /如果输入流没有结束就继续进行

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

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

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

19、codefile);/目标代码生成 fclose(code); #endif#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 C. Louden */*/#ifndef _GL

20、OBALS_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 */#define MAXRESERVED 8 /定义了

21、关键字个数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 TokenType; / 定义了关键字，运算符等内容的枚举值 extern FILE* source; /* source co

22、de 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;/定义了语句类型的枚举值，这个决定树的节点typedef

23、 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; struct treeNode * sibling; i

24、nt 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 with line numbers *

25、 during parsing */extern int EchoSource;/* TraceScan = TRUE causes token information to be * 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 linearized form * (using ind

26、ents 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 TraceCode;/* Error = TRUE

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

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

29、个字符出错，设置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; return lineBuflinepos+; else E

30、OF_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,"else",ELSE,"end&q

31、uot;,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;/* 扫描仪的主要功能函数gettoken返回源文件中

32、下一个标记 */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; switch (state) case START: if (is

33、digit(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; else state = DONE; switch (c) case EOF: save = FA

34、LSE; currentToken = ENDFILE; break; case '=': currentToken = EQ; break; case '<': currentToken = LT; break; case '+': currentToken = PLUS; break; case '-': currentToken = MINUS; break; case '*': currentToken = TIMES; break; case '/': currentToken =

35、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 = '&#

36、39;) state = START; break; case INASSIGN: state = DONE; if (c = '=') currentToken = ASSIGN; else /* 在输入中备份 */ ungetNextChar(); save = FALSE; currentToken = ERROR; break; case INNUM: if (!isdigit(c) /* 在输入中备份 */ ungetNextChar(); save = FALSE; state = DONE; currentToken = NUM; break; case INID

37、: if (!isalpha(c) /* 在输入中备份*/ ungetNextChar(); save = FALSE; 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) toke

38、nStringtokenStringIndex+ = (char) c; /*解析单词结束*/ if (state = DONE) tokenStringtokenStringIndex = '/0' if (currentToken = ID) currentToken = reservedLookup(tokenString); if (TraceScan) fprintf(listing,"/t%d: ",lineno); printToken(currentToken,tokenString); return currentToken;SCAN.H/

39、*/ /* 对于tiny编译器的扫描程序接口 */*/#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 compil

40、er */* Compiler Construction: Principles and Practice */* Kenneth C. Louden */*/#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 tr

41、ee construction */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 p

42、rints a syntax tree to 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 "glob

43、als.h"#include "util.h"/* 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: fprin

44、tf(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

45、,")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: fprin

46、tf(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: /* should never happen */ fprintf(listing,"Unknown token: %dn",token); /* Function newStmtNode creates a new stat