编译原理实验-简单词法分析(含源代码及实验结果).doc

附录一 实验报告样式

《编译原理》实验报告
实验2 简单词法分析
姓名 陈婷婷 学号 1009050121 班级 计科1001班

时间： 2012/4/5 地点:文波
同 组 人：无
指导教师：朱少林
实验目的
通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法；掌握词法分析的实现方法；上机调试编出的词法分析程序。

实验内容
⑴ 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。
⑵ 掌握词法分析的实现方法。
⑶ 上机调试编出的词法分析程序。
⑷ 为简单起见，假设编译语言为具有下特征的C_minus。该词法分析器要求至少能够识别C_minus中的以下几类单词：
a． 关键字：else if int return void while共6个，所有的关键字都是保留字，并且必须是小写；
b． 标识符：识别与C语言词法规定相一致的标识符，通过下列正则表达式定义：ID = letter (letter | digit)*；
c． 常数：NUM=(+ | - |ε)digit digit*(.digit digit* |ε)(e(+ | - |ε) digit digit* |ε)，letter = a|..|z|A|..|Z|，digit = 0|..|9，包括整数，如123, -123, +123等；小数，如123.45, +123.45, -123.45；科学计数法表示的常数，如+1.23e3，-2.3e-9；
d． 专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */；

实验环境

软件：VC++6.0

实验前准备
1、 方案设计：
① 准备模拟数据：本实验中使用 “测试文件.c”

②程序思想：
该实验要识别关键字、标识符、常数、专用符号（分界符、算术运算符和关系运算符）。
对于关键字本实验主要识别10个（break、do、else float if int for switch main char） ，使用的数据结构为：
struct Key//用于关键字和标识符及常数，由于常数有科学计数法的表示，所以该实验中把常数当做字符串进行检测输出
{
char name[20];
int i;
int t;
};
Key keyword[10];//存放10个关键字
然后在函数void initial()对Key keyword[10]进行初始化。函数int search_key(char *teststring, FILE *f)用来将识别到的以字母开头的字符串teststring与定义的关键字一一比较，如果是关键字则把它写入文件f中，否则在检验是否是标识符；如果是关键字则返回1,否则返回0.
对与标识符和常数，使用的数据结构是一样的，这是因为识别一个标识符和识别一个常数都是要读入多个字符才能识别一个完整的，而且标识符表和常数表都是在识别过程中建立的，都所以用到的数据结构为：
struct Key//用于关键字和标识符及常数
{
char name[20];
int i;
int t;
};

struct key_infor//记录标识符表，常数表的相关信息
{
struct Key *head;
int key_length;
};
识别到一个以字母开头的符号串后如果不是关键字，就调用void search_table(char *teststring, key_infor *p, FILE *f)与已经识别到的标识符一一比较，如果是新的则赋予新的i值并打印输出到屏幕并且写入f中（只要是标志符就写入文件f中）。Main()中将识别到的标识符（不重复）写入另外的文件中。
search_table中关键部分如下：
while( j<i&&strcmp(teststring,point[j].name))
{
j++;
}//与已有的标识符一一比较
if(j==i)//说明是新的标识符
{
strcpy(point[j].name,teststring);

p->key_length++;
point[j].i=j;
point[j].t=6;

}
识别到一个完整的常数则进行与标识符相似的处理，void search_number(char *teststring, key_infor *p, FILE *f)的思想与void search_table(char *teststring, key_infor *p, FILE *f)的基本一致。Main()中将识别到的常数（不重复）写入另外的文件中。
如果既不是字母开头也不是数字开头，则调用void search_sign(char x, FILE *file, FILE *f)，该函数实现对专用符号的识别，并把识别到的专用符号写入文件f中。
该实验有六个输出文件，存放输出结果。其中与标志符相关的有两个，一个存放识别到的所有标识符（有重复，即测试文件中的所有标识符），一个存放不重复的（重复的只存一次），与常数相关的文件类似也2个，另外的的两个分别存放识别到的专用符号和关键字。
2、 程序设计
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

struct Key//用于关键字和标识符及常数，由于常数有科学计数法的表示，所以该实验中把常数当做字符串进行检测输出
{
char name[20];
int i;
int t;
};
Key keyword[10];//存放10个关键字

struct key_infor//记录标识符表，常数表的相关信息
{
struct Key *head;
int key_length;
};

struct op//用于除关系运算符以外的专用符号
{
char mark;
int ii;
int tt;
};
op seperateop[8] ;
op mathop[4];
struct reop//用于除关系运算符以外的专用符号
{
char remark[3];
int iii;
int ttt;
};
reop relatop[8];
char a[10]={',',';','.','=','(',')','{','}','[',']'};//分界符
char b[4]={'+','-','*','/'};//算术运算符

char signal[8][4]={"<","<=","=",">",">=","<>","==","!="};
void initial()//初始化关键字表 分界符表 算术运算符表 关系运算符表
{
for(int j=0; j<10;j++)//初始化关键字表
{
keyword[j].t=1;
keyword[j].i=j;

}
strcpy(keyword[0].name,"break");
strcpy(keyword[1].name,"do");
strcpy(keyword[2].name,"else");
strcpy(keyword[3].name,"float");
strcpy(keyword[4].name,"if");
strcpy(keyword[5].name,"int");
strcpy(keyword[6].name,"for");
strcpy(keyword[7].name,"switch");
strcpy(keyword[8].name,"main");
strcpy(keyword[9].name,"char");
printf("以下是可以识别的关键字内部表示\n");
printf("关键字 i值 t值\n");
for(int k=0;k<10;k++)
{
printf("%s\t",keyword[k].name);
printf("%d\t",keyword[k].i);
printf("%d\n",keyword[k].t);
}

for(int m=0;m<10;m++)//初始化分界符表
{
seperateop[m].mark=a[m];
seperateop[m].ii=m;
seperateop[m].tt=2;
}
printf("以下是可以识别的分界符内部表示\n");
printf("分界符 i值 t值\n");
for(int n=0;n<10;n++)
{
printf("%c\t",seperateop[n].mark);
printf("%d\t",seperateop[n].ii);
printf("%d\n",seperateop[n].tt);
}

for(int p=0;p<4;p++)//初始化算术运算符表
{
mathop[p].mark=b[p];
mathop[p].ii=p+16;//先用十进制表示？？？？？？？？？？
mathop[p].tt=3;
}
printf("以下是可以识别的算术运算符内部表示\n");
printf("算术运算符 i值 t值\n");
for(int q=0;q<4;q++)
{
printf("%c\t\t",mathop[q].mark);
printf("%d\t",mathop[q].ii);//查如何用十六进制输出？？？？？？？？
printf("%d\n",mathop[q].tt);
}
for(int r=0;r<8;r++)//初始化关系运算符表
{
strcpy(relatop[r].remark,signal[r]);
relatop[r].iii=r;//这里用十进制表示？？？？？？？？
relatop[r].ttt=4;
}
printf("以下是可以识别的关系运算符内部表示\n");
printf("关系运算符 i值 t值\n");
for(int s=0;s<8;s++)
{
printf("%s\t\t",relatop[s].remark);
printf("%d\t",relatop[s].iii);//查如何用十六进制输出？？？？？？？？
printf("%d\n",relatop[s].ttt);
}

}

int search_key(char *teststring, FILE *f)//设置返回值用于确定是否需要检验是不是标识符
{//检测是否为关键字，如果是则写入关键字文件中
int j=0;
int i=10;
while( j<i&&strcmp(teststring,keyword[j].name))
{
j++;
}//与关键字一一比较
if(j==i)//不是关键字则返回
return 0;
else//是关键字打印该关键字并将该关键字写入文件
{
printf("%s是关键字,i=%d,t=%d\n",keyword[j].name,keyword[j].i,keyword[j].t);

}

fprintf(f,"%s\t%5d\%5d\n",keyword[j].name,keyword[j].i,keyword[j].t);//将识别到的关键字写入文件f中
return 1;
}

void search_table(char *teststring, key_infor *p, FILE *f)//查填符号表函数,p为指向结构体的指针
{
int i=p->key_length;//i记录标识符表的长度
int j=0;
Key *point;
point=p->head;
while( j<i&&strcmp(teststring,point[j].name))
{
j++;
}//与已有的标识符一一比较
if(j==i)//说明是新的标识符
{
strcpy(point[j].name,teststring);

p->key_length++;
point[j].i=j;
point[j].t=6;

}
printf("%s是标志符,i=%d,t=%d\n",point[j].name,point[j].i,point[j].t);
fprintf(f,"%s\t%5d\t%5d\n",point[j].name,point[j].i,point[j].t);//将新的标识符写入标识符文件f中
return ;
}
void search_number(char *teststring, key_infor *p, FILE *f)//查填常数表函数,p为指向结构体的指针
{
int i=p->key_length;//i记录常数表的长度
int j=0;
Key *point;
point=p->head;
while( j<i&&strcmp(teststring,point[j].name))
{
j++;
}//与已有的标识符一一比较
if(j==i)//说明是新的标识符
{
strcpy(point[j].name,teststring);

p->key_length++;
point[j].i=j;
point[j].t=5;

}
printf("%s是常数,i=%d,t=%d\n",point[j].name,point[j].i,point[j].t);
fprintf(f,"%s\t%5d\t%5d\n",point[j].name,point[j].i,point[j].t);//将新的常数写入文件f中
return ;
}

Void search_sign(char x, FILE *file, FILE *f)
{//检测是否为专用符号
int j=0;
char temp=x;
while( j<10 && x!=seperateop[j].mark)//检测是否为分界符
{
j++;
}//与定义的8个分隔符一一比较
if(j<10)//是分隔符

{
printf("%c是分界符,i=%d,t=%d\n",seperateop[j].mark,seperateop[j].ii,seperateop[j].tt);
fprintf(f,"%c\t %d\t %d\n",seperateop[j].mark,seperateop[j].ii,seperateop[j].tt);//将识别到的分隔符写入文件f中

}
else //不是分界符，就把j赋值0，与算术运算符比较
{
j=0;
while( j<4&&x!=mathop[j].mark)
{
j++;
}//与定义的4个算术运算符一一比较
if(j<4)//是算术运算符

{
printf("%c是算术运算符,i=%d,t=%d\n",mathop[j].mark,mathop[j].ii,mathop[j].tt);
fprintf(f,"%c\t %d\t %d\n",mathop[j].mark,mathop[j].ii,mathop[j].tt);//将识别到的算术运算符写入文件f中

}
else
switch(x)
{

case'>':
{
x=fgetc(file);

if (x=='=')
{

printf("%s是关系运算符,i=%d,t=%d\n",relatop[4].remark,relatop[4].iii,relatop[4].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[4].remark,relatop[4].iii,relatop[4].ttt);//将识别到的关系运算符写入文件f中
break;
}
else
{
fseek(file,-1L,SEEK_CUR);
x=temp;
printf("%s是关系运算符,i=%d,t=%d\n",relatop[3].remark,relatop[3].iii,relatop[3].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[3].remark,relatop[3].iii,relatop[3].ttt);//将识别到的关系运算符写入文件f中
break;
}

}

case'<':
{
x=fgetc(file);
if (x=='=')
{
printf("%s是关系运算符,i=%d,t=%d\n",relatop[1].remark,relatop[1].iii,relatop[1].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[1].remark,relatop[1].iii,relatop[1].ttt);//将识别到的关系运算符写入文件f中
break;
}

else if(x=='>')
{
printf("%s是关系运算符,i=%d,t=%d\n",relatop[5].remark,relatop[5].iii,relatop[5].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[5].remark,relatop[5].iii,relatop[5].ttt);//将识别到的关系运算符写入文件f中
break;

}
else
{
fseek(file,-1L,SEEK_CUR);
x=temp;
printf("%s是关系运算符,i=%d,t=%d\n",relatop[0].remark,relatop[0].iii,relatop[0].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[0].remark,relatop[0].iii,relatop[0].ttt);//将识别到的关系运算符写入文件f中
break;

}

}

case'=':
{
x=fgetc(file);
if(x=='=')
{
printf("%s是关系运算符,i=%d,t=%d\n",relatop[6].remark,relatop[6].iii,relatop[6].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[6].remark,relatop[6].iii,relatop[6].ttt);//将识别到的关系运算符写入文件f中
break;
}
else
{
fseek(file,-1L,SEEK_CUR);
x=temp;
printf("%s是关系运算符,i=%d,t=%d\n",relatop[2].remark,relatop[2].iii,relatop[2].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[2].remark,relatop[2].iii,relatop[2].ttt);//将识别到的关系运算符写入文件f中
break;
}

}
case'!':
{
x=fgetc(file);
if(x=='=')
{
printf("%s是关系运算符,i=%d,t=%d\n",relatop[7].remark,relatop[7].iii,relatop[7].ttt);
fprintf(f,"%s\t %d\t %d\n",relatop[7].remark,relatop[7].iii,relatop[7].ttt);//将识别到的关系运算符写入文件f中
break;
}
}

}
}
return;
}

void main()
{
char readchar;
char teststr[20];//存放标识符
char linkstr[2]={0};//用于把字符readchar连接到teststr
initial();

FILE *key_result;//新建并打开关键字结果.txt文件
key_result=fopen("关键字结果.txt","w+");
fprintf(key_result,"关键字\t i值 t值\n");

FILE *table_result;//新建并打开文件
table_result=fopen("标识符结果.txt","w+");
fprintf(table_result,"标识符\t i值 t值\n");

key_infor information;//用于指向符号表
Key mark[400];//定义符号表最多可以有400个符号
information.head=mark;
information.key_length=0;

key_infor numinformation;//用于指向常数表
Key nummark[400];//定义符号表最多可以有400个符号
numinformation.head=nummark;
numinformation.key_length=0;

FILE *sign_result;//新建并打开专用符号结果.txt文件
sign_result=fopen("专用符号结果.txt","w+");
fprintf(sign_result,"专用符号\ti值\tt值\n");

FILE *number_result;//新建并打开常数结果.txt文件
number_result=fopen("常数结果.txt","w+");
fprintf(number_result,"常数\t i值 t值\n");

FILE *fp;
fp=fopen("测试文件.c","r");
if (fp==NULL)
{
printf("打开文件失败！");
exit(0);
}//打开测试文件fp
readchar=fgetc(fp);
while(readchar!=EOF)
{
teststr[0]=0;
if(readchar<='z'&& readchar>='a'||readchar>='A'&& readchar<='Z')//第一个是字母转向关键字与标识符

{

while(readchar<='z'&& readchar>='a'||readchar>='A'&& readchar<='Z'||readchar>='0'&& readchar<='9')
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
if(strlen(teststr)!=0 )
{

int n=search_key( teststr, key_result);//先检查是否是关键字
if(n!=1)//返回值是0,不是关键字,则继续检验是否为标识符
search_table(teststr, &information,table_result );
}

}//这个循环结束后就读入一个标识符

else if(readchar>=48&&readchar<=57)//如果是数字
{

while(readchar>=48&&readchar<=57)
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
if (readchar=='.')
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
while(readchar>=48&&readchar<=57)
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
if (readchar=='e')
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
if (readchar=='+'||readchar=='-')
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
while(readchar>=48&&readchar<=57)
{
linkstr[0]=readchar;
strcat(teststr,linkstr);//会自动添加‘\0’
readchar=fgetc(fp);
}
search_number(teststr, &numinformation,number_result );

}
else//判断是否为专用运算符
{
search_sign(readchar, fp, sign_result);
readchar=fgetc(fp);
}

}
fclose(fp);//关闭测试文件
fclose(key_result);//关闭关键字文件
fclose(table_result);//关闭标识符文件
fclose(sign_result);
FILE *table=fopen("符号表.txt","w+");//新建"符号表.txt"文件
fprintf(table,"标识符\t i值 t值\n");

if(table==NULL)
{
printf("文件打开失败!");
exit (0);
}
int i=0;
while(i<information.key_length)
{

fprintf(table,"%s\t%5d\t%5d\n",mark[i].name,mark[i].i,mark[i].t);//把识别到的标识符写入"符号表.txt"文件

i++;
}
fclose(table);
FILE *NUMBER=fopen("常数表.txt","w+");//新建"常数表.txt"文件
fprintf(NUMBER,"常数\t i值 t值\n");

if(NUMBER==NULL)
{
printf("文件打开失败!");
exit (0);
}
int p=0;
while(p<numinformation.key_length)
{

fprintf(NUMBER,"%s\t%5d\t%5d\n",nummark[p].name,nummark[p].i,nummark[p].t);//把识别到的标识符写入"符号表.txt"文件

p++;
}
fclose(NUMBER);

}
实验步骤
①将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见下图。

图 词法分析程序流程图
②标识符的正规式定义和确定的有限自动机见实验一
③常数的正规式定义：NUM=(+ | - |ε)digit digit*(.digit digit* |ε)(e(+ | - |ε) digit digit* |ε)，letter = a|..|z|A|..|Z|，digit = 0|..|9
化简后的确定的有限自动机如下：

实验结果及其分析：
① 关键字结果.txt（用于存放识别到的关键字）内容如下：
关键字 i值 t值
int 5 1
int 5 1
int 5 1
int 5 1
char 9 1
int 5 1
char 9 1
char 9 1
main 8 1
char 9 1
int 5 1
char 9 1
if 4 1
else 2 1
int 5 1
char 9 1
char 9 1
int 5 1
for 6 1
if 4 1
② 标识符结果.txt（存放识别到的所有标识符）
标识符 i值 t值
include 0 6
stdio 1 6
h 2 6
qq 3 6
temp 4 6
temp 4 6
s 5 6
search 6 6
str 7 6
c 8 6
void 9 6
str 7 6
c 8 6
m 10 6
i 11 6
printf 12 6
please 13 6
input 14 6
a 15 6
string 16 6
gets 17 6
str 7 6
puts 18 6
please 13 6
input 14 6
the 19 6
you 20 6
search 6 6
c 8 6
getchar 21 6
m 10 6
search 6 6
str 7 6
c 8 6
m 10 6
printf 12 6
can 22 6
not 23 6
find 24 6
printf 12 6
the 19 6
c 8 6
you 20 6
search 6 6
is 25 6
d 26 6
n 27 6
m 10 6
search 6 6
str 7 6
c 8 6
i 11 6
i 11 6
str 7 6
i 11 6
i 11 6
str 7 6
i