编译原理词法分析程序实验报告.doc

编译原理实验报告
实验名称：编写词法分析程序
实验类型：设计性实验
指导教师：*****
专业班级：软件工程1401
姓 名：****
学 号：**********
实验地点：东六E座301
实验成绩：_________________
日期： 2016 年 5 月 8 日
实验一
编写词法分析程序
一、实验目的
1. 通过设计、调试词法分析程序，掌握词法分析程序的设计工具（有穷自动机），进一步理解自动机理论
2. 掌握正则文法和正则表达式转换成有穷自动机的方法及有穷自动机实现的方法
3. 确定词法分析程序的输出形式及标识符及关键字的区分方法
4. 加深对理论知识的理解
二、实验设计
1. 设计原理：
对源程序代码从头到尾扫描，将符合词法语言规则的单词输出，包括：标识符、保留字、无符号整数、分界符、运算符、注释分离；判断程序的词法是否正确
TEST语言的词法规则如下：
1）、标识符：字母打头，后接任意字母或数字。
2）、保留字：标识符的子集，包括：if,else,for,while,do, int,write,read。
3）、无符号整数：由数字组成，但最高位不能为0，允许一位的0。
4）、分界符：(、)、;、{、}
5）、运算符：+、-、*、/、=、<、>、>=、<=、!=、==
6）、注释符：/* */
2. 设计方法：
1) 用正则表达式或正则文法描述程序设计语言的词法规则，通常采用正则表达式；一个正则表达式对应一条词法规则
2) 为每个正则表达式构造一个NFA，用来识别正则表达式描述的单词将每一个NFA合并、化简得到最简的DFA
3) 将多个NFA合并为一个NFA
4) 将NFA转换成等价的DFA。
5) 最小化DFA
6) 确定单词的输出形式。
7) 化简后的DFA＋单词输出形式⇒构造词法分析程序
3. 设计过程：
1) 将TEST语言的六个语法规则分别转换成正则表达式
2) 为每个正则表达式构造一个NFA，用来识别正则表达式描述的单词
3) 将5个NFA转换成一个NFA，再将NFA化简确定化。
4. 设计结果：
1) 每一条TEST语言对应的正则表达式如下：
标识符：( a|b|……|z|A|B……|Z )( 0|1|……|9| a|b|……|z|A|B……|Z )*
保留字：标识符的子集
无符号整数： ( (1……|9 )( 0|1|……|9)* )|0
分界符：( | ) | ; | { | }
运算符：+ | - | * | / | = | < | > | >= | <= | != | ==
注释符：/*（其他）*/
2) NFA如图
3) 化简、确定化的DFA
三、实验过程
1. 将TEST语言的六个语法规则转换成正则表达式
2. 将每个正则表达式装换成NFA,再将NFA合并化简
3. 最终得到设计结果如上所示：
4. 根据确定化的DFA编写代码
5. 测试实验数据
三、实验结果
1. 测试数据：
/*This a test program.*/
int abc;
int 123;
int A$@;
int i;
int n;
int b,c;
int 2a;
int a2;
read n;
n = 012345;
for (i=1;i<=n; i= i+1)
abc=abc+i;
if(i!=n) n = n+i;
if (!n) b = b+c;
/*The loop ended
write abc;
2. 实验现象：
a) 控制台显示的数据：
b) 输出文本的数据：
int int
ID abc
int int
NUM 123
int int
ID A
Error $
Error @
int int
ID i
int int
ID n
int int
ID b
Error ,
ID c
int int
NUM 2
ID a
int int
ID a2
read read
ID n
ID n
NUM 0
NUM 12345
for for
ID i
NUM 1
ID i
ID n
ID i
ID i
NUM 1
ID abc
ID abc
ID i
if if
ID i
ID n
ID n
ID n
ID i
if if
Error !
ID n
ID b
ID b
ID c
c) 数据分析：
根据TEST语法规则，我们可以知道
int A$@;这一句中的$和@是不合法的
int b,c;这一句中的逗号是不合法的
if (!n) b = b+c;这一句中!是不合法的
/*The loop ended 这一句都是不合法的
四、讨论及分析
单词分类方法：
按照标识符、数字、分解符、注释符、运算符分类；其中需要注意的是（>|<=）可以直接结束，也可以连接=，！必须及=连接才合法，对于/需要多重考虑，即在注释这个部分也可能是/符号
构建词法分析程序的一般过程：、
1、 根据词法规则写出正则文法或者正则文法。
2、 为每一个正则表达式构造一个NFA，然后将多个NFA合并为一个NFA
3、 将NFA转化成DFA，并且化简最小化DFA
4、 确定单词的输出形式
5、 根据化简后的DFA和单词输出程序构造词法分析程序
五、附录：关键代码
//开始读取文件中的字符
ch = getc(fin);
while(ch != EOF)
i = 0;
while(ch == ' ' || ch == '\n' || ch == '\t')
if(ch == '\n')
line ++;
ch = getc(fin);
//标识符处理
if(isalpha(ch))
while(isalpha(ch) || isdigit(ch))
buff[i++] = ch;
ch = getc(fin);
buff[i] = '\0';
//保留字
int n = 0;
while((n < 8) && strcmp(buff,keyword[n]))
n++;
if(n < 8)
fprintf(fout,"%s\t%s\n",buff);
else
fprintf(fout,"%s\t%s\n","ID",buff);
//数字处理
else if(isdigit(ch))
//单个数字“0”
if(ch == '0')
buff[0] = ch;
buff[1] = '\0';
fprintf(fout,"%s\t%s\n","NUM",buff);
ch = getc(fin);
//数字的组合
else
while(isdigit(ch))
buff[i++] = ch;
ch = getc(fin);
buff[i] = '\0';
fprintf(fout,"%s\t%s\n","NUM",buff);
//单分界符
else if(strchr(singleword,ch) > 0)
buff[0] = ch;
buff[1] = '\0';
ch = getc(fin);
fprintf(fout,"%s\t%s\n",buff,buff);
//双分界符
else if(strchr(doubleword,ch) > 0)
buff[0] = ch;
ch = getc(fin);
if(ch == '=')
buff[1] = ch;
buff[2] = '\0';
ch = getc(fin);
fprintf(fout,"%s\t%s\n",buff,buff);
else
buff[1] = '\0';
if(buff[0] == '!')
printf("Line %d\t%s\t%s\n",line,"错误：",buff);
fprintf(fout,"%s\t%s\n","Error",buff);
else
fprintf(fout,"%s\t%s\n",buff,buff);
//注释
else if(ch == '/')
ch = getc(fin);
if(ch == '*')
char ch1 = getc(fin);
while(true)
if(ch1 == EOF)
printf("Line %d\t%s\t没有匹配！\n", line,"错误:" );
break;
ch = ch1;
ch1 = getc(fin);
if(ch =='*' && ch1 == '/')
break;
ch = getc(fin);
else
buff[0] = '/';
buff[1] = '\0';
//输出单分界符'/'
fprintf(fout,"%s\t%s\n",buff,buff);
else
buff[0] = ch;
buff[1] = '\0';
flag = 3;
ch = getc(fin);
printf("Line %d\t%s\t%s\n", line, "错误:", buff);
fprintf(fout,"%s\t%s\n","Error",buff);
fclose(fin);
fclose(fout);
return flag;
第 12 页