词法分析设计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<string,int> Keywords; //保存关键字map<string,int> Sep; //保存界符map<string,int> Relop; //保存比较运算符map<string,int> Op; //保存其他运算符map<string,int>id; //保存输入字符串中的idmap<string,int>num; //保存数字vector<token>Token; //保存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);}else{l_it=id.find(s);if (l_it==id.end()){id[s]=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()){num[s]=nNum;token t={s,"num",nNum++};Token.push_back(t);}else {token t={s,"num",l_it->second};Token.push_back(t);}break;default: //errortoken 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=1;else if (ch=='=') state=6;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; //errorbreak;case 1: ch=ln.get();if(ch=='='||ch=='>') state=2;else if(ch=='<') state=4;else state=5;break;case 2:s+=ch;addToken(s,4);state=0;break;case 4:s+=ch;addToken(s,3);state=0;break;case 5: //* addToken(s,4);ln.seekg(-1,ios::cur);state=0;break;case 6: ch=ln.get();if(ch=='=') state=7;else state=8;break;case 7:s+=ch;addToken(s,4);state=0;break;case 8: //* addToken(s,3);ln.seekg(-1,ios::cur);state=0;break;case 9: ch=ln.get();if(ch=='=') state=10;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;}else{addToken(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);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: //errorwhile((ch=ln.get())!=EOF){if(isSep(ch)!=-1||ch==13||ch==10||ch==32||ch==9) break;else s+=ch;}addToken(s,6); //errorstate=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 ，添加一个唯一的初始状态，产生式连接。