@TOC
一、词法分析简介
词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。
词法分析是编译程序的第一个阶段且是必要阶段；词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；实现词法分析程序的常用途径:自动生成,手工生成。
完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。
从左至右地对源程序进行扫描，按照语言的词法规则识别各类单词，并产生相应单词的属性字。
二、设计要求
创建一个词法分析程序，它支持对正规文法的分析。必须使用DFA（确定性有限自动机）或NFA（非确定性有限自动机）来实现这一项目。该程序的输入是一个文本文件，包括一组由该正规文法产生的产生式以及待识别源代码字符串。该程序的输出是一个符号表（二元式），它由5种类型符号：关键词，识别符，常量，界符和操作符。
三、开发环境
硬件环境：PC机 windows10 64 位
编程语言：C++
运行环境：codeblocks或vs
四、实现过程
用子集法将NFA转化为DFA。具体实现是：做一个NFA_set类型的栈，新状态不停的进栈，每次从堆栈中弹出一个，计算其转换的结果，是新状态就进栈，重复则丢弃，只记录好dfa的转换，直到栈空。最后成功构造出DFA。
对输入源程序的扫描过程很简单，一次读入一个字符，成串的送入匹配和DFA判断其合法性。给出输出结果。
五、分析过程框架图
在这里插入图片描述
六、运行结果
识别程序的一部分输出结果：
在这里插入图片描述
对应的用于语法分析的部分输入：
在这里插入图片描述
七、部分核心代码
void NFA_to_DFA() { num_new_set=0; NFA_set work_set; NFA_set worked_set; work_set.set[work_set.len++]=start; worked_set.len=0; stack<NFA_set> s; get_closure(work_set); s.push(work_set); new_set[num_new_set++]=work_set; for(int i=0;i<150;++i) { for(int j=0;j<150;++j) { dfa[i][j]='-1'; } } for(int i=0;i<150;++i) is_final[i]=false; if(Is_contained_Y(work_set)) is_final[num_new_set-1]=true; while(!s.empty()) { work_set=s.top(); s.pop(); for(int i=0;i<len_final;++i) { for(int j=0;j<work_set.len;++j) { for(int k=0;k<move[work_set.set[j]][final[i]].len;++k) { if(move[work_set.set[j]][final[i]].set[k]!='#' && move[work_set.set[j]][final[i]].set[k]!='Y' && !Is_in_set(move[work_set.set[j]][final[i]].set[k],worked_set)) { worked_set.set[worked_set.len++]=move[work_set.set[j]][final[i]].set[k]; } if(move[work_set.set[j]][final[i]].set[k]=='Y' && !Is_in_set(move[work_set.set[j]][final[i]].set[k],worked_set)) { worked_set.set[worked_set.len++]='Y'; //用Y表示终态 } } } get_closure(worked_set); if(worked_set.len>0 && Is_in(worked_set)==-1) { dfa[num_new_set-1][final[i]]=num_new_set; s.push(worked_set); new_set[num_new_set++]=worked_set; if(Is_contained_Y(worked_set)) { is_final[num_new_set-1]=true; } } if(worked_set.len>0 && Is_in(worked_set)>-1 && final[i]!='@') { dfa[Is_in(work_set)][final[i]]=Is_in(worked_set); } worked_set.len=0; } } }
