1 简介

2 语法树

语法树结点设计

首先根据支持的特殊字符和普通字符定义一系列语法树结点. 目前支持的通配符有: “.?+*|”等, 分别表示匹配任意字符, 0个或1个字符, 1个或多个字符, 任意个字符, 或关系, 此外还有一个隐式的连结关系. 因此定义了如下语法树结点:

  1. StarNode: 表示*
  2. DotNode: 表示.
  3. CharNode: 表示任意字符
  4. UnionNode: 表示|
  5. ExistNode: 表示?
  6. CatNode: 表示连结关系

由于+可以被*代表, 例如a+表示一个或多个a, 等价于aa*. 因此没有为+专门设置一个语法树结点.

每个结点都继承于父节点ParseTreeNode, 每个结点内根据自身是几元操作符拥有不同的私有变量. 例如StarNode, ExistNode代表的是一元操作符, 因此只有一个指向其他结点的指针, 而UnionNode和CatNode代表的是二元操作符, 因此有左右两个子结点. DotNode和CharNode可以看做代表零元操作符, 是整棵语法树的最终叶子结点, 不同的是CharNode可以代表一个特定的字符, 因此也需要一个私有变量来保存这个特定的字符.

语法树设计

对于”a.b*|ab”这样一个正则表达式, 针对上面设计的语法树结点, 一颗典型的语法树如下图所示:

parse_tree2.png

语法树解析

为了得到上面这样一棵树, 需要parser来对字符串文本进行解析. 我使用了从右到左的方法. 这是因为一元通配符表达的关系是它左边那个元素, 这样从右到左解析时, 首先看到的是通配符, 根据不同通配符可以决定往左看几个字符.

首先定义三个函数:

  1. parse_whole_tree: 该函数接受一个字符串和起始结束地址, 负责在这个文本串的指定区间内解析出一颗语法树, 并返回语法树的根节点和新位置.
  2. parse_one_node: 该函数也接受一个字符串和起始结束地址, 负责从指定区间的最右边开始, 解析出一个独立结点, 然后返回解析得到的语法树结点以及解析完之后新的位置. 此处独立结点的意思是,
    1. 对于起始位置是零元操作符(包括普通字符)的, 直接返回这个零元操作符对应的结点(DotNode或者CharNode).
    2. 对于起始位置是一元操作符的, 返回一个完整的一元操作符. 完整的意思是指, 要一直解析下去直到这个一元操作符的子结点也完整或者子节点是一个零元操作符
  3. get_next_op: 该函数接受一个字符串和起始位置, 返回下一个二元操作符, 由于目前二元操作符只有Union和连结符, 所以返回的就是这两者之一.

可以看到, 对于一个正则表达式s, parse_whole_tree(s, 0, s.length())返回的就是s对应的语法树.

函数实现

  • get_next_op

    这个函数很简单, 从起始位置开始向左遍历, 如果连续两个普通字符, 返回连结符, 如果在此之前发现了一个’|’, 则返回Union符.

  • parse_one_node

    从起始位置开始检查字符, 分情况处理:

    1. 一元运算符: 新建一个对应的语法树结点如StarNode, ExsitNode, 然后调用parse_one_node获取下一个独立结点, 使之成为StarNode的子节点.
    2. ‘.': 新建一个DotNode并返回.
    3. ‘)': 从左向右找到第一个'(‘, 这样找到的左括号必然与这个右括号是一对, 然后对于这个区间内的字符串调用parse_whole_tree获取一个语法树
    4. ‘]': 从左向右找到对应的左方括号, 对其中的所有字符建立CharNode并用UnionNode串起来. 这一步动作通过辅助函数parse_bracket_node完成.
    5. 其他: 所有其他字符被看做是普通字符, 新建一个CharNode并返回.
  • parse_whole_tree

    首先调用parse_one_node, 从字符串最右边获取一个独立的结点, 然后进入循环: 首先获取下一个二元操作符, 接着在这个操作符左边继续调用parse_one_node获取一个独立节点, 然后根据二元操作符新建CatNode或者UnionNode将两个独立节点串起来. 最终遍历完成, 返回一颗完整的语法树.

3 根据语法树生成自动机

Automata类与State类

State类

State类表示一个状态, 它有三种类型:

  1. StartType
  2. NormalType
  3. EndType

还有三个函数:

  1. add_edge(char ch,State* s): 对State对象进行设置, 使得这个状态能接受字符ch, 并跳转到s.
  2. next_state(char ch, stack<State*> s): 寻找这个状态接受ch后的状态, 并加入到栈s中, 如果没有这样的跳转, 返回-1;
  3. next_epsilon_state(stack<State*> s): 寻找这个状态所有ε跳转, 并把ε跳转后的状态加入到栈s中.

Automata类

Automata类表示一个状态机, 它其实是多个State类的集合(状态的跳转信息存在于State类中), 但实际上只保存了初始状态和终止状态两个, 其他状态可以由初始状态推到得到.

NFA中状态机可能有多个起始状态和终止状态, 为了统一, 每个Automata类保存有一个起始状态一个终止状态, 同时, 这个起始状态可以ε跳转到真正的起始状态, 同样, 真正的终止状态可以ε跳转到状态机保存的终止状态, 这样做的缺点就是增加了冗余的状态的个数, 但是实现起来很方便.

Automata类除了两个getter函数分别返回起始状态和终止状态外, 只有一个功能性函数, accept(string s), 负责对字符串s运行状态机, 并返回这个字符串能否被状态机接受(即达到终止状态).

自动机生成

对于语法树的每个节点, 都有一个gen_automata方法, 负责为具体的结点生成具体的自动机. 为了避免每个结点在递归生成自动机时重复生成, 用一个私有成员变量self保存已经生成好的自动机. 下面举几个典型例子进行说明.

StarNode

gen_automata.png

其中Child Automata调用StarNode的子节点的gen_automata方法生成.

CharNode

gen_automata_charnode.png

UnionNode

gen_automata_union.png

gen_automata_union.png

自动机运行

这部分功能在Automata类的accept函数中实现, 首先定义两个栈

std::stack<State*> s1, s2;

再用两个指针sta1, sta2分别指向这两个栈, 并通过调用自动机起始状态State 对象的next_epsilong_state函数获取所有起始状态能经过ε跳转达到的状态, 存放于sta1中. 然后开始遍历输入字符串, 对于字符串的每个输入字符c, 遍历sta1 中存放的每个状态, 获取这个状态经过ε跳转或者接受c能达到的状态, 存放到sta2里. 当遍历完sta1后, sta1指向的栈成为空栈, sta2栈存放的都是输入c后自动机可能处于的状态的集合. 这时只要简单的交换sta1和sta2, 就能开始下一次循环. 最终当整个输入字符串都处理完毕, 检查sta1(之前和sta2换了一下, 此时sta2为空, sta1存放着最终可能处于的状态), 如果sta1中存在终止状态, 则说明这个输入字符串可以被自动机接受.

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>