大家好，又见面了，我是你们的朋友全栈君。
用C语言米用模拟DFA算法编写一个扫描器
/*
第一章：相关知识
DFA定义：一个确定的有穷自动机(DFA) M是一个五元组：M= ( K,厶f, S, Z)其中
0K是一个有穷集，它的每个元素称为一个状态；
工是一个有穷字母表，它的每个元素称为一个输入符号，所以也称工为输入符号字母
表；
f是转换函数，是 KX》tK的映射，即，如 f (ki, a) =kj,
(ki € K, kj € K)就意味着，当前状态为ki,输入符为a时，将转换为下一个状态 kj,
我们把kj称作ki的一个后继状态；
S € K是唯一的一个初态；
Z??K是一个终态集，终态也称可接受状态或结束状态。
第二章：题目
用C语言米用模拟DFA算法编写一个扫描器(词法分析器)用来识别：
由任意个a或b开始后接aa再自加或自减1的字符串，即正规式r=(a|b)*aa(+|-)1描述的语 言 L (r)
该词法分析器的任务：
滤掉源程序中的无用成分，如空格；
识别正规式r=(a|b)*aa(+|-)1描述的字符串。
从键盘读入或打开文件读入字符串，词法分析器读入字符ywe串后扫描源字符串，
若发现符合符合正规式r描述的字符串时，输出“ye或”可接受”或可识别”
否则输出“ n或’不可识别”。
第三章：分析
第一节?
K有10个状态，也就是10个元素: 0，也就是开始状态’a’，转到状态 s1’b’，转到状态 s2
K有10个状态，也就是10个元素: 0，也就是开始状态
‘a’，转到状态 s1
‘b’，转到状态 s2
状态S3:从s2开始接受了一个字母’a’，转到状态S3
状态s4:从s3开始接受了一个字母’a’，转到状态s4
状态S5:如果s1已经连续接受了至少两个字母’a’,从s4开始接受一个符号 ‘+’，转到状
态s5。
从s4开始接受了一个符号’+’,转到状态S5。
状态S6:如果s1已经连续接受了至少两个字母’a’,从s4开始接受一个符号’-‘，转到状
态s6。
或
从S4开始接受了一个符号’-‘，转到状态s6。
状态S7:从S5或S6开始接受了一个数字’1’，转到S7。
状态S8:从S7开始接受了一个字符串结束符号’\0’，转到状态S8。【这是成功状态】
状态s9:【这是出错状态】 第二节 .
根据正规式(a|b)*aa(+|-)1 ，我们可以分析出 习包含的字母有：a,b,+,-,1 第三节 .
根据正规式 (a|b)*aa(+|-)1 ，我们分析出转换函数 f 有：
F[0]. s0 –(输入一个字母 ‘a’) –> s1
F[1]. s0 –(输入一个字母 ‘b’) –> s2
F[2]. s1 –(输入一个字母 ‘a’) –> s1
F[3]. s2 –(输入一个字母 ‘b’) –> s2
F[4]. s2 –(输入一个字母 ‘a’) –> s3
F[5]. s3 –(输入一个字母 ‘a’) –> s4
F[6]. 如果状态 s1 中已经累积有至少两个字母 ‘a’
s1 –(输入一个符号 ‘+’) –> s5
F[7]h. s4 –(输入一个字母 ‘+’) –> s5
F[8]. 如果状态 s1 中已经累积有至少两个字母 ‘a’
s1 –(输入一个符号 ‘-‘) –> s6
F[9]. s4 –(输入一个字母 ‘-‘) –> s6
F[10]. s5 –(输入一个数字 ‘1’) –> s7
F[11]. s6 –(输入一个数字 ‘1’) –> s7
F[12]. s7 –(输入一个字符串结束符’\0′) –> s8(成功状态)
F[13].其他情况，统一进入状态s9(出错状态)
第四节 .
根据正规式(a|b)*aa(+|-)1 ，我们分析出【唯一的】初态 S即K中的s0
第五节 .
,s9(出根据正规式(a|b)*aa(+|-)1，我们分析出结束状态有两个，即K中的s8(
,s9(出
错状态 ) */
#include /* 下面的一组全局参数是作为自动机的参数 */
// 正则式
const char regex[]=”(a|b)*aa(+|-)1″;
// 状态集合
int states[10]={0};
// 状态总数
const int statesAmount = sizeof(states)/sizeof(int);
// 可接受的字符集合
const char letterSet[]=”ab+-1″;
// 开始状态
const int startStateId=0;
// 可接受的结束状态集 const int endStateIds[]={8,9};
// 可接受的结束状态总数
const int endStates
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/126746.html原文链接：https://javaforall.net
