编译原理课程设计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部分。#include"globals.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 <stdio.h>#include <stdlib.h>#include <ctype.h>#include <string.h>#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.h"void 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 EQ: fprintf(listing,"=n"); break; case LPAREN: fprintf(listing,"(n"); break; case RPAREN: fprintf(listing,")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 BT: fprintf(listing,">n"); break;case LQ: fprintf(listing,"<=n"); break;case BQ: 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;k<MAXCHILDREN;k+) p->childk=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;k<MAXCHILDREN;k+) p->childk=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;k<indentno;k+) fprintf(listing," "); void printTree( TreeNode*t) int i; INDENT; while(t!=NULL) printSpace(); if(t->nodekind=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",t->attr.name); 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",t->attr.name); 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;i<MAXCHILDREN;i+) printTree(t->childi); t=t->sibling; UNINDENT;文件scan.h代码如下：#ifndef _SCAN_H_#define _SCAN_H_#define MAXTOKENLEN 40extern char tokenStringMAXTOKENLEN+1;TokenType getToken(void);#endif文件scan.c代码如下：#include"globals.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<MAXRESERVED;i+) if(!strcmp(s,reservedWordsi.str)return reservedWordsi.tok;return ID;TokenType getToken(void)/token串存放的索引 int tokenStringIndex=0;/存放返回的token TokenType currentToken;/现在的状态 StateType state=START;/token串的标记 int save; int f1=0; /标志取>:1、<:2、=:3和!:4 int d=getNextChar(); if(d=EOF) currentToken=ENDFILE; return currentToken; else ungetNextChar(); while(state!=DONE) int c=getNextChar(); save=TRUE; switch(state) case START: if(isdigit(c) state=INNUM; else if (isalpha(c) state=INID; else if(c='>') 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<=MAXTOKENLEN) tokenStringtokenStringIndex+= (char)c; if(state=DONE) tokenStringtokenStringIndex='0' if(currentToken=ID) currentToken=reserveLookup(tokenString); if (TraceScan) fprintf(listing,"t%d:",lineno); printToken(currentToken,tokenString); return currentToken;文件parse.h代码如下：#ifndef _PARSER_H#define _PARSER_HTreeNode*parse(void);#endif文件parse.c代码如下：#include "globals.h"#include "util.h"#include "parse.h"#include "scan.h"static TokenType token;/递归下降函数声明static TreeNode*program(void);static TreeNode*declaration(void);static TreeNode*func_declaration(void);static TreeNode*var_declaration(void);static TreeNode*params(void);static TreeNode*param_list(void);static TreeNode*param(void);static TreeNode*compound_stmt(void);static TreeNode*local_var_declaration(void);static TreeNode*statement_list(void);static TreeNode*statement(void);static TreeNode*selection_stmt(void);static TreeNode*iteration_stmt(void);static TreeNode*return_stmt(void);static TreeNode*expression_stmt(void);static TreeNode*expression(void);static TreeNode*simple_expression(TreeNode*k);static TreeNode*additive_expression(TreeNode*k);static TreeNode*term(TreeNode*k);static TreeNode*factor(TreeNode*k);static TreeNode*var(void);static TreeNode*call(TreeNode*k);static TreeNode*args(void);static void syntaxError(char*me) fprintf(listing,"n>>> "); 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();