CN103544142B - 一种状态机 - Google Patents

Abstract

本发明实施例提供一种状态机，所述状态机包括：规则模块，用于预先制定待识别字符集的划分规则，所述划分规则包括划分字符集所依据的特征；编辑模块，用于按照所述划分规则中划分字符集所依据的特征为状态机编辑正则表达式；预分类模块，用于利用所述划分规则对待识别字符集中的字符进行预分类；状态识别模块，用于利用所述正则表达式识别经过划分的待识别字符集。

Description

一种状态机

技术领域

本发明涉及计算机技术领域，特别涉及一种状态机。

背景技术

词法分析（lexical analysis）是计算机语言学的基本功能之一，用于定义单词的组成方法。进行语法分析的程序或者函数称为词法分析器（Lexicalanalyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

词法分析的第一阶段为识别所处理的单词中包含的字符集，该过程通常基于状态机。状态机为描述单词组成方法的图形，状态机由状态点和转换箭头组成，表示在一定的输入条件下，状态转换的过程。一个状态机和一个正则表达式相对应。

现有的状态机主要有非确定性有限状态机和确定性有限状态机两种；其中非确定性有限状态机为在一定的输入条件下，状态转换不唯一的状态机；确定性有限状态机为在一定的输入条件下，状态转换唯一的状态机。

现有的状态机所包含的状态与状态转换一般有上百个，由于数量大，所以使状态机的复杂性非常高，而状态机的高复杂性导致了编程语言在微系统上的实现有一定困难，并且导致处理字符的速度缓慢。

发明内容

有鉴于此，本发明的目的在于提供一种状态机，通过对字符的预分类将多种具有相同特征的字符统一为一个特征值，实现状态数量的减少，提高状态机的运行速度。

为实现上述目的，本发明有以下技术方案：

一种状态机，其特征在于，所述状态机包括：

规则模块，用于预先制定待识别字符集的划分规则，所述划分规则包括划分字符集所依据的特征；

编辑模块，用于按照所述划分规则中划分字符集所依据的特征为状态机编辑正则表达式；

预分类模块，用于利用所述划分规则对待识别字符集中的字符进行预分类；

状态识别模块，用于利用所述正则表达式识别经过划分的待识别字符集。

所述规则模块包括：

第一规则单元，用于以大写字母、小写字母、数字和下划线作为划分字符集所依据的特征制定待识别字符集的划分规则。

所述规则模块包括：

第二规则单元，用于以名词、动词、代词、数量词和标点符号作为划分字符集所依据的特征制定待识别字符集的划分规则。

所述规则模块还包括：

特征值单元，用于为每个特征定义一个特征值。

所述预分类单元包括：

特征值输出单元，用于判断待识别字符集中的字符是否符合划分规则中的任意一个特征，如果符合则输出该特征的特征值。

通过以上技术方案可知，本发明存在的有益效果是，通过划分规则将待识别字符集中的字符预分类，从而将几十种甚至上百种字符根据特征简化为有限的若干个种类，并且根据所述特征编辑出简化的正则表达式，则该正则表达式对应的状态机仅对小数量特征进行识别，从而实现状态机的简化，提高了状态机运行的速度。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例所述状态机结构示意图；

图2为本发明另一实施例所述状态机结构示意图；

图3为本发明所述字符预分类流程图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明公开了一种状态机，参照图1所示，所述状态机具体为：

规则模块，用于预先制定待识别字符集的划分规则，所述划分规则包括划分字符集所依据的特征；

编辑模块，用于按照所述划分规则中划分字符集所依据的特征为状态机编辑正则表达式；

预分类模块，用于利用所述划分规则对待识别字符集中的字符进行预分类；

状态识别模块，用于利用所述正则表达式识别经过划分的待识别字符集。

本实施例为本发明所述状态机的一个基础实施例，本实施例存在的有益效果是，通过划分规则将待识别字符集中的字符预分类，从而将几十种甚至上百种字符根据特征简化为有限的若干个种类，并且根据所述特征编辑出简化的正则表达式，则该正则表达式对应的状态机仅对小数量特征进行识别，从而实现状态机的简化。

参照图2所示为本发明所述状态机的另一个具体实施例。本实施例中所述状态机具体包括：

规则模块，用于预先制定待识别字符集的划分规则，所述划分规则包括划分字符集所依据的特征；

本实施例中所述规则模块包括：

第一规则单元，用于以大写字母、小写字母、数字和下划线作为划分字符集所依据的特征制定待识别字符集的划分规则；

第二规则单元，用于以名词、动词、代词、数量词和标点符号作为划分字符集所依据的特征制定待识别字符集的划分规则；

特征值单元，用于为每个特征定义一个特征值；

编辑模块，用于按照所述划分规则中划分字符集所依据的特征为状态机编辑正则表达式；

预分类模块，用于利用所述划分规则对待识别字符集中的字符进行预分类；

本实施例中所述预分类模块包括：

特征值输出单元，用于判断待识别字符集中的字符是否符合划分规则中的任意一个特征，如果符合则输出该特征的特征值；

状态识别模块，用于利用所述正则表达式识别经过划分的待识别字符集。

本实施例中采用宏定义的方式对特征值进行定义，假设按照所述第一规则单元中所制定的划分规则对字符进行划分，则所述宏定义表达式为：

const int a2z=512,A2Z=513,z2n=514,underscore=515,others=516

其含义是，大写字母A~Z在程序语言中的表示符号为A2Z，小写字符a~z在程序语言中的表示符号为a2z，数字0~9在程序语言中的表示符号为z2n，下划线在程序语言中的表示符号为underscore，不符合上述特征的情况在程序语言中的表示符号为others；本实施例中特意加入了others这一特征，也就是如果某一字符不符合大写字母、小写字母、数字或下划线四者任意一个特征，则认为该字符属于others这一特征，输出特征值为516。

本实施例中定义A2Z的特征值为513，a2z的特征值为512，z2n的特征值为514，underscore的特征值为515，others的特征值为516。实际应用中特征值可以定义为任何数字。以上分类方式与特征值的定义为本实施例中采取的优选方案，在实际情况中可以在不影响整体方案的前提下采取其他方式。

所述编辑模块根据上述划分规则为状态机编辑正则表达式，本实施例中的正则表达式为：

{a2z,A2Z,underscore}{a2z,A2Z,underscore,z2n}*

该正则表达式的含义为：字符集中第一个字符为a2z、A2Z或underscore，其他若干字符为a2z、A2Z、underscore或z2n；也就是表示该正则表达式不允许字符集的第一个字符为数字。

同样按照上述划分规则，对待识别的字符集进行划分，即在状态识别模块识别待识别字符集之前，对待识别字符集中的字符进行预分类。

本实施例中特别规定，a2z为第一特征，A2Z为第二特征,z2n为第三特征,underscore为第四特征,others为第五特征。所述特征值输出单元在判断某一字符特征并输出特征值的时候，从第一特征到第五特征依次判断该字符是否与该特征匹配，若该字符匹配某一特征则输出该特征的特征值，若不匹配则继续用下一个特征进行判断，具体参见图3。

此处以待识别字符集为英文单词“English”为例，待识别字符集共包括7个字符。

待识别字符集的第一个字符为“E”，判断字符“E”是否符合第一特征即a2z，结果为不符合；再判断该字符是否符合第二特征即A2Z，结果为符合，则输出第二特征的特征值513。

待识别字符集的第二个字符为“n”，判断字符“n”是否符合第一特征a2z，结果为符合，则输出第二特征的特征值512。

按照上述方式依次判断该字符集中的其他所有字符，得到每一个字符的特征值，即完成了待识别字符集的预分类。

传统不存在上述预分类过程的情况下，一般认为：大写字母A~Z为26个特征，小写字母a~z为26个特征，数字0~9为10个特征，下划线为1个特征，其他情况为1个特征，总计64个特征，利用上述64个特征编辑正则表达式之后，正则表达式对应的状态机必须对上述全部特征及其转换状态与反馈状态进行识别，状态机需要识别的特征达到数百个。

按照本发明所述方法将待识别字符集预分类，将上述64个特征简化为本实施例中给出的5个特征，并且利用上述5个特征编辑正则表达式。相应的本发明实施例所述正则表达式对应的状态机所需要识别的特征数量上大大减少。本发明由此实现了状态机的简化，提高状态机的运行速度。

同理，再以本实施例当中所述第二规则单元以名词、动词、代词、数量词和标点符号作为划分字符集所依据的特征制定待识别字符集的划分规则为例，同样可以实现简化状态机的目的。

以中文句子“我是一个兵”为例，可以根据第二规则单元中的划分规则，将“我”划分为代词，“是”划分为动词，“一”和“个”均属于数量词，“兵”划分为名词，并且根据设置输出对应的特征值。本实施例中除划分规则改变之外，状态机中其余模块和单元的工作原理与上述完全相同，所以不再重复描述。

本实施例存在的有益效果是，通过对于所述状态机更加具体的公开的和描述，并且配合实际字符集和划分规则进行距离说明，使得本实施例所述状态机在图1所示实施例的基础之上，内容更加完整清晰。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

Claims (1)

1.一种状态机，其特征在于，所述状态机包括：

规则模块，用于预先制定待识别字符集的划分规则，所述划分规则包括划分字符集所依据的特征；

编辑模块，用于按照所述划分规则中划分字符集所依据的特征为状态机编辑正则表达式；

预分类模块，用于利用所述划分规则对待识别字符集中的字符进行预分类；

状态识别模块，用于利用所述正则表达式识别经过划分的待识别字符集；

其中，所述规则模块包括：

第一规则单元，用于以大写字母、小写字母、数字和下划线作为划分字符集所依据的特征制定待识别字符集的划分规则；

所述规则模块包括：

第二规则单元，用于以名词、动词、代词、数量词和标点符号作为划分字符集所依据的特征制定待识别字符集的划分规则；

所述规则模块还包括：

特征值单元，用于为每个特征采用宏定义的方式定义一个特征值；

所述预分类单元包括：

特征值输出单元，用于判断待识别字符集中的字符是否符合划分规则中的任意一个特征，如果符合则输出该特征的特征值。