编译原理实验报告
实验名称:编写词法分析程序
实验类型:
指导教师:***** 专业班级:软件工程 1401
姓 名:****
号:
**********
实验地点:东六E座301
实验成绩:
日期:2016 年5 月8 日
实验一
编写词法分析程序
一、 实验目的通过设计、调试词法分析程序,掌握词法分析程序的设计工具(有穷自 动机),进一步理解自动机理论
掌握正则文法和正则表达式转换成有穷自动机的方法及有穷自动机实现 的方法
确定词法分析程序的输出形式及标识符与关键字的区分方法
加深对理论知识的理解
二、 实验设计
设计原理:
对源程序代码从头到尾扫描,将符合词法语言规则的单词输出,包括: 标识符、保留字、无符号整数、分界符、运算符、注释分离;判断程序 的词法是否正确
TEST语言的词法规则如下:
1)、标识符:字母打头,后接任意字母或数字。
2 )、保留字:标识符的子集,包括:if,else,for,while,do, in t,write,read 。
3)、无符号整数:由数字组成,但最高位不能为 0,允许一位的0。
4)、分界符:(、)、;、{、}
5) 、运算符: +、-、*、/、=、<、>、>=、<=、!=、==
6) 、注释符:/* */
设计方法:
1) 用正则表达式或正则文法描述程序设计语言的词法规则,通常采用 正则表达式;一个正则表达式对应一条词法规则
2) 为每个正则表达式构造一个NFA用来识别正则表达式描述的单词将 每一个NFA合并、化简得到最简的DFA
3) 将多个NFA合并为一个NFA
4) 将NFA转换成等价的DFA
5) 最小化DFA
6) 确定单词的输出形式。
7) 化简后的DFA^单词输出形式?构造词法分析程序
设计过程:
1) 将TEST语言的六个语法规则分别转换成正则表达式
2) 为每个正则表达式构造一个NFA用来识别正则表达式描述的单词
3) 将5个NFA转换成一个NFA再将NFA化简确定化。
设计结果:
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
三、实验过程
将TEST语言的六个语法规则转换成正则表达式
将每个正则表达式装换成 NFA,再将NFA合并化简
最终得到设计结果如上所示:
根据确定化的DFA编写代码
测试实验数据
三、实验结果
测试数据:
{ /*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 en ded
write abc;
}
实验现象:
控制台显示的数据: 输入源程序文件名及路径: C:\Users\August^Docunents\data. txt
输入筍法分*斤榆岀文禅名及路盗;C: \Users\Augus-t\DocunierLt£\priEt? txt Line 5 惜误;$
Line 5 错误;@
Line 8 错误:,
Line 18 错误 !
Line 19错误: 没有匹配!
词迭分析有错,编译停止!
Process returned 0 (0x0) execution time ; 15* 453 s
Press any key to continue.
b)输出文本的数据:
{ {
int int
ID abc int int
NUM23 int int
ID A
Error $
Error @
J J
int int
ID i int int
ID n
int int
ID b
Error ,
ID c
TOC \o "1-5" \h \z J J
int int
NUM!
ID a
J J
int int
ID a2
J J
read read
ID n
ID n
NUM)
NUM2345 for for
ID i
NUM
ID i
<=<=
ID n
ID i
ID i
+ +
NUM
))
{ {
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 en ded 这一句都是不合法的四、讨论与分析
单词分类方法:
按照标识符、数字、分解符、注释符、运算符分类;其中需要注意的是
(>|<=)可以直接结束,也可以连接=,!必须与=连接才合法,对于/需要多 重考虑,即在注释这个部分也可能是/符号
构建词法分析程序的一般过程:、
1、 根据词法规则写出正则文法或者正则文法。
2、 为每一个正则表达式构造一个 NFA然后将多个NFA合并为一个NFA
3、 将NFA转化成DFA并且化简最小化DFA
4、 确定单词的输出形式
5、根据化简后的DFA和单词输出程序构造词法分析程序
五、附录:关键代码
//开始读取文件中的字符
ch = getc(fi n);
while(ch != EOF)
{
i = 0;
while(ch == ' ' || ch == '\n' || ch == '\t')
{
if(ch == '\n')
line ++;
ch = getc(fi n);
}
// 标识符处理
if(isalpha(ch))
{
while(isalpha(ch) || isdigit(ch))
{
buff[i++] = ch;
ch = getc(fi n);
}
buff[i] = '\0';
// 保留字
int n = 0;
while((n < 8) && strcmp(buff,keyword[n]))
n++;
if(n < 8)
fprin tf(fout,"%s\t%s\n",buff);
else
fprin tf(fout,"%s\t%s\n","ID",buff);
}
// 数字处理
else if(isdigit(ch))
{
// 单个数字“ 0”
if(ch == '0')
{
buff[0] = ch;
buff[1] = '\0';
fprin tf(fout,"%s\t%s\n","NUM",buff);
ch = getc(fi n);
}
// 数字的组合
else
{
while(isdigit(ch))
buff[i++] = ch;
<烟哮>
总丄匸匸nq
(H hh lp)±=
egoo)6 H ip
召 Hofcnq
(0 A (llop」o/v\2qnop)」lp」ls)± ① SO5
fees =
宀
enqfcnq-=5s&la&=」no&l£」d4
egoo)6 H ip
Job H
(0 A (LIO P」OM①-6U-S)」lp」ls)七
feco 曲
enq-MnN=-=5s&乍S&=」no&l£」d4
Job丄二匸nq
宀
egoo)6 H ip
buff[2] = '\0';
ch = getc(fi n);
fprin tf(fout,"%s\t%s\n",buff,buff);
}
else
{
buff[1] = '\0';
if(buff[0] == '!')
{
",buff);printf("Line %d\t%s\t%s\n",line," 错误
",buff);
fprin tf(fout,"%s\t%s\n","Error",buff);
}
else
{
fprin tf(fout,"%s\t%s\n",buff,buff);
}
}
}
// 注释
else if(ch == '/')
ch = getc(fi n);
if(ch == '*')
{
char chi = getc(fi n);
while(true)
{
if(ch1 == EOF)
{
line,"printf("Line %d\t%s\t 没有匹配! \n",
line,"
break;
}
ch = ch1;
ch1 = getc(fi n);
if(ch =='*' && ch1 == '/') break;
}
ch = getc(fi n);
}
else
buff[O] = '/';
buff[1] = '\0';
// 输出单分界符'/'
fprin tf(fout,"%s\t%s\n",buff,buff);
}
}
else
{
buff[0] = ch;
buff[1] = '\0';
flag = 3;
错误:"
错误:",buff);
prin tf("Li ne %d\t%s\t%s\n", li ne," fprin tf(fout,"%s\t%s\n","Error",buff);
}
}
fclose(fi n);
fclose(fout);
retur n flag;