一种带通配符正则表达式的有穷自动机生成方法

摘要

本发明涉及一种带通配符正则表达式的有穷自动机生成方法，其特征在于，按照如下步骤实现：S1：根据带通配符正则表达式生成抽象语法树，并对该抽象语法树的每个节点编号；S2：根据抽象语法树计算每个节点的nullable(n)和每个节点的三个位置集合；S3：将抽象语法树根节点的firstpos（n0）作为第一个状态，存储到到状态集合中；遍历状态集合，若在遍历过程中产生新的状态，则将新的状态加入到状态集合中，记录转换关系；在遍历每个状态时，计算该状态中的每个字符的跟随状态，并根据条件存放到状态集合中。本发明所提出的一种带通配符正则表达式的有穷自动机生成方法，有效的提高了编译的效率，降低了对内存的消耗。

主权项

一种带通配符正则表达式的有穷自动机生成方法，其特征在于，按照如下步骤实现：S1：根据带通配符正则表达式生成抽象语法树（T），并对该抽象语法树（T）的每个节点编号；S2：根据步骤S1中所生成的所述抽象语法树（T）计算每个节点的nullable(n)和每个节点的三个位置集合；其中，nullable(n)表示节点n代表的子表达式是否可以为空；三个位置集合分别表示为：firstpos(n)、lastpos(n)和followpos(p)，且firstpos(n)表示节点n代表的子树的开始字符的位置集合，lastpost(n) 表示节点n代表的子树的结束字符的位置集合，followpos(p)表示节点p之后的可以跟随的节点的位置集合；S3：根据步骤S1和步骤S2中得到的结果，生成有穷自动机（DFA），并将输出的有穷自动机（DFA）表示为D；将所述抽象语法树（T）根节点的firstpos(n0)作为第一个状态，并存储到有穷自动机（DFA）的状态集合（Dstates）中，然后开始遍历状态集合（Dstates），直到状态集合（Dstates）中的所有状态都完成遍历；若在遍历过程中产生新状态，且在状态集合（Dstates）中不存在该新状态，则该新状态存储到状态集合（Dstates）中，若在状态集合（Dstates）中存在该新状态，则不将该新状态存储到状态集合（Dstates）中；在判断该新状态过程中，不论该新状态是否存在于状态集合（Dstates）中，均记录转换关系，并将该转换关系存储到有穷自动机（DFA）的状态之间的转换关系集合（Dtrans）中；其中，在遍历状态集合（Dstates）中每个状态时，计算该状态中的每个字符的跟随状态，并根据条件存放到状态集合（Dstates）中。