编译原理词法分析和ll文法判定

1、武汉科技大学实验报告课程名称编译原理 专业班级姓 名学 号实验一 词法分析器设计【实验目的】1熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。2复习高级语言，进一步加强用高级语言来解决实际问题的能力。3通过完成词法分析程序，了解词法分析的过程。【实验内容】用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。【实验步骤和要求】1 要求绘出词法分析过程的流程图。2 根据词法分析的目的以及内容，确定完成分析过程所需模块。3 写出每个模块的源代码。

2、4 整理程序清单及所得结果。【流程图】【源代码】/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/最大常数表长度#define MAX_SYMLEN31/最大符号长度#define MAX_NUMLEN10/最大常数长度#define MAX_BUFFERMAX_SYMLEN+1/最大缓冲长度#define MAX_KEYWORD27/关键字数量#def

5、ine MAX_OPWORDA8/单字运算符数量#define MAX_OPWORDB4/双字运算符数量#define MAX_ENDWORD8/单字界符数量#define MAX_ERROR5/错误类型数量#define TYPE_KEYWORD1/关键字类型号#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/符号描述结构体(含错误描述结构)int type;/类型号(0:错误)int id;/ID号(错误值)int line;/所在行数/int no;/SYM编号

7、/列号char nameMAX_SYMLEN+1;/所取的词;struct FORM/表格结构体int symnum;int numnum;struct SYMF/符号表项结构体int id;char nameMAX_SYMLEN+1;symfMAX_SYMFORM;struct NUMF/常量表项结构体int id;char nameMAX_NUMLEN+1;numfMAX_NUMFORM;struct SYMINFO/词法分析信息结构体int num;struct SYM symMAX_SYM;struct FORM form;/取词函数(返回读字符数量,如果是0则表示结束,lin表示当前

8、行数)int _stdcall getsym(const char *in,struct SYM *out,int *ln,struct FORM *form);/取所有词函数(正常返回0,否则返回严重错误号)int _stdcall getsyminfo(const char *in,struct SYMINFO *out);#ifdef _cplusplus#endif#endif#include getsym.h/关键字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;/建符号缓冲区int i,m=0,n=0,e=0;/序号/非字符数/字符数/出错标记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;/符号结尾置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/不属于关键字for(i=0;isymnum;i+)if(strcmp(b,)=0) break;if(i=form-symnum)/不在符号表中则添加if(form-symnum=MAX_SYMFORM)/超出符号表范围产生严重错误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)/数字开头情况e=0;while(ISNUMBER(*in)|ISLETTER(*in)if(ISLETTER(*in) e=1;/含字母则置出错标记if(n=MAX_NUMLEN) bn=*in;n+; in+;bMAX_NUMLEN=0;/数字尾置0if(nname,b);if(e|nMAX_NUMLEN)/有出错标记或超出数字最大长度out-type=TYPE_ERROR;if(e)/含字母情况out-id=ERR_NUMBER;else/超出数字最大长度情况out-id=ERR_OVERNUMLEN;else/无错情况if(fo

14、rm-numnum=MAX_NUMFORM)/超出常量表范围产生严重错误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;/每次取词偏移量/当前行数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.结果实验二 LL（1）语法分析程序设计 【实验目的】1熟悉判断LL（1）文法的方法及对某一输入串的分析过程。2学会构造表达式文法的预测分析表。【实验内容】编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。【实验步骤和要求】1 从键盘读入输入串，并判断正误；2 若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；3 若符合LL（1）文法，由程序自动构造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/*产生式右部结构*/int rCursor;/*右部序号*/struct pRNode *next;struct pNode/*产生式结点结构*/int lCursor;/*左部符号序号*/int rLength;/*右部长度*/*注当rLength = 1 时，rC

20、ursor = -1为空产生式*/struct pRNode *rHead;/*右部结点头指针*/;char VnMaxVnNum + 1;/*非终结符集*/int vnNum;char VtMaxVtNum + 1;/*终结符集*/int vtNum;struct pNode PMaxRuleNum;/*产生式*/int PNum;/*产生式实际个数*/char bufferMaxPLength + 1;char ch;/*符号或string ch;*/char stMaxStLength; /*要分析的符号串*/struct collectNode/*集合元素结点结构*/int nVt;/

21、*在终结符集中的下标*/struct collectNode *next;struct collectNode* firstMaxVnNum + 1;/*first集*/struct collectNode* followMaxVnNum + 1;/*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/*预测分析表存放为产生式的编号，+1用于存放结束符，多+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();/*输入终结符*/void InputVn();/*输入非终结符*/void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/void InputP();/*产生式输入*/bool CheckP(char * st);/*判断产生式正确性*/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();/*构造预测分析表*/void ShowAT();/*输出分析表*/void Identify(char *st);/*主控程序,为操作方便*/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/void InitStack();/*初始化栈及符号串*/void ShowStack();/*显示符号栈中内容*/void Pop();/*栈顶出栈*/void Push(int r);/*使用产生式入栈操作*/#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是否继续进行句型分析？(y / n):);todo = getchar();while(y != todo & n != todo)printf(n(y / n)? );todo = getchar();

26、if(y = todo)int i;InitStack();printf(请输入符号串(以#结束) : );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的内容*/void ShowChArray(char* collect)int k = 0;while(0 != collectk

29、)printf( %c , collectk+);printf(n);/*输入非终结符*/void InputVn()int inErr = 1;int n,k;char ch;while(inErr)printf(n请输入所有的非终结符，注意：);printf(请将开始符放在第一位，并以#号结束:n);ch = ;n = 0;/*初始化数组*/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 = #;/*以“#”标志结束用于判断长度是否合法*/k = n;/*k用于记录n以便改Vnn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar();printf(n符号数目超过限制！n);inErr = 1;continue;/*正确性确认，正确则，执行下下面，否则重新输入*/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;/*输入终结符*/void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf(n请输入所有的终结符，注意：);printf(以#号结束:n);ch = ;n = 0;/*初始化数组*/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、 = #;/*以“#”标志结束*/k = n;/*k用于记录n以便改Vtn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar()printf(n符号数目超过限制！n);inErr = 1;continue;/*正确性确认，正确则，执行下下面，否则重新输入*/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;/*产生式输入*/void InputP()char ch;int i = 0, n,num;printf(请输入文法产生式的个数：);scanf(%d, &num);PNum = num;getchar();/*消除回车符*/printf(n请输入文法的%d个产生式,并以回车分隔每个产生式：, num);printf(n);while(i num)printf(第%d个：, i);/*初始化*/for(n =0; n MaxPLength; n+)buffern = 0;/*输入产生式串*/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+;/*调试时使用*/elseprintf(输入符号含非法在成分，请重新输入！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)/*注:此处因编程出错,使空产生式时rlength同样是1,故此处同样可处理空产生式*/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)/*当产生式右部都能推出空时*/AddFirst(U, -1);/*加入first集*/void AddFirst(int U, in

37、t nCh)/*当数值小于100时nCh为Vt*/*当处理非终结符时,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)/*当为初始符时*/AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能处理：U-xVyVz的情况*/pt = pt-next;if(NULL != pt)pt = pt-next;/*V右侧的符号*/if(NULL = pt)/*当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-)，调用AddFollow加入Vt或y的first集*/while(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1);/*y的前缀中有空时，加如first集*/pt = pt-next;if(NULL = pt)/*当后面的字符可以推出空时*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);els

41、e/*发现不为空的字符时*/AddFollow(V, pt-rCursor, 1);/*当数值小于100时nCh为Vt*/*#用-1表示,kind用于区分是并入符号的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/*为非终结符时，要区分是加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(