编译原理 实验 有限自动机
数学与信息工程学院
《编译原理》
实验报告二
实验名称：有限自动机的运行 实 验 室： 班 级： 姓 名： 学 号：
有限自动机的运行
一、
实验目的
1. 理解有限自动机的作用；
2. 利用状态图和状态表表示有限自动机； 3. 以程序实现有限自动机的运行过程;
4. 利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的十六进制；
二、 实验环境
操作系统：window xp
编写环境：visual c++ 编写语言：c 语言 三、
实验内容
1. 简单介绍你所设计的有限自动机。
有符号十六进制有限自动机
能识别（+|-）dd*(.dd*| ε)h|H 格式的字符串，其中d 为0-9，A-F ，a-f ；
例如，+2.fh, -f.2H, f.fh， 6h 均为合法十六进制数，而b.h ，.ffh, 5.6.fh, zzh, 不合法十六进制数
状态图：
d 为0-9，A-F ，a-f ，0为初始状态，5为结束状态，输入必须以h ，H 结尾
ff 均为
3. 测试数据和结果。
四、 实验结果
经测试程序均能识别各种有符号十六进制数，各个状态之间的转换也没有出错，程
序正确，功能能够实现。
五、 调试分析
一开始程序中字符跟数字的判断是分开的，所以状态表多了完全相同的一列，调中发现这两列可以合并，精简代码和空间，修改代码实现精简。
六、 实验小结
由于有模板，所以思考时间很少，程序编写是思路比较清晰，所以调试基本没有出错，基本上时间均用在编写代码，在无符号，有正符号，有负符号的考虑上无法做到一个很好的缩减状态，所以多扩展了一个状态表示有符号的状态。
了解了自动机的工作方式，能够很有结构的结局一类问题。
附录：源代码
#include #include #include #define F 0 #define RIGHT 1 #define DOT 2 #define H 3
bool IsRightWord(char ch) /*判断是否为a-f,A-F, 这里的ch 已经被转换成了大写，所以只需判断是否为A-F*/ {
if(ch >= 'A' && ch
}
int state[6][4]={ //状态转移表 1,2,0,0, };
0,2,0,0, 0,2,3,5, 0,4,0,0, 0,4,0,5, 0,0,0,0,
bool Accept(char * str)//判断是否为正确的有符号十六进制数 {
int s=0;
int len = strlen(str); int i;
for (i=0;i
if(str[i]=='-'||str[i]=='+') { }
else if(isdigit(str[i])||IsRightWord(toupper(str[i]))) {
if(state[s][RIGHT] == 0) return false; s = state[s][RIGHT];
if(state[s][F] == 0) return false; s = state[s][F];
}
else if(str[i] == '.') {
}
}
if(state[s][DOT] == 0) return false;
s = state[s][DOT]; }
else if(toupper(str[i])=='H') { }
if(state[s][H] == 0) return false; s = state[s][H];
if(s == 5) return true; else return false;
int main () { }
char str[1005];
while (gets(str)!=NULL) {
if(Accept(str)) { }
printf("Accept!\n");
else { printf("Not Accept!\n"); }
}
return 0;