编译原理课程设计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