編譯原理詞法分析和ll文法判定

1、武漢科技大學(xué)實驗報告課程名稱編譯原理 專業(yè)班級姓 名學(xué) 號實驗一 詞法分析器設(shè)計【實驗?zāi)康摹?熟悉詞法分析的基本原理，詞法分析的過程以及詞法分析中要注意的問題。2復(fù)習(xí)高級語言，進一步加強用高級語言來解決實際問題的能力。3通過完成詞法分析程序，了解詞法分析的過程?！緦嶒瀮?nèi)容】用C語言編寫一個PL/0詞法分析器，為語法語義分析提供單詞，使之能把輸入的字符串形式的源程序分割成一個個單詞符號傳遞給語法語義分析，并把分析結(jié)果（基本字，運算符，標(biāo)識符，常數(shù)以及界符）輸出?！緦嶒灢襟E和要求】1 要求繪出詞法分析過程的流程圖。2 根據(jù)詞法分析的目的以及內(nèi)容，確定完成分析過程所需模塊。3 寫出每個模塊的源代碼。

2、4 整理程序清單及所得結(jié)果?！玖鞒虉D】【源代碼】/resource.h#define IDD_MAINDLG 101#define IDR_MENU 102#define IDI_ICON 104#define IDC_INPUT 1001#define IDC_OUTPUT 1003#define IDC_ERRPUT 1004#define IDC_BUTTON1 1005#define ID_START 40001#define ID_ABOUT 40003#define ID_OPEN 40005#define ID_SAVE 40006#define ID_LISTKEY 40007

3、/ Next default values for new objects/ #ifdef APSTUDIO_INVOKED#ifndef APSTUDIO_READONLY_SYMBOLS#define _APS_NEXT_RESOURCE_VALUE 105#define _APS_NEXT_COMMAND_VALUE 40008#define _APS_NEXT_CONTROL_VALUE 1007#define _APS_NEXT_SYMED_VALUE 101#endif#endif/getsym.h#ifndef _GETSYM_H_#define _GETSYM_H_#inclu

4、de /For memset()#include /For strcpy()#define ISLETTER(c)(c)=A&(c)=a&(c)=0&(c)=33 &(c)=126)#define MAX_SYM32768/最大符號量#define MAX_SYMFORM1024/最大符號表長度#defineMAX_NUMFORM4096/最大常數(shù)表長度#define MAX_SYMLEN31/最大符號長度#define MAX_NUMLEN10/最大常數(shù)長度#define MAX_BUFFERMAX_SYMLEN+1/最大緩沖長度#define MAX_KEYWORD27/關(guān)鍵字數(shù)量#def

5、ine MAX_OPWORDA8/單字運算符數(shù)量#define MAX_OPWORDB4/雙字運算符數(shù)量#define MAX_ENDWORD8/單字界符數(shù)量#define MAX_ERROR5/錯誤類型數(shù)量#define TYPE_KEYWORD1/關(guān)鍵字類型號#define TYPE_SYMBOL2/符號類型號#define TYPE_NUMBER3/常量類型號#define TYPE_OPWORD4/運算符類型號#define TYPE_ENDWORD5/界符類型號#define TYPE_ERROR-1/錯誤類型號#define ERR_OVERSYMLEN1/以下是一般錯誤號#def

6、ine ERR_OVERNUMLEN2#define ERR_NUMBER3#define ERR_WRONGOP4#define ERR_OVERSYMFORM10001/以下是嚴重錯誤號#define ERR_OVERNUMFORM 10002#define ERR_OVERSYMNUM10003#define ERR_OVERERRNUM10004#ifdef _cplusplusextern C #endifstruct SYM/符號描述結(jié)構(gòu)體(含錯誤描述結(jié)構(gòu))int type;/類型號(0:錯誤)int id;/ID號(錯誤值)int line;/所在行數(shù)/int no;/SYM編號

7、/列號char nameMAX_SYMLEN+1;/所取的詞;struct FORM/表格結(jié)構(gòu)體int symnum;int numnum;struct SYMF/符號表項結(jié)構(gòu)體int id;char nameMAX_SYMLEN+1;symfMAX_SYMFORM;struct NUMF/常量表項結(jié)構(gòu)體int id;char nameMAX_NUMLEN+1;numfMAX_NUMFORM;struct SYMINFO/詞法分析信息結(jié)構(gòu)體int num;struct SYM symMAX_SYM;struct FORM form;/取詞函數(shù)(返回讀字符數(shù)量,如果是0則表示結(jié)束,lin表示當(dāng)前

8、行數(shù))int _stdcall getsym(const char *in,struct SYM *out,int *ln,struct FORM *form);/取所有詞函數(shù)(正常返回0,否則返回嚴重錯誤號)int _stdcall getsyminfo(const char *in,struct SYMINFO *out);#ifdef _cplusplus#endif#endif#include getsym.h/關(guān)鍵字BASIC:13,EXTEND:14const char* const keytxtMAX_KEYWORD=procedure,call,begin,end,var,co

9、nst,if,then,while,do,read,write,odd,program,type,function,array,integer,real,char,boobean,case,of,repeat,until,to,down;/單字運算符const char opatxtMAX_OPWORDA=+,-,*,/,=,#,;/雙字運算符const char* const opbtxtMAX_OPWORDB=,:=,;/單字界符const char eoptxtMAX_ENDWORD=(,),;,.,:;/錯誤提示信息const char* const errtxtMAX_ERROR=O

10、K,/Not used.Too long symbol,Too long number,Mixed number and letter,Unkown operator,;int getsym(const char *in,struct SYM *out,int *ln,struct FORM *form)char bMAX_BUFFER;/建符號緩沖區(qū)int i,m=0,n=0,e=0;/序號/非字符數(shù)/字符數(shù)/出錯標(biāo)記memset(out,0,sizeof(struct SYM);while(!ISCHAR(*in)/濾出前面的非字符if(*in=10) (*ln)+;/換行時,ln+if(

11、*in+) m+; else return 0;/如果無字符則退出out-line=*ln;if(ISLETTER(*in)/字母開頭情況while(ISLETTER(*in)|ISNUMBER(*in)if(n=MAX_SYMLEN) bn=*in;n+; in+;bMAX_SYMLEN=0;/符號結(jié)尾置0if(nname,b);if(nMAX_SYMLEN)/超出符號最大長度out-type=TYPE_ERROR;out-id=ERR_OVERSYMLEN;elsefor(i=0;iMAX_KEYWORD;i+)if(strcmp(b,keytxti)=0) break;if(itype=

12、TYPE_KEYWORD;out-id=i;else/不屬于關(guān)鍵字for(i=0;isymnum;i+)if(strcmp(b,)=0) break;if(i=form-symnum)/不在符號表中則添加if(form-symnum=MAX_SYMFORM)/超出符號表范圍產(chǎn)生嚴重錯誤out-type=TYPE_ERROR;out-id=ERR_OVERSYMFORM;return m+n;form-symfi.id=i;strcpy(,b);form-symnum+;out-type=TYPE_SYMBOL;/符號類型out-id=

13、i;return m+n;if(ISNUMBER(*in)/數(shù)字開頭情況e=0;while(ISNUMBER(*in)|ISLETTER(*in)if(ISLETTER(*in) e=1;/含字母則置出錯標(biāo)記if(n=MAX_NUMLEN) bn=*in;n+; in+;bMAX_NUMLEN=0;/數(shù)字尾置0if(nname,b);if(e|nMAX_NUMLEN)/有出錯標(biāo)記或超出數(shù)字最大長度out-type=TYPE_ERROR;if(e)/含字母情況out-id=ERR_NUMBER;else/超出數(shù)字最大長度情況out-id=ERR_OVERNUMLEN;else/無錯情況if(fo

14、rm-numnum=MAX_NUMFORM)/超出常量表范圍產(chǎn)生嚴重錯誤out-type=TYPE_ERROR;out-id=ERR_OVERNUMFORM;return m+n;form-numfform-numnum.id=form-numnum;strcpy(,b);out-type=TYPE_NUMBER;out-id=form-numnum;form-numnum+;return m+n;for(i=0;iMAX_OPWORDB;i+)/雙字運算符情況if(*(short*)in=*(short*)(opbtxti) break;if

15、(itype=TYPE_OPWORD;out-id=MAX_OPWORDA+i;*(short*)out-name=*(short*)opbtxti;out-name2=0;return m+2;out-name0=*in;out-name1=0;for(i=0;iMAX_OPWORDA;i+)/單字運算符情況if(*in=opatxti) break;if(itype=TYPE_OPWORD;out-id=i;return m+1;for(i=0;iMAX_ENDWORD;i+)/單字界符情況if(*in=eoptxti) break;if(itype=TYPE_ENDWORD;out-id

16、=i;return m+1;out-type=TYPE_ERROR;out-id=ERR_WRONGOP;/其他符號則出錯return m+1;int getsyminfo(const char *in,struct SYMINFO *out)int offset,ln=1;/每次取詞偏移量/當(dāng)前行數(shù)memset(out,0,sizeof(struct SYMINFO);while(1)offset=getsym(in,&out-symout-num,&ln,&out-form);if(offset=0) break;/完成取詞則退出if(out-num=MAX_SYM) return ERR

17、_OVERSYMNUM;/超出符號信息最大值if(out-symout-num.type=TYPE_ERROR&out-symout-num.id=10000)return out-symout-num.id;/有嚴重錯誤則退出out-num+;in+=offset;return 0;Test.Txtprogram test;procedure func(a:integer,b:char);beginvar c:char;read(c);if c=1234 thenb:=c*320;b:=(a-b)/10000;end;beginconst s:=4444;a:=b333;while s=a

18、dobegincall test;end;write(a);end.結(jié)果實驗二 LL（1）語法分析程序設(shè)計 【實驗?zāi)康摹?熟悉判斷LL（1）文法的方法及對某一輸入串的分析過程。2學(xué)會構(gòu)造表達式文法的預(yù)測分析表?！緦嶒瀮?nèi)容】編寫一個語法分析程序，對于給定的輸入串，能夠判斷識別該串是否為給定文法的句型?！緦嶒灢襟E和要求】1 從鍵盤讀入輸入串，并判斷正誤；2 若無誤，由程序自動構(gòu)造FIRST、FOLLOW集以及SELECT集合，判斷是否為LL（1）文法；3 若符合LL（1）文法，由程序自動構(gòu)造LL（1）分析表；4 由算法判斷輸入符號串是否為該文法的句型。（可參考教材96頁的例題1）【源代碼】#inc

19、lude stdio.h#include stdlib.h#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct pRNode/*產(chǎn)生式右部結(jié)構(gòu)*/int rCursor;/*右部序號*/struct pRNode *next;struct pNode/*產(chǎn)生式結(jié)點結(jié)構(gòu)*/int lCursor;/*左部符號序號*/int rLength;/*右部長度*/*注當(dāng)rLength = 1 時，rC

20、ursor = -1為空產(chǎn)生式*/struct pRNode *rHead;/*右部結(jié)點頭指針*/;char VnMaxVnNum + 1;/*非終結(jié)符集*/int vnNum;char VtMaxVtNum + 1;/*終結(jié)符集*/int vtNum;struct pNode PMaxRuleNum;/*產(chǎn)生式*/int PNum;/*產(chǎn)生式實際個數(shù)*/char bufferMaxPLength + 1;char ch;/*符號或string ch;*/char stMaxStLength; /*要分析的符號串*/struct collectNode/*集合元素結(jié)點結(jié)構(gòu)*/int nVt;/

21、*在終結(jié)符集中的下標(biāo)*/struct collectNode *next;struct collectNode* firstMaxVnNum + 1;/*first集*/struct collectNode* followMaxVnNum + 1;/*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/*預(yù)測分析表存放為產(chǎn)生式的編號，+1用于存放結(jié)束符，多+1用于存放#(-1)*/int analyseStackMaxStackDepth + 1;/*分析棧*/int topAnalyse;/*分析棧頂*/*int reverseSta

22、ckMaxStackDepth + 1;/*顛倒順序棧*/*int topReverse;/*倒敘棧頂*/void Init();/*初始化*/int IndexCh(char ch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/void InputVt();/*輸入終結(jié)符*/void InputVn();/*輸入非終結(jié)符*/void ShowChArray(char* collect, int num);/*輸出Vn或Vt的內(nèi)容*/void InputP();/*產(chǎn)生式輸入*/bool CheckP(char * st);/*判斷產(chǎn)生式正確性*/void F

23、irst(int U);/*計算first集,U-xx.*/void AddFirst(int U, int nCh);/*加入first集*/bool HaveEmpty(int nVn); /*判斷first集中是否有空(-1)*/void Follow(int V);/*計算follow集*/void AddFollow(int V, int nCh, int kind);/*加入follow集，kind = 0表加入follow集，kind = 1加入first集*/void ShowCollect(struct collectNode *collect);/*輸出first或foll

24、ow集*/void FirstFollow();/*計算first和follow*/void CreateAT();/*構(gòu)造預(yù)測分析表*/void ShowAT();/*輸出分析表*/void Identify(char *st);/*主控程序,為操作方便*/*分析過程顯示操作為本行變換所用，與教程的顯示方式不同*/void InitStack();/*初始化棧及符號串*/void ShowStack();/*顯示符號棧中內(nèi)容*/void Pop();/*棧頂出棧*/void Push(int r);/*使用產(chǎn)生式入棧操作*/#include LL1.hvoid main(void)char

25、todo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf(所得first集為：);ShowCollect(first);printf(所得follow集為：);ShowCollect(follow);CreateAT();ShowAT();todo = y;while(y = todo)printf(n是否繼續(xù)進行句型分析？(y / n):);todo = getchar();while(y != todo & n != todo)printf(n(y / n)? );todo = getchar();

26、if(y = todo)int i;InitStack();printf(請輸入符號串(以#結(jié)束) : );ch = getchar();i = 0;while(# != ch & i MaxStLength)if( != ch & n != ch)sti+ = ch;ch = getchar();if(# = ch & i MaxStLength)sti = ch;Identify(st);else printf(輸入出錯！n);getchar();void Init()int i,j;vnNum = 0;vtNum = 0;PNum = 0;for(i = 0; i = MaxVnNum;

27、 i+)Vni = 0;for(i = 0; i = MaxVtNum; i+)Vti = 0;for(i = 0; i MaxRuleNum; i+)Pi.lCursor = NULL;Pi.rHead = NULL;Pi.rLength = 0;PNum = 0;for(i = 0; i = MaxPLength; i+)bufferi = 0;for(i = 0; i MaxVnNum; i+)firsti = NULL;followi = NULL;for(i = 0; i = MaxVnNum; i+)for(j = 0; j = MaxVnNum + 1; j+)analyseTa

28、bleij = -1;/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/int IndexCh(char ch)int n;n = 0;/*is Vn?*/while(ch != Vnn & 0 != Vnn)n+;if(0 != Vnn)return 100 + n;n = 0;/*is Vt?*/while(ch != Vtn & 0 != Vtn)n+;if(0 != Vtn)return n;return -1;/*輸出Vn或Vt的內(nèi)容*/void ShowChArray(char* collect)int k = 0;while(0 != collectk

29、)printf( %c , collectk+);printf(n);/*輸入非終結(jié)符*/void InputVn()int inErr = 1;int n,k;char ch;while(inErr)printf(n請輸入所有的非終結(jié)符，注意：);printf(請將開始符放在第一位，并以#號結(jié)束:n);ch = ;n = 0;/*初始化數(shù)組*/while(n MaxVnNum)Vnn+ = 0;n = 0;while(# != ch) & (n MaxVnNum)if( != ch & n != ch & -1 = IndexCh(ch)Vnn+ = ch;vnNum+;ch = getch

30、ar();Vnn = #;/*以“#”標(biāo)志結(jié)束用于判斷長度是否合法*/k = n;/*k用于記錄n以便改Vnn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar();printf(n符號數(shù)目超過限制！n);inErr = 1;continue;/*正確性確認，正確則，執(zhí)行下下面，否則重新輸入*/Vnk = 0;ShowChArray(Vn);ch = ;while(y != ch & n != ch)if(n != ch)printf(輸入正確確認?(y/n):);scanf(%c, &ch);if(n = ch)pr

31、intf(錄入錯誤重新輸入！n);inErr = 1;elseinErr = 0;/*輸入終結(jié)符*/void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf(n請輸入所有的終結(jié)符，注意：);printf(以#號結(jié)束:n);ch = ;n = 0;/*初始化數(shù)組*/while(n MaxVtNum)Vtn+ = 0;n = 0;while(# != ch) & (n MaxVtNum)if( != ch & n != ch & -1 = IndexCh(ch)Vtn+ = ch;vtNum+;ch = getchar();Vtn

32、 = #;/*以“#”標(biāo)志結(jié)束*/k = n;/*k用于記錄n以便改Vtn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar()printf(n符號數(shù)目超過限制！n);inErr = 1;continue;/*正確性確認，正確則，執(zhí)行下下面，否則重新輸入*/Vtk = 0;ShowChArray(Vt);ch = ;while(y != ch & n != ch)if(n != ch)printf(輸入正確確認?(y/n):);scanf(%c, &ch);if(n = ch)printf(錄入錯誤重新輸入！n);in

33、Err = 1;elseinErr = 0;/*產(chǎn)生式輸入*/void InputP()char ch;int i = 0, n,num;printf(請輸入文法產(chǎn)生式的個數(shù)：);scanf(%d, &num);PNum = num;getchar();/*消除回車符*/printf(n請輸入文法的%d個產(chǎn)生式,并以回車分隔每個產(chǎn)生式：, num);printf(n);while(i num)printf(第%d個：, i);/*初始化*/for(n =0; n MaxPLength; n+)buffern = 0;/*輸入產(chǎn)生式串*/ch = ;n = 0;while(n != (ch =

34、getchar() & n rCursor = IndexCh(buffer3);pt-next = NULL;Pi.rHead = pt;n = 4;while(0 != buffern)qt = (pRNode*)malloc(sizeof(pRNode);qt-rCursor = IndexCh(buffern);qt-next = NULL;pt-next = qt;pt = qt;n+;Pi.rLength = n - 3;i+;/*調(diào)試時使用*/elseprintf(輸入符號含非法在成分，請重新輸入！n);/*判斷產(chǎn)生式正確性*/bool CheckP(char * st)int

35、n;if(100 IndexCh(st0)return false;if(- != st1)return false;if( != st2)return false;for(n = 3; 0 != stn; n +)if(-1 = IndexCh(stn)return false;return true;/*=first & follow=*/*計算first集,U-xx.*/void First(int U)int i,j;for(i = 0; i PNum; i+)if(Pi.lCursor = U)struct pRNode* pt;pt = Pi.rHead;j = 0;while(j

36、 pt-rCursor)/*注:此處因編程出錯,使空產(chǎn)生式時rlength同樣是1,故此處同樣可處理空產(chǎn)生式*/AddFirst(U, pt-rCursor);break;elseif(NULL = firstpt-rCursor - 100)First(pt-rCursor);AddFirst(U, pt-rCursor);if(!HaveEmpty(pt-rCursor)break;elsept = pt-next;j+;if(j = Pi.rLength)/*當(dāng)產(chǎn)生式右部都能推出空時*/AddFirst(U, -1);/*加入first集*/void AddFirst(int U, in

37、t nCh)/*當(dāng)數(shù)值小于100時nCh為Vt*/*當(dāng)處理非終結(jié)符時,AddFirst不添加空項(-1)*/struct collectNode *pt, *qt;int ch;/*用于處理Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;elseqt = pt;pt = pt-next;if(NULL = pt)pt = (struct collectNode *)malloc(sizeof(struct collectNode);pt-nVt = nCh;pt-next = NULL;if(NULL = firstU - 100)firstU -

38、 100 = pt;elseqt-next = pt;/*qt指向first集的最后一個元素*/pt = pt-next;elsept = firstnCh - 100;while(NULL != pt)ch = pt-nVt;if(-1 != ch)AddFirst(U, ch);pt = pt-next;/*判斷first集中是否有空(-1)*/bool HaveEmpty(int nVn)if(nVn nVt)return true;pt = pt-next;return false;/*計算follow集,例：U-xVy,U-xV.(注：初始符必含#-1)*/void Follow(i

39、nt V)int i;struct pRNode *pt;if(100 = V)/*當(dāng)為初始符時*/AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能處理：U-xVyVz的情況*/pt = pt-next;if(NULL != pt)pt = pt-next;/*V右側(cè)的符號*/if(NULL = pt)/*當(dāng)V后為空時V-xV，將左符的follow集并入V的follow集中*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor);AddFollow(

40、V, Pi.lCursor, 0);else/*不為空時V-xVy,(注意：y-)，調(diào)用AddFollow加入Vt或y的first集*/while(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1);/*y的前綴中有空時，加如first集*/pt = pt-next;if(NULL = pt)/*當(dāng)后面的字符可以推出空時*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);els

41、e/*發(fā)現(xiàn)不為空的字符時*/AddFollow(V, pt-rCursor, 1);/*當(dāng)數(shù)值小于100時nCh為Vt*/*#用-1表示,kind用于區(qū)分是并入符號的first集，還是follow集kind = 0表加入follow集，kind = 1加入first集*/void AddFollow(int V, int nCh, int kind)struct collectNode *pt, *qt;int ch;/*用于處理Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;elseqt = pt;pt = pt-next;if(NULL = p

42、t)pt = (struct collectNode *)malloc(sizeof(struct collectNode);pt-nVt = nCh;pt-next = NULL;if(NULL = followV - 100)followV - 100 = pt;elseqt-next = pt;/*qt指向follow集的最后一個元素*/pt = pt-next;else/*為非終結(jié)符時，要區(qū)分是加first還是follow*/if(0 = kind)pt = follownCh - 100;while(NULL != pt)ch = pt-nVt;AddFollow(V, ch, 0)

43、;pt = pt-next;elsept = firstnCh - 100;while(NULL != pt)ch = pt-nVt;if(-1 != ch)AddFollow(V, ch, 1);pt = pt-next;/*輸出first或follow集*/void ShowCollect(struct collectNode *collect)int i;struct collectNode *pt;i = 0;while(NULL != collecti)pt = collecti;printf(n%c:t, Vni);while(NULL != pt)if(-1 != pt-nVt)printf( %c, Vtpt-nVt);elseprintf( #);pt = pt-next;i+;printf(n);/*計算first和follow*/void FirstFollow()int i;i = 0;while(0 != Vni)if(