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

课程名称编译原理专业班级姓名学号实验一词法分析器设计【实验目的】1．熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。2．复习高级语言，进一步加强用高级语言来解决实际问题的能力。3．通过完成词法分析程序，了解词法分析的过程。【实验内容】用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。【实验步骤和要求】要求绘出词法分析过程的流程图。根据词法分析的目的以及内容，确定完成分析过程所需模块。写出每个模块的源代码。整理程序清单及所得结果。【流程图】【源代码】//resource.h#defineIDD_MAINDLG101#defineIDR_MENU102#defineIDI_ICON104#defineIDC_INPUT1001#defineIDC_OUTPUT1003#defineIDC_ERRPUT1004#defineIDC_BUTTON11005#defineID_START40001#defineID_ABOUT40003#defineID_OPEN40005#defineID_SAVE40006#defineID_LISTKEY40007//Nextdefaultvaluesfornewobjects//#ifdefAPSTUDIO_INVOKED#endif#endif//getsym.h#ifndef_GETSYM_H_#define_GETSYM_H_#include<stdlib.h> //Formemset()#include<string.h> //Forstrcpy()#defineISLETTER(c) ((c)>='A'&&(c)<='Z'||(c)>='a'&&(c)<='z')#defineISNUMBER(c) ((c)>='0'&&(c)<='9')#defineISCHAR(c) ((c)>=33&&(c)<=126)#defineMAX_SYM 32768 //最大符号量#defineMAX_SYMFORM 1024 //最大符号表长度#define MAX_NUMFORM 4096 //最大常数表长度#defineMAX_SYMLEN 31 //最大符号长度#defineMAX_NUMLEN 10 //最大常数长度#defineMAX_BUFFER MAX_SYMLEN+1//最大缓冲长度#defineMAX_KEYWORD 27 //关键字数量#defineMAX_OPWORDA 8 //单字运算符数量#defineMAX_OPWORDB 4 //双字运算符数量#defineMAX_ENDWORD 8 //单字界符数量#defineMAX_ERROR 5 //错误类型数量#defineTYPE_KEYWORD 1 //关键字类型号#defineTYPE_SYMBOL 2 //符号类型号#defineTYPE_NUMBER 3 //常量类型号#defineTYPE_OPWORD 4 //运算符类型号#defineTYPE_ENDWORD 5 //界符类型号#defineTYPE_ERROR -1 //错误类型号#defineERR_OVERSYMLEN 1 //以下是一般错误号#defineERR_OVERNUMLEN 2#defineERR_NUMBER 3#defineERR_WRONGOP 4#defineERR_OVERSYMFORM 10001 //以下是严重错误号#defineERR_OVERNUMFORM10002#defineERR_OVERSYMNUM 10003#defineERR_OVERERRNUM 10004#ifdef__cplusplusextern"C"{#endifstructSYM //符号描述结构体(含错误描述结构)};structFORM //表格结构体{ intsymnum; intnumnum; structSYMF //符号表项结构体 { intid; charname[MAX_SYMLEN+1]; }symf[MAX_SYMFORM]; structNUMF //常量表项结构体 { intid; charname[MAX_NUMLEN+1]; }numf[MAX_NUMFORM];};structSYMINFO //词法分析信息结构体{ intnum; structSYMsym[MAX_SYM]; structFORMform;};//取词函数(返回读字符数量,如果是0则表示结束,lin表示当前行数)int__stdcallgetsym(constchar*in,structSYM*out,int*ln,structFORM*form);//取所有词函数(正常返回0,否则返回严重错误号)int__stdcallgetsyminfo(constchar*in,structSYMINFO*out);#ifdef__cplusplus}#endif#endif#include"getsym.h"//关键字[BASIC:13,EXTEND:14]constchar*constkeytxt[MAX_KEYWORD]={ "procedure","call","begin","end","var","const", "if","then","while","do","read","write","odd", "program","type","function","array","integer", };//单字运算符constcharopatxt[MAX_OPWORDA]={ '+','-','*','/','=','#','<','>'};//双字运算符constchar*constopbtxt[MAX_OPWORDB]={ "<=",">=",":=","<>"};//单字界符constchareoptxt[MAX_ENDWORD]={ '(',')',',',';','.','[',']',':'};//错误提示信息constchar*consterrtxt[MAX_ERROR]={ "OK", //Notused. "Toolongsymbol", "Toolongnumber", "Mixednumberandletter", "Unkownoperator",};intgetsym(constchar*in,structSYM*out,int*ln,structFORM*form){ charb[MAX_BUFFER]; //建符号缓冲区 inti,m=0,n=0,e=0; //序号/非字符数/字符数/出错标记 memset(out,0,sizeof(structSYM)); while(!ISCHAR(*in)) //滤出前面的非字符 { if(*in==10)(*ln)++;//换行时,ln++ if(*in++)m++;elsereturn0; //如果无字符则退出 } out->line=*ln; if(ISLETTER(*in)) //字母开头情况 { while(ISLETTER(*in)||ISNUMBER(*in)) { if(n<=MAX_SYMLEN)b[n]=*in; { out->type=TYPE_ERROR; out->id=ERR_OVERSYMLEN; } else { for(i=0;i<MAX_KEYWORD;i++) if(strcmp(b,keytxt[i])==0)break; if(i<MAX_KEYWORD) //属于关键字 { out->type=TYPE_KEYWORD; out->id=i; } else //不属于关键字 { for(i=0;i<form->symnum;i++) if(strcmp(b,form->symf[i].name)==0)break; if(i==form->symnum) //不在符号表中则添加 { if(form->symnum>=MAX_SYMFORM) { //超出符号表范围产生严重错误 out->type=TYPE_ERROR; out->id=ERR_OVERSYMFORM; returnm+n; } form->symf[i].id=i; strcpy(form->symf[i].name,b); form->symnum++; } out->type=TYPE_SYMBOL; //符号类型 out->id=i; } } returnm+n; } if(ISNUMBER(*in)) //数字开头情况 { e=0; } b[MAX_NUMLEN]=0; //数字尾置0 if(n<MAX_NUMLEN)b[n]=0; strcpy(out->name,b); if(e||n>MAX_NUMLEN) //有出错标记或超出数字最大长度 { out->type=TYPE_ERROR; if(e) //含字母情况 out->id=ERR_NUMBER; else //超出数字最大长度情况 out->id=ERR_OVERNUMLEN; } else //无错情况 { if(form->numnum>=MAX_NUMFORM) { //超出常量表范围产生严重错误 out->type=TYPE_ERROR; out->id=ERR_OVERNUMFORM; returnm+n; } form->numf[form->numnum].id=form->numnum; strcpy(form->numf[form->numnum].name,b); out->type=TYPE_NUMBER; out->id=form->numnum; form->numnum++; } returnm+n; } for(i=0;i<MAX_OPWORDB;i++) //双字运算符情况 if(*(short*)in==*(short*)(opbtxt[i]))break; if(i<MAX_OPWORDB) { out->type=TYPE_OPWORD; out->id=MAX_OPWORDA+i; *(short*)out->name=*(short*)opbtxt[i]; out->name[2]=0; returnm+2; } { out->type=TYPE_OPWORD; out->id=i; returnm+1; } for(i=0;i<MAX_ENDWORD;i++) //单字界符情况 if(*in==eoptxt[i])break; if(i<MAX_ENDWORD) { out->type=TYPE_ENDWORD; out->id=i; returnm+1; } out->type=TYPE_ERROR; out->id=ERR_WRONGOP; //其他符号则出错 returnm+1;}intgetsyminfo(constchar*in,structSYMINFO*out){ intoffset,ln=1; //每次取词偏移量/当前行数 memset(out,0,sizeof(structSYMINFO)); while(1) { offset=getsym(in,&out->sym[out->num],&ln,&out->form); if(offset==0)break; //完成取词则退出 if(out->num>=MAX_SYM)returnERR_OVERSYMNUM;//超出符号信息最大值 if(out->sym[out->num].type==TYPE_ERROR&&out->sym[out->num].id>=10000) returnout->sym[out->num].id;//有严重错误则退出 out->num++; in+=offset; } return0;}Test.Txtprogramtest;procedurefunc(a:integer,b:char);begin varc:char; end;begin consts:=4444; a:=b[333]; whiles=ado begin calltest; end; write(a);end.结果实验二LL（1）语法分析程序设计【实验目的】1．熟悉判断LL（1）文法的方法及对某一输入串的分析过程。2．学会构造表达式文法的预测分析表。【实验内容】编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。【实验步骤和要求】从键盘读入输入串，并判断正误；若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；若符合LL（1）文法，由程序自动构造LL（1）分析表；由算法判断输入符号串是否为该文法的句型。（可参考教材96页的例题1）【源代码】#include"stdio.h"

#include"stdlib.h"#defineMaxRuleNum8

#defineMaxVnNum5

#defineMaxVtNum5

#defineMaxStackDepth20

#defineMaxPLength20

#defineMaxStLength50

structpRNode/*产生式右部结构*/

{intrCursor;/*右部序号*/structpRNode*next;

};structpNode/*产生式结点结构*/

{intlCursor;/*左部符号序号*/intrLength;/*右部长度*//*注当rLength=1时，rCursor=-1为空产生式*/structpRNode*rHead;/*右部结点头指针*/

};

intPNum;/*产生式实际个数*/

charbuffer[MaxPLength+1];

charch;/*符号或stringch;*/

charst[MaxStLength];/*要分析的符号串*/structcollectNode/*集合元素结点结构*/

{intnVt;/*在终结符集中的下标*/structcollectNode*next;

};structcollectNode*first[MaxVnNum+1];/*first集*/

structcollectNode*follow[MaxVnNum+1];/*follow集*/intanalyseTable[MaxVnNum+1][MaxVtNum+1+1];

/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/intanalyseStack[MaxStackDepth+1];/*分析栈*/

inttopAnalyse;/*分析栈顶*/

/*intreverseStack[MaxStackDepth+1];/*颠倒顺序栈*/

/*inttopReverse;/*倒叙栈顶*/

voidInit();/*初始化*/

intIndexCh(charch);

/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/

voidInputVt();/*输入终结符*/

voidInputVn();/*输入非终结符*/

voidShowChArray(char*collect,intnum);/*输出Vn或Vt的内容*/

voidInputP();/*产生式输入*/

boolCheckP(char*st);/*判断产生式正确性*/

voidFirst(intU);/*计算first集,U->xx...*/

voidAddFirst(intU,intnCh);/*加入first集*/

boolHaveEmpty(intnVn);/*判断first集中是否有空(-1)*/

voidFollow(intV);/*计算follow集*/

voidAddFollow(intV,intnCh,intkind);/*加入follow集，kind=0表加入follow集，kind=1加入first集*/

voidShowCollect(structcollectNode**collect);/*输出first或follow集*/

voidFirstFollow();/*计算first和follow*/

voidCreateAT();/*构造预测分析表*/

voidShowAT();/*输出分析表*/

voidIdentify(char*st);/*主控程序,为操作方便*/

/*分析过程显示操作为本行变换所用，与教程的显示方式不同*/

voidInitStack();/*初始化栈及符号串*/

voidShowStack();/*显示符号栈中内容*/

voidPop();/*栈顶出栈*/

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();}if('y'==todo){inti;InitStack();printf("请输入符号串(以#结束):");ch=getchar();i=0;while('#'!=ch&&i<MaxStLength){if(''!=ch&&'\n'!=ch){st[i++]=ch;}ch=getchar();}if('#'==ch&&i<MaxStLength){st[i]=ch;Identify(st);}elseprintf("输入出错！\n");}}getchar();

}

voidInit()

{inti,j;vnNum=0;vtNum=0;PNum=0;for(i=0;i<=MaxVnNum;i++)Vn[i]='\0';for(i=0;i<=MaxVtNum;i++)Vt[i]='\0';for(i=0;i<MaxRuleNum;i++){P[i].lCursor=NULL;P[i].rHead=NULL;P[i].rLength=0;}PNum=0;for(i=0;i<=MaxPLength;i++)buffer[i]='\0';for(i=0;i<MaxVnNum;i++){first[i]=NULL;follow[i]=NULL;}for(i=0;i<=MaxVnNum;i++){for(j=0;j<=MaxVnNum+1;j++)analyseTable[i][j]=-1;}

}

/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/

intIndexCh(charch)

{intn;n=0;/*isVn?*/while(ch!=Vn[n]&&'\0'!=Vn[n])n++;if('\0'!=Vn[n])return100+n;n=0;/*isVt?*/while(ch!=Vt[n]&&'\0'!=Vt[n])n++;if('\0'!=Vt[n])returnn;return-1;

}

/*输出Vn或Vt的内容*/

voidShowChArray(char*collect)

{intk=0;while('\0'!=collect[k]){printf("%c",collect[k++]);}printf("\n");

}

/*输入非终结符*/

voidInputVn()

{intinErr=1;intn,k;charch;while(inErr){printf("\n请输入所有的非终结符，注意：");printf("请将开始符放在第一位，并以#号结束:\n");ch='';n=0;/*初始化数组*/while(n<MaxVnNum){Vn[n++]='\0';}n=0;while(('#'!=ch)&&(n<MaxVnNum)){if(''!=ch&&'\n'!=ch&&-1==IndexCh(ch)){Vn[n++]=ch;vnNum++;}ch=getchar();}Vn[n]='#';/*以“#”标志结束用于判断长度是否合法*/k=n;/*k用于记

}

/*输入终结符*/

voidInputVt()

{intinErr=1;intn,k;charch;while(inErr){printf("\n请输入所有的终结符，注意：");printf("以#号结束:\n");ch='';n=0;/*初始化数组*/while(n<MaxVtNum){Vt[n++]='\0';}n=0;while(('#'!=ch)&&(n<MaxVtNum)){if(''!=ch&&'\n'!=ch&&-1==IndexCh(ch)){Vt[n++]=ch;vtNum++;}ch=getchar();}Vt[n]='#';/*以“#”标志结束*/k=n;/*k用于记录n以便改Vt[n]='\0'*/if('#'!=ch){if('#'!=(ch=getchar())){while('#'!=(ch=getchar()))printf("\n符号数目超过限制！\n");inErr=1;continue;}}/*正确性确认，正确则，执行下下面，否则重新输入*/Vt[k]='\0';ShowChArray(Vt);ch='';while('y'!=ch&&'n'!=ch){if('\n'!=ch){printf("输入正确确认?(y/n):");}scanf("%c",&ch);}if('n'==ch){printf("录入错误重新输入！\n");inErr=1;}else{inErr=0;}}

}

/*产生式输入*/

voidInputP()

{charch;inti=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++)buffer[n]='\0';/*输入产生式串*/ch='';n=0;while('\n'!=(ch=getchar())&&n<MaxPLength){if(''!=ch)buffer[n++]=ch;}buffer[n]='\0';

/*printf("%s",buffer);*/if(CheckP(buffer)){/*填写入产生式结构体*/pRNode*pt,*qt;P[i].lCursor=IndexCh(buffer[0]);pt=(pRNode*)malloc(sizeof(pRNode));pt->rCursor=IndexCh(buffer[3]);pt->next=NULL;P[i].rHead=pt;n=4;while('\0'!=buffer[n]){qt=(pRNode*)malloc(sizeof(pRNode));qt->rCursor=IndexCh(buffer[n]);qt->next=NULL;pt->next=qt;pt=qt;n++;}P[i].rLength=n-3;i++;/*调试时使用*/}elseprintf("输入符号含非法在成分，请重新输入！\n");}

}

/*判断产生式正确性*/

boolCheckP(char*st)

{intn;if(100>IndexCh(st[0]))returnfalse;if('-'!=st[1])returnfalse;if('>'!=st[2])returnfalse;for(n=3;'\0'!=st[n];n++){if(-1==IndexCh(st[n]))returnfalse;}returntrue;

}

/*====================first&follow======================*/

/*计算first集,U->xx...*/

}

/*加入first集*/

voidAddFirst(intU,intnCh)/*当数值小于100时nCh为Vt*/

/*当处理非终结符时,AddFirst不添加空项(-1)*/

{structcollectNode*pt,*qt;intch;/*用于处理Vn*/pt=NULL;qt=NULL;if(nCh<100){pt=first[U-100];while(NULL!=pt){if(pt->nVt==nCh)break;else{qt=pt;pt=pt->next;}}if(NULL==pt){pt=(structcollectNode*)malloc(sizeof(structcollectNode));pt->nVt=nCh;pt->next=NULL;if(NULL==first[U-100]){first[U-100]=pt;}else{qt->next=pt;/*qt指向first集的最后一个元素*/}pt=pt->next;}}else{pt=first[nCh-100];while(NULL!=pt){ch=pt->nVt;if(-1!=ch){AddFirst(U,ch);}pt=pt->next;}}

}

/*判断first集中是否有空(-1)*/boolHaveEmpty(intnVn)

{if(nVn<100)/*为终结符时(含-1)，在follow集中用到*/returnfalse;structcollectNode*pt;pt=first[nVn-100];while(NULL!=pt){if(-1==pt->nVt)returntrue;pt=pt->next;}returnfalse;

}

/*计算follow集,例：U->xVy,U->xV.(注：初始符必含#——"-1")*/

voidFollow(intV)

{inti;structpRNode*pt;if(100==V)/*当为初始符时*/AddFollow(V,-1,0);for(i=0;i<PNum;i++){pt=P[i].rHead;while(NULL!=pt&&pt->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==follow[P[i].lCursor-100]&&P[i].lCursor!=V){Follow(P[i].lCursor);}AddFollow(V,P[i].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==follow[P[i].lCursor-100]&&P[i].lCursor!=V){Follow(P[i].lCursor);}AddFollow(V,P[i].lCursor,0);}else/*发现不为空的字符时*/{AddFollow(V,pt->rCursor,1);}}}}

}/*当数值小于100时nCh为Vt*/

/*#用-1表示,kind用于区分是并入符号的first集，还是follow集

kind=0表加入follow集，kind=1加入first集*/

}

/*输出first或follow集*/

voidShowCollect(structcollectNode**collect)

{inti;structcollectNode*pt;i=0;while(NULL!=collect[i]){pt=collect[i];printf("\n%c:\t",Vn[i]);while(NULL!=pt){if(-1!=pt->nVt){printf("%c",Vt[pt->nVt]);}elseprintf("#");pt=pt->next;}i++;}printf("\n");

}

/*计算first和follow*/

voidFirstFollow()

{inti;i=0;while('\0'!=Vn[i]){if(NULL==first[i])First(100+i);i++;}i=0;while('\0'!=Vn[i]){if(NULL==follow[i])Follow(100+i);i++;}

}

/*=================构造预测分析表,例：U::xyz=============*/

voidCreateAT()

{inti;structpRNode*pt;structcollectNode*ct;for(i=0;i<PNum;i++){pt=P[i].rHead;while(NULL!=pt&&HaveEmpty(pt->rCursor)){/*处理非终结符，当为终结符时，定含空为假跳出*/ct=first[pt->rCursor-100];while(NULL!=ct){if(-1!=ct->nVt)analyseTable[P[i].lCursor-100][ct->nVt]=i;ct=ct->next;}pt=pt->next;}if(NULL==pt){/*NULL==pt，说明xyz->,用到follow中的符号*/ct=follow[P[i].lCursor-100];while(NULL!=ct){if(-1!=ct->nVt)analyseTable[P[i].lCursor-100][ct->nVt]=i;else/*当含有#号时*/analyseTable[P[i].lCursor-100][vtNum]=i;ct=ct->next;}}else{if(100<=pt->rCursor)/*不含空的非终结符*/{ct=first[pt->rCursor-100];while(NULL!=ct){analyseTable[P[i].lCursor-100][ct->nVt]=i;ct=ct->next;}}else/*终结符或者空*/{if(-1==pt->rCursor)/*-1为空产生式时*/{ct=follow[P[i].lCursor-100];while(NULL!=ct){if(-1!=ct->nVt)analyseTable[P[i].lCursor-100][ct->nVt]=i;else/*当含有#号时*/analyseTable[P[i].lCursor-100][vtNum]=i;ct=ct->next;}}else/*为终结符*/{analyseTable[P[i].lCursor-100][pt->rCursor]=i;}}}}

}

/*输出分析表*/

voidShowAT()

{inti,j;analyseTable[i][j]);elseprintf("error\t");}printf("\n");}

}/*=================主控程序=====================*/

voidIdentify(char*st)

{intcurrent,step,r;/*r表使用的产生式的序号*/printf("\n%s的分析过程：\n",st);printf("步骤\t分析符号栈\t当前指示字符\t使用产生式序号\n");step=0;current=0;/*符号串指示器*/printf("%d\t",step);ShowStack();printf("\t\t%c\t\t--\n",st[current]);while('#'!=st[current]){if(100>analyseStack[topAnalyse])/*当为终结符时*/{if(analyseStack[topAnalyse]==IndexCh(st[current])){/*匹配出栈，指示器后移*/Pop();current++;step++;printf("%d\t",step);ShowStack();printf("\t\t%c\t\t出栈、后移\n",st[cur