编译原理课程设计C-语言编译器.doc

编译原理课程设计报告课题名称： C-语言编译器设计 提交文档学生姓名： 李杰 提交文档学生学号： 0743041240 同组 成 员 名 单： 无 指导 教 师 姓 名： 金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2010年 6 月 10日1. 课程设计目标实验建立C-编译器。只含有scanner和parser部分。2. 分析与设计（1）实现方法：编程语言为C语言。编程方法：scanner部分根据DFA图用switch-case结构实现状态转换；parser部分用递归下降分析方法实现。（2）扫描器：C惯用的词法1、语言的关键字：else if int return void while 2、专用符号：+ - * / = = != = ; , ( ) /* */ 3、其他标记是ID和NUM，通过下列正则表达式定义：ID = letter letter* NUM = digit digit* letter = a|.|z|A|.|Z digit = 0|.|94、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。 5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套各单词的状态转换图（DFA图如下）词法结构见文件globals.h中。（3）分析器：分析树结构见文件globals.h中。C的BNF语法如下：（4）代码设计说明：程序结构：语法分析函数parse通过调用词法分析函数getToken实现语法分析。文件和函数的设计说明：文件main.c包含相应头文件，及main函数的实现；文件golbals.h包含符号表和分析数的数据结构及在其它文件中使用的变量；文件util.h 和util.c实现与词法分析和语法分析输出相关的函数printToken和printTree，以及分析树节点初始化相关的函数newStmtNode，newExpNode(Expkind)和copyString；文件scan.h 和scan.c实现词法分析，主要函数为getToken；文件parse.h 和parse.c实现语法分析，函数为与文法规则对应的函数。关键数据结构3. 程序代码实现文件main.c代码如下：/实验建立C-编译器。只含有scanner和parser部分。#includeglobals.h#include util.h#include scan.h#include parse.h/全局变量和标志int lineno=0;FILE*source;FILE*listing;FILE*code;int EchoSource=TRUE;int TraceScan=TRUE;int TraceParse=TRUE;int Error=FALSE;int main(int argc,char*argv) TreeNode*syntaxTree; char pgm120; /代码文件名 if(argc!=2) fprintf(stderr,usage:%s C:source.c n,argv0); return -1; strcpy(pgm,argv1); if (strchr(pgm,.)=NULL) strcat(pgm,.tny); source=fopen(pgm,r); if(source=NULL) fprintf(stderr,file %s not found n,pgm); return -1; listing=stdout; fprintf(listing,n C-COMPILATION: %sn,pgm); / while (getToken()!=ENDFILE); EchoSource=FALSE;TraceScan=FALSE; syntaxTree=parse(); if(TraceParse) fprintf(listing,nSyntax treen:); printTree(syntaxTree); fclose(source); return 0;文件globals.h代码如下：#ifndef _GLOBALS_H_#define _GLOBALS_H_#include #include #include #include #ifndef FALSE#define FALSE 0#endif#ifndef TRUE#define TRUE 1#endif#define MAXRESERVED 6typedef enumENDFILE,ERROR,IF,ELSE,INT,RETURN,VOID,WHILE, /关键字ID,NUM,ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI,BT,LQ,BQ,UEQ,DOU,LZGH,RZGH,LDGH,RDGH,/特殊字符 TokenType;extern FILE* source ;extern FILE* listing;extern FILE* code;extern int lineno;/语法分析树typedef enum Stmtk,Expk Nodekind;typedef enum IfK,ElseK,IntK,ReturnK,VoidK,WhileK,AssignK,HanK,HanshutiK Stmtkind;typedef enum Opk,Constk,Idk,Vark Expkind;typedef enum Void,Integer,Boolean ExpType; #define MAXCHILDREN 3typedef struct treeNodestruct treeNode*childMAXCHILDREN;struct treeNode*sibling;int lineno; Nodekind nodekind;union Stmtkind stmt; Expkind exp; kind;union TokenType op; int val;char*name; attr; ExpType type; TreeNode;extern int EchoSource;extern int TraceScan;extern int TraceParse;extern int Error;#endif文件util.h代码如下：#ifndef _UTIL_H_#define _UTIL_H_void printToken( TokenType, const char*) ;/为分析树TreeNode*newStmtNode(Stmtkind);TreeNode*newExpNode(Expkind);char*copyString( char*);void printTree( TreeNode*);#endif文件util.c代码如下：#include globals.h#include util.hvoid printToken( TokenType token, const char* tokenString ) switch (token) case IF: case INT: case ELSE: case RETURN: case VOID: case WHILE: fprintf(listing, reserved word: %sn,tokenString); break; case ASSIGN: fprintf(listing,=n); break; case LT: fprintf(listing,n); break;case LQ: fprintf(listing,=n); break; case UEQ: fprintf(listing,!=n); break;case DOU: fprintf(listing,n); break;case LZGH: fprintf(listing,n); break;case RZGH: fprintf(listing,n); break;case LDGH: fprintf(listing,n); break; case RDGH: 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: /* should never happen */ fprintf(listing,Unknown token: %dn,token); TreeNode*newStmtNode(Stmtkind kind) TreeNode*p=(TreeNode*)malloc(sizeof(TreeNode); int k; if(p=NULL) fprintf(listing,out of memory error at line %dn,lineno); else for(k=0;kchildk=NULL; p-sibling=NULL; p-nodekind=Stmtk; p-kind.stmt=kind; p-lineno=lineno; return p;TreeNode*newExpNode(Expkind kind) TreeNode*p=(TreeNode*)malloc(sizeof(TreeNode); int k; if(p=NULL) fprintf(listing,out of memory error at line %dn,lineno); else for(k=0;kchildk=NULL; p-sibling=NULL; p-nodekind=Expk; p-kind.exp=kind; p-lineno=lineno; p-type=Void; return p;char*copyString( char*s)int i;char*p;if(s=NULL) return NULL; i=strlen(s)+1;p=malloc(i);if(p=NULL) fprintf(listing,out of memory error at line %dn,lineno); else strcpy(p,s); return p;static indentno=0;#define INDENT indentno+=2#define UNINDENT indentno-=2static void printSpace(void)int k;for(k=0;knodekind=Stmtk) switch (t-kind.stmt) case IfK: fprintf(listing,Ifn); break; case IntK: fprintf(listing,Intn); break; case VoidK: fprintf(listing,Voidn); break; case ReturnK: fprintf(listing,Returnn); break; case WhileK: fprintf(listing,Whilen); break; case AssignK: fprintf(listing,Assign to: %sn,); break; case HanK: fprintf(listing,Hanshun); break; case HanshutiK: fprintf(listing,Hanshutin); break; default: fprintf(listing,Unknown stmt kindn); break; else if(t-nodekind=Expk) switch (t-kind.exp) case Opk: fprintf(listing,Op:); printToken(t-attr.op,0); break; case Constk: fprintf(listing,Const: %dn,t-attr.val); break; case Idk: fprintf(listing,Id: %sn,); break; case Vark: fprintf(listing,Vark: %dn,t-attr.val); break; default: fprintf(listing,Unknown exp kindn); break; else fprintf(listing,Unknown exp kindn); for(i=0;ichildi); t=t-sibling; UNINDENT;文件scan.h代码如下：#ifndef _SCAN_H_#define _SCAN_H_#define MAXTOKENLEN 40extern char tokenStringMAXTOKENLEN+1;TokenType getToken(void);#endif文件scan.c代码如下：#includeglobals.h#include util.h#include scan.h/DFA中的状态typedef enumSTART,INID,INNUM,DONE,INASSIGN,INCOMMENT,ZHU,ZZHU StateType;char tokenStringMAXTOKENLEN+1;#define BUFLEN 256 /代码文件的行数static char lineBufBUFLEN; /保存当前行static int linepos=0; /lineBuf中的当前位置static int bufsize=0; /buffer 串的大小static int EOF_Flag=FALSE;/获取字符从lineBufBUFLEN中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+; /先返回lineBuflinepos，后linepos加1.else EOF_Flag=TRUE; return EOF;else return lineBuflinepos+;/没有取得字符。static void ungetNextChar(void)if(!EOF_Flag) linepos-;/关键字的查找表static struct char* str; TokenType tok; reservedWordsMAXRESERVED= if,IF,else,ELSE,void,VOID,return,RETURN,int,INT,while,WHILE;/关键字的查找static TokenType reserveLookup(char*s)int i;for(i=0;i:1、) f1=1; state=INASSIGN; else if(c=) f1=2; state=INASSIGN; else if(c=) f1=3; state=INASSIGN; else if(c=!) f1=4; state=INASSIGN; else if(c= )|(c=t)|(c=n) save=FALSE; else if (c=/) save=FALSE; state=ZHU; else state=DONE; switch (c) case EOF: save=FALSE; currentToken=ENDFILE; break; case +: currentToken=PLUS; break; case -: currentToken=MINUS; break; case *: currentToken=TIMES; break; case (: currentToken=LPAREN; break; case ): currentToken=RPAREN; break; case : currentToken=LZGH; break; case : currentToken=RZGH; break; case : currentToken=LDGH; break; case : currentToken=RDGH; break; case ;: currentToken=SEMI; break; case ,: currentToken=DOU; break; default: currentToken=ERROR; break; break; case ZHU: if(c=*) save=FALSE; state=INCOMMENT; else ungetNextChar(); save=TRUE; /取“/”号 state=DONE; currentToken=OVER; break; case INCOMMENT: save=FALSE; if(c=EOF) state=DONE; currentToken=ENDFILE; else if(c=*) state=ZZHU; break; case ZZHU: save=FALSE;if(c=EOF) state=DONE; currentToken=ENDFILE;else if(c=*) state=ZZHU; else if(c=/) state=START; else state=INCOMMENT; break; case INASSIGN: state=DONE; if(c=) if(f1=1) currentToken=BQ; else if(f1=2) currentToken=LQ; else if(f1=3) currentToken=EQ; else if(f1=4) currentToken=UEQ; else save=FALSE; currentToken=ERROR; else ungetNextChar(); if(f1=1) currentToken=BT; else if(f1=2) currentToken=LT; else if(f1=3) currentToken=ASSIGN; else save=FALSE; currentToken=ERROR; break; case INNUM: if(!isdigit(c) /NUM完。 ungetNextChar(); save=FALSE; state=DONE; currentToken=NUM; break; case INID: if(!isalpha(c) /标识符完。 ungetNextChar(); save=FALSE; state=DONE; currentToken=ID; break; case DONE: default: /should never happen fprintf(listing,Scanner Bug: state=%dn,state); state=DONE; currentToken=ERROR; break; if(save)&(tokenStringIndex ); fprintf(listing,Syntax error at line %d: %sn,lineno,me); Error=TRUE;static void match(TokenType ex)if(token=ex) token=getToken();else syntaxError(unexoected token-); printToken(token, tokenString); fprintf(listing, ); static TreeNode*program() TreeNode* t=declaration(); TreeNode* p=t; while(token!=INT)&(token!=VOID) syntaxError(unexpected token-); printToken(token, tokenString);token=getToken(); while(token=INT)|(token=VOID) TreeNode* q; q=declaration();if(q!=NULL)if(t=NULL) t=p=q;else p-sibling=q; p=q; return t;static TreeNode*declaration(void) TreeNode* t=NULL; if(token=INT) t=newStmtNode(IntK);match(INT); if(token=VOID) t=newStmtNode(VoidK);match(VOID); if(t!=NULL)&(token=ID) TreeNode* p=NULL; p=newExpNode(Idk); =copyString(tokenString); t-child0=p; match(ID); if(token=LPAREN)&(t-child0!=NULL) t-child1=func_declaration(); else if(token=LZGH)|(token=SEMI) t-child1=var_declaration(); else syntaxError(unexpected token-); printToken(token, tokenString); return t;static TreeNode*func_declaration(void) TreeNode* t=newStmtNode(HanK); match(LPAREN); t-child0=params(); /*get the param list*/ match(RPAREN); t-child1=compound_stmt(); return t;static TreeNode*var_declaration(void) TreeNode* t=NULL; if(token=LZGH) match(LZGH); t=newExpNode(Vark);if(t!=NULL)&(token=NUM) t-attr.val=atoi(tokenString); else syntaxError(unexpected token-); printToken(token, tokenString); match(NUM); match(RZGH); match(SEMI); else match(SEMI); /将;号辨别放在declaration中 return t;static TreeNode*params(void) TreeNode* t=NULL; if(token=VOID) t=newStmtNode(VoidK); match(VOID); else if(token=INT) t=param_list(); else syntaxError(unexpected token-); printToken(token, tokenString); return t;static TreeNode*param_list(void) TreeNode* t=param(); TreeNode* p=t; while(token=DOU) TreeNode*q=NULL; match(DOU); q=param(); if(q!=NULL) if(t=NULL) t=p=q; else p-sibling=q; p=q; return t;static TreeNode*param(void) TreeNode* t=NULL; if(token=INT) t=newStmtNode(IntK); match(INT); if(token=ID) TreeNode* p=NULL; p=newExpNode(Idk); =copyString(tokenString); t-child0=p; match(ID); else syntaxError(unexpected token-); printToken(token, tokenString); if(token=LZGH)&(t-child0!=NULL) match(LZGH); t-child1=newExpNode(Vark); match(RZGH); else return t; else syntaxError(unexpected token-); printToken(token, tokenString); return t;static TreeNode*compound_stmt(void) TreeNode* t=newStmtNode(HanshutiK); match(LDGH); if(token=INT) t-child1=local_var_declaration();if(token=RDGH) match(RDGH); return t; else t-child2=statement_list(); else if(token=RDGH) match(RDGH); return t; else t-child0=statement_list(); while(token!=RDGH)&(token!=ENDFILE) token=getToken(); match(RDGH); return t;stat