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

可编辑版/词法分析设计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界符〔查表";",",","<",">","[","]","{","}"运算符"*","/","%","+","-","<<","=",">>","&","^","|","++","--","+=","-=","*=","/=","%=","&=","^=","|="relop：其他单词是标识符〔ID和整型常数〔SUM,通过正规式定义。id/keywords:digit:空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字,词法分析阶段通常被忽略。空白、制表符和换行符:4. 相关自动机描述DFA:DFA0：流程图5. 核心数据结构描述〔1生成的token序列由name、type、attr保存。structtoken{ stringname; stringtype;intattr;};〔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. 核心算法描述〔1voidaddToken<strings,inttypes为找到的字符串,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://error tokent={s,"id",-1}; Token.push_back<t>;break; }}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;