正则表达式的边界

我们在日常当中使用正则表达式搜索各种字符串,但是手里有这么厉害的一个工具,我们也必须知道它的局限所在。

RegExp背后对应的是Finite Automaton,有限状态自动机。这种自动机的特点就是Memoryless,也就是”无内存”。这种自动机的总是从一种状态移动到下一种状态,而不会去记录之前的状态。

因此,我们根据这个特点,可以判断出正则表达式必然有它的局限性,而这个局限性肯定是和它这种Memoryless的特点相关。事实也确实如此:正则表达式表达不了nested结构。

我们无法用正则表达式表达一个任意深度的nested结构。比如这样的字符串:

{1 {2 {3 { ... } 3} 2} 1}

假设上面的字符串是由任意多的{}这样的大括号对来组成,我们没法写一个正则表达式来匹配这个结构。也就是说,我们可以匹配固定层数的nest结构,但我们不能写一个通用的表达式,表达一种抽象的nest结构。

其实我们从正则表达式背后的有限状态机,也就是Finite Automaton这个名字就可以看出来,它能匹配的是有限状态。因为这种状态机是Memoryless的,只会从一个状态转移到另一个状态,因此它无法记录nest结构,也就无法匹配nest结构。

因此,我们不能使用正则表达式表示nest结构。实际上我们多写写正则表达式就可以很容易理解这点:我们写的正则表达式都是一个模式接着另一个模式,每一个模式内部可以用|来表达”或”的关系,但其实正则表达式表达不了nest的模式。

在语言领域,Chomsky早已经把正则表达式背后所能表达的语法给规范化了。实际上,正则表达式所能表达的语法,叫做Regular grammar1

我们可以看看Chomsky对语言的规范化分类:

57c1fa20921710324914f29ed64ce4e3.jpeg

如上图所示,Type-3 Grammar就是对应的Regular Grammar,并且可以看到对应的Abstract machineFinite

Regular GrammarContext-Free Grammar,也就是Type-2 Grammar的一个子集。我们并不能使用正则表达式匹配所有的Context-Free Grammar,因为Context-Free Grammar是允许nest结构存在的。

首先我们必须知道,我们所使用的计算机语言都是context-free grammar,也就是说,我们的编程语言里面都有nest结构存在的。这个是非常容易理解的,比如下面Java语言的代码里面的Nested Class:

class OuterClass {
    ...
    class NestedClass {
        ...
    }
}

实际上Parser在分析语法的时候,是必须要支持匹配这种很常见的nested结构的,这个和Lexer阶段使用正则表达式来匹配Token来讲,要求更高。因此Parser是无法使用正则表达式来完成Rules匹配工作的。

我们可以看看上面的图,看看Context-Free Grammar对应的Abstract Machine是什么,可以看到对应的是Pushdown Automaton,简称PDA,也就是中文翻译过来的”下推自动机”。

PDAFA的基础上加入了stack,具有了内存,不再是Memoryless,因此它可以匹配nest结构,这对于语法分析至关重要:因为除了匹配nest结构,Parser在做语法分析的时候,不光要匹配某个字符串,还要把字符串前后关联,匹配具体的语法规则,而不只是状态的变化。

接下来想给大家讲讲各种自动机的边界。先看下面这幅图2

1d89bd6ad785278095939b4115183c7f.jpeg

上面的图展示了各种自动机的边界,最里面是Combinational logic:基础的逻辑是所有自动机的基石,比如”or”还有”and”这些逻辑关系。

然后是最基础的自动机:Finite-state machine,这种自动机是可以进行状态的跃迁,但没有内存,无法进行语义分析。

Finite-status machine加上一个stack内存,就变成了Pushdown automaton,这样的自动机不但可以进行状态的跃迁,还可以访问stack内存。这样就可以对context-free language进行语法规则分析。

如果我们把PDAstack内存变成可以随机访问的内存,就得到了Turning Machine:不但可以进行状态的跃迁,还可以有随机的存取空间。

因此图灵机就是一个完备的计算机,我们的程序往往是图灵完备的,也是要运行在图灵机上。举个例子,我们的电脑当然是图灵机,然后很多虚拟机其实也是图灵机,比如Java的JVM也是图灵机。

同样的道理,如果只是运行正则表达式引擎,我们就不需要内存。如果只是运行PDA Parser,我们就只需要stack型内存而不需要随机访问内存。

希望给大家通过这篇文章,能够理清楚了知识的脉络,各种自动机的边界,以及它们的适用范围,有了这个知识基础,很多时候可以帮助大家明白自己面对什么问题该用什么工具。这种选择工具的能力无比重要。

  1. https://en.wikipedia.org/wiki/Regular_grammar 

  2. https://en.wikipedia.org/wiki/Turing_machine 

My Github Page: https://github.com/liweinan

Powered by Jekyll and Theme by solid

If you have any question want to ask or find bugs regarding with my blog posts, please report it here:
https://github.com/liweinan/liweinan.github.io/issues