編譯原理課程設(shè)計(jì)C語言詞法分析器語法分析器

1、編譯原理課程設(shè)計(jì)c語言詞法分析器語法分析器 姓名： 某某某 學(xué)號(hào)： 班級： 軟件一班 學(xué)院： 信息科學(xué)與技術(shù)學(xué)院2014年11月17日目錄1c語言詞法分析器的設(shè)計(jì)31.1實(shí)驗(yàn)?zāi)康?1.2實(shí)驗(yàn)要求31.3實(shí)驗(yàn)環(huán)境31.4實(shí)現(xiàn)分析31.4.1詞法分析的理論構(gòu)架31.4.2程序入口設(shè)計(jì)41.4.3程序執(zhí)行中的流程41.4.4程序的出口設(shè)計(jì)51.5源代碼51.6結(jié)果分析81.7收獲與體會(huì)112語法分析器122.1實(shí)驗(yàn)?zāi)康?22.2實(shí)驗(yàn)要求122.3實(shí)驗(yàn)環(huán)境122.4實(shí)現(xiàn)分析122.4.1ll(1)分析方法的思想122.4.2程序的入口分析122.4.3程序運(yùn)行的流程132.4.4程序的出口設(shè)計(jì)142.

2、5源代碼142.6結(jié)果分析272.7收獲與體會(huì)30參考文獻(xiàn)：311 c語言詞法分析器的設(shè)計(jì)1.1 實(shí)驗(yàn)?zāi)康耐ㄟ^設(shè)計(jì)、編制、調(diào)試一個(gè)具體的詞法分析程序，加深對詞法分析原理的理解，并掌握在對程序設(shè)計(jì)語言源程序進(jìn)行掃描過程中將其分解為各類單詞的詞法分析方法。1.2 實(shí)驗(yàn)要求所編寫的詞法分析器要能對最基本的c語言程序進(jìn)行詞法分析。1.3 實(shí)驗(yàn)環(huán)境1. windows 7操作系統(tǒng)2. 華碩筆記本，內(nèi)存4g，處理器i53. 裝有microsoft visual studio 2010,并安裝framework4.01.4 實(shí)現(xiàn)分析1.4.1 詞法分析的理論構(gòu)架詞法分析器的功能輸入源程序，按照構(gòu)詞規(guī)則分解成

3、一系列單詞符號(hào)。單詞是語言中具有獨(dú)立意義的最小單位，包括關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符、界符和常量等(1) c語言的關(guān)鍵字經(jīng)過搜索共有32個(gè)， 是由程序語言定義的具有固定意義的標(biāo)識(shí)符。我編寫的詞法分析器只將其中的一部分常用的定義在程序中，他們有break,case,char,const,continue,default,do,double,else,enun, extern,float,for,goto,if,int,long,return,static,struct,switch,sizeof,typedef,union,unsigned,void,volatile,while而對于c語言的一些保留

4、字如“main”、“return”等我沒有將其放入關(guān)鍵字的范圍內(nèi)。(2) 標(biāo)識(shí)符 用來表示各種名字，如變量名，數(shù)組名，過程名等等。(3) 常數(shù) 常數(shù)的類型一般有整型、實(shí)型、布爾型、文字型等。(4) 運(yùn)算符 我在本詞法分析器里面定義了“+”、“-”、“*”、“/”四種運(yùn)算符。(5) 界符 我則定義了如下11種, ; . ( ) = : 1.4.2 程序入口設(shè)計(jì)次法分析入口的設(shè)計(jì)方法很多，為了我們每次運(yùn)行時(shí)方便起見，我們將我們的c語言程序放入一個(gè)txt文件中，每次我們運(yùn)行程序時(shí)，程序?qū)⒆孕凶x取文件中的c語言代碼，并將對其進(jìn)行詞法分析將分析結(jié)果輸出到控制臺(tái)，這樣的輸入方法避免了我們重復(fù)輸入程序的問題

5、，我們需要對某程序進(jìn)行詞法分析時(shí)，我們只需要將我們的c語言程序拷貝到我們的txt文件中，運(yùn)行程序即可進(jìn)行詞法分析了。開始1.4.3 程序執(zhí)行中的流程打開txt文件讀取c語言代碼掃描、是否讀取到相應(yīng)字符nnnn n nyyy y yy界符？關(guān)鍵字？標(biāo)識(shí)符？運(yùn)算符？常數(shù)？記錄標(biāo)號(hào)記錄標(biāo)號(hào)記錄標(biāo)號(hào)記錄標(biāo)號(hào)記錄標(biāo)號(hào)輸出結(jié)束1.4.4 程序的出口設(shè)計(jì)上面我們講解了我們詞法分析器的入口，但是我們的輸出是怎樣設(shè)計(jì)的呢。首先為了使我們的程序有參考對照，我將我們的c語言程序首先輸出到控制臺(tái)上，以便與后面的詞法分析是做一個(gè)參考，無需再去打開我們相應(yīng)的txt文件做對照了。其次，我將我的關(guān)鍵字和相應(yīng)的界符以及相應(yīng)的運(yùn)

6、算符都編上一個(gè)序號(hào)，并且將其一一個(gè)二元式的方式輸出到控制臺(tái)上，以便災(zāi)后面的詞法分析結(jié)果中形成對比。最后我們將詞法分析的結(jié)果輸出到控制臺(tái)上，輸出格式為，我們將每一句代碼作為一個(gè)單位，在每句代碼后面我們將給出本局代碼分析得到詞法分析后的字符標(biāo)號(hào)。例如：typedef struct |22|19| 其意義就是typedef 和struct對應(yīng)的標(biāo)號(hào)為22和19這兩種種別1.5 源代碼/ cifa.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。#include stdafx.h#include #include #include #include #include #include #includeusin

7、g namespace std;bool isletter(char ch) if (ch=a & ch=a & ch=0 & ch=9) return true; else return false;bool isp(char ch) if(ch=+|ch=*|ch=-|ch=/) return true; else return false;bool isj(char ch) if(ch=,|ch=;|ch=.|ch=(|ch=)|ch=|ch=|ch=|ch=:|ch=|ch=|ch=|ch=#) return true; / else return false;bool isblank

8、(char ch) if(ch= |ch=t) return true; else return false;int main() string src,ste,s; char ch0,ch,ch12; char ktt5520=break,case,char,const,continue,default,do,double,else,enun,extern,float,for,goto,if,int,long,return,static,struct,switch,sizeof, typedef,union,unsigned,void,volatile, while,標(biāo)識(shí)符,無符號(hào)數(shù) ,;,

9、:,.,(,),？,+,-,+,-,*,/,=,=,=,!=,#; / int pos=0; file *fp; fp=fopen(d:in.txt,r); ch0=fgetc(fp); while(ch0!=eof) /if(ch0!=t)src+=ch0; src+=ch0; ch0=fgetc(fp); src+=#; coutsrcendl; ch=srcpos+; ste= ; for(int j=0;j54;j+)coutjkttjendl; cout詞法分析:n; while(ch!=#) char str20; if(ch!=n) if(isdigit(ch) /判斷常數(shù) in

10、t i=0; while(isdigit(ch)|ch=.) stri+=ch; /i+; ch=srcpos+; stri=0; ste=ste+|+22; coutstr; continue; else if(isletter(ch) /判斷字符 int i=0,j; while(isletter(ch)|isdigit(ch) stri+=ch; /i+; ch=srcpos+; stri=0; for(j=0;j28;j+) /判斷是否關(guān)鍵字 int t=strcmp(str,kttj); if(t=0) stringstream ss; ste+=|; ssste;ssste; br

11、eak; if(j=28)ste=ste+|+28; / cout ; coutstr; continue; else if(isp(ch) /判斷是否運(yùn)算符 int i=0,j; stri+=ch; stri=0; for(j=34;j38;j+) int t=strcmp(str,kttj); if(t=0) stringstream ss; ste+=|; ssste;ssste; break; coutstr; ch=srcpos+; continue; else if(isj(ch) /判斷是否界符 int i=0,j; while(isj(ch) stri+=ch; ch=srcp

12、os+; stri=0; for(j=23;j47;j+) int t=strcmp(str,kttj); if(t=0) stringstream ss; ste+=|; ssste;ssste; break; coutstr; continue; else if(isblank(ch) coutch; ch=srcpos+; continue; else coutstebase=(int *)malloc(maxqsize*sizeof(int);/為base申請空間 if(!q-base) printf(隊(duì)列構(gòu)建失?。ò慈我怄I返回主菜單）n);getch();system(cls);ch

13、oice(q);q-front =q-rear = 0;/隊(duì)列頭，尾的初始化 return ok;int main()sqqueue *q;/定義隊(duì)列 qq = (sqqueue*) malloc(maxqsize*sizeof(sqqueue);/為q申請空間initqueue(q);/構(gòu)造空隊(duì)列choice(q);/調(diào)用選擇函數(shù)，獲取主菜單return ok;運(yùn)行后的結(jié)果：如圖1.1 我先將txt文件中的代碼取出圖 1.1如圖1.2 將我的標(biāo)號(hào)顯示在控制臺(tái)上圖 1.2如圖1.3 輸出詞法分析結(jié)果圖 1.3上述結(jié)果和我的預(yù)期一樣，實(shí)現(xiàn)了對c語言的詞法分析。1.7 收獲與體會(huì)首先，這個(gè)詞法分析

14、器我是用c語言編寫，工作量確實(shí)有點(diǎn)大，但是由于扎實(shí)的c語言基本功，我還是很快的編寫出了程序，是我對c語言的使用更加熟練了，此外由于是編寫的c語言詞法分析器，所以我需要更全面深刻的去了解c語言的知識(shí)，使我找到了一些盲區(qū)，比如有一些c語言的關(guān)鍵字還不是很熟悉。其次，我還認(rèn)真的學(xué)習(xí)了編譯原理的詞法分析知識(shí)，對正規(guī)式，狀態(tài)轉(zhuǎn)換圖，以及自動(dòng)機(jī)的知識(shí)有了新的理解，并將其運(yùn)用到我的程序中來，大大的開闊了我的視野，使我的編程能力又上了一個(gè)臺(tái)階2 語法分析器2.1 實(shí)驗(yàn)?zāi)康耐ㄟ^設(shè)計(jì)、編制、調(diào)試一個(gè)具體的語法分析程序，加深對語法分析原理的理解，學(xué)習(xí)并掌握一種語法分析的方法，讓我們鞏固上課內(nèi)容，學(xué)習(xí)ll(1)分析法

15、，學(xué)會(huì)自上而下的文法分析方法。2.2 實(shí)驗(yàn)要求語法分析是編譯過程的核心部分。他的任務(wù)是在詞法分析識(shí)別單詞符號(hào)串的基礎(chǔ)上，分析并判斷程序的的語法結(jié)構(gòu)是否符合語法規(guī)則。由此編寫一個(gè)語法分析器。2.3 實(shí)驗(yàn)環(huán)境1、 windows 7操作系統(tǒng)2、 華碩筆記本，內(nèi)存4g，處理器i53、 裝有visual c+ 6.0,并安裝framework4.0注：因?yàn)楸境绦蚴褂玫搅薴printf和fscanf兩個(gè)系統(tǒng)函數(shù)，由于microsoft visual studio 2010出于安全考慮將這兩個(gè)函數(shù)的參數(shù)增加為了4個(gè)，但是本程序依舊使用的老版本時(shí)的三個(gè)參數(shù)，所以本程序只能在visual c+ 6.0上運(yùn)行。

16、2.4 實(shí)現(xiàn)分析2.4.1 ll(1)分析方法的思想自定向下分析時(shí)從左向右掃描輸入串，分析過程中采用的最左推導(dǎo)，并且只需向右看一個(gè)符號(hào)就可以決定如何推導(dǎo)，通過給定的文法構(gòu)造預(yù)測分析表和實(shí)現(xiàn)某個(gè)符號(hào)串 的分析。 我們知道一個(gè)文法要能進(jìn)行l(wèi)l（1）分析，那么這個(gè)文法應(yīng)該滿足：無二義性，無左遞歸，無左公因子。當(dāng)文法滿足條件后，再分別構(gòu)造文法每個(gè)非終結(jié)符的first和follow集合，然后根據(jù)first和follow集合構(gòu)造ll（1）分析表，最后利用分析表，根據(jù)ll(1)語法分析構(gòu)造一個(gè)分析器。ll（1）的語法分析程序包含了三個(gè)部分，總控程序，預(yù)測分析表函數(shù)，先進(jìn)先出的語法分析棧。2.4.2 程序的入

17、口分析本程序?yàn)榱藢?shí)現(xiàn)語法分析器的重用性，我設(shè)置了必須先將我們需要分析的文法輸入，但是為了能夠高效的輸入文法，我設(shè)定了將文法的產(chǎn)生式放在相應(yīng)的txt文件中，每次我們只需將我們的文法產(chǎn)生式放入次txt文件，運(yùn)行程序就會(huì)自動(dòng)將該文法的ll（1）分析表生成，如此我們便可以高效的實(shí)現(xiàn)語法分析。除此之外我還設(shè)定了本程序的編寫者，和文件位置的指定。會(huì)在結(jié)果分析中有具體反映。輸以輸入以#結(jié)束的符號(hào)串。2.4.3 程序運(yùn)行的流程#和文法開始符號(hào)進(jìn)棧第一個(gè)輸入符號(hào)讀進(jìn)a棧頂符號(hào)托出去放x中x彈棧，將y1y2yk逆序放入s棧中，若右部符號(hào)串為，則不進(jìn)棧x=a?xvt?x=#?查mx,a=xy1y2ykx=a?將下一

18、個(gè)輸入符號(hào)讀進(jìn)axvt?出錯(cuò)出錯(cuò)stopyyyyynnnnn2.4.4 程序的出口設(shè)計(jì)為了方便，我先將txt文件中的產(chǎn)生式輸出到了控制臺(tái)上以便觀察，我將讀出的產(chǎn)生式分為左部，中部，右部，并將其分別讀入pronodei.leftsym,、 pronodei.midsym0 、pronodei.midsym1)、pronodei.rightsymj。因?yàn)橹胁课叶x的是“-”符號(hào)故必須需要兩個(gè)結(jié)構(gòu)參數(shù)來存儲(chǔ)。將產(chǎn)生式輸出后，我用讀到的產(chǎn)生式構(gòu)造文法每個(gè)非終結(jié)符的first和follow集合，然后根據(jù)first和follow集合構(gòu)造ll（1）分析表。并將其輸出到控制臺(tái)上。最后讀入我們將需要分析的式子，

19、通過ll（1）分析表生成的規(guī)約，把式子放入規(guī)約棧中分析，并將分析過程輸出到控制臺(tái)上。2.5 源代碼/ yufa2.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。#include #include #include #include #include using namespace std; #define pro_midsym_max 2#define pro_rightsym_max 10#define untinfo_fir_max 10#define untinfo_fol_max 10#define stack_init_size 100#define stackincrement 10 t

20、ypedef struct pronode /產(chǎn)生式結(jié)構(gòu) char leftsym; /產(chǎn)生式左邊的符號(hào) char midsympro_midsym_max; /產(chǎn)生式推導(dǎo)符號(hào) char rightsympro_rightsym_max; /產(chǎn)生式右邊的符號(hào)，不超過十個(gè) int length; /產(chǎn)生式長度pronode; typedef struct untinfo /每個(gè)非終結(jié)符的信息結(jié)構(gòu)，包括first和follow集合 char firstuntinfo_fir_max; char followuntinfo_fol_max;untinfo;typedef struct /構(gòu)造順序棧,

21、存儲(chǔ)符號(hào) char *base; char *top; int stacksize;sqstack;typedef struct qnode /構(gòu)造單鏈隊(duì)列，存儲(chǔ)輸入符號(hào)串 char data; struct qnode *next;qnode,*queueptr; typedef struct queueptr front; /隊(duì)頭指針 queueptr rear; /隊(duì)尾指針linkqueue;int pronum; /產(chǎn)生式個(gè)數(shù)char unterminate15; /非終結(jié)符表char terminate15; /終結(jié)符表char pronull20; /記錄能產(chǎn)生空字符的非終結(jié)符pr

22、onode sheet1515; /分析表char select1515; /select集合，以便于構(gòu)造分析表linkqueue remain; /剩余符號(hào)串 void inituntinfo(untinfo untinfo,int untinfonum); /初始化函數(shù)，對每個(gè)非終結(jié)符的信息結(jié)構(gòu)進(jìn)行初始化void initpronode(pronode pronode,int pronum); /初始化函數(shù)，對每個(gè)非終結(jié)符的產(chǎn)生式結(jié)構(gòu)進(jìn)行初始化void initstack(sqstack &s); /初始化棧void initqueue(linkqueue &q); /初始化隊(duì)列void

23、enqueue(linkqueue &q,char c); /在隊(duì)尾插入新的元素void exit(); /棧溢出處理函數(shù)void error();/出錯(cuò)處理void push(sqstack &s, char c); /入棧char pop(sqstack &s); /出棧void initsheet(pronode* sheet,int m,int n) ; /初始化分析表函數(shù)bool readpro(pronode pronode,char filename);/從文件讀取產(chǎn)生式函數(shù)void printpro(pronode pronode,int pronum); /顯示產(chǎn)生式void

24、 setunterminate(char unterminate,pronode pronode,int pronum); /設(shè)置非終結(jié)符表void setterminate(char unterminate,pronode pronode,int pronum); /設(shè)置終結(jié)符表int getnumofut(char unterminate); /獲得非終結(jié)符個(gè)數(shù)int getnumoft(char terminate); /獲得終結(jié)符個(gè)數(shù)int getutloaction(char unterminate,char c); /獲得非終結(jié)符在非終結(jié)符表中的位置int gettlocactio

25、n(char unterminate,char c); /獲得終結(jié)符在終結(jié)符表中的位置void first(pronode pronode,untinfo untinfo); /計(jì)算各非終結(jié)符的first集void follow(pronode pronode,untinfo untinfo); /計(jì)算各非終結(jié)符的follow集void addchar(char charray,char c); /將非終結(jié)符的所有first值加入first集void addchartochar(char charray,char otherarray); /將非終結(jié)符的所有first集加入first集void

26、 addfollow(char follow,char c); /將非終結(jié)符的所有follow值加入follow集bool isnull(char c); /非終結(jié)符能否產(chǎn)生空字符bool isterminate(char c); /判斷是否為終結(jié)符號(hào)void setsheet(pronode pronode,untinfo untinfo); /設(shè)置分析表void setselect(pronode pronode,untinfo untinfo);/設(shè)置select集合void inputsym(); /輸入字符串函數(shù)void scan(); /分析掃描的主控程序char getsym(l

27、inkqueue &q) ; /獲取下一字符void printsym(sqstack &s); /顯示符號(hào)棧符號(hào)void printremain(linkqueue &q); /顯示剩余符號(hào)串void printsheet(int row,int col); /顯示所使用產(chǎn)生式void success(); /分析成功void main() char filename10; cout編制人：徐玉松，20122617，軟件一班endl; cout請輸入放有產(chǎn)生式的文件（如：xuyusong.txt）:filename; pronode pronode20; initpronode(pronod

28、e,20); if(readpro(pronode,filename) /*輸出文法產(chǎn)生式*/ cout該文法產(chǎn)生式為：endl; printpro(pronode,pronum); /*設(shè)置非終結(jié)符表和終結(jié)符表*/ setunterminate(unterminate,pronode,pronum); setterminate(terminate,pronode,pronum); /* 輸出first集*/ int numofut = getnumofut(unterminate); int numoft = getnumoft(terminate); untinfo untinfo20;

29、inituntinfo(untinfo,20); /* 輸出first集*/ first(pronode,untinfo); /* 輸出follow集*/ follow(pronode,untinfo); /*設(shè)置select*/ setselect(pronode,untinfo); /*輸出sheet*/ coutendl分析表:endl; setsheet(pronode,untinfo); coutt; for(int jj = 0 ; jj numoft ; jj+) coutterminatejjt; coutendl; for(int mm = 0 ; mm numofut ;

30、mm+) coutunterminatemmt; for(int mn = 0 ; mn numoft; mn+) printsheet(mm,mn); coutt; coutendl; inputsym(); /輸入字符串 scan(); /主控程序 else error(); void initpronode(pronode pronode,int pronum) /初始化函數(shù)，對每個(gè)非終結(jié)符的產(chǎn)生式結(jié)構(gòu)進(jìn)行初始化 for(int i = 0 ; i pronum ; i+) pronodei.leftsym = 0; memset(pronodei.midsym,0,pro_midsym

31、_max); memset(pronodei.rightsym,0,pro_rightsym_max); pronodei.length = 0; void inituntinfo(untinfo untinfo,int untinfonum) /初始化函數(shù)，對每個(gè)非終結(jié)符的信息結(jié)構(gòu)進(jìn)行初始化 for(int i = 0 ; i = s.stacksize) /棧滿，追加存儲(chǔ)空間 s.base = (char *)realloc(s.base,(s.stacksize + stackincrement) * sizeof(char); if(!s.base) exit(); /存儲(chǔ)分配失敗 s

32、.top = s.base + s.stacksize; s.stacksize += stackincrement; *(s.top) = c; s.top = s.top + 1; char pop(sqstack &s) /出棧 if(s.top = s.base ) return null; s.top = s.top - 1; char tmpchar = *(s.top); return tmpchar; void initqueue(linkqueue &q) /初始化隊(duì)列 q.front = q.rear = (queueptr)malloc(sizeof(qnode); if

33、(!q.front) exit(); /存儲(chǔ)分配失敗 q.front-next = null; void enqueue(linkqueue &q,char c) /在隊(duì)尾插入新的元素 queueptr p = (queueptr)malloc(sizeof(qnode); if(!p) exit(); /存儲(chǔ)分配失敗 p-data = c; p-next = null; q.rear-next = p; q.rear = p; void exit() /溢出處理 cout溢出！endl; void error() /出錯(cuò)處理 cout分析出錯(cuò)！endl; void initsheet(pro

34、node* sheet,int m,int n) /初始化分析表函數(shù),以便將無定義的表格定義為error for (int i = 0 ; i m;i+) for(int j = 0 ; j n ; j+) sheetij.leftsym = 0; /用0標(biāo)記無定義的表格 bool readpro(pronode pronode,char filename) file* pfile; if(pfile = fopen(filename,r) = null) cout打開文件出錯(cuò)！endl; return false; char tmpchar; int tmpindex = 0; fscanf

35、(pfile,%c,&tmpchar); while(tmpchar != #) /求出產(chǎn)生式的個(gè)數(shù) if(tmpchar = ;) tmpindex+; fscanf(pfile,%c,&tmpchar); pronum = tmpindex; rewind(pfile); for(int i = 0;i pronum;i+) /讀出各產(chǎn)生式并置于已定義的數(shù)據(jù)結(jié)構(gòu)pronode中, /同時(shí)可將非終結(jié)符置于非終結(jié)符號(hào)表 fscanf(pfile,%c %c %c,&pronodei.leftsym,&pronodei.midsym0, &pronodei.midsym1); pronodei.midsym2 = 0; fscanf(pfile,%c,&tmpchar); int j = 0; while(tmpchar != ;) pronodei.rightsymj = tmpchar; fscanf(pfile,%c,&tmpchar); j+; pronodei.rightsy