深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

引擎类型 程序

DFA awk(大多数版本)、egrep(大多数版本)、flex、lex、MySQL、Procmail

传统NFA GNU Emacs、Java、grep(大多数版本)、less、more、.NET语言、PCRE library、Perl、PHP(所有三套正则库)、Python、Ruby、sed(大多数版本)、vi

POSIX NFA mawk、Mortice Kern Systems'utilities、GNU Emacs(明确指定时使用)

DFA/NFA混合 GNU awk、GNU grep/egrep、Tcl

NFA(非确定型有穷自动机):表达式主导

正则:“to(nite|knight|night)”

目标文本:“tonight”

正则表达式从“t”开始,每次检查一部分(由引擎查看表达式的一部分),同时检查当前文本是否匹配表达式的当前部分。如果是,则继续表达式的下一部分,直到表达式的所有部分都能匹配。

此例中第一个元素是“t”,它会重复尝试,在目标字符串中找到“t”为止,然后检查“o”,过程与此一致。然后是“(nite|knight|night)”部分,表达式会一次尝试,直到宣告匹配成功或失败才会停止。 表达式中的控制权在不同元素之间转换,所以作者称其为“表达式主导”

所以正则:“nfa|nfa not”,目标字符串:“nfa not”中,也只是匹配“nfa”而已,而不会完整的匹配。

DFA (确定型有穷自动机) :文本主导

DFA引擎在扫描字符串时,会记录“当前有效”的所有匹配可能。

还是最初的例子,引擎移动到“t”时,它会在当前处理匹配可能中添加一个潜在的可能

接下来扫描的每个字符,都会更新当前的可能匹配序列。继续扫描两个字符之后的情况如上图。分支“knight”被排除。

书中作者称其问文本主导,是因为扫描每个字符的时候都对引擎进行了控制

测试引擎类型

1.如果支持忽略优先量词,那么基本就是传统NFA。DFA不支持忽略优先量词,POSIX NFA中也没有意义。

2.DFA不支持捕获型括号和回溯。在这两种混合类型的引擎中,如果没有使用捕获型括号,就会使用DFA

ps:在RegexBuddy中似乎只有传统NFA,起码做1的验证时结果是这样的,所以DFA和混合型引擎在这就不做验证了,本文也主要针对java,所以这里指着重介绍和java相关内容

两条普适原则(来自 《精通正则表达式》 v3) :

1.优先匹配最左面(最靠开头)的匹配结果

注意:此原则并没有规定优先匹配结果的长度,而只是规定在所有可能的匹配结果中,优先选择最左边的(可能有)。

作者关于此原则的解释:匹配先从需要查找的字符串的起始位置尝试匹配。这里的“尝试匹配”的意思是:在当前位置测试整个正则表达式能匹配的每个可 能。如果在当前位置测试了所有的可能之后找不到匹配结果,就需要从字符的第二个字符之前的位置开始重新尝试……只有在尝试过所有的起始位置(直到字符串的 最后一个字符)都找不到匹配结果的情况下,才会报告失败。

下面给出一个例子:

目标字符串“This is a cat.”

我想匹配字符“is”,我的正则为“is”

结果如下(图1):

这里找到了两个结果,根据原则1,最先找到的是“this”中的“is”,而并没有找到“is”这个单词。这也很容易理解。下面我们看看RegexBuddy中debug的过程

深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

这里怎么会有这么多字符,目标字符串实际只有13个字符,那么多出来的那些都是哪来的呢?

我觉得,RegexBuddy是把字符与字符之间的位置也算为一个character。再来看看图1

我之所以把每一个字符都装在表格里,就是让大家看的清楚。这里,每一个竖线(其实是不存在的)也作为一个character,我觉得这样是有道理的,比如零宽断言,它的匹配就是在某一个竖线的位置。我们不妨用“^”测试一下,看看debug的结果。

深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

当正则以“字符串起始位置锚点”开头,引擎就会知道如果能匹配,那么肯定是从字符串开头,所以不需要做更多的尝试。

ps:这和RegexBuddy上面的debug结果似乎是矛盾的。确实是这样,不知道是不是其一个bug,起码v3.5.4是这样的

RegexBuddy暂时是不支持字符组的集合操作的,不知这算功能缺失还是算个bug

2.标准的量词(*,+,?,{m,n})是匹配优先的

目标字符串:“copyright 2003”

正则:“.*”,那么匹配的结果为全部字符

正则:“.*[0-9]*”,这个时候,由于量词是匹配优先的,所以“.*”会匹配整个字符串,而后面的“[0-9]*”怎什么也匹配不到 ,这并不影响最终结果,因为“*”表示0个也可以,我们可以添加一组括号来验证这个结果,如下图显示的一样

深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

我们现在将正则改成这样:“.*[0-9]+”,这时候“.*”也会先把字符串全部匹配,之后是“[0-9]+”这个部分,发现它要求至少匹配到一 个数字才行,所以它会强迫“.*”吐出它之前匹配到的内容给自己使用,当“.*”吐出字符“3”之后,“[0-9]+”成功匹配,至此匹配结束,不再进行 其他尝试。

我们来debug看看这一过程:

深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

分类:默认分类 时间:2013-03-17 人气:0
本文关键词:
分享到:

相关文章

  • JAVA程序求职必看-125条常见的java面试笔试题汇总 2012-01-01

    1.抽象: 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节。抽象包括两个方面,一是过程抽象,二是数据抽象。 2.继承:  继承是一种联结类的层次模型,并且允许和鼓励类的重用,它提供了一种明确表述共性的方法。对象的一个新类可以从现有的类中派生,这个过程称为类继承。新类继承了原始类的特性,新类称为原始类的派生类(子类),而原始类称为新类的基类(父类)。派生类可以从它的基类那里继承方法和实例变量,

  • 混血儿新生命--Java+PHP整合 2012-01-01

    最近才有时间处理此事,将此设想应用到现实应用程序中。 下面从两个方面讲解如何开发与发布。 示例:讲解java+php 开发模式,以菜单管理为例。 示例如下: 一:java 结构代码 java开发结构图如下: java 程序代码请看在下面上传文件,由于上传文件不能大于2M,所以用到的lib 没有上传,如需求,可留邮箱给我,我发给大家。 注:PHP和Java各有其语言内部定义的数据类型,当PHP数据传送到Java,或Java数据传送到PHP时,LAJP在内部自动地、准确地对他们进行转换,程序员无需进

  • java之jvm学习笔记(策略和保护域) 2012-01-02

    前面一节,我们做了一个简单的实验,来说明什么是策略文件,在文章的最后,也顺带的讲了一下什么是策略,还有策略的作用。 为了引出另外一个很重要的概念ProtectionDomain(保护域),所以我们还是要先来回顾一下什么是策略。 首先,什么是策略,今天的东西纯粹是比较概念的。当然,如果你读过笔记九,今天的东西,就真的是soso 策略与策略文件: java对应用程序的访问控制策略是由抽象类java.security.Policy的一个子类的单例所表示,任何时候,每个应用程序实际上只有一个Policy

  • java 线程 新类库中的构件 CyclicBarrier使用 2012-01-05

    package org.rui.thread.newc; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.concurrent.BrokenBarrierException; import java.util.concurrent.CyclicBarrier; import java.util.concurrent.ExecutorService; impor

  • Java 学习笔记:深入Serializable 2012-01-07

    Java的Serializable Serialization(序列化)是一种将对象以一连串的字节描述的过程;反序列化deserialization是一种将这些字节重建成一个对象的过程。Java序列化API提供一种处理对象序列化的标准机制。在这里你能学到如何序列化一个对象,什么时候需要序列化以及Java序列化的算法,我们用一个实例来示范序列化以后的字节是如何描述一个对象的信息的。 说白了,Java都是通过对象来描述实体,而对象是不能再网络上传递的,如果将对象生成一种可以解析的"一连串的字节描述"

  • java流--考验你的想象力 2012-01-07

    在学习java的学习中,我们会接触到一个概念,就是“流”,大概分为输入输出流,在我们的想象中,流,是水,是动态的,但是让我们在只有0和1的电脑上想象水流,这是个抽象的概念,今天,我们一起随着我的文字,梳理一下这些流! 首先,我们要知道电脑硬件的一点知识,我电脑上对数据的存储有三种方式,外界存储,内存,缓存。比如电脑上的硬盘,光盘,U盘等都是外存,咱们平常说的内存条就是内存,缓存是直接在CPU里的。我们就将这几个东西理解为容器,外存就像是门口的河,内存就是咱们家的水桶,缓存咱们自己的水杯,而水呢?

  • java学习笔记 第二篇 核心技术 2012-01-07

    第十章 接口、继承与多态 10.1 类的继承(extends关键字) 1.继承的基本思想是基于某个父类的扩展,制定出一个新的子类,子类可以继承父类原有的属性和方法,也可以增加原来父类所不具备的属性和方法,或者直接重写父类中的某些方法。 2.可以在子类的构造方法中使用super()语句调用父类的构造方法,也可以在子类中使用super关键字调用父类的成员方法,但子类没有权限调用父类中被修饰为private的方法。 重写方法 3.继承也可以重写(也称覆盖)父类的成员方法。重写就是在子类中将父类的成员方

  • 如何为Mac更新Java? 2012-01-07

      每次启动 Java 小应用程序、Java Web Start 应用程序或 Java 控制面板时,系统将首先启动程序,然后在后台 (因此不会影响 Java 应用程序的性能) 确定在过去 7 天内是否检查过 Java 更新,小编根据自己的经验为大家提供一篇java mac版更新教程。   在 Java 控制面板中更新 Java   1、单击位于 System Preferences(系统首选项)下的 Java 图标来启动 Java Control Panel(Java 控制面板)。   2、转到

  • Ubuntu 14.04安装java的方法以Ubuntu14.04为例 2012-01-08

      因为Linux软件的安装都需要使用到命令,很多人在安装java的时候遇到了不少问题,下面小编以Ubuntu14.04为例,给大家详细介绍下java的安装,一起来学习下吧。   JRE vs OpenJDK vs Oracle JDK   在我们继续了解如何安装Java之前,让我们快速地了解JRE、OpenJDK和Oracle JDK之间的不同之处。   JRE(Java Runtime Environment),它是你运行一个基于Java语言应用程序的所正常需要的环境。如果你不是一个程序员的

  • mysql orcale数据类型跟java对照 2012-01-08

    oracle 中Number 分为两种 1.Number 2.Number(10,2) 第一种对应的是java中的整形 int long short byte 而第二种对应java中的 浮点型 float double oracle中的的date 对应java中的 java.util.date java.sql.date 是都可以的 但通常应用java.util.date 因为它的作用范畴大于java。sql。date number要根据oracle数据库定义类型的细节来决定 如果是number

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.047 (s). 10 q(s)