用C语言采用模拟DFA算法编写一个扫描器.doc资源-CSDN文库

133 浏览量 2022-11-17 06:23:05 上传评论收藏 28KB DOC 举报

资源推荐

资源详情

资源评论

用 C 语言采用模拟 DFA 算法编写一个扫描器

/*

第一章：相关知识

DFA 定义：一个确定的有穷自动机（DFA）M 是一个五元组：M=（K，Σ，f，S，Z）其中

　　① K 是一个有穷集，它的每个元素称为一个状态；

　　② Σ 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称 Σ 为输入符号

字母表；

　　③ f 是转换函数，是 K×Σ→K 上的映射，即，如 f（ki，a）=kj，

（ki∈K，kj∈K）就意味着，当前状态为 ki，输入符为 a 时，将转换为下一个状态 kj，

我们把 kj 称作 ki 的一个后继状态；

　　④ S ∈ K 是唯一的一个初态；

　　⑤ ZK 是一个终态集，终态也称可接受状态或结束状态。

第二章：题目

用 C 语言采用模拟 DFA 算法编写一个扫描器（词法分析器）用来识别：

由任意个 a 或 b 开始后接 aa 再自加或自减 1 的字符串，即正规式 r=(a|b)*aa(+|-)1 描述的

语言 L（r）。

该词法分析器的任务：

（1）滤掉源程序中的无用成分，如空格；

（2）识别正规式 r=(a|b)*aa(+|-)1 描述的字符串。

从键盘读入或打开文件读入字符串，词法分析器读入字符 ywe 串后扫描源字符串，

若发现符合符合正规式 r 描述的字符串时，输出“yes”或“可接受”或“可识别”，

否则输出“no”或“不可识别”。

第三章：分析

第一节.

根据正规式(a|b)*aa(+|-)1，我们可以分析出 K 有 10 个状态，也就是 10 个元素：

状态 s0:这时候已经识别的字符个数为 0，也就是开始状态

状态 s1:从状态 s0 开始接受连续的字母 'a'，转到状态 s1

状态 s2:从状态 s0 开始接受连续的字母 'b'，转到状态 s2

状态 s3:从 s2 开始接受了一个字母 'a'，转到状态 s3

状态 s4:从 s3 开始接受了一个字母 'a'，转到状态 s4

状态 s5:如果 s1 已经连续接受了至少两个字母 'a',从 s4 开始接受一个符号 '+'，转

到状态 s5 。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

内容反馈

xinkai1688

粉丝: 322
资源: 8万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip