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

东南大学-编译原理-词法分析器实验报告词法分析设计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保存。struct token string name; string type; int attr; ; （2）本文的大多数数据结构都用map来保存，优点是查找方便，大大提高时间复杂度。 map Keywords; /保存关键字 map Sep; /保存界符map Relop; /保存比较运算符map Op; /保存其他运算符mapid; /保存输入字符串中的idmapnum; /保存数字vectorToken; /保存token序列，大小未知，所以采用vector保存6.核心算法描述（1）void addToken(string s,int type）s为找到的字符串，type为可能类型。 将分析出来的token()序列添加到Token序列表中。如果是类型为1，查看关键词表，若找到，其类型为关键词并将其以类型为关键词存储到Token表中；若未找到，则查找id表，若找到，说明该id已经出现过，否则添加新的id到id表中，将该i字符串以类型为id添加到Token表中。如果类型为2，在界符表中查找，如果找到以类型为界符存储到Token表中，同理其他几种类型。可能类型为1-5，如果出现其他类型表示是词法分析器中发现额错误，将错误信息记录下来。void addToken(string s,int type) switch(type)case 1: l_it=Keywords.find(s); if (l_it!=Keywords.end() token t=s,keywords,l_it-second; Token.push_back(t); elsel_it=id.find(s); if (l_it=id.end() ids=idNum; token t=s,id,idNum+; Token.push_back(t); else token t=s,id,l_it-second; Token.push_back(t); break;case 2:l_it=Sep.find(s); if (l_it!=Sep.end() token t=s,separatrix,l_it-second; Token.push_back(t); break;case 3:l_it=Op.find(s); if (l_it!=Op.end() token t=s,op,l_it-second; Token.push_back(t); break;case 4:l_it=Relop.find(s); if (l_it!=Relop.end() token t=s,relop,l_it-second; Token.push_back(t); break;case 5: l_it=num.find(s); if (l_it=num.end() nums=nNum; token t=s,num,nNum+; Token.push_back(t); else token t=s,num,l_it-second; Token.push_back(t); break; default: /error token t=s,id,-1; Token.push_back(t); break; （2） void lexical() 词法分析器，按字符读入文法并对其进行处理。从状态0开始处理，如果是空白符则一直在状态0，如果第一个字符为字母，继续往后寻找，直至不是字母或是数字结束；若第一个字符为数字，将其拼凑成一个数字，数字可以有小数点等，详细见状态转换图，注意以数字开头容易出现一种例如3a类型的错误，所以以数字开头的一定要往下多找一个，看最后一个数字后面是否为空白符或界符或者其他允许出现的符号，如果后面紧跟着字母则报错。如上同理分析运算符等。注意每次处理完遇到一个字符串都要将其送到addToken()添加到Token表中并回到状态0，继续往下处理。 void lexical()fstream ln(E:ln.txt); char ch,tempch; int state=0; string s=,key=; while(!ln.eof() switch(state) case 0: ch=ln.get(); s=ch; if (ch=13|ch=10|ch=32|ch=9) state=0; s=; else if (ch=) state=9;else if (isLetter(ch) state=13;else if (isDigit(ch) state=15; else if (ch=+|ch=-|ch=*|ch=/|ch=&|ch=|) state=20; tempch=ch; else if (ch=) state=44; else if (isSep(ch)!=-1) state=47;else if (isOp(s)!=-1) state=48; else if (isRelop(s)!=-1) state=49; else state=50; /error break; case 1: ch=ln.get(); if(ch=|ch=) state=2; else if(ch=) state=11; else state=12; break;case 10: s+=ch; addToken(s,4); state=0;break;case 11:s+=ch;addToken(s,3); state=0; break; case 12: /* state=0;addToken(s,4); ln.seekg(-1,ios:cur); break;case 13: ch=ln.get(); if(isDigit(ch)|isLetter(ch) s+=ch; else state=14; break; case 14: /* state=0;addToken(s,1); ln.seekg(-1,ios:cur);break;case 15: ch=ln.get(); if (isDigit(ch) s+=ch; else if (ch=.)s+=ch; state=16; else state=18; break; case 16: ch=ln.get(); s+=ch;if (isDigit(ch) state=17; else state=50; /error break;case 17: ch=ln.get(); if (isDigit(ch) s+=ch; state=17; else state=18; break; case 18: /* if (isLetter(ch) s+=ch; state=50; elseaddToken(s,5); ln.seekg(-1,ios:cur); state=0; break;case 20: ch=ln.get(); if(ch=tempch|ch=) state=21; else state=23; break;case 21: s+=ch; addToken(s,3); state=0; break; case 23:addToken(s,3); ln.seekg(-1,ios:cur); state=0; break; case 44: ch=ln.get(); if (ch=) state=45; else state=46; break;case 45: s+=ch; addToken(s,3); break; case 46:addToken(s,3); ln.seekg(-1,ios:cur); break;case 47:addToken(s,2); state=0; break; case 48:addToken(s,3); state=0;break; case 49: addToken(s,4); state=0; break; case 50: /error while(ch=ln.get()!=EOF) if(isSep(ch)!=-1|ch=13|ch=10|ch=32|ch=9) break; else s+=ch; addToken(s,6); /error ln.seekg(-1,ios:cur); state=0; break;default: break; 7.测试用例待测字符串：void fun() int a=2,b=3,3a; a+;b-; a+=b; b*=a; int c=a+4; int d=b*5; 产生结果在out.txt中（注意，无论输入输出文件都要保存在E盘根目录下） 8.出现的问题与解决方案 本实验的难点就是进行有效地进行状态如转换，先对每一个简单部分，如空白符、id、digit等画出自动机状态，然后由NFA-DFA，添加一个唯一的初始状态，产生式连接。再将DFA中等价的状态合并最后变成DFA0。这样便大大简化了代码量，也使得逻辑思维更加清晰。 9.自我体会 将理论运用到实际，不仅可以帮我们更好地复习理论知识，还可以让我们发发掘到一些更深刻层面上的东西。通过本次实验，我深入了解了词法分析的过程，对NFA,DFA,DFA0之间的转换也更能更加熟练地运用。这次实验还有许多需要加强的地方，比如还可以对id的类型进行明确分类，是函数还是变量，是什么类型的，返回类型是什么等等。之后有机会的话，我一定会更加深入的研究，将这个实验更加完善。