词法分析与语法分析程序设计

第1页实验三词法分析与语法分析程序设计一．实验目的基本掌握计算机语言的词法分析程序和语法分析程序的设计方法。二．实验要求、内容及步骤实验要求：1.根据以下的正规式，画出状态图；标识符：字母(字母|数字字符)*关键字：ifthenelsewhiledo十进制整数：0|（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*运算符和分隔符：+-*/=()。2.根据状态图，设计词法分析函数intscan()，从键盘读入数据，分析出一个单词。3.对于只含有+、*运算的算术表达式的如下文法，编写相应的语法分析程序，要求用LL(1)分析表实现，并以id+id*id为例进行测试：E—＞TE′E′—＞+TE′|εT—＞FT′T′—＞*FT′|εF—＞（E）|id实验步骤：1.根据状态图，设计词法分析算法；2.采用C++语言，实现该算法；3.调试程序：输入一组单词，检查输出结果；第2页4.编制给定文法的非递归的预测分析程序，并加以测试。三．实验设备计算机、Windows操作系统、VisualC++程序集成环境。四．实验原理1.词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序列。产生下述小语言的单词序列。这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：单词符号种别编码助记符内码值DIMIFDOSTOPEND标识符常数（整）=+***，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR------内部字符串标准二进形式------对于这个小语言，有几点重要的限制：首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的：IF（5）=x。其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来第3页处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为IFi0i=1;而绝对不要写成IFi0i=1;因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。这个小语言的单词符号的状态转换图，如下图：第4页2.语法分析是决定如何使用一个文法生成一个终结符串的过程。语法分析器能识别由加+减-乘*除/乘方^括号（）操作数所组成的算术表达式，其文法如下：E→E+T|E-T|TT→T*F|T/F|FF→P^F|Pp→(E)|i使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。分析表格式：id+*()$EE—＞TE′E—＞TE′E′E′—＞+TE′E′—＞εE′—＞εTT—＞FT′T—＞FT′T′T′—＞εT′—＞*FT′T′—＞εT′—＞εFF—＞idF—＞(E)3.中间代码生成器产生上述算术表达式的中间代码（四元式序列）。第5页五．实验代码及结果词法分析代码：#includestring.h#includeiostreamusingnamespacestd;charprog[100],token[10];charch;intsyn,p,m=0,n,row,sum=0;char*rwtab[20]={dim,if,do,stop,end,and,begin,bool,case,char,false,for,int,not,or,set,then,true,until,while};voidscaner(){for(n=0;n9;n++)token[n]=NULL;ch=prog[p++];while(ch==''){ch=prog[p];p++;}if((ch='a'&&ch='z')||(ch='A'&&ch='Z')){m=0;while((ch='0'&&ch='9')||(ch='a'&&ch='z')||(ch='A'&&ch='Z')){token[m++]=ch;ch=prog[p++];}token[m++]='\0';p--;syn=21;for(n=0;n20;n++){if(strcmp(token,rwtab[n])==0){第6页syn=n+1;break;}}}elseif((ch='0'&&ch='9')){{sum=0;while((ch='0'&&ch='9')){sum=sum*10+ch-'0';ch=prog[p++];}}p--;syn=7+15;if(sum32767)syn=-1;}elseswitch(ch){case'=':syn=8+15;token[0]=ch;break;case'+':syn=9+15;token[0]=ch;break;case'*':m=0;token[m++]=ch;ch=prog[p++];if(ch=='*'){syn=11+15;token[m++]=ch;}else{syn=10+15;p--;}break;第7页case',':syn=12+15;token[0]=ch;break;case'(':syn=13+15;token[0]=ch;break;case')':syn=14+15;token[0]=ch;break;case'#':syn=0;token[0]=ch;break;case'':m=0;token[m++]=ch;ch=prog[p++];if(ch==''){syn=17+15;token[m++]=ch;}elseif(ch=='='){syn=16+15;token[m++]=ch;}else{syn=15+15;p--;}break;case'':m=0;token[m++]=ch;ch=prog[p++];if(ch=='='){syn=19+15;token[m++]=ch;}else{syn=18+15;p--;}break;case':':m=0;token[m++]=ch;ch=prog[p++];if(ch=='=')第8页{syn=21+15;token[m++]=ch;}else{syn=20+15;p--;}break;case'/':syn=22+15;token[0]=ch;break;case'-':syn=23+15;token[0]=ch;break;case';':syn=24+15;token[0]=ch;break;default:syn=-1;break;}}voidmain(){p=0;row=1;coutendlendlendl;cout词法分析endlendl;cout请输入一段程序（以#结束）:;do{cin.get(ch);prog[p++]=ch;}while(ch!='#');p=0;coutendl词法分析结果如下endl;cout种别编码自身值endl;do{scaner();switch(syn){第9页case22:cout(syn,sum)endl;break;case-1:coutErrorinrowrow!endl;break;default:cout(syn,token)endl;break;}}while(syn!=0);}词法分析结果：语法分析代码：第10页#includestring.h#includemalloc.h#includeiostreamusingnamespacestd;typedefstructtable//分析表存储结构{charm[100];}table;tableM[100][100];//定义分析表typedefstructstacknode//定义栈内元素节点(带头结点（为空）的){chardata;structstacknode*next;}stackk;voidinitlink(stackk*&s)//初始化新栈{s=(stackk*)malloc(sizeof(stackk));s-next=NULL;}voidpoplink(stackk*&s)//顶元素出栈{stackk*p;charv;if(s-next!=NULL){p=s-next;v=p-data;s-next=p-next;}free(p);}voidpushlink(stackk*&s,charx)//新元素入栈{stackk*p;p=(stackk*)malloc(sizeof(stackk));第11页p-data=x;p-next=s-next;s-next=p;}voiddisplay(stackk*s)//打印现实显示栈内元素{stackk*p;inti=0,j;charst[100];p=s-next;while(p!=NULL){st[i++]=p-data;p=p-next;}for(j=i-1;j=0;j--)printf(%c,st[j]);for(j=0;j16-i;j++)//打印对齐格式printf(%c,'');}chargettop(stackk*s)//返回栈顶元素值{if(s-next==NULL)return0;elsereturns-next-data;}intfind(charc,chararray[])//查找函数，{inti;intflag=0;for(i=0;i100;i++){第12页if(c==array[i])flag=1;}returnflag;}intlocation(charc,chararray[])//定位函数,指出字符所在位置{inti;for(i=0;i100;i++){if(c==array[i])returni;}}voiderror()//出错函数定义{printf(%15c出错!\n,'');}voidanalyse(charVn[],charVt[]){inti,j,m,p,q,length,t,h;charw,X;charstr[100];opt0:scanf(%s,str);for(i=0;istrlen(str);i++){if(!find(str[i],Vt)){printf(输入字符串有误!请重新输入!);gotoopt0;break;}}第13页stackk*st;initlink(st);pushlink(st,'#');pushlink(st,Vn[0]);//#与识别符号入栈j=0;h=1;w=str[0];printf(步骤%-12c分析栈%-24c剩余输入串%-12c所用产生式\n,'','','');opt1:printf(%-16d,h);//显示步骤h++;display(st);//显示分析栈中内容X=gettop(st);//上托栈顶符号放入Xpoplink(st);for(intk=0;k14+j;k++)//打印对齐格式printf(%c,'');for(t=j;tstrlen(str);t++){printf(%c,str[t]);//显示剩余字符串}if(find(X,Vt)&&X!='#')//分析栈的栈顶元素和剩余输入串的第一个元素相比较{if(X==w){printf(%15c匹配\n,X);j++;w=str[j];gotoopt1;}elseerror();}else第14页{if(X=='#'){if(X==w){printf(%8c是该文法的句子！\n,'');}elseerror();}else{p=location(X,