TINY部分源碼分析報告

精品資料TINY源碼分析一、文件概述MAIN.C:主函數(shù)GLOBALS.H:全局定義的文件SCAN.C/SCAN.H:詞法分析PARSE.C/PARSE.H:語法分析UTIL.C/UTIL.H:構(gòu)造樹SYMTAB.C/SYMTAB.H:符號表CGEN.C/CGEN.H:生成"匯編代碼"CODE.C/CODE.H:這個只是用來把分析過程輸出到屏幕的.二、各個文件的分析1.MAIN.C:主要有三個FILE*句柄:source-源代碼文件。listing-顯示分析過程的文件，這里重定向到stdout。code-目標(biāo)匯編代碼文件。從該文件中可知程序運(yùn)行的流程：檢查參數(shù)正確否（tiny.exefilename）->構(gòu)造語法樹（調(diào)用parse函數(shù)）->根據(jù)語法樹生成代碼（調(diào)用codeGen函數(shù)，該函數(shù)又調(diào)用cGen函數(shù)。2.GLOBALS.H:定義了關(guān)鍵字個數(shù)8個。定義了關(guān)鍵字，運(yùn)算符等內(nèi)容的枚舉值。定義了語句類型的枚舉值，這個決定樹的結(jié)點。可編輯修改定義了變量類型(也就三種，void,integer,boolean)。定義了樹的節(jié)點-這個最重要了！其結(jié)構(gòu)如下所示：typedefstructtreeNodestructtreeNode*childMAXCHILDREN;structtreeNode*sibling;intlineno;NodeKindnodekind;unionStmtKindstmt;ExpKindexp;kind;unionTokenTypeop;intval;char*name;attr;ExpTypetype;/*fortypecheckingofexps*/TreeNode;3.UTIL.C/UTIL.H主要函數(shù)TreeNode*newStmtNode(StmtKindkind)此函數(shù)創(chuàng)建一個有關(guān)語法樹的聲明節(jié)點TreeNode*newExpNode(ExpKindkind)此函數(shù)創(chuàng)建一個有關(guān)語法樹的表述節(jié)點char*copyString(char*s)此函數(shù)分配和創(chuàng)建一個新的已存在樹的復(fù)制voidprintTree(TreeNode*tree)輸出一個語法樹這兩個文件主要是關(guān)于語法樹的創(chuàng)建和輸出4.SCAN.c/SCAN.H主要有這么幾個函數(shù)：staticintgetNextChar(void);staticvoidungetNextChar(void);staticTokenTypereservedLookup(char*s);TokenTypegetToken(void);reservedLookup函數(shù)是查找關(guān)鍵字的，在符號表中找。這里還定義了一個保存關(guān)鍵字的結(jié)構(gòu)：staticstructchar*str;TokenTypetok;reservedWordsMAXRESERVED"if",IF,"then",THEN,"else",ELSE,"end",END,"repeat",REPEAT,"until",UNTIL,"read",READ,"write",WRITE;最重要的是getToken(void)函數(shù)。這個相當(dāng)于lex的功能，進(jìn)行詞法分析。也就是一個DFA，switch后面跟了一堆的case。其中g(shù)etNextChar(void)函數(shù)的思路，以下列出：staticintgetNextChar(void)if(!(linepos<bufsize)lineno+;if(fgets(lineBuf,BUFLEN-1,source)if(EchoSource)fprintf(listing,"%4d:%s",lineno,lineBuf);bufsize=strlen(lineBuf);linepos=0;returnlineBuflinepos+;elseEOF_flag=TRUE;returnEOF;elsereturnlineBuflinepos+;4.PARSE.C/PARSE.H有這么幾個函數(shù)：TreeNode*parse(void)staticTreeNode*stmt_sequence(void);staticTreeNode*statement(void);staticTreeNode*if_stmt(void);staticTreeNode*repeat_stmt(void);staticTreeNode*assign_stmt(void);staticTreeNode*read_stmt(void);staticTreeNode*write_stmt(void);staticTreeNode*exp(void);staticTreeNode*simple_exp(void);staticTreeNode*term(void);staticTreeNode*factor(void);最重要的是parse這個函數(shù)，就是用來構(gòu)造整個程序的語法樹的。下面的一堆私有函數(shù)構(gòu)造相應(yīng)語法的語法樹，然后parse最后把它們這些子樹整合成一個大樹。5.SYMTAB.C/SYMTAB.H這個是符號表操作的，也就是詞法分析的時候查找表，看該token是不是關(guān)鍵字。如果不是，就當(dāng)作表識符添加進(jìn)去。在語法分析的時候也要用到，看變量有沒有聲明的時候用的。三、實驗心得：通過這次實驗，仔細(xì)地去查看和分析了TINY編譯器的部分源碼。了解到了編譯器的運(yùn)行：檢查參數(shù)正確否(tiny.exefilename)->構(gòu)造語法樹(調(diào)用parse函數(shù))->根據(jù)語法樹生成代碼(調(diào)用codeGen函數(shù))，同時熟悉了編譯器是如何使用prase函數(shù)進(jìn)行語法樹的構(gòu)建以及語法樹生成代碼的轉(zhuǎn)化，最主要的是進(jìn)一步清晰了解到編譯器的構(gòu)造和運(yùn)行原理，加深了對課本知識的運(yùn)用和拓展，感覺收獲很大！Main.c/*/*/*/*/*/*File:main.c/*MainprogramforTINYcompiler/*CompilerConstruction:PrinciplesandPractice/*KennethC.Louden/*/#include "globals.h/* set NO_PARSE to TRUE to get a scanner-only compiler創(chuàng)建一個只掃描的編譯器*/#define NO_PARSE FALSE/* set NO_ANALYZE to TRUE to get a parser-only compiler時創(chuàng)建一個只分析和掃描的編譯器*/#define NO_ANALYZE FALSENO_PARSE 為 true 時NO_ANALYZE 為 true/*setNO_CODEtoTRUEtogetacompilerthatdoesnot*generatecodeNO_CODE為true時創(chuàng)建一個執(zhí)行語義分析，但不生成代碼的編譯器*/#include "util.h"#if NO_PARSE #include "scan.h" #else#include "parse.h" #if !NO_ANALYZE #include "analyze.h #if !NO_CODE #include "cgen.h" #endif#defineNO_CODEFALSE/如果NO_PARSE為true,調(diào)用頭文件scan.h/否則調(diào)用頭文件prase.h/如果NO_ANALYZE為true,調(diào)用頭文件analyze.h/如果NO_CODE為true,調(diào)用頭文件cgen.h#endif#endif/結(jié)束預(yù)處理語句符號/*allocateglobalvariables分配全局變量*/intlineno=0;FILE*source;/指針指向源代碼文件地址FILE*listing;/指針指向顯示分析過程的文件的地址FILE*code;/指針指向目標(biāo)匯編代碼文件的地址/*allocateandsettracingflags分配和設(shè)置跟蹤標(biāo)志*/intEchoSource=FALSE;intTraceScan=FALSE;intTraceParse=FALSE;intTraceAnalyze=FALSE;intTraceCode=FALSE;intError=FALSE;/跟蹤標(biāo)志全部初始化為falsemain(intargc,char*argv)TreeNode*syntaxTree;charpgm120;/*sourcecodefilename*/if(argc!=2)fprintf(stderr,"usage:%s<filename>n",argv0);exit(1);/如果argv不為2，打印顯示信息并退出strcpy(pgm,argv1);/復(fù)制argv1地址以null為退出字符的存儲器區(qū)塊到另一個存儲器區(qū)塊品pgm內(nèi)if(strchr(pgm,'.')=NULL)strcat(pgm,".tny");/把.tyn文件所指字符串添加到pgm結(jié)尾處并添加'0'。source=fopen(pgm,"r");/以只讀的方式打開pgm文件，并將指向pgm文件的指針返回給sourceif(source=NULL)fprintf(stderr,"File%snotfoundn",pgm);exit(1);/如果源代碼文件為空，打印顯示信息并退出listing=stdout;/*sendlistingtoscreen清單發(fā)送到屏幕*/fprintf(listing,"nTINYCOMPILATION:%sn",pgm);/答應(yīng)顯示語句#ifNO_PARSEwhile(getToken()!=ENDFILE);/如果輸入流沒有結(jié)束就繼續(xù)進(jìn)行循環(huán)，直至結(jié)束#elsesyntaxTree=parse();/調(diào)用prase()函數(shù)構(gòu)造語法樹if(TraceParse)fprintf(listing,"nSyntaxtree:n");printTree(syntaxTree);/如果語法分析追蹤標(biāo)志為TRUE且沒有語法錯誤,則將生成的語法樹輸出到屏幕#if!NO_ANALYZEif(!Error)if(TraceAnalyze)fprintf(listing,"nBuildingSymbolTable.n");buildSymtab(syntaxTree);/輸出含符號表信息的語法樹if(TraceAnalyze)fprintf(listing,"nCheckingTypes.n");typeCheck(syntaxTree);/輸出含類型檢查的語法樹if(TraceAnalyze)fprintf(listing,"nTypeCheckingFinishedn");/打印結(jié)束信息#if!NO_CODEif(!Error)char*codefile;intfnlen=strcspn(pgm,".");codefile=(char*)calloc(fnlen+4,sizeof(char);strncpy(codefile,pgm,fnlen);strcat(codefile,".tm");/將源文件名，去掉擴(kuò)展名，添加擴(kuò)展名.tmcode=fopen(codefile,"w");/以只寫的方式打開目標(biāo)匯編代碼文件，并返回地址給codez指針if(code=NULL)printf("Unabletoopen%sn",codefile);exit(1);/如果code指針為空，打印顯示信息并退出codeGen(syntaxTree,codefile);/目標(biāo)代碼生成fclose(code);#endif#endif#endif/結(jié)束之前對應(yīng)的條件編譯fclose(source);/關(guān)閉源代碼文件return0;GLOBALS.H/*/*File:globals.h*/*GlobaltypesandvarsforTINYcompiler*/*mustcomebeforeotherincludefiles*/*CompilerConstruction:PrinciplesandPractice*/*KennethC.Louden*/*/#ifndef_GLOBALS_H_#define_GLOBALS_H_/宏定義#include<stdio.h>#include<stdlib.h>#include<ctype.h>#include<string.h>/頭文件引用#ifndefFALSE#defineFALSE0/定義FALSE為0#endif#ifndefTRUE#defineTRUE1/定義TRUE為1#endif/*MAXRESERVED=thenumberofreservedwords*/#defineMAXRESERVED8/定義了關(guān)鍵字個數(shù)8個typedefenum/*book-keepingtokens*/ENDFILE,ERROR,/*reservedwords*/IF,THEN,ELSE,END,REPEAT,UNTIL,READ,WRITE,/*multicharactertokens*/ID,NUM,/*specialsymbols*/ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMITokenType;/定義了關(guān)鍵字，運(yùn)算符等內(nèi)容的枚舉值externFILE*source;/*sourcecodetextfileexternFILE*listing;/*listingoutputtextfile源代碼地址*/顯示分析過程的文件的地址*/目標(biāo)匯編代碼文件的地址 */externFILE*code;/*codetextfileforTMsimulatorexternintlineno;/*sourcelinenumberforlisting*/*/*Syntaxtreeforparsing*/*/typedefenumStmtK,ExpKNodeKind;/定義了語句類型的枚舉值，這個決定樹的節(jié)點typedefenumIfK,RepeatK,AssignK,ReadK,WriteKStmtKind;typedefenumOpK,ConstK,IdKExpKind;/*ExpTypeisusedfortypechecking*/typedefenumVoid,Integer,BooleanExpType;/定義了變量類型#defineMAXCHILDREN3/定義了最大子節(jié)點typedefstructtreeNode/定義了樹的節(jié)點structtreeNode*childMAXCHILDREN;structtreeNode*sibling;intlineno;NodeKindnodekind;unionStmtKindstmt;ExpKindexp;kind;unionTokenTypeop;intval;char*name;attr;ExpTypetype;/*fortypecheckingofexps*/TreeNode;/*Flags for tracing*/*/*/*EchoSource=TRUEcausesthesourceprogramto* beechoedtothelistingfilewithlinenumbers* duringparsing* /externintEchoSource;/*TraceScan=TRUEcausestokeninformationtobe* printedtothelistingfileaseachtokenis* recognizedbythescanner* /externintTraceScan;/*TraceParse=TRUEcausesthesyntaxtreetobe* printedtothelistingfileinlinearizedform* (usingindentsforchildren)* /externintTraceParse;/*TraceAnalyze=TRUEcausessymboltableinserts* andlookupstobereportedtothelistingfile*/externintTraceAnalyze;/*TraceCode=TRUEcausescommentstobewritten* totheTMcodefileascodeisgenerated*/externintTraceCode;/*Error=TRUEpreventsfurtherpassesifanerroroccurs*/externintError;#endifSCAN.C/*詞法掃描程序*/#include"globals.h"#include"util.h"#include"scan.h"/*定義的狀態(tài)*/typedefenumSTART,/*初始狀態(tài)*/INASSIGN,/*進(jìn)入到賦值狀態(tài)*/INCOMMENT,/*進(jìn)入到注釋狀態(tài)*/INNUM,/*進(jìn)入到數(shù)字狀態(tài)*/INID,/*進(jìn)入到標(biāo)志符狀態(tài)*/DONE/*狀態(tài)結(jié)束*/StateType;/*每當(dāng)語法分析程序需要一個單詞時,就調(diào)用該子程序,得到（類別碼,單詞的值）*/*語義標(biāo)識符和保留字*/chartokenStringMAXTOKENLEN+1;/*BUFLEN=源代碼的輸入緩沖長度*/#defineBUFLEN256staticcharlineBufBUFLEN;/*當(dāng)前行*/staticintlinepos=0;/*在linebuf中的當(dāng)前位置*/staticintbufsize=0;/*緩沖區(qū)的字符串當(dāng)前大小*/staticintEOF_flag=FALSE;/*如果讀入下一個字符出錯，設(shè)置EOF_flag為假。*/*從linebuffer中讀取下一個非空白字符，如果讀完，則讀入新行。*/staticintgetNextChar(void)if(!(linepos<bufsize)lineno+;if(fgets(lineBuf,BUFLEN-1,source)if(EchoSource)fprintf(listing,"%4d:%s",lineno,lineBuf);bufsize=strlen(lineBuf);linepos=0;returnlineBuflinepos+;elseEOF_flag=TRUE;returnEOF;elsereturnlineBuflinepos+;/*如果讀入下一個字符出錯，在linebuf中回退一個字符。*/staticvoidungetNextChar(void)if(!EOF_flag)linepos-;/*保留字的查找表*/staticstructchar*str;TokenTypetok;reservedWordsMAXRESERVED="if",IF,"then",THEN,"else",ELSE,"end",END,"repeat",REPEAT,"until",UNTIL,"read",READ,"write",WRITE;/*標(biāo)識符是否是保留字*/staticTokenTypereservedLookup(char*s)inti;for(i=0;i<MAXRESERVED;i+)if(!strcmp(s,reservedWordsi.str)returnreservedWordsi.tok;returnID;/*掃描儀的主要功能函數(shù)gettoken返回源文件中下一個標(biāo)記*/TokenTypegetToken(void)/*存入tokenstring的位置*/inttokenStringIndex=0;/*保存當(dāng)前要返回的token；*/TokenTypecurrentToken;當(dāng)前狀態(tài)StateTypestate=START;/*表示保存到tokenstring的flag*/intsave;while(state!=DONE)intc=getNextChar();/*從輸入buf中讀入一個字符*/save=TRUE;switch(state)caseSTART:if(isdigit(c)state=INNUM;elseif(isalpha(c)/*判斷字母*/state=INID;elseif(c=':')state=INASSIGN;elseif(c='')|(c='/t')|(c='/n')save=FALSE;elseif(c='')save=FALSE;state=INCOMMENT;elsestate=DONE;switch(c)caseEOF:save=FALSE;currentToken=ENDFILE;break;case'=':currentToken=EQ;break;case'<':currentToken=LT;break;case'+':currentToken=PLUS;break;case'-':currentToken=MINUS;break;casecurrentToken=TIMES;break;case'/':currentToken=OVER;break;case'(':currentToken=LPAREN;break;case')':currentToken=RPAREN;break;case'':currentToken=SEMI;break;default:currentToken=ERROR;break;break;caseINCOMMENT:save=FALSE;if(c=EOF)state=DONE;currentToken=ENDFILE;elseif(c='')state=START;break;caseINASSIGN:state=DONE;if(c='=')currentToken=ASSIGN;else/*在輸入中備份*/ungetNextChar();save=FALSE;currentToken=ERROR;break;caseINNUM:if(!isdigit(c)/*在輸入中備份*/ungetNextChar();save=FALSE;state=DONE;currentToken=NUM;break;caseINID:if(!isalpha(c)/*在輸入中備份*/ungetNextChar();save=FALSE;state=DONE;currentToken=ID;break;caseDONE:default:/*應(yīng)該不會執(zhí)行*/fprintf(listing,"ScannerBug:state=%d/n",state);state=DONE;currentToken=ERROR;break;if(save)&&(tokenStringIndex<=MAXTOKENLEN)tokenStringtokenStringIndex+=(char)c;/*解析單詞結(jié)束*/if(state=DONE)tokenStringtokenStringIndex='/0'if(currentToken=ID)currentToken=reservedLookup(tokenString);if(TraceScan)fprintf(listing,"/t%d:",lineno);printToken(currentToken,tokenString);returncurrentToken;SCAN.H/*/*對于tiny編譯器的掃描程序接口*/*/#ifndef_SCAN_H_#define_SCAN_H_/*maxtokenlen是token的最大大小*/#defineMAXTOKENLEN40/*tokenString數(shù)組保存每個token*/externchartokenStringMAXTOKENLEN+1;/*f函數(shù)getToken返回源程序中的下一個token*/TokenTypegetToken(void);#endifUTIL.H/*/*/*File:util.h/*UtilityfunctionsfortheTINYcompiler*/*CompilerConstruction:PrinciplesandPractice*/*/*KennethC.Louden/*/#ifndef_UTIL_H_#define_UTIL_H_/*ProcedureprintTokenprintsatoken* anditslexemetothelistingfile* /voidprintToken(TokenType,constchar*);/*FunctionnewStmtNodecreatesanewstatement* nodeforsyntaxtreeconstruction* /TreeNode*newStmtNode(StmtKind);/*FunctionnewExpNodecreatesanewexpression* nodeforsyntaxtreeconstruction* /TreeNode*newExpNode(ExpKind);/*FunctioncopyStringallocatesandmakesanew* copyofanexistingstring* /char*copyString(char*);/*procedureprintTreeprintsasyntaxtreetothe* listingfileusingindentationtoindicatesubtrees* /voidprintTree(TreeNode*);#endifUTIL.C/*/*/*File:util.c/*Utilityfunctionimplementation*/*fortheTINYcompiler*/*CompilerConstruction:PrinciplesandPractice*/*/*KennethC.Louden/*/#include"globals.h#include"util.h"/*ProcedureprintTokenprintsatoken* anditslexemetothelistingfile此函數(shù)輸出一個標(biāo)號*/voidprintToken(TokenTypetoken,constchar*tokenString)/和一個詞素switch(token)caseIF:caseTHEN:caseELSE:caseEND:caseREPEAT:caseUNTIL:caseREAD:caseWRITE:fprintf(listing,"reservedword:%sn",tokenString);break;caseASSIGN:fprintf(listing,":=n");break;caseLT:fprintf(listing,"<n");break;caseEQ:fprintf(listing,"=n");break;caseLPAREN:fprintf(listing,"(n");break;caseRPAREN:fprintf(listing,")n");break;caseSEMI:fprintf(listing,"n");break;casePLUS:fprintf(listing,"+n");break;caseMINUS:fprintf(listing,"-n");break;caseTIMES:fprintf(listing,"*n");break;caseOVER:fprintf(listing,"/n");break;caseENDFILE:fprintf(listing,"EOFn");break;caseNUM:fprintf(listing,"NUM,val=%sn",tokenString);break;caseID:fprintf(listing,"ID,name=%sn",tokenString);break;caseERROR:fprintf(listing,"ERROR:%sn",tokenString);break;default:/*shouldneverhappen*/fprintf(listing,"Unknowntoken:%dn",token);/*FunctionnewStmtNodecreatesanewstatement* nodeforsyntaxtreeconstruction* /TreeNode*newStmtNode(StmtKindkind)/此函數(shù)創(chuàng)建一個有關(guān)此法樹的聲明節(jié)點TreeNode*t=(TreeNode*)malloc(sizeof(TreeNode);inti;if(t=NULL)fprintf(listing,"Outofmemoryerroratline%dn",lineno);elsefor(i=0;i<MAXCHILDREN;i+)t->childi=NULL;t->sibling=NULL;t->nodekind=StmtK;t->kind.stmt=kind;t->lineno=lineno;returnt;/*FunctionnewExpNodecreatesanewexpression*nodeforsyntaxtreeconstruction*/TreeNode*newExpNode(ExpKindkind)/此函數(shù)創(chuàng)建一個有關(guān)此法樹的表述節(jié)點TreeNode*t=(TreeNode*)malloc(sizeof(TreeNode);inti;if(t=NULL)fprintf(listing,"Outofmemoryerroratline%dn",lineno);elsefor(i=0;i<MAXCHILDREN;i+)t->childi=NULL;t->sibling=NULL;t->nodekind=ExpK;t->kind.exp=kind;t->lineno=lineno;t->type=Void;returnt;/*FunctioncopyStringallocatesandmakesanew*copyofanexistingstring*/char*copyString(char*s)/此函數(shù)分配和創(chuàng)建一個新的已存在樹的復(fù)制intn;char*t;if(s=NULL)returnNULL;n=strlen(s)+1;t=malloc(n);if(t=NULL)fprintf(listing,"Outofmemoryerroratline%dn",lineno);elsestrcpy(t,s);returnt;/*VariableindentnoisusedbyprintTreeto* storecurrentnumberofspacestoindent*/staticindentno=0;/此變量被函數(shù)printTree用來存儲要縮進(jìn)的空格個數(shù)/*macrostoincrease/decreaseindentation*/#defineINDENTindentno+=2/這個宏增加縮進(jìn)空格個數(shù)#defineUNINDENTindentno-=2/這個宏減少縮進(jìn)空格個數(shù)/*printSpacesindentsbyprintingspaces*/staticvoidprintSpaces(void)/此函數(shù)通過打印空格縮進(jìn)inti;for(i=0;i<indentno;i+)fprintf(listing,"");/*procedureprintTreeprintsasyntaxtreetothe* listingfileusingindentationtoindicatesubtrees*/voidprintTree(TreeNode*tree)/輸出一個語法樹inti;INDENT;while(tree!=NULL)printSpaces();if(tree->nodekind=StmtK)switch(tree->kind.stmt)caseIfK:fprintf(listing,"Ifn");break;caseRepeatK:fprintf(listing,"Repeatn");break;caseAssignK:fprintf(listing,"Assignto:%sn",tree->attr.name);break;caseReadK:fprintf(listing,"Read:%sn",tree->attr.name);break;caseWriteK:fprintf(listing,"Writen");break;default:fprintf(listing,"UnknownExpNodekindn");break;elseif(tree->nodekind=ExpK)switch(tree->kind.exp)caseOpK:fprintf(listing,"Op:");printToken(tree->attr.op,"0");break;caseConstK:fprintf(listing,"Const:%dn",tree->attr.val);break;caseIdK:fprintf(listing,"Id:%sn",tree->attr.name);break;default:fprintf(listing,"UnknownExpNodekindn");break;elsefprintf(listing,"Unknownnodekindn");for(i=0;i<MAXCHILDREN;i+)printTree(tree->childi);tree=tree->sibling;UNINDENT;