一、实验目的

了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA编写通用的词法分析程序。（选做）

二、实验内容

1．根据状态转换图直接编程

编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。

具体任务有：
（1）组织源程序的输入
（2）识别单词的类别并记录类别编号和值，形成二元式输出，得到单词流文件
（3）删除注释、空格和无用符号
（4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。
（5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。
标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址
注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。
常量表结构：常量名，常量值

2．编写DFA模拟程序（选做）

算法如下：
DFA（S=S0,MOVE[ ][ ],F[ ],ALPHABET[ ]）
/S为状态，初值为DFA的初态，MOVE[ ][ ]为状态转换矩阵，F[ ] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[ ][ ] 中列标题的字母顺序一致。/
{
Char Wordbuffer[10]=“”//单词缓冲区置空
Nextchar=getchar（）；//读
i=0；
while（nextchar！=NULL）//NULL代表此类单词
{ if （nextchar！∈ALPHABET[]） {ERROR（“非法字符”），return（“非法字符”）；}
S=MOVE[S][nextchar] //下一状态
if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误
wordbuffer[i]=nextchar ； //保存单词符号
i++；
nextchar=getchar（）；
}
Wordbuffer[i]=‘\0’;
If（S∈F）return（wordbuffer）； //接受
Else return（“不接受”）；
}
该算法要求：实现DFA算法，给定一个DFA（初态、状态转换矩阵、终态集、字母表），调用DFA（），识别给定源程序中的单词，查看结果是否正确。

三、实验要求

1．能对任何S语言源程序进行分析（S语言定义见下面）

在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。

2．能检查并处理某些词法分析错误

词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。
本实验要求处理以下两种错误（编号分别为1，2）：
1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。
2：源程序文件结束而注释未结束。注释格式为：/* …… */

四、S语言定义

1.保留字和特殊符号表

单词代码	单词	单词助记符	内码值
1	int	int	-
2	char	char	-
3	float	float	-
4	void	void	-
5	const	const	-
6	for	for	-
7	if	if	-
8	else	else	-
9	then	then	-
10	while	while	-
11	switch	switch	-
12	break	break	-
13	begin	begin	-
14	end	end	-
15
16
17	标识符	id	在符号表中的位置
18	数字（包括整数和实数）	num	在常数表中的位置
19	+	+	-
20	-	-	-
21	*	*	-
22	/	/	-
23	%	%	-
24	(	(	-
25	)	)	-
26	[	[	-
27	]	]	-
28
29	<	relop	-
30	>	relop	-
31	<=	relop	-
32	>=	relop	-
33	==	relop	-
34	!=	relop	-
35	,	,	-
36	;	;	-
37	/=	/=	-
38	+=	+=	-
39	-=	-=	-
40	*=	*=	-
41	%=	%=	-
42	||	or	-
43	&&	and	-
44	!	not	-
45	=	=	-

单词的构词规则：
字母=[A-Z a-z]
数字=[0-9]
标识符=（字母|）（字母|数字|）*
数字=数字(数字)*( .数字+|)

2．S语言表达式和语句说明

1．算术表达式:+、-、、/、%
2．关系运算符：>、>=、<、<=、==、！=
3．赋值运算符：=，+=、-=、=、/=、%=
4．变量说明：类型标识符 变量名表；
5．类型标识符：int char float
6．If语句：if 表达式then 语句 [else 语句]
7．For语句：for（表达式1；表达式2；表达式3） 语句
8．While语句：while 表达式 do 语句
9．S语言程序：由函数构成，函数不能嵌套定义。

函数格式为：
返回值   函数名（参数）
begin
   数据说明
    语句
end
10．复合语句构成
begin
       语句序列
end

五、程序参考结构说明

1．Initscanner函数：程序初始化：输入并打开源程序文件和目标程序文件，初始化保留字表
2．Scanner函数：若文件未结束，反复调用lexscan函数识别单词。
3．Lexscan函数：根据读入的单词的第一个字符确定调用不同的单词识别函数
4．Isalpha函数：识别保留字和标识符
5．Isnumber函数：识别整数，如有精力，可加入识别实数部分工功能
6．Isanotation函数：处理除号/和注释
7．Isother函数识别其他特殊字符
8．Output函数：输出单词的二元式到目标文件，输出格式（单词助记符，单词内码值），如（int，-）（rlop，>）……
9．Error函数：输出错误信息到屏幕
10．除此之外，还可以设置查符号表，填写符号表等函数，学生可自行设计。

六、实验过程说明

测试源程序示例：

//aa.c
void  aa( )
begin
float  rate,circle; 
rate=3;
circle=3.14*rate*rate;
end

输出结果：
（1）输出结果文件：

（void,-）(id, 0)  ((,-)   (),-)  (begin,-  )  ( float,-)  (id,1)……

（2）标识符的符号表：

          Name                  type                   address
0	aa		
1	rate		
2	circle		
3			
4			
5			

（3）常数表：

                           Name                 value      
0	3	
1	3.14	
2		
3		

程序源码：

#include<stdio.h> 
#include<stdlib.h> 
#include<ctype.h> 
#include<string.h> 
#define MAX 10// 保留字符号长度 
#define MAXSIZE 45// 保留字和特殊符号表长度 
#define NUM 30// 标识符和常数的个数
FILE *in,*out;// 指向文件的指针 
char infile[MAX];// 文件名字 
char token[MAX];//字符组，存放构成单词符号的字符串 
char Word[NUM][MAX];// 标识符 
char consts[NUM][MAX];// 常数 
char lownum[NUM][MAX]={"0","1","2","3","4","5","6","7","8","9", "10","11","12",
						"13","14","15","16","17","18","19" "20","21","22","23",
						"24","25","26","27","28","29"}; //自定义表
int n=1;// 行号 
int num=0; // 错误统计数
typedef struct Key_word// 保留字和特殊符号表结构 
{ 
	//int keyNum; //种别编码 
	char keyWord[MAX]; // 单词符号 
	char keySign[MAX]; //助记符 
	char keyValue[MAX]; //内码值 
}Key_word; //初始化保留字表
Key_word Key[MAXSIZE]=//保留字和特殊符号数组 
{
	{"int","int","-"},//保留字 1 
	{"char","char","-"},//2 
	{"float","float","-"}, //3 
	{"void","void","-"},//4 
	{"const","const","-"},//5 
	{"for","for","-"}, //6 
	{"if","if","-"},//7 
	{"else","else","-"},//8 
	{"then","then","-"}, //9 
	{"while","while","-"},//10 
	{"switch","switch","-"},//11 
	{"break","break","-"}, //12 
	{"begin","begin","-"},//13 
	{"end","end","-"},//14 
	{"","",""}, //15空余出来，以便扩充 
	{"","",""},//16 
	{"","id",""},//17标示符 
	{"","num",""}, //18数字（常数和实数） 
	{"+","+","-"},//19 
	{"-","-","-"},//20 
	{"*","*","-"},//21 
	{"/","/","-"},//22 
	{"%","%","-"},//23 
	{"(","(","-"},//24 
	{")",")","-"},//25 
	{"[","[","-"},//26 
	{"]","]","-"},//27 
	{"","",""},//28 
	{"<","rlop","<"},//29 
	{">","rlop",">"},//30 
	{"<=","rlop","<="},//31 
	{">=","rlop",">="},//32 
	{"=","rlop","="}, //33 
	{"!=","rlop","!="},//34 
	{",",",","-"},//35 
	{";",";","-"},//36 
	{"/=","/=","-"},//37 
	{"+=","+=","-"},//38 
	{"-=","-=","-"}, //39 
	{"*=","*=","-"},//40 
	{"%=","%=","-"},//41 
	{"||","or","-"}, //42 
	{"&&","and","-"},//43 
	{"!","not","-"},//44 
	{"=","=","-"}//45 
}; 
//打开关闭文件
int Initscanner() 
{ 
	printf(" 请输入要输入的文件 :\n"); 
	scanf("%s",infile); 
	//读取指定文件 
	if((in=fopen(infile,"r"))==NULL) 
	{ 
		printf("cannot open infile!\n"); 
		return 0; 
	}
	 
	//将文件输出 
	if((out=fopen("word.txt","a+"))==NULL) 
	{ 
		printf("cannot open outfile!\n"); 
		return 0; 
	} 
	return 0; 
} 
//写入文件 
void Output(int n,int m) 
{ 
	//在文件中写入二元组（Key[n].keySign，
	fputs("(",out); 
	fputs(Key[n].keySign,out); 
	fputs(",",out); 
	//如果是关键字或特殊字符，
	//在文件中写入（Key[n].keySign，Key[n].keyValue    
	//Key[n].keyValue都是 — 
	if(m==-1) 
		fputs(Key[n].keyValue,out); 
	//如果是表示符，写入标识符在自定义表中对应的下标的值（Key[n].keySign，lownum[m]
	else 
		fputs(lownum[m],out);// 下标
	//在文件中写入（Key[n].keySign，Key[n].keyValue） 
	fputs(")",out); 
}
//扫描指针回退一个字符 
void remove() 
{ 
	//int fseek( FILE *stream, long offset, int origin );stream为文件指针 offset为偏移量，正数表示正向偏移，负数表示负向偏移
	//SEEK_SET： 文件开头 SEEK_CUR： 当前位置 SEEK_END： 文件结尾
	fseek(in,-1,SEEK_CUR); 
} 
 
//Isalpha 函数：识别保留字和标识符
int Isalpha() 
{ 
	int i; 
	// 关键字，16个关键字，循环匹配 
	for(i=0;i<16;i++)
	{ 	//判断token是否等于Key[i].keyWord
		if(strcmp(token,Key[i].keyWord)==0) 
		{ 
			Output(i,-1); //匹配到对应的关键字，传回关键字在数组中的位置，-1表示是关键字 
			return 0; 
		} 
	} 
	//标识符 Word[NUM][MAX] 
	//i=表示符id 
	for(i=0;i<NUM;i++) 
	{
		//如果标示符表【i】位置不为空，并且标示符表【i】中存在该标示符 
		if((Word[i][0]!=NULL)&&strcmp(token,Word[i])==0) 
		{ 
			Output(16,i); 
			return 0; 
		}
		//如果标示符表【i】位置为空 
		if(Word[i][0]==NULL) 
		{ 
			//将token中的值复制到标示符表Word[i]中 
			strcpy(Word[i],token); 
			Output(16,i); 
			return 0; 
		} 
	} 
	return 0; 
} 
//Isnumber 函数 :consts[NUM][MAX] 识别整数，如有精力，可加入识别实数部分工功能 
int Isnumber()
{ 
	int i;
	for(i=0;i<NUM;i++) 
	{ 
		//如果数字表(consts[i]位置不为空，并且数字表中存在该数字 
		if((consts[i][0]!=NULL)&&strcmp(token,consts[i])==0) 
		{ 
			Output(17,i); 
			return 0; 
		} 
		// 如果数字表(consts[i]位置为空
		if(consts[i][0]==NULL) 
		{ 
			//将token中的值复制到数字表consts[i]中 
			strcpy(consts[i],token); 
			Output(17,i); 
			return 0; 
		} 
	} 
	return 0; 
} 

//Isanotation 函数：处理除号 /和注释 
void Isanotation() //提示第一个字符已经存为 /了 
{ 
	char ch,pre; 
	ch=getc(in); 
	if(ch=='=')// "/=" 
		Output(36,-1); 
	else if(ch=='*')// "/*" 
	{ 
		ch=getc(in); 
		do{ 
			//如果文件结束，则返回非0值，否则返回0 
			if(feof(in)) 
			{ 
				num++; //记录错误数量 
				printf("\n 第(%d) 行 : 注释错误 : /*后面的字符全部当做注释，缺少结束注释*/\n",n); 
				break; 
			} 
			pre=ch; 
			ch=getc(in); 
		}
		while(pre!='*'||ch!='/'); 
	} 
	else if(ch=='/')// "//" 
	{ 
		ch=getc(in); 
		while (ch != '\n')
		{
			ch=getc(in); 	
		}
		n++; 
	}   
	else// "/" 
	{ 
		remove(); //多读入一个字符，指针回退一个字符
		Output(21,-1); 
	} 
} 
//Isother 函数识别其他特殊字符
void Isother() 
{ 
	int i=1;
	int j=0; 
	char ch;
	//()，[] 
	//, ;
	//< > ! %     <= >= != %= 
	//+ - * =
	if(token[0]=='<'||token[0]=='>'||token[0]=='!'||token[0]=='%'||
		token[0]=='+'||token[0]=='-'||token[0]=='*'||token[0]=='=') 
	{ 
		ch=getc(in); 
		if(ch=='=') 
			token[i++]=ch; 
		else 
			remove(); 
	}
	//|  || 
	else if(token[0]=='|') 
	{ 
		ch=getc(in); 
		if(ch=='|') 
			token[i++]=ch; 
		else 
			remove(); 
	}
	//&  && 
	else if(token[0]=='&') 
	{ 
		ch=getc(in); 
		if(ch=='&') 
			token[i++]=ch; 
		else 
			remove(); 
	} 
	//字符串数组结尾就是'\0',表示这串字符到结尾了 
	token[i]='\0'; 
	//匹配字符表是否存在该字符 
	
	for(i=18;i<45;i++) 
	{ 
		if(strcmp(token,Key[i].keyWord)==0) 
		{ 
			Output(i,-1); //-1表示特殊字符 
			break; 
		} 
	} 
	//如果不存在，输出非法字符 
	if(i==45) 
	{ 
		num++; 
		printf("\n 第(%d)行 : 字符错误 : %s 字符非法 \n",n,token); 
	} 
} 
//Scanner函数：若文件未结束，反复调用lexscan函数识别单词。 
void Scanner() 
{ 
	char ch; 
	int i; 
	ch=getc(in); 
	while(!feof(in)) 
	{ 
		while(ch==' '||ch=='\t'||ch=='\n') // 先统计行数
		{ 
			if(ch=='\n') 
			++n; 
			ch=getc(in); 
		} 
		// 标识符 isalpha(ch)单词
		if(((ch>='a')&&(ch<='z'))||(ch=='_'))
		{ 
			i=1; 
			token[0]=ch; 
			ch=getc(in);
			//当ch为非字母或数字时，终止循环 
			while(((ch>='a')&&(ch<='z'))||((ch>='0')&&(ch<='9')))//word number 
			{ 
				token[i++]=ch; 
				ch=getc(in); 
			}  
			token[i]='\0'; 
			//识别保留字和标识符 
			Isalpha(); 
		}
		// 整数 
		else if((ch>='0')&&(ch<='9'))
		{ 
			i=1; 
			token[0]=ch; 
			ch=getc(in); 
			//当ch不是数字时终止循环 
			while(isdigit(ch)) 
			{ 
				token[i++]=ch; 
				ch=getc(in); 
			}
			//如果下一位为. 
			if(ch=='.')
			{
				token[i++]=ch; 
				ch=getc(in);  
				while(isdigit(ch))
				{
					token[i++]=ch; 
					ch=getc(in); 
				}
			}
			token[i]='\0';  
			Isnumber();
		} 
		else if(ch=='/')// 区分 "/" , "/=" , "/*" 
		{ 
			token[0]=ch; 
			Isanotation(); 
			ch=getc(in); 
		} else //特殊字符
		{ 
			token[0]=ch; 
			Isother(); 
			ch=getc(in); 
		} 
	} 
} 

void show() 
{ 
	int i; 
	char ch; 
	printf("分析程序：\n");
	rewind(in);
	while(!feof(in)) 
	{ 
		printf("%c",getc(in)); 
	}
	printf("\n 二元式 :\n"); 
	rewind(out); 
	while(!feof(out)) 
	{ 
		printf("%c",getc(out)); 
	} 
	printf("\n 标志符表 \n"); 
	for(i=0;i<NUM;i++) 
	{ 
		if(Word[i][0]!=NULL) 
		printf("%d,%s\n",i,Word[i]); 
	} 
	printf("\n 常数表 \n"); 
	for(i=0;i<NUM;i++) 
	{ 
		if(consts[i][0]!=NULL) 
		printf("%d,%s\n",i,consts[i]); 
	} 
} 

int main() 
{
	//初始化 
	Initscanner(); 
	Scanner(); 
	printf("\n 共有 %d 个错误 \n",num); 
	show(); 
	fclose(in); 
	fclose(out); 
	return 0;
} 

在文件夹下新建chengxu.txt文件，用于程序分析

//aa.c
void $ aa( )
begin  $
/*hsahdkjashdjg*/
float  rate,circle;  
rate=3;  $
circle=3.14*rate*rate;
end 

$
@

在文件夹下新建word.txt文件，用于输出分析的二元组结果

运行结果：

输入文件chengxu.txt

实验总结：

将近两年没有用c语言编程，在实验刚开始做时，甚至连怎么用dev运行一个项目这么基础的东西都不会了，后来通过自己查找，想起来要先编译，再运行。当看到词法分析器，这么多的实验报告后，我很蒙，不知道从什么地方下手，于是我一遍一遍的看老师发的视频，参考书上的案例，由于书上的代码不全，有些函数不存在，可以说，书上的就是伪代码。

我只能自己去问百度了，首先我再百度上查找了一份用java编写的词法分析器，一看，直接拷贝到编辑器运行一边，运行成功，并且可以分析出字符的不合法，还能找出错误，这使我找到了方向，于是我准备研究这个代码，因为我对java比较熟悉，语法读起来还是比较方便的，从头到尾的仔细读了一遍，每一个不懂得就打上注释。

后来读着读着，我开始慢慢理解什么叫标示符，什么叫保留字，还有数字需要读出来存到常数表，标示符需要判断结束存储到标识符表，大概了解了词法分析器的作用和功能，我开始发现如果要想写好，并且这么多字符，要写的井而有序，思路清晰，一定要画好状态转换图。

首先打一遍草稿，然后再在专业画图工具Visio上绘制，这个图花费了我很长时间，我参考书上的，起初绘制的状态转换图，每个符号都返回一个二元组，图画了一大长溜，画完图后，开始编程c语言版的，为什么我对java那么熟悉，不编java版的呢，其实自己也是想顺便练习一下c编程，实验中明确给出了要用到的函数，一个初始化，一个用来循环字符，最后一个关闭文件流。

函数都知道了，开始准备需要什么样的数组，由于之前看过一个java版的，对于这方面有一定的了解。

要存储保留字，标示符，还有常数，先建立一个表结构，用于存储保留字和特殊符号表，在查找是否是保留字和特殊符号表时，就遍历查询此表，建立一个标示符表，假如读到一个字符串，那么先查询保留字和特殊符号表，如果可以查到那就是保留字，如果查不到，那么再查询标示符表，如果在标示符表也查不到，那就将这个字符串加入到标识符表，此外还要建立一个常数表，还要建立一个记录行号的计数位，还有一个记录错误的计数位。

下面，才开始按实验给出的函数编程，首先打开读文件，和写文件，初始化操作，再就是循环程序一个一个读取字符串，数字，符号，并且对其进行处理。

在处理小数点的时候，迷糊了好久，问了一次老师，后来把状态转换图绘制出来，才清晰了许多。

再往下就是对注释处理，在这里要把‘/’这个符号的处理和其他符号的处理分开了，读取了第一个字符是‘/’后，还要继续往下读取，看看后面是‘/’还是‘’还是‘=’，还是没有，这里最难处理的就是‘’因为结束的时候你要读取两个字符，需要挨着的两个字符是‘*/’才行，其次就是‘/’这是单行注释，遇到回车换行符结束就行了。

再继续往下走，就是符号的处理，每个字符都要写一个返回，代码耦合度太高了，再次改进状态转换图，这时候就把字符分类处理，那些第二个字符是‘=’的分成一组，第一个字符是‘|’和‘&’的单独处理，剩下其他的，就直接去符号表查找，有就输出，没有就报错，并且记录行号，输出非法字符。

到此，实验结束。通过这次试验，收获很多，也激发了我对编译原理的兴趣，不断地思考，给我带来了成功后的快感。希望在今后的学习中也会如此。畅快淋漓！