东南大学-编译原理-词法分析器实验报告

词法分析设计1.实验目的通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。2.实验内容用C++语言实现对C++语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。3.实验原理本次实验采用NFA-DFA-DFA0的过程:对待分析的简单的词法（关键词/id/num/运算符/空白符等）先分别建立自己的FA，然后将他们用产生式连接起来并设置一个唯一的开始符，终结符不合并。待分析的简单的词法（1）关键字：asm,auto,bool,break,case,catch,char,class,const,const_cast等（2）界符（查表）;,,,(,),[,],{,}（3）运算符*,/,%,+,-,,=,,&,^,|,++,--,+=,-=,*=,/=,%=,&=,^=,|=relop：（4）其他单词是标识符（ID）和整型常数（SUM），通过正规式定义。id/keywords:digit:（5）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。空白、制表符和换行符:4.相关自动机描述DFA:DFA0：5.流程图5.核心数据结构描述（1）生成的token序列由name、type、attr保存。structtoken{stringname;stringtype;intattr;};（2）本文的大多数数据结构都用map来保存，优点是查找方便，大大提高时间复杂度。mapstring,intKeywords;//保存关键字mapstring,intSep;//保存界符mapstring,intRelop;//保存比较运算符mapstring,intOp;//保存其他运算符mapstring,intid;//保存输入字符串中的idmapstring,intnum;//保存数字vectortokenToken;//保存token序列，大小未知，所以采用vector保存6.核心算法描述（1）voidaddToken(strings,inttype）s为找到的字符串，type为可能类型。将分析出来的token()序列添加到Token序列表中。如果是类型为1，查看关键词表，若找到，其类型为关键词并将其以类型为关键词存储到Token表中；若未找到，则查找id表，若找到，说明该id已经出现过，否则添加新的id到id表中，将该i字符串以类型为id添加到Token表中。如果类型为2，在界符表中查找，如果找到以类型为界符存储到Token表中，同理其他几种类型。可能类型为1--5，如果出现其他类型表示是词法分析器中发现额错误，将错误信息记录下来。voidaddToken(strings,inttype){switch(type){case1:l_it=Keywords.find(s);if(l_it!=Keywords.end()){tokent={s,keywords,l_it-second};Token.push_back(t);}else{l_it=id.find(s);if(l_it==id.end()){id[s]=idNum;tokent={s,id,idNum++};Token.push_back(t);}else{tokent={s,id,l_it-second};Token.push_back(t);}}break;case2:l_it=Sep.find(s);if(l_it!=Sep.end()){tokent={s,separatrix,l_it-second};Token.push_back(t);}break;case3:l_it=Op.find(s);if(l_it!=Op.end()){tokent={s,op,l_it-second};Token.push_back(t);}break;case4:l_it=Relop.find(s);if(l_it!=Relop.end()){tokent={s,relop,l_it-second};Token.push_back(t);}break;case5:l_it=num.find(s);if(l_it==num.end()){num[s]=nNum;tokent={s,num,nNum++};Token.push_back(t);}else{tokent={s,num,l_it-second};Token.push_back(t);}break;default://errortokent={s,id,-1};Token.push_back(t);break;}}（2）voidlexical()词法分析器，按字符读入文法并对其进行处理。从状态0开始处理，如果是空白符则一直在状态0，如果第一个字符为字母，继续往后寻找，直至不是字母或是数字结束；若第一个字符为数字，将其拼凑成一个数字，数字可以有小数点等，详细见状态转换图，注意以数字开头容易出现一种例如3a类型的错误，所以以数字开头的一定要往下多找一个，看最后一个数字后面是否为空白符或界符或者其他允许出现的符号，如果后面紧跟着字母则报错。如上同理分析运算符等。注意每次处理完遇到一个字符串都要将其送到addToken()添加到Token表中并回到状态0，继续往下处理。voidlexical(){fstreamln(E:\ln.txt);charch,tempch;intstate=0;strings=,key=;while(!ln.eof()){switch(state){case0:ch=ln.get();s=ch;if(ch==13||ch==10||ch==32||ch==9){state=0;s=;}elseif(ch=='')state=1;elseif(ch=='=')state=6;elseif(ch=='')state=9;elseif(isLetter(ch))state=13;elseif(isDigit(ch))state=15;elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='&'||ch=='|'){state=20;tempch=ch;}elseif(ch=='^')state=44;elseif(isSep(ch)!=-1)state=47;elseif(isOp(s)!=-1)state=48;elseif(isRelop(s)!=-1)state=49;elsestate=50;//errorbreak;case1:ch=ln.get();if(ch=='='||ch=='')state=2;elseif(ch=='')state=4;elsestate=5;break;case2:s+=ch;addToken(s,4);state=0;break;case4:s+=ch;addToken(s,3);state=0;break;case5://*addToken(s,4);ln.seekg(-1,ios::cur);state=0;break;case6:ch=ln.get();if(ch=='=')state=7;elsestate=8;break;case7:s+=ch;addToken(s,4);state=0;break;case8://*addToken(s,3);ln.seekg(-1,ios::cur);state=0;break;case9:ch=ln.get();if(ch=='=')state=10;elseif(ch=='')state=11;elsestate=12;break;case10:s+=ch;addToken(s,4);state=0;break;case11:s+=ch;addToken(s,3);state=0;break;case12://*state=0;addToken(s,4);ln.seekg(-1,ios::cur);break;case13:ch=ln.get();if(isDigit(ch)||isLetter(ch))s+=ch;elsestate=14;break;case14://*state=0;addToken(s,1);ln.seekg(-1,ios::cur);break;case15:ch=ln.get();if(isDigit(ch))s+=ch;elseif(ch=='.'){s+=ch;state=16;}elsestate=18;break;case16:ch=ln.get();s+=ch;if(isDigit(ch))state=17;elsestate=50;//errorbreak;case17:ch=ln.get();if(isDigit(ch)){s+=ch;state=17;}elsestate=18;break;case18://*if(isLetter(ch)){s+=ch;state=50;}else{addToken(s,5);ln.seekg(-1,ios::cur);state=0;}break;case20:ch=ln.get();if(ch==tempch||ch=='=')state=21;elsestate=23;break;case21:s+=ch;addToken(s,3);state=0;break;case23:addToken(s,3);ln.seekg(-1,ios::cur);state=0;break;case44:ch=ln.get();if(ch=='=')state=45;elsestate=46;break;case45:s+=ch;addToken(s,3);break;case46:addToken(s,3);ln.seekg(-1,ios::cur);break;case47:addToken(s,2);state=0;break;case48:addToken(s,3);state=0;break;case49:addToken(s,4);state=0;break;case50://errorwhile((ch=ln.get())!=EOF){if(isSep(ch)!=-1||ch==13||ch==10||ch==32||ch==9)break;elses+=ch;}addToken(s,6);//errorln.seekg(-1,ios::cur);state=0;break;default:break;}}}7.测试用例待测字符串：voidfun(){inta=2,b=3,3a;a++;b--;a+=b;b*=a;intc=a+4;intd=b*5;}产生结果在out.txt中（注意，无论输入输出文件都要保存在E盘根目录下）8.出现的问题与解决方案本实验的难点就是进行有效地进行状态如转换，先对每一个简单部分，如空白符、id、digit等画出自动机状态，然后由NFA-DFA，添加一个唯一的初始状态，产生式连接。再将DFA中等价的状态合并最后变成DFA0。这样便大大简化了代码量，也使得逻辑思维更加清晰。9.自我体会将理论运用到实际，不仅可以帮我们更好地复习理论知识，还可以让我们发发掘到一些更深刻层面上的东西。通过本次实验，我深入了解了词法分析的过程，对NFA,DFA,DFA0之间的转换也更能更加熟练地运用。这次实验还有许多需要加强的地方，比如还可以对id的类型进行明确分类，是函数还是变量，是什么类型的，返回类型是什么等等。之后有机会的话，我一定会更加深入的研究，将这个实验更加完善。