无符号数的有穷自动机的实现.doc

内蒙古工业大学信息工程学院
实验报告成绩： 指导教师审核（签名）： 年 月 日
预习报告□ 实验报告□
无符号数的有穷自动机的实现
(一)实验目的
无符号数的有穷自动机的实现目的是使学生掌握文法的形式描述，穷自动机的概念。将文法转换成有穷自动机的方法，理解出错处理程序思想，如何用状态矩阵实现一个穷自动机的机内表示。
(二)实验内容
1．无符号数的BNF描述
1) <无符号数> à d <余留无符号数> | . <十进制数> | e <指数部分>
2) <余留无符号数>àd <余留无符号数> | . <十进制数> | e <指数部分>|ε
3) <十进制小数> à d <余留十进制小数>
4) <余留十进制小数> e <指数部分> | d <余留十进制小数> | ε
5) <指数部分> à d <余留整指数> | + <整指数> | - <整指数>
6) <整指数> à d <余留整指数>
7) <余留整指数> à d <余留整指数> | ε
2．将G[<无符号数>]文法转换成有穷自动机。
3．构造状态矩阵；将有穷自动机的状S1 S2 ……Sn及输入的字a1 a2 ……am 构成一个n*m的矩阵。
4．用状态矩阵设计出一个词法分析程序。
5．扫描无符号数，根据文法给出无符号数出错的位置。
(三)实验要求
1.学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告
2．用C语言或其它高级语言编写程序
3．写出实验报告

实验报告成绩： 指导教师审核（签名）： 年 月 日
预习报告□ 实验报告□
无符号数的有穷自动机的实现
(一)实验目的
通过上机实习，熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。
(二)实验内容
1．无符号数的BNF描述
1) <无符号数> à d <余留无符号数> | . <十进制数> | e <指数部分>
2) <余留无符号数>àd <余留无符号数> | . <十进制数> | e <指数部分>|ε
3) <十进制小数> à d <余留十进制小数>
4) <余留十进制小数> e <指数部分> | d <余留十进制小数> | ε
5) <指数部分> à d <余留整指数> | + <整指数> | - <整指数>
6) <整指数> à d <余留整指数>
7) <余留整指数> à d <余留整指数> | ε
2．无符号数的有穷自动机实现的思想
用0-----表示无符号数； 用1-----表示余留无符号数；
用2----表示十进制小数；用3-----表示余留十进制小数；
用4-----表示指数部分； 用5-----表示整指数；
用6-----表示余留整指数。
输入无符号数序列，从左到右扫描，遇到“#”号结束扫描。设一个字符数组，接收输入的无符号数，对输入的无符号数逐一进行分析，用一个中间变量接收当前字符。当前字符值发生错误时，输出错误信息；当前字符值正确时，分析下一个字符，反复判断，直至分析完毕。
3．无符号数的有穷自动机（Z表示结束符）
无符号数有穷自动机由图1所示。

图1 有穷自动机
4．无符号数有穷自动机的状态转换矩阵
无符号数有穷自动机的状态转换矩阵由表1所示。

d
e
·
＋
－
ε
0
1
4
2
Φ
Φ
Φ
1
1
4
2
Φ
Φ
Z
2
3
Φ
Φ
Φ
Φ
Φ
3
3
4
Φ
5
Φ
Z
4
6
Φ
Φ
Φ
5
Φ
5
6
Φ
Φ
Φ
Φ
Φ
6
6
Φ
Φ
Φ
Φ
Z

(三)实验要求
1.学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告
2．用C语言或其它高级语言编写程序
3．写出实验报告
(四)程序流程图

是#？
是数字?
Y
是数字?
读一个字符
Y
是#？
出错
结束
Y
初 始 化
读一个字符
是否为#？
是数字?
读一个字符
是#？
N
是小数点.
读一个字符
是数字？
出错
读一个字符
是#？
N
是指数e
读一个字符
出错
是符号+/ -
读一个字符
Y

Y

N

Y

N

N
Y

N

Y
Y

Y
Y

N
N
N

出错

N

(五)程序代码
// zhangtianyou.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdio.h>
#define LEN 30

int main()
{
char number[LEN]={0};
lab0:int i=0;
printf("Please input a number:\n");
scanf("%s",number);
if(number[i]=='#')
{
printf("input this number is right!\n");
goto last;
}
else
{
lab1:if(number[i]>='0'&&number[i]<='9')
{
i++;
if(number[i]=='#')
{
printf("input this number is right!\n");
goto last;
}
else goto lab1;

}
else
{
if(number[i]=='.')
{
i++;
do{
if(number[i]>='0'&&number[i]<='9')i++;
else
{
printf("input this number is error!\n");
goto last;
}
}while(number[i]!='#');
printf("input this number is right!\n");
}
else
{
if(number[i]=='e'||number[i]=='E')
{
i++;
if(number[i]=='+'||number[i]=='-')
{
lab2: i++;
if(number[i]=='#')
{
printf("input this number is right!\n");
goto last;
}
else
{
if(number[i]>='0'&&number[i]<='9')goto lab2;
else printf("input this number is error!\n");
}
}
else
{
lab3:if(number[i]>='0'&&number[i]<='9')
{
i++;
if(number[i]=='#')printf("input this number is right!\n");
else goto lab3;
}
else printf("input this number is error!\n");
}
}
else
printf("input this number is error!\n");
}
}

}
last:printf("");
goto lab0;
return 0;
}
(六) 程序运行结果测试
测试结如下图，测试结果符合实验要求。能够对不确定的有穷自动机BNF到确定的有穷自动机DFA的实现。

(七)调试程序出现的问题及解决的方法
实验中编程基本没什么问题，就是刚开始对实验的理解没有吃透，不知道怎么编程，但是，看了老师编写的试验流程图，对实验的原理和实验的实现有了清晰地思路。

(八)实验心得体会
通过本次试验，让我知道了我们编写程序的编译器是怎么编译程序和怎么工作的，也对编译课的理论知识有了一些加深的了解。这次试验通过对于无符号数有穷自动机的实现，运用了词法分析，从左到右扫描字符对原程序进行扫描，产生一个个单词序列，用以语法分析，其它阶段。词法分析从不确定的有穷自动机BNF到确定的有穷自动机DFA的实现，最后确定的有穷自动机DFA的最小化。这次试验通过实践把老师讲的理论知识得到了充分的展示，对我们的编程打下了坚实的理论知识。所以，这次试验让我受益匪浅。

第 页