文档章节

『阿男的编程本质论』*08 正则表达式是万能的吗?*

阿男weli
 阿男weli
发布于 2017/01/04 05:18
字数 1454
阅读 134
收藏 0

『阿男的编程本质论』*08 正则表达式是万能的吗?*

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

阿男之前开了个NFA和DFA的专题^1,共计10篇文章,主要是为大家介绍了正则表达式背后的有限状态自动机,也就是Finite Automaton。这种自动机的特点就是Memoryless,也就是"无内存"。这种自动机的总是从一种状态移动到下一种状态,而不会去记录之前的状态。

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

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

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

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

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

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

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

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

输入图片说明

如上图所示,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在做语法分析的时候,不光要匹配某个字符串,还要把字符串前后关联,匹配具体的语法规则,而不只是状态的变化。

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

输入图片说明

上面的图展示了各种自动机的边界,最里面是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型内存而不需要随机访问内存。

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

(这个系列之前的文章在豆瓣^4,大家可以自行查看)

© 著作权归作者所有

阿男weli
粉丝 16
博文 32
码字总数 24051
作品 0
私信 提问
Linux系统命令三剑客之 awk

命令名称:awk 作用: 对文本和数据进行处理 详细说明: awk 是一种编程语言,用于在linux/unix下对文本和数据进行处理。 数据可以来自标准输入(stdin)、一个或多个文件,或其它命令的输出。...

民工哥
2017/11/13
0
0
QLineEdit设置输入类型

在MFC编程中,我们可以通过设置输入框的属性,让用户只能输入数字。 在QT中的输入框(QLineEdit)可以通过绑定QIntValidator/QDoubleValidator/QRegExpValidator对象来控制用户的输入。 *** ...

qt_plus
2016/11/10
780
0
pyqt学习基础 -插曲- python 正则表达式学习

python 正则表达式学习 资源来自 学习资源来自ubuntu wiki 正则表达式介绍 正则表达式,各种语言都有相关的库。就其本质而言,正则表达式(或 RE)是一种小型的、高度专业化的编程语言 简单模...

Cosven
2014/08/24
125
0
使用Jakarta-ORO库的几个例子

简介 Jakarta-ORO是最全面以及优化得最好的正则表达式API之一,Jakarta-ORO库以前叫做OROMatcher,是由Daniel F. Savarese编写,后来他赠给Jakarta Project。 Jakarta-ORO正则表达式库支持P...

jing31
2010/08/20
1K
2
java学习计划

源于传智播客毕向东老师的教学计划: day01-01-基本常识 day01-02-Java的跨平台性 day01-03-Java环境搭建(安装) day01-04-Java环境搭建(环境变量配置) day01-05-Java环境搭建(环境变量配置技...

Bony
2016/05/14
65
0

没有更多内容

加载失败,请刷新页面

加载更多

前端面试题汇总

一. HTML常见的兼容性 1.HTML5 标签在低版本浏览器不兼容 解决办法:使用html5shiv库,引入下列语句 <!--[if lte IE 8]> <script src="https://cdn.bootcss.com/html5shiv/r29/html5.js"></sc......

蓝小驴
42分钟前
10
0
OSChina 周四乱弹 —— 我气的脸都黑了!

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐《Red Battle》- 高橋李依 / 豊崎愛生 《Red Battle》- 高橋李依 / 豊崎愛生 手机党少年们想听歌,请使劲儿戳(这里) @丶Lion ...

小小编辑
55分钟前
688
24
找OSG教程, B站就有

https://www.bilibili.com/video/av64849038?from=search&seid=11632913960900279653

洛克人杰洛
今天
6
0
学习记录(day07-Vue组件、自定义属性、自定义事件)

[TOC] 1.1.1什么是组件 一个vue文件就是一个组件 组件将html标签/css样式/对应JS打包成一个整体,也可以理解钻进一个具有样式和特效的自定义标签。 一、编写组件(提供方)<template> <di...

庭前云落
今天
5
0
使用Prometheus监控SpringBoot应用

通过之前的文章我们使用Prometheus监控了应用服务器node_exporter,数据库mysqld_exporter,今天我们来监控一下你的应用。(本文以SpringBoot 2.1.9.RELEASE 作为监控目标) 编码 添加依赖 使...

JAVA日知录
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部