词法分析器及其算法的设计与实现2015年11月11日星期三班级：13级软件工程学号： E21314003 姓名：李世（一）.词法分析器的设计 1.1 目的与要求通过设计、编写和调试词法分析程序（又称扫描器），了解扫描器的组成结构，不同种类单词的识别方法，掌握由单词的词法规则出发，画出识别单词的状态转换图，然后再用程序实现的扫描器的设计方法。
1.2 词法分析器实现中的约定设计的扫描器可以是一个子程序，也可以是一个完整的程序，其输入是源程序字符串，输出是单词符号本身。
为简化编译程序的编写过程，对Simple 语言源程序的书写，可以做如下假定：(1) 假定Simple 语言采用自由格式书写；(2) 可以使用注释，用/*……*/或者//标识，但注释不能插在单词内部，注释要在一行内结束。
若在某一行的结束，没有遇到注释后面的结束标记，自动认为注释结束； (3) 一行可以有多个语句，一个语句也可以分布在多个行中，单词之间、语句之间可以插入任意空格，但单词中间不能有空格符号，单词中间也不能有回车换行符，即单词不能跨行书写；(4) 为了避免超前搜索、提高运行效率，假定关键字都是保留字。
(5) 1.3 词法分析器的总体设计(6) 词法分析器的功能时从源程序中读入一个个字符，依据一定的构词规则，识别出各类有用的单词。
图1为词法分析器的输入输出接口：对图1细化，可得词法分析程序的顶层数据流图，如图2所示：图1. 词法分析器的输入输出接口细化图2可得词法分析程序的详细数据流图：在词法分析程序的详细数据流图中，各个加工处理模块完成的功能如下：1.1读一行并显示：收到读下一行的命令后，从源程序读入一行，装入缓冲区buffer ，行计数器加1，并打印。
需要注意的是，回车换行在源程序（文本文件）中用两个字符0D 0A H 来表示,而用高级语言（C 语言）读入内存后，就用一个字符0AH 来表示，这是在用高级语言编写词法分析器时常被忽略而导致错误的原因。
1.2 读一非空字符：收到读入一个字符的命令后，从缓冲区读入一非空字符（空格的ASCII码为20H ），列计数器加1.若buffer 已空，则在读入一行，类计数器置0. 1.3 分类：根据单词的首字符决定对不同单词的处理。
1.4 识别标识符/关键字：当读入一个字母时，开始识别标识符和关键字，边拼写边从buffer 中读入下一个符号。
当读入一非字母、数字符号时，标识符识别已经完成。
但已经多读入一个符号，所以列图3. 词法分析程序的详细数据流图图2. 词法分析程序的顶层数据流图计数回退，减1。
然后查关键字表，判断拼出的符号串是否为关键字。
若是关键字，输出其种别码（token）；否则识别的单词就是标识符，同时输出标识符及其种别码。
1.5 识别数值常数：当读入数字时，开始识别整数或实数。
边拼写边读入下一个符号，当遇到“.”时，还要继续拼写该常数（实数情况）。
如果遇到E或e，要识别带指数的常数。
如果遇到其他非数字符号时，数字常数识别完毕。
输出常数及其种别码。
1.6 处理注释/除号：当读入“/”时，开始识别注释或除号。
若是注释（“/*”）时，最后两个连续读入的符号应是“*/”，不再读入下一符号，列计数器不变。
当判定是除号“/”时，已多读入一个字符，列计算器减1，输出除号“/”的种别码。
同样可识别注释符号//。
1.7 识别界符和运算符识别其他界符，对于<、>、：等符号，还需要再读入下一个符号，判断是否为双界符。
若不是，列计数器减1，输出单词的种别码。
1.8 识别文字常数：当读入单引号时，忽略它，开始拼写字符常数，不断读入下一个符号，搜索下一个单引号，当读入下一个单引号时，字符常数拼写结束。
最后列计数器不减1，然后输出该常数。
注：以上加工1.4~1.8都需要从buffer中每次读入一个字符，进行列计数。
由于假定每个单词不跨行，所以不用考虑从源程序中读出下一行到缓冲区的功能。
1.9 输出token：对于各种界符与关键字输出其在编译器的内部表示形式（token），对常数与标识符则让它流入下一个加工。
2 查填符号表：如果是标识符或常数，首先查看名字栏和类型栏（字符常数的类型栏中填有“字符常数”，标识符的类型栏空白），判断有无同名和同类型的入口。
如果有同名入口P1，则把P1作为token的自身值填入它的二元式；如果不同名，则将字符串存入符号表中，把它的长度和在字符串表中的开始位置及其类型（标识符为空白）填入符号表的新入口P中，并把P作为token的自身值填入二元式中。
对数值常数的处理是：先查符号表的val栏，若发现相同的常数则直接输出其二元式。
若表内无相同的常数，则将数值常数填入表内，在type栏内填入整型或实型，然后输出其二元式。
二元式包含该常数在符号表中的入口。
1.4 词法分析程序的详细设计将图3的词法分析程序的详细数据流图，可以得到词法分析程序的总体框架。
词法分析器的输出：（1）源文件的token表（系统单词出现几次就输出几次）(2) 源文件的符号表（二）Simple语言的定义Simple语言是一种类PASCAL语言，它以赋值语句为基础，包括顺序、条件和循环三种结构。
有变量说明和常量说明，有多种数据类型：整型、实型、字符型等。
它包括以下语法成份：（1）数据类型：整型、布尔型、实型、和字符型。
（2）表达式：可以进行算术、布尔表达式的运算。
（3）说明语句：常量说明（用const定义）、变量说明（用var定义）。
（4）赋值语句。
（5）控制语句：if语句、while语句、repeat语句、和for循环语句。
（6）begin……end复合语句。
（7）程序（program）语句与结束（end）语句。
Simple语言的语法定义如下：1. Simple语言字符集的定义：(1)<字符集> ::= <字母>︱<数字>︱<单界符>(2)<字母> ::= a︱b︱c︱……︱z︱A︱B︱C︱……︱Z(3)<数字> ::= 0︱1︱2︱……︱9(4)<单界符> ::= +︱-︱*︱/︱=︱<︱>︱(︱)︱{︱}︱:︱;︱,︱‟︱_︱.note: 不在该字符集范围内的其他字符视为非法字符。
2. Sample 语言词法定义(1)<单词>::= <保留字>︱<双界符>︱<标识符>︱<常数>︱<单界符>(2)<保留字>::= and︱begin︱bool︱case︱char︱const︱do︱else︱and︱false︱for︱if︱input︱integer︱not︱of︱or︱output︱program︱read︱real︱repeat︱then︱to︱true︱until︱var︱while︱write(3)<双界符>::= /*︱*/︱<=︱>=︱<>︱:=︱//(4)<标识符>::= <字母>︱<标识符><数字>︱<标识符><字母>(5)<常数>::= <整数>︱<布尔常数>︱<字符常数>︱<常数标识符>︱<实数>(6)<整数>::= <无符号整数>︱+<无符号整数>︱-<无符号整数>(7)<无符号整数>::= <数字>︱<无符号整数><数字>(8)<布尔常数>::= true︱false(9)<字符常数>::= 除…‟以外的任意字符串(10)<常数标识符>::= <标识符>(11)<实数>::= <小数>︱<指数>(12)<小数>::= <整数>.<无符号整数>︱<整数>(13)<指数>::= <小数>E<整数>︱<小数>e<整数>3. Sample语言数据类型的定义<简单类型>::= integer︱bool︱char︱real4.Sample语言表达式的定义(1)<表达式>::= <算术表达式>︱<布尔表达式>(2)<算术表达式>::= <项>+<算术表达式>︱+<项>︱<项>(3)<项>::= <项>*<因子>︱<项>/<因子>︱<因子>(4)<因子>::= <算术量>(5)<算术量>::= <标识符>︱<整数>︱<实数>(6)<布尔表达式>::= <布尔项>or<布尔表达式>︱<布尔项>(7)<布尔项>::= <布尔因子>and<布尔项>︱<布尔因子>(8)<布尔因子>::= <布尔量>︱not<布尔因子>(9)<布尔量>::= <布尔表达式>︱<布尔常数>︱<标识符>︱<算术表达式><关系符><算术表达式>(10)<关系符>::= <︱>︱<>︱<=︱>=︱=5. Sample语言语句的定义(1)<语句>::= <说明语句>︱<执行语句>(2)<说明语句>::= <常量说明><变量说明>(3)<常量说明>::= const<常数定义>︱ε(4)<常数定义>::= <标识符>=<常数><常数定义>︱<标识符>=<常数>;(5)<变量说明>::= var<变量定义>︱ε(6)<变量定义>::= <标识符表>:<简单类型>;︱<标识符表>:<简单类型><变量定义>;(7)<标识符表>::= <标识符>,<标识符表>︱<标识符>(8)<执行语句>::= <简单句>︱<结构句>(9)<简单句>::= <赋值句>(10)<赋值句>::= <变量>:=<表达式>(11)<变量>::= <标识符>(12)<结构句>::= <复合句>︱<if语句>︱<while语句>︱<for语句>︱<repeat语句>(13)<复合句>::= begin<语句表>end(14)<语句表>::= <执行语句>；<语句表>︱<执行语句>(15)<if语句>::= if<布尔表达式>then<执行语句>(16)<if语句>::= if<布尔表达式>then<执行语句1>︱else<执行语句2>(17)<while语句>::= while<布尔表达式>do<执行语句>(18)<for语句>::= for<标识符>:=<算术表达式1>to<算术表达式2>do<执行语句>(19)<repeat语句>::= repeat<执行语句>until<布尔表达式>6.Sample语言程序的定义(1)<程序>::=program<标识符>；<分程序>(2)<分程序>::= <常量说明><变量说明><符合句>.（三）.调试运行结果（四）.实验源代码：#include<iostream>#include<string>#include<iomanip>#include"fstream"#include"sstream"using namespace std;int n;int k=0;string s[200];string h[49]={"and","begin","bool","case","char","const","do","else","end","false","for","if","input","integer","not","of","or","output","program","read","real","repeat","then","to","true","until","var","while","write","+","-","*","/","<",">","<=",">=","<>","=",":=",";",",","'",":","/*","*/","//","(",")"};struct ji1{int hang;int token;string name;string type;}p[200];struct ji2{int hang1[10];int token1;string name1;string type1;int m;}q[200];void text()//导入程序，并存储在字符串数组中{cout<<"请输入程序行数";cin>>n;ifstream a("D:\\123.txt");inti = 0;for(i;i<n;i++){getline(a,s[i]);cout<<s[i]<<endl;}}void panbie1(string a)//对字符串进行判断{int flag=0;for(inti=0;i<29;i++){if(a==h[i]){p[k].token=i+1;p[k].type="关键字";k++;flag=1;}}if(a.length()==1){p[k].token=56;p[k].type="标识符";k++;}if((a.length()>1)&&(flag==0)){p[k].token=55;p[k].type="id";k++;}}void panbie2(string a)//对符号进行判断{for(inti=29;i<39;i++){if(a==h[i]){p[k].token=i+1;p[k].type="运算符";k++;}}for(i=39;i<49;i++){if(a==h[i]){p[k].token=i+1;p[k].type="界符";k++;}}}void huafen()//对一行程序进行划分，并进行简单判断{inti=0,flag=0;string a;for(i;i<n;i++){for(int j=0;j<s[i].length();j++){if(s[i][j]==32||s[i][j]==0)continue;if((s[i][j]<='z')&&(s[i][j]>='a')){a=a+s[i][j];if(s[i][j+1]<'a'||s[i][j+1]>'z'){p[k].name=a;p[k].hang=i+1;panbie1(a);a="";}}if((s[i][j]<='9')&&(s[i][j]>='0')){a=a+s[i][j];if(s[i][j+1]<'0'||s[i][j+1]>'9'||(s[i][j+1]==32)){p[k].type="整常数";p[k].token=51;p[k].name=a;p[k].hang=i+1;k++;a="";}}if(((s[i][j]>'z')||(s[i][j]<'a'))&&((s[i][j]>'9')||(s[i][j]<'0'))){a=a+s[i][j];if(((s[i][j+1]<='z')&&(s[i][j+1]>='a'))||((s[i][j+1]<='9')&&(s[i][j+1]>='0'))||(s[i][j+1]==32)||(s[i][j+1]==0)) {p[k].name=a;p[k].hang=i+1;panbie2(a);a="";flag=1;}if((a.length()==1)&&(flag==0)){if((s[i][j]=='<')&&(s[i][j+1]=='='))continue;else if((s[i][j]=='<')&&(s[i][j+1]=='>'))continue;else if((s[i][j]=='>')&&(s[i][j+1]=='='))continue;else if((s[i][j]=='*')&&(s[i][j+1]=='/'))continue;else if((s[i][j]=='/')&&(s[i][j+1]=='*'))continue;else if((s[i][j]=='/')&&(s[i][j+1]=='/'))continue;else if((s[i][j]==':')&&(s[i][j+1]=='='))continue;else{p[k].name=a;p[k].hang=i+1;panbie2(a);a="";}}if(a.length()==2){p[k].hang=i+1;panbie2(a);a="";}}flag=0;}}}void display()//显示token表{cout<<"-------------------------------token表-------------------------------"<<endl;cout<<"所在行数"<<" 单词本身"<<" token码"<<" 类型"<<endl;for(inti=0;i<k;i++){cout<<" "<<p[i].hang<<" ";cout<<p[i].name<<" ";cout<<p[i].token<<" ";cout<<p[i].type<<" ";cout<<endl;}cout<<"-------------------------------------------------------------------"<<endl<<endl;}int change()//将token表转换为符号表{inti=0,j=0,l,flag=0;for(i;i<200;i++)q[i].m=1;for(i=0;i<k;i++){for(l=0;l<j+1;l++){if(p[i].name!=q[l].name1)flag++;else{q[l].hang1[q[l].m]=p[i].hang;q[l].m++;break;}if(flag==j+1){q[j].token1=p[i].token;q[j].type1=p[i].type;q[j].hang1[0]=p[i].hang;j++;break;}}flag=0;}return j;}void display1()//显示符号表{cout<<"-------------------------------符号表-------------------------------"<<endl;int j=change(),g;cout<<"行号"<<"单词本身"<<" token码"<<" 类型"<<" 引用信息"<<endl;for(inti=0;i<j;i++){cout<<q[i].hang1[0]<<" ";cout<<q[i].name1<<" ";cout<<q[i].token1<<" ";cout<<q[i].type1<<" ";for(g=1;g<q[i].m;g++){cout<<q[i].hang1[g]<<" ";}cout<<endl;}cout<<"--------------------------------------------------------------------"<<endl;}void main(){cout<<"*****************************欢迎使用!******************************"<<endl; cout<<"* 词法分析器及其算法的设计与实现*"<<endl;cout<<"* 作者：李世13级软件工程E21314003 *"<<endl;cout<<"********************************************************************"<<endl;text();huafen();display();display1();cout<<"***************************欢迎再次使用!****************************"<<endl; }。