dfa算法c语言,用c语言采用模拟dfa算法编写一个扫描器.docx

用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