欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基于有限状态自动机的数据类型识别功能(1)

程序员文章站 2022-09-27 20:19:42
有限状态自动机(FSM):是一种表达某一状态到另一状态发生转化的数学模型。 例如:在长跑比赛开始时 我处于等待的状态下,待裁判喊 预备 时,我就会从等待状态转换到预备状态。听到裁判的枪声时,我就从预备状态转换到奔跑状态 。这个过程就相当于有限状态自动机。 FSM的状态就是一个事件当前所处于的情况。 ......

 

有限状态自动机(fsm):是一种表达某一状态到另一状态发生转化的数学模型。

例如:在长跑比赛开始时 我处于等待的状态下,待裁判喊 预备 时,我就会从等待状态转换到预备状态。听到裁判的枪声时,我就从预备状态转换到奔跑状态 。
这个过程就相当于有限状态自动机。

基于有限状态自动机的数据类型识别功能(1)

 

fsm的状态就是一个事件当前所处于的情况。

有限状态自动机在编程中的应用十分广泛

例如:对输入的字符进行判断 判断字符串组成的数字属于整型还是浮点型。 同时它也是词法分析的核心 可用于分析一串字符中给的组成词的含义。

因为最近在学习编译原理,所以想实现一个简单的fsm。 计划使用java语言。希望能做一个分析所输入的字符串,解析出字符串组成的字串属于什么数据类型。

准备

在编写fsm程序之前需要先画出状态转化图,在我的构想里:

1.整数是只由0~9的数字组成。

2.浮点数比整数多了一个小数点,并且小数点不能出现在数字的第一位和最后一位。

3.增加科学计数法数字,例如:1.2e2   其中用e2代替10的二次方 e的左边必须是小数,并且小数点只能出现在紧跟着第一位数字的后面。

4.可以对一行字符串进行解析。

基于上面4点,我大致画了一下状态转换图:

基于有限状态自动机的数据类型识别功能(1)

红色字体代表8种状态

箭头上的 0-9 e . - 带当输入的字符位他们时

黄色下划线代表改状态可以输出结果了

蓝色代表循环

例如:初始状态为0时,当输入0-9任意一个字符时 状态0向状态1转变。

当继续输入0-9时状态不变,但是状态1在输入结束后可以输出 int。

在状态1的前提下若输入 小数点,那么就会向状态2转变。状态2不支持输出。

在状态2的前提下输入0-9那么就会向状态3转变,同时,状态3支持输出。以此类推

状态1可以输出int (123)

状态3可以输出float(123.4)

状态6可以输出科学计数法(1.2e2)

状态7可以输出科学计数法(1.2e-2)

使用二维数组表示各状态

如何才能将这些状态信息表达出来,我使用的是二位数组

数组的纵轴表示8中状态

数组横轴表示输入的字符

数组元素表示下一跳状态

基于有限状态自动机的数据类型识别功能(1)

根据状态转换图可以把二维表填满

比如:

第0行的第0列 表示 在状态0时输入字符0

第0行的第1列 表示 在状态0时输入字符1

第0行的第10列 表示 在状态0时输入字符.

第0行的第11列 表示 在状态0时输入字符e

第0行的第12列 表示 在状态0时输入字符-

数组元素表示下一跳状态值

基于有限状态自动机的数据类型识别功能(1)

简单填一下 -1表示错误状态 大概是这个样子 貌似多了一行,而且填的时候可能有填错的。不过大概就这样先吧 哈哈。

通过观察发现 可以进行简化 ,对纵轴的下标0-9统一用下标0来表示吧

基于有限状态自动机的数据类型识别功能(1)

这样子就二维数组就没那么大了。

下一次用代码一步步实现