C语言语法分析器

郑州轻工业学院编译原理课程设计总结报告设计题目：词法分析器（语法分析器）学生姓名：系别：专业：班级：学号：指导教师：20013年6月2日目录设计题目………3运行环境（软、硬件环境）……3算法设计的思想………………3算法流程图……………………5算法设计分析…………………5六、源代码…………6七、运行结果……………………11八、收获及体会……………………12（一）设计题目词法分析器（二）运行环境VisualC++.6.0(三)算法设计的思想源程序源程序词法分析器Token串各种单词符号对应的种别码:单词符号种别码单词符号种别码begin1:17if2:=18then3<20while4<>21do5<=22end6>23letter(letter|digit)*10>=24digitdigit*11=25+13(26-14)27*15;28/16#0算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。主程序示意图：主程序示意图如下；其中初值包括如下两个方面：关键字表的初值。关键字作为特殊标示符处理，把它们预先安排到一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如果能查到匹配的单词，则该单词为关键字，否则为一般的标识符。关键字表为一个字符串数组，其描述如下：Char*rwtab[6]={“begin”,”if”,”then”,”while”,”do”,”end”};置初值调用扫描子程序调用扫描子程序输出单词二元组输出单词二元组输入串结束？否输入串结束？是结束结束(2)程序需要用到的主要变量为syn,token和sum。2．扫描子程序的算法思想首先设置3个变量：（1）token用来存放构成单词符号的字符串；（2）sum用来存放整型单词（3）syn用来存放单词符号的种别码。main（四）算法的流程图main变量初始化变量初始化忽略空格忽略空格结束文件结束否结束文件结束否否拼字符串 其它字符拼字符串对不同符号给出相应的syn值是否是关键字 数字对不同符号给出相应的syn值是否是关键字报错拼数报错拼数syn为对应单词的种别码syn=10syn=11syn为对应单词的种别码syn=10syn=11结束 结束（五）算法设计分析算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。其中初值包括如下两个方面：（一）关键字表的初值。关键字作为特殊标示符处理，把它们预先安排到一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如果能查到匹配的单词，则该单词为关键字，否则为一般的标识符。关键字表为一个字符串数组，其描述如下：Char*rwtab[6]={“begin”,”if”,”then”,”while”,”do”,”end”};(2)程序需要用到的主要变量为syn,token和sum。2．扫描子程序的算法思想首先设置3个变量：（1）token用来存放构成单词符号的字符串；（2）sum用来存放整型单词（3）syn用来存放单词符号的种别码。（六）源代码#include<stdio.h>#include<iostream.h>#include<string.h>#defineMAX150//词法分析表的最大容量#defineMAXBUF255//缓冲区的最大缓冲量charprog[MAXBUF],token[MAX];charch;intsyn,p,m,n,sum;char*rwtab[6]={"begin","if","then","while","do","end"};/////////////////////////////////////////////////词法分析程序///////////////////////////////////////////////voidscaner(){ for(m=0;m<MAX;m++) token[m]=NULL; m=0;sum=0; ch=prog[p++]; while(ch=='') ch=prog[p++];//读取下一个字符; if(ch>=65&&ch<=122/*是字母字符*/) { while(ch>=65&&ch<=122||ch>=48&&ch<=57)/*为字母字符或数字字符*/ { token[m++]=ch; ch=prog[p++];//读取下一个字符； } token[m++]='\0'; p=p-1; syn=10; for(n=0;n<6;n++) if(strcmp(token,rwtab[n])==0) { syn=n+1;//给出syn值; break; } } elseif(ch>=48&&ch<=57/*ch为数字字符*/) { while(ch>=48&&ch<=57/*ch为数字字符*/) { sum=sum*10+ch-'0'; ch=prog[p++];//读取下一个字符； } p=p-1;//回退一个字符； syn=11; } elseswitch(ch) {case'<':m=0;token[m++]=ch; ch=prog[p++];//读取下一个字符； if(ch=='>') { syn=21; token[m++]=ch; } elseif(ch=='=') { syn=22; token[m++]=ch; } else { syn=20; p=p-1;//回退一个字符； } break; case'>':token[m++]=ch;; ch=prog[p++];//读取下一个字符； if(ch=='=') { syn=24;//将>=的中别码=>syn; token[m++]=ch;; } else { syn=23; p=p-1;//回退一个字符； } break; case':':token[m++]=ch;; ch=prog[p++];//读取下一个字符； if(ch=='=') { syn=18; token[m++]=ch;; } else { syn=17; p=p-1;//回退一个字符； } break; case'+':syn=13;token[0]=ch; break; case'-':syn=14;token[0]=ch; break; case'*':syn=15;token[0]=ch; break; case'/':syn=16;token[0]=ch; break; case'=':syn=25;token[0]=ch; break; case';':syn=26;token[0]=ch; break; case'(':syn=27;token[0]=ch; break; case')':syn=28;token[0]=ch; break; case'#':syn=0;token[0]=ch; break; default:syn=-1; break; }}/////////////////////////////////////////////主函数///////////////////////////////////////////voidmain(){ charA; cout<<"*****************************************"<<endl; loop: p=0; cout<<"*****************************************"<<endl;printf("pleaseinputstring(以#结束):\n"); do { scanf("%c",&ch); prog[p++]=ch;//输入源程序字符串，送到缓冲区prog[p++]中； } while(ch!='#'); p=0; do { scaner(); switch(syn) { case11:cout<<"("<<syn<<","<<sum<<")"<<endl;//输出（数的二元组）； break; case-1:cout<<"error"<<endl; break; default:cout<<"("<<syn<<","<<token<<")"<<endl;//输出(其他单词二元组); } }while(syn!=0); cout<<"*****************************************"<<endl; cout<<"请确定是否继续使用程序:S为继续；其它为退出；"<<endl; cout<<"是否继续:"; cin>>A; switch(A) { case'S':gotoloop; default:cout<<"*****************************************"<<endl; cout<<"Thankyou!ByeBye!"<<endl; cout<<"*****************************************"<<endl; break; }}（七）运行结果分析（八）收获及体会为期一周的编译原理课程设计结束了，我们这次的任务是做一个编译器。这次课程设计我做的是用C++编写词法分析器，编译程序是在单词的级别上来分析和翻译源程序的，因此词法分析是编译的基础。通过此次实验，我基本上了解了词法分析器的工作原理和功能以及实现方法。进一步学习了C语言的知识。此次实验，遇到的最大的一个问题就是用了C++语言里的cin输入字符串，结果空格符号直接给预处理掉了，导致开始的关键字与字母连接时会不识别，最后通过查阅，终于找到了这个问题的所在，最后通过C语言里的Scanf函数来输入，就解决了这个问题。总而言之，本程序实现了所要求的全部功能。美中不足的是程序中没有运用文件，对文件的掌握不是很到位，相信经过以后的程序训练，会熟练的运用文件来编程。目录一、设计题目………14二、运行环境（软、硬件环境）…………………14三、算法设计的思想………………14四、算法流程图……………………15五、算法设计分析…………………16六、源代码…………17七、运行结果……………………26八、收获及体会……………………27（一）设计题目语法分析器（二）运行环境VisualC++.6.0(三)算法设计的思想利用C语言编制递归下降分析程序，并对简单语言进行语法分析。待分析的简单语言得语法：EE+T|E-T|TTT*F|T/F|F

F(E)|i输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“Accept!RightExpression!”，否则输出“Error!!!”。（四）算法的流程图（五）算法设计分析语法分析：a)∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。用直接改写法消除左递归，得到如下：ETE’E’+TE’|−TE’|εTFT’T’*FT’|/FT’|εF(E)|ib)对于以上改进的方法。可得：对于E’:

FIRST(E’)=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，−，ε}对于T’: FIRST(T’)=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε}而且： FIRST(E)=FIRST(T)=FIRST(F)=FIRST((E))∪FIRST(i)={(，i}由此我们容易得出各非终结符的FOLLOW集合如下：FOLLOW(E)={)，#}FOLLOW(E’)=FOLLOW(E)={)，#}FOLLOW(T)=FIRST(E’)\ε∪FOLLOW(E’)={+，−，)，#}FOLLOW(T’)=FOLLOW(T)={+，−，)，#}FOLLOW(F)=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，−，)，#}由以上FOLLOW集可以我们可以得出SELECT集如下：对E SELECT（ETE’）=FIRST(TE’)=FIRST(T)={(，i}对E’ SELECT（E’+TE’）={+}

SELECT（E’−TE’）={−}

SELECT（E’ε）={ε，)，#}对T SELECT（TFT’）={(，i}对T’ SELECT（T’*FT’）={*}SELECT（T’∕FT’）={∕}SELECT（T’ε）={ε，+，−，)，#}对F SELECT（F(E)）={(}SELECT（Fi）={i}∴ SELECT(E’+TE’)∩SELECT（E’−TE’）∩SELECT（E’ε）=SELECT(T’*FT’)∩SELECT（T’∕FT’）∩SELECT（T’ε）=SELECT（F(E)）∩SELECT（Fi）=由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。（六）源代码#include<stdio.h>#include<dos.h>#include<stdlib.h>#include<string.h>chara[50],b[50],d[200],e[10];charch;intn1,i1=0,flag=1,n=5;inttotal=0;intE();intE1();intT();intG();intS();intF();voidinput();voidinput1();voidoutput();voidmain()/*递归分析*/{intf,p,j=0;charx;d[0]='E';d[1]='=';d[2]='>';d[3]='T';d[4]='G';d[5]='#';printf("Pleaseinputcharacterstring(length<50,endof'#'):\n");do{scanf("%c",&ch);a[j]=ch;j++;}while(ch!='#');n1=j;ch=b[0]=a[0];printf("步骤\t文法\t分析串\t\t分析字符\t剩余串\n");f=E1();if(f==0)return;if(ch=='#'){printf("\nAccept!RightExpression!\n\n");p=0;x=d[p];while(x!='#'){printf("%c",x);p=p+1;x=d[p];/*输出推导式*/}}else{printf("\nError!!!\n");printf("回车返回\n");getchar();getchar();return;}printf("\n");printf("回车返回\n");getchar();getchar();}intE1(){intf,t;printf("%d\tE-->TG\t",total);total++;flag=1;input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);}intE(){intf,t;printf("%d\tE-->TG\t",total);total++;e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#';output();flag=1;input();input1();f=T();if(f==0)return(0);t=G();if(t==0)return(0);elsereturn(1);intT(){intf,t;printf("%d\tT-->FS\t",total);total++;e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#';output();flag=1;input();input1();f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}intG(){intf;if(ch=='+'){b[i1]=ch;printf("%d\tG-->+TG\t",total);total++;e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=T();if(f==0)return(0);G();return(1);}printf("%d\tG-->^\t",total);total++;e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';output();flag=1;input();input1();return(1);}intS(){intf,t;if(ch=='*'){b[i1]=ch;printf("%d\tS-->*FS\t",total);total++;e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=F();if(f==0)return(0);t=S();if(t==0)return(0);elsereturn(1);}printf("%d\tS-->^\t",total);total++;e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';output();flag=1;a[i1]=ch;input();input1();return(1);}intF(){intf;if(ch=='('){b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';output();flag=0;input();input1();ch=a[++i1];f=E();if(f==0)return(0);if(ch==')'){b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;flag=0;input();input1();ch=a[++i1];}else{printf("\nError!!!\n");return(0);}}elseif(ch=='i'){b[i1]=ch;printf("%d\tF-->i\t",total);total++;e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';output();flag=0;input();input1();ch=a[++i1];}else{printf("\nError!!!\n");return(0);}return(1);}voidinput(){intj=0;