編譯原理課程設計報告書

本文格式為Word版，下載可任意編輯——編譯原理課程設計報告書目錄

一、設計題目-1-二、運行環(huán)境-1-三、算法設計的思想-1-四、算法的流程圖-3-五、算法設計分析-6-六、源代碼-11-七、運行結果分析-28-八、收獲及體會-32-

一、設計題目

簡易C語言編譯器

二、運行環(huán)境

?硬件環(huán)境：奔騰Ⅳ處理器，主頻2.0GHz；內(nèi)存512M；硬盤80G以

上；1024×768顯示分辯率

?軟件環(huán)境：WindowsXP2；VisualC++6.0

三、算法設計的思想

編譯程序的工作過程一般可以分為五個階段：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、優(yōu)化、目標代碼生成。每一個階段在功能上是相對獨立的，它一方面從上一個階段獲取分析的結果來進行分析，另一方面由將結果傳遞給下一個階段。由編譯程序的五個階段就對應了編譯系統(tǒng)的結構。

其中詞法分析器利用超前探尋、狀態(tài)轉(zhuǎn)換等方法，將源程序轉(zhuǎn)化成為一個一個的單詞符號二元式。一般程序語言的單詞符號包括關鍵字、運算符、常數(shù)、標識符和界符。語法分析器將這些單詞符號作為輸入，對它進行語法分析。語法分析分為兩種方法：自上而下分析法和自下而上分析法。針對不同程序語言的語法規(guī)則可以采取不同的分析方法，當然兩種方法也可以同時使用。語法分析器把語法單元作為輸入供語義分析器使用。一般的語義分析器主要采用的是語法制導方法，即在語法分

-1-

析的同時進行語法分析，并產(chǎn)生一定的語義動作，來生成中間代碼。上面三個過程可以與硬件無關，而接下來的優(yōu)化器和目標代碼生成器是針對某一種處理器而言的。代碼優(yōu)化是將語義分析生成的中間代碼進行優(yōu)化，產(chǎn)生執(zhí)行效率更高的代碼。目標代碼生成器最終生成可以在某種機器上運行的機器語言或者匯編語言。在整個編譯過程中還包括對表格的操作和對錯誤的處理，這些也都是十分重要的環(huán)節(jié)。

下圖給出了編譯系統(tǒng)的結構框圖：

源程序表格管理優(yōu)化器中間代碼目標代碼生成器目標代碼語法單元語義分析與中間代碼生成器中間代碼語法分析器詞法分析器單詞符號出錯處理-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、語法分析：

終止出棧，產(chǎn)生式逆序棧頂不為’#〞初始化堆棧，并將’#’和’S’放入堆棧從詞法輸出中讀入token序列，放入input開始是棧頂為終結符是棧頂=get()否查分析表是否需要錯誤恢復出是棧get=getch()否否否是錯誤恢復，入棧，并輸出產(chǎn)生式-4-

3、語義分析：

終止輸出增加屬性Buffer緩存開始詞法分析語法分析生成語法樹語法樹入棧-5-

五、算法設計分析

1、使用的數(shù)據(jù)結構和關鍵變量

structStack{//棧結構體:序號、內(nèi)容、連接下一結點指針};

structGuiyue{//規(guī)則集結構體:序號、規(guī)則長度、符號、連接下一結點指針};

structRelation{//分析表結構體:狀態(tài)序號、對應符號列、操作類型的對應序號、操作類型、連接下一結點指針};

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{//單詞表結構體:單詞名字、標識類型、狀態(tài)、序號、行號、連接符號表指針、連接下一結點指針};

FILE*fp1,fp2;//文件指針introw=1;//字符行變量intline[10000],Lin[300];//字符行intw_num;//單詞所在行、字符數(shù)charbuffer[10000];//字符串緩沖區(qū)

structWord*head,*find;//單詞表結構體頭指針structRelation*r_head;//分析表結構體頭指針structGuiyue*g_head;//規(guī)約集結構體頭指針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、主要功能函數(shù)簡述

以下是實現(xiàn)的主要功能函數(shù)的信息簡述，具體實現(xiàn)請參看六、源代碼intjudge(charch)

功能：接收ch判斷字符，變量flag返回字符類別voidscan()

-9-

功能：掃描輸入源文件，并生成單詞種別碼structWord*InitWord()

功能：包括分割單詞、標識單詞、生成變量符號表、完善單詞屬性表intResultAnely(Relation*r_head,Stack*s_head,charstr[],Guiyue*g_head,intcal)功能：詞法分析函數(shù)int

ResultAnely(Relation

*r_head,Stack

*s_head,char

str[],Guiyue*g_head,intcal)功能：語法分析函數(shù)

voidProduceStyle(charstr[],intorder_num)功能：算術表達式四元式函數(shù)

voidBoolStyle(charstr[],intorder_num)功能：布爾表達式四元式函數(shù)

voidFourStyle(intgoon,Word*head)功能：顯示四元式函數(shù)

Stack*MarkPush(Stack*ip,charmark,intI_i)功能：進棧

voidMarkPop(Stack*ip)功能：出棧

voidFindWordDeclare(Word*head)

功能：正確性檢測函數(shù)，查找保存字是否被聲名和符號是否對稱Relation*FirstRelation()功能：初始化分析表函數(shù)Guiyue*FirstGuiyue()功能：初始化規(guī)則表函數(shù)

-10-

六、源代碼(部分)

由于此次試驗中所用全部代碼量太多，在此只列出主要的功能模塊(函數(shù))的代碼以做基本概要的說明：

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;//規(guī)約

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};//初始化規(guī)則表

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;}}//:規(guī)約~

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-

//======================================================//主函數(shù):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