编译原理课程设计报告书

本文格式为Word版，下载可任意编辑——编译原理课程设计报告书目录

一、设计题目-1-二、运行环境-1-三、算法设计的思想-1-四、算法的流程图-3-五、算法设计分析-6-六、源代码-11-七、运行结果分析-28-八、收获及体会-32-

一、设计题目

简易C语言编译器

二、运行环境

?硬件环境：奔腾Ⅳ处理器，主频2.0GHz；内存512M；硬盘80G以

上；1024×768显示分辩率

?软件环境：WindowsXP2；VisualC++6.0

三、算法设计的思想

编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。

其中词法分析器利用超前探寻、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入，对它进行语法分析。语法分析分为两种方法：自上而下分析法和自下而上分析法。针对不同程序语言的语法规则可以采取不同的分析方法，当然两种方法也可以同时使用。语法分析器把语法单元作为输入供语义分析器使用。一般的语义分析器主要采用的是语法制导方法，即在语法分

-1-

析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。上面三个过程可以与硬件无关，而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编语言。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是十分重要的环节。

下图给出了编译系统的结构框图：

源程序表格管理优化器中间代码目标代码生成器目标代码语法单元语义分析与中间代码生成器中间代码语法分析器词法分析器单词符号出错处理-2-

四、算法的流程图

1、词法分析：

printf(\over\\n\);Fclose(fp);Getch();bufferChar!='#'Out()bufferChar=alpha(bufferChar);rollback();bufferChar=digitbufferChar=other(bufferChar);rollback();(bufferChar);rollback();bufferChar!='#'isalpha(bufferChar)isdigit(bufferChar)note();Main()initial_buffer()init()终止-3-

2、语法分析：

终止出栈，产生式逆序栈顶不为’#〞初始化堆栈，并将’#’和’S’放入堆栈从词法输出中读入token序列，放入input开始是栈顶为终结符是栈顶=get()否查分析表是否需要错误恢复出是栈get=getch()否否否是错误恢复，入栈，并输出产生式-4-

3、语义分析：

终止输出增加属性Buffer缓存开始词法分析语法分析生成语法树语法树入栈-5-

五、算法设计分析

1、使用的数据结构和关键变量

structStack{//栈结构体:序号、内容、连接下一结点指针};

structGuiyue{//规则集结构体:序号、规则长度、符号、连接下一结点指针};

structRelation{//分析表结构体:状态序号、对应符号列、操作类型的对应序号、操作类型、连接下一结点指针};

structSign{//符号表结构体:自变量名、标识类型、连接下一结点指针

charname[20];intline_States;charrank_Letter;intrelationship;charname;

structRelation*next;intnum;intcount;charname;structGuiyue*next;intnum;charname;structStack*next;

-6-

};

charkind;structSign*next;

structWord{//单词表结构体:单词名字、标识类型、状态、序号、行号、连接符号表指针、连接下一结点指针};

FILE*fp1,fp2;//文件指针introw=1;//字符行变量intline[10000],Lin[300];//字符行intw_num;//单词所在行、字符数charbuffer[10000];//字符串缓冲区

structWord*head,*find;//单词表结构体头指针structRelation*r_head;//分析表结构体头指针structGuiyue*g_head;//规约集结构体头指针structStack*s_head;//栈结构体头指针

charname[20];charmark_name;intstate;intnum;intline;structSign*link;structWord*next;

-7-

2、用到的LR文法

[Terminator]mv(){}i=;fewabcd,S03、A->SA04、A->S05、C->C;X06、C->X07、X->YZ08、Y->a09、Y->b10、Y->c11、Y->d12、Z->i,i13、Z->i

14、S->f(E){A}e{A}15、S->w(E){A}16、S->i=L;17、E->E&H18、E->H19、H->H|G

-8-

20、H->G21、G->ii>i23、G->i#i24、G->i@i25、G->(E)26、G->!E27、G->i28、L->L+I29、L->I30、I->I-K31、I->K32、K->K/T33、K->K34、T->T*F35、T->F36、F->(L)37、F->n38、F->i

3、主要功能函数简述

以下是实现的主要功能函数的信息简述，具体实现请参看六、源代码intjudge(charch)

功能：接收ch判断字符，变量flag返回字符类别voidscan()

-9-

功能：扫描输入源文件，并生成单词种别码structWord*InitWord()

功能：包括分割单词、标识单词、生成变量符号表、完善单词属性表intResultAnely(Relation*r_head,Stack*s_head,charstr[],Guiyue*g_head,intcal)功能：词法分析函数int

ResultAnely(Relation

*r_head,Stack

*s_head,char

str[],Guiyue*g_head,intcal)功能：语法分析函数

voidProduceStyle(charstr[],intorder_num)功能：算术表达式四元式函数

voidBoolStyle(charstr[],intorder_num)功能：布尔表达式四元式函数

voidFourStyle(intgoon,Word*head)功能：显示四元式函数

Stack*MarkPush(Stack*ip,charmark,intI_i)功能：进栈

voidMarkPop(Stack*ip)功能：出栈

voidFindWordDeclare(Word*head)

功能：正确性检测函数，查找保存字是否被声名和符号是否对称Relation*FirstRelation()功能：初始化分析表函数Guiyue*FirstGuiyue()功能：初始化规则表函数

-10-

六、源代码(部分)

由于此次试验中所用全部代码量太多，在此只列出主要的功能模块(函数)的代码以做基本概要的说明：

intjudge(charch)//接收ch判断字符，变量flag返回字符类别{

intflag;

if(ch=='!'||ch=='$'||ch==''||ch==':'||ch=='\flag=1;

elseif('0'mark_name=='i'){w_name[cal]=find;cal++;}if(find->next!=NULL){

if((find->mark_name==find->next->mark_name)')||(find->mark_name==';'')||(find->mark_name==')''||find->next->mark_name=='('||find->next->mark_name==')'||

find->next->mark_name=='+'||find->next->mark_name=='-'||find->next->mark_name=='*'||

find->next->mark_name=='/'||find->next->mark_name=='ca++;}

if(find->name[0]>='0'}

intj=0;

for(i=0;ilink;end=1;while(s_firstelses_first=s_first->next;}if(end==1

-14-

ip->name='$';for(i=0;imark_name=='(')||(word_fu[i]->mark_name=='{'))ip=MarkPush(ip,word_fu[i]->mark_name,i);else

if((ip->name=='('elsecoutname!='$')coutline_States=i;r_new->rank_Letter=Let[i][j];r_new->relationship=sr[i][j];r_new->name=SS[i][j];r_find->next=r_new;r_find=r_new;r_new->next=NULL;}}

returnr_head;}

Guiyue*FirstGuiyue(){

-17-

Guiyue*g_head,*g_find,*g_new;g_head=NULL;//规约

charroot[]=

{'B','Q','S','A','A','C','C','X','Y','Y','Y','Y','Z','Z','S','S','S','E','E','H','H','G','G','G','G','G','G','G','L','L','I','I','K','K','T','T','F','F','F'};intLR[]=

{1,7,3,2,1,3,1,2,1,1,1,1,3,1,11,7,4,3,1,3,1,3,3,3,3,3,2,1,3,1,3,1,3,1,3,1,3,1,1};//初始化规则表

for(inti=0;inum=i;g_new->count=LR[i];g_new->name=root[i];g_find->next=g_new;g_find=g_new;g_new->next=NULL;}

returng_head;}

intResultAnely(Relation*r_head,Stack*s_head,charstr[],Guiyue*g_head,intcal){Relation*r_find;Guiyue*g_find;Stack*s_find;//Stack*s_look;s_find=s_head;

intadmition=1,goon=1,in,out=1,hang=-1,count;//charstack[200];charname;

//coutnext;}//:入栈~

if(r_find->line_States==s_find->numintg=r_find->relationship;while(g){g_find=g_find->next;g--;}name=g_find->name;count=g_find->count;admit=0;for(intk=0;k

a=0;}r_find=r_find->next;}}//:规约~

if(r_find->line_States==s_find->numgoon=0;out=0;coutnext;}if(admit==1){//判断输入流是否正确，如在分析表中找不到关系，则输入流错误goon=0;coutname='$';stack_a->next=NULL;

stack_b=(structStack*)malloc(sizeof(structStack));stack_b->name='#';stack_b->next=NULL;f_head=NULL;intadmit,cal,four;four=1;//四元式序号cal=0;admit=1;

while(admit){if(str[cal]=='='){stack_a=MarkPush(stack_a,str[cal],cal);cal++;}else

if(stack_b->name=='#'||stack_b->name=='+'||stack_b->name=='-'||stack_b->name=='*'||stack_b->name=='/'){

if((str[cal]>='a')cal++;}elseif(str[cal]=='('){stack_b=MarkPush(stack_b,'#',cal);cal++;}else

if((stack_b->name=='#')cal++;}elseif((stack_b->name=='#')cal++;

-21-

}elseif((stack_b->name=='#')')){admit=0;}else

if(stack_b->name=='+'||stack_b->name=='-'||stack_b->name=='*'||stack_b->name=='/'){

if((stack_b->name=='+'||stack_b->name=='-')cal++;}else{if(f_head==NULL){f_new=(structFourStyle*)malloc(sizeof(structFourStyle));f_find=f_new;f_head=f_find;}else{f_new=(structFourStyle*)malloc(sizeof(structFourStyle));f_find->next=f_new;f_find=f_new;f_new->next=NULL;}f_new->num=order_num;f_new->Word=stack_b->name;MarkPop(stack_b);f_new->Opr2=stack_a->name;MarkPop(stack_a);f_new->Opr1=stack_a->name;MarkPop(stack_a);temp=four+65;f_new->Result=temp;stack_a=MarkPush(stack_a,f_new->Result,cal);

-22-

four++;}}}if(cal!=3'){f_new=(structFourStyle*)malloc(sizeof(structFourStyle));f_new->num=order_num;f_new->Opr1=stack_a->name;MarkPop(stack_a);f_new->Word=stack_a->name;MarkPop(stack_a);f_new->Opr2='_';f_new->Result=stack_a->name;MarkPop(stack_a);f_find->next=f_new;f_find=f_new;f_new->next=NULL;four++;}elseif(cal==3'){f_new=(structFourStyle*)malloc(sizeof(structFourStyle));f_new->num=order_num;f_new->Opr1=stack_a->name;MarkPop(stack_a);f_new->Word=stack_a->name;MarkPop(stack_a);f_new->Opr2='_';f_new->Result=stack_a->name;f_head=f_new;f_new->next=NULL;four++;}}

f_find=f_head;while(f_find){/*cout.width(20);*/coutnumnext;}}

voidBoolStyle(charstr[],intorder_num){structFourStyle{charWord,Opr1,Opr2;intOrder,num;structFourStyle*next;};

structFourStyle*b_head,*b_find,*b_new,*p[100];b_head=NULL;intcal,admit,i=0;admit=1;cal=0;

while(admit){if(str[cal]!='|'b_head=b_find;p[i]=b_find;i++;}else{b_new=(structFourStyle*)malloc(sizeof(structFourStyle));p[i]=b_new;i++;b_find->next=b_new;b_find=b_new;b_new->next=NULL;}b_new->Opr1=str[cal];cal++;b_new->Word=str[cal];cal++;b_new->Opr2=str[cal];cal++;

-24-

b_new->num=order_num;b_new->Order=0;b_new=(structFourStyle*)malloc(sizeof(structFourStyle));p[i]=b_new;i++;b_new->Opr1='_';b_new->Word='j';b_new->Opr2='_';b_new->num=order_num;b_new->Order=0;b_find->next=b_new;b_find=b_new;b_new->next=NULL;}elseif(str[cal]=='|'){p[i-1]->Order=p[i-1]->num+1;cal++;}elseif(str[cal]=='cal++;}if(str[cal]=='$'){admit=0;p[0]->Order=order_num;p[i-2]->Order=p[i-2]->num+2;if(str[cal-4]=='}}}

b_find=b_head;while(b_find){coutnumnext;}

-25-

}

voidPrint(intt,Word*head,FILE*fp,Relation*r_head){structWord*w_look;structSign*s_look;structRelation*r_new;inti=0;switch(t){case1:{coutnext;}break;}case2:{coutmark_namenext;}coutlink;coutnext;}break;}case4:{coutline_States){coutrank_Letterrelationship;}r_new=r_new->next;}break;}}}

-27-

//======================================================//主函数:voidmain()voidmain(){

coutnext=NULL;

r_head=(Relation*)malloc(sizeof(Relation));r_head->next=NULL;

s_head=(Stack*)malloc(sizeof(Stack));s_head->name='$';s_head->num=0;

s_head->next=NULL;intgoon=2,cal,i=0;

chardocument[50],str[1000];//另存输入流FILE