什么是正则文法

正则文法是比较靠谱的文法。它在CFG的基础上继续进行限制:

每一个正则文法的规则只能是以下两个规则之一:

  • 形如\(A \rightarrow a\)的规则。
  • 形如\(A \rightarrow aB\)的规则。

可以看到这文法是很简单的,过于简单会引起不好用,所以我们也有“增强版”的正则文法,它多了一条规则:

  • 如果\(A, B, C...\)是正则文法左端的符号,那么\(X = ABC...\)也是正则文法。

这个“增强”实际上是允许正则文法进行连接,我们在后面会看到,它和原来的正则文法是完全等价的。

正则文法对应的自动机

自动机的使用是比较广泛的,我们在数字电路和网络协议中都看到过它的身影。在这里,我们使用的是“有限状态自动机”,它简单地说就是一张表或者一幅有向图,这张表或者这幅图记录着状态如何变化(以及什么是起始状态,什么是终止状态等等)。那么,它和正则文法是怎么联系起来的呢?

先不讨论“增强”型的正则文法,只讨论一般的正则文法。一个非常关键的想法是:把非终结符当作一种“状态”

这样抽象地说可能有点难以理解,我们来说一个具体的文法:

\[S \rightarrow aA\] \[A \rightarrow bB\] \[B \rightarrow cC\] \[C \rightarrow d\]

很容易可以看出来,这定义的是\(abcd\)这个字符串。

我们可以构想,有这样的一台机器,它输入一个字符串,输出一个布尔值,也就是说,如果这个字符串是“abcd”,那就输出真,否则输出假。

使用“把非终结符当作一种状态”的思想,可以让我们制造出来这种机器。

这机器的开始状态是\(S\),然后读入一个字符,如果为”a”,就进入\(A\)状态,在\(A\)状态,也读入一个字符,如果为”b”,就进入\(B\)状态,直至在\(C\)状态读入”d”后进入成功状态。

用图片来表示,就是这样:

1

(由于是自动生成的,符号可能不太一样)

如果没能执行刚才的操作,这机器就进入“失败”状态。这就解决了我们的判断问题。

你可能会问,这究竟有什么用呢?不就是匹配个字符串吗,需要这么麻烦?

我们经常研究一个问题“如何组合简单的东西来完成复杂的任务”。一个经久不衰的答案是“封闭性”。而正则文法和自动机恰恰是封闭的。

什么意思呢?如果你把一个非终结符和其对应的自动机看作一种“运算单元”,你就会发现,一个或多个“运算单元”可以通过以下的运算生成另一个更复杂的运算单元:

  1. \(A = aB\) 将一个终结符和一个非终结符连接,会生成一个可以匹配更长语言的非终结符
  2. \(A = BC\) 把两个终结符连接起来,会生成一个匹配更长语言的非终结符
  3. \(A = B \| C\) 将一个终结符和一个终结符用 “|” 连接, 可以生成一个匹配它们两个所对应的语言的终结符

另外的几个操作暂时不引入了,我们需要思考的是,刚才我们说把非终结符当作一种“状态,而这里,我们实际上做的是把非终结符当作一个状态机

通过非终结符之间的运算,状态机可以进行组合,以形成更复杂的状态机。这样一来,我们就可以用这种结构构造相当复杂的匹配方法。

把正则文法改写为非确定型自动机

我们前面已经说了,我们实际上是把非终结符当作一个状态机,所以,我们只要研究各种文法组合如何改写成状态机的组合就好。

首先来看最简单的

\[A = aB\]

\(B\) 是一个状态机,那么\(A\)就应该是一个新的状态机,它的开始状态由a变成B的开始状态,类似于这样:

2

变为

3

注意我画的状态机的尾部指向的是\(\epsilon\),而不是成功状态\(<>\),这是为什么呢?

因为在状态机没有构造好的时候,状态机的尾部相当于是“游离”的,我们有两种情况:

  • 要么在最后的构造中,将尾部指向\(<>\)状态
  • 要么在某一次构造中,将尾部指向其他状态

然后我们来看看两个非终结符之间的连接:

\[A = BC\]

这应该如何处理呢?答案很简单,就是将\(B\)状态机的尾部,指向\(C\)状态机的开始状态,然后把新状态机的尾部设置为\(C\)状态机的尾部就好。

例如,\(B\)状态机还是上次的B状态机,而\(C\)状态机为:

4

那么,\(A\)状态机就会是:

5

其他的操作符也大抵类似,不过要注意的是我们这里保证每一次操作产生的自动机开始状态都有且仅有一个

把NFA改写成DFA

NFA最大的特点是允许“不确定性”,也就是说,对于一个给定的状态转移因子(比如说”a”),有可能有两种不同的状态转移方法。

例如下图:

6

第“6”号状态如果遇到了“a”,那么它有两种可能,一种是转移到自己本身,另一种是转移到第”7”号状态。

有编程经验的人立刻会想到,如果要解决这个问题,恐怕需要使用一些图的搜索技术,比如深度优先搜索–先转移到自己,如果后面的转移失败就转移到第”7”号状态。

而这样的方法,效率是不佳的。有没有一种方法,可以使得我们不是“搜索”,而是线性地“匹配”呢?

这就是把NFA改写为DFA的原始动力。

至于如何改写呢?我懒得写了,请自行查询相关资料吧。

实现一个正则表达式引擎

有了上面的思考,我们就可以来实现一个正则表达式解析引擎了。具体的实现,见此处

第一步 解析正则表达式

必须指出,正则表达式本身不是正则语法。因为正则语法不可能匹配一个可以无穷地嵌套括号的语言,而正则表达式允许括号的无穷嵌套。

所以,要解析正则表达式,必须利用解析CFG的一些办法。

不过,一个比较好的消息是,可以利用解析数学表达式的算法–调度场算法解析正则表达式。

解析的结果并不是一颗树,而是对应树的后序遍历结果–后缀正则表达式

第二步 由正则表达式生成NFA

我们使用了自左向右扫描后缀正则表达式的办法来生成NFA。

具体的做法和求一个数学表达式没有太大区别,就是如果是一个字符,就压栈,如果是一个运算符,就弹出对应的元素,运算后放入栈里。

不过这里有一个问题,那就是栈里放些什么呢?

仔细思考一下会发现,栈里有两种元素

  • 一个字符
  • 一个自动机

我们这样来表示栈里的元素

  internal class BeginState
    {
        public int internalState { get; set; }
        public BeginState() { internalState = 0; }
        public BeginState(int state)
        {
            internalState = state;
        }
    }

  internal class EndState{...}

  internal class StateInStack
    {
        public BeginState Begin { get; set; }
        public EndState End { get; set; }
        public void PointEndTo(int state, in Nfa<CharWithEmpty> nfa)
        {
            PointEndToWithout(state, nfa);
            End.internalList.Clear();
        }
        public void PointEndToWithout(int state, in Nfa<CharWithEmpty> nfa)
        {
            foreach (var (estate, how) in End)
            {
                nfa.SetStateTransition(estate, state, how);
            }
        }
    }
  internal class StackElement
    {
        public StateInStack State { get; set; } = null;
        public CharWithEmpty symbol { get; set; } = null;

        public StackElement(in BeginState begin, in EndState end)
        {
            State = new StateInStack();
            State.Begin = begin;
            State.End = end;
        }
        public StackElement(char sym)
        {
            symbol = new CharWithEmpty( sym);
        }
        public StackElement() {
            State = new StateInStack();
        }
    }

这样一来就可以优雅地实践刚才所描述的组合算法了。

第三步 由NFA生成DFA

这里我们使用广度优先搜索的方法,从BeginState开始,搜索出它的\(\epsilon\)闭包,然后分析可能的状态转移。对每一个可能的状态转移都求其\(\epsilon\)闭包,之后将它压入队列中,直至队列为空。