正则表达式之原理篇

正则表达式之原理篇

背景        最近公司规范出来后，关于字符串不提倡用 “ + ”  进行拼接，于是自己写了个function，利用正则表达式来进行匹配。对于正则表达式，之前不了解原理，每次要用的时候查一下，很浪费时间。

内容 基础知识； 正则表达式引擎； 贪婪与非贪婪模式； DFA与NFA引擎； 回溯机制及常见的回溯形式 基础知识 1. 占有字符：正则表达式匹配过程中，如果子表达式匹配到东西，而并非是一个位置，并最终保存到匹配的结果当中 2. 零宽度：只匹配一个位置，或者是匹配的内容并不保存到匹配结果中 一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配 3.控制权：正则表达式由左到右依次进行匹配，通常情况下是由一个表达式取得控制权，从字符串的的某个位置进行匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的（例如：（表达式一）（表达式二）意思就是表达式一匹配完成后才能匹配表达式二，而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始）。

如果表达式一是零宽度，那表达式一匹配完成后，表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个 4. 元字符  5. 反义元字符 6. 转义字符：\  使元字符失去它的意义，仅代表其输入中字符的意义 需要转义的字符列表 \ * + ? | { [ ( ) ^ $ . # 和 空白 7. 重复限定符：匹配优先量词，忽略优先量词，即：贪婪与非贪婪 {n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 '*' 8. 字符类：[ ]，区分大小写 9. 分支条件： | 10. 分组 ：（）指定子表达式，可限制多选项的范围、将若干字符组合为一个单元、受问号或星号之类的量词作用，例：(\d{1,3}){3}\d{3} 断言；(? 11. 括号及反向引用：（子表达式一）（子表达式二）\1      此时括号作用为分组，它具有记忆的功能，即在正则表达式内部仍然能回忆上次匹配到的是什么；\1、\2、\n 是用在正则表达式的匹配环节。在正则表达式的替换环节，则要使用像 $1、$2、$n 这样的语法 12. 平衡组 参考 正则表达式引擎 有两个主要特点： 1. 默认贪婪匹配；（ 贪婪匹配与非贪婪匹配 ） 2. 返回最先匹配到的结果 针对简单的正则匹配进行分析，例：         当把cat应用到“He captured a catfish for his cat”，引擎先比较c和“H”，结果失败了。于是引擎再比较c和“e”，也失败了。

直到第四个字符，c匹配了“c”。a匹配了第五个字符。到第六个字符t没能匹配“p”，也失败了。

引擎再继续从第五个字符重新检查匹配性。直到第十五个字符开始，cat匹配上了“catfish”中的“cat”，正则表达式引擎急切的返回第一个匹配的结果，而不会再继续查找是否有其他更好的匹配 Rubular: 基于 Web 的 Ruby 正则表达式编辑器 贪婪与非贪婪（又称惰性、懒惰等）模式 两者影响的是被量词修饰的子表达式的行为。 贪婪模式在整个表达式匹配成功的前提下，尽可能多的匹配；而非贪婪模式（只被部分NFA引擎支持）在整个表达式匹配成功的前提下，尽可能少的匹配。

匹配优先量词（属于贪婪模式的量词）： “{m,n}”、“{m,}”、“?”、“*”和“+”。 忽略优先量词（匹配优先量词后加上“?”：非贪婪模式的量词）： “{m,n}?”、“{m,}?”、“??”、“*?”和“+?” 例： 源字符串：aa正则表达式一：正则表达式二：DFA与NFA引擎（JS的正则引擎是NFA：非确定型有限自动机） 参考： 正则表达式引擎及其分类 DFA引擎：在线性时状态下执行，不要求回溯（因此永远不测试相同的字符两次）；确保匹配最长的可能的字符串；因为只包含有限的状态（？），所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式 传统的NFA引擎：运行匹配回溯算法——以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。

但传统 NFA的 回溯使它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现 POSIX NFA 引擎：与传统 NFA 引擎类似，不同点：在可以确保已找到了可能的最长的匹配之前，它们将继续回溯（更慢）；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索 例： 字符串： this is yansen’s dog 正则表达式： /ya(msen|nsen|nsem)/ NFA工作方式：先在字符串中查找 y， 然后匹配其后是否为 a；  如果是 a 则继续查找其后是否为 m； 如果不是则匹配其后是否为 n (此时淘汰 msen 支分支)； 然后继续看其后是否依次为 s,e； 接着测试是否为 n ，是 n 则匹配成功，不是则测试是否为 m 。为什么是 m ？因为 NFA 工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！ DFA：从 this 中 t 开始依次查找 y ，定位到 y ，已知其后为 a ，则查看表达式是否有 a ，此处正好有 a； 然后字符串 a 后为 n ，DFA依次测试表达式，此时 msen 不符合要求淘汰。

nsen 和 nsem 符合要求，然后DFA依次检查字符串，检测到 sen 中的 n 时只有 nsen 分支符合，则匹配成功！ 由此两种引擎是完全不同的工作方式：NFA以表达式为主导，更容易操纵；DFA以文本为主导（搜索更快） 回溯机制 引擎是如何来处理那些模糊的条件匹配？ 从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法” --来自百度百科 本质上就是深度优先搜索算法：尝试匹配失败时的下一步通常就是回溯 JS中正则表达式会产生回溯的地方都有哪些呢？ 常见的回溯形式 1.贪婪量词 例：正则：/ab{1,3}c/ 可视化形式 1. 没有回溯的匹配：当目标字符串是"abbbc"时 匹配过程 2. 有回溯的匹配：当目标字符串是“abbc”时 匹配过程 上图第5步有红颜色（仅表示匹配不成功）：此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。

当然，此时整个表达式匹配成功了；上图的第6步，就是“回溯” 即：尝试可能的顺序是“从多往少”的方向去尝试：首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了 另一个清晰的回溯： 正则：/".*"/ 目标字符串："acd"ef 省略了尝试匹配双引号失败的匹配过程 其实“.*”最简单但也是非常影响效率的 2.惰性量词 虽然惰性量词不贪，但也会有回溯的现象（为了整体匹配成） 正则表达式 目标字符串："12345" 匹配过程 3.分支结构 分支也是惰性的，比如/Java|Javascript/，去匹配字符串"Javascript"，得到的结果是"Java"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构中可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。

正则表达式概述 什么是正则表达式

正则表达式概述 正则表达式在程序设计语言中存在着广泛的应用，特别是用来处理字符串。如匹配字符串、查找字符串、替换字符串等。

可以说，正则表达式是一段文本或一个公式，它是用来描述用某种模式去匹配一类字符串的公式，并且该公式具有一定的模式。

本小节将介绍正则表达式的基本概念、第一个正则表达式，以及测试正则表达式的工具Code Architects Regex Tester。 什么是正则表达式 正则表达式（Regular Expression）起源于人类神经系统的早期研究。神经生理学家Warren McCulloch和Walter Pitts研究出一种使用数学方式描述神经网络的方法。1956年，数学家Stephen Kleene发表了一篇标题为“神经网事件的表示法”的论文，并在该论文中引入了“正则表达式”这一个概念。

该论文称正则表达式是：“正则集的代数”的表达式。因此，采用“正则表达式”这个术语。正则表达式的定义存在多种说法，具体如下： 正则表达式就是用某种模式去匹配一类字符串的公式，主要用来描述字符串匹配的工具。

正则表达式描述了一种字符串匹配的模式。它可以用来检查字符串是否含有某种子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。 正则表达式是由普通字符（如字符a到z）以及特殊字符（称为元字符）组成的文字模式。

正则表达式作为一个模板，将某个字符模式与所搜索的字符串进行匹配。 正则表达式就是用于描述某些规则的工具。这些规则经常用于处理字符串中的查找或替换字符串。

换句话说，正则表达式就是记录文本规则的代码。 正则表达式就是用一个“字符串”来描述一个特征，然后去验证另一个“字符串”是否符合这个特征。 学过《编译原理》的读者可能知道不确定有限自动机（Non-deterministic finite automaton，简称NFA）和确定有限自动机（Deterministic finite automaton，简称DFA）。其实，正则表达式是一个不确定有限自动机。

NFA和DFA的最大区别在于它们的状态转换函数。NFA可以对同一个字符串产生多种理解方式，而DFA则只有唯一的一种理解方式。也正因为如此，NFA在匹配过程中可能会回溯，NFA的效率一般要低于DFA。因此，在书写正则表达式时尽量减少回溯来提高正则表达式的效率。

如果你使用过Windows或DOS下用于文件查找的通配符*和?，那么你不难理解正则表达式。如果你需要查找所有Word文档，那么可能使用表达式*.doc。其中，字符*是一个通配符，它可以代表任意字符串。正则表达式和通配符具有相似性，它也可以使用一些字符（如字符.）表示任意字符。

然而，它比通配符更具有精确性。 在正则表达式中，匹配是最常用的一个词语，它描述了正则表达式动作结果。给定一段文本或字符串，使用正则表达式从文本或字符串中查找出符合正则表达式的字符串。

有可能文本或字符存在不止一个部分满足给定的正则表达式，这时每一个这样的部分被称为一个匹配。其中，匹配存在下面3种类型： 形容词性的匹配，即一个字符串匹配一个正则表达式。 动词性的匹配，即在文本或字符串里匹配正则表达式。

名词性的匹配，即字符串中满足给定的正则表达式的一部分。 正则表达式的应用非常广泛，特别是在字符串处理方面。目前来说，正则表达式已经在很多软件中得到广泛了应用，如Linux、Unix、HP等操作系统，C#、PHP、Java等程序开发环境，以及很多的应用软件中，都可以看到正则表达式的这样或那样的应用。正则表达式常见的应用如下： 验证字符串，即验证给定的字符串或子字符串是否符合指定特征，譬如验证是否是合法的邮件地址、验证是否为合法的HTTP地址等。

查找字符串，从给定的文本中查找符合指定特征的字符串，比查找固定字符串更加灵活方便。 替换字符串，即把给定的字符串中的符合指定特征的子字符串替换为其他字符串，比普通的替换更强大。 提取字符串，即从给定的字符串中提取符合指定特征的子字符串。

java中的正则表达式跟编译原理有什么联系

首先，正则表达式不仅在Java里有，其它语言里面也有，它是一个数学上的概念，各个语言中的正则表达式是它的不同形式的实现。其次，编译原理的词法分析里，会用到正则表达式去匹配源程序中的各种token(记号)，比如说int a = 8;里识别出：类型名：int变量名：a运算符：=数字：8结尾分号：;总之，二者有联系，但不是一回事。

在正则表达式中\\.和.有什么区别？

一、作为Java的转义字符1.在Java中，反斜杠（\）是一个特殊的字符，被称为转义字符，它的作用是用来转义后面一个字符。转义后的字符通常用于表示一个不可见的字符或具有特殊含义的字符，例如换行（\n）、回车符(\r)、制表符(\t)。

2.在Java中以下字符都有特殊意义，无法直接表示单引号：char c = 'a'; 表示字符类型的数据时需要使用单引号将字符左右括起来。

所以要表示字符'则需要使用\'双引号：String str = "abc"; 表示字符串类型的数据时需要使用双引号将字符串左右括起来。要表示字符串"则需要\"反斜杠：String regex = "你好\n\t阿"; 在Java代码中\表示转义字符，所以如果要表示字面意思的\，则需要使用\\所以用反斜杠加上本身字符来进行表示。二、在正则表达式中2.1Java中正则表达式的\\表示将下一字符标记为特殊字符。如\d表示数字字符匹配，等效于 [0-9]。

\w表示匹配任何字类字符（字母数字下划线），注意包括下划线。与"[A-Za-z0-9_]"等效。在其他语言中，\\ 表示：我想要在正则表达式中插入一个普通的（字面上的）反斜杠，请不要给它任何特殊的意义。

在 Java 中，\\ 表示：我要插入一个正则表达式的反斜线，所以其后的字符具有特殊的意义。在 Java 中，\\ 表示：我要插入一个正则表达式的反斜线，所以其后的字符具有特殊的意义。在 Java 中，\\ 表示：我要插入一个正则表达式的反斜线，所以其后的字符具有特殊的意义。

\\中的第一个\表示java的转义字符\由编译器解析，第二个\是正则表达式\由正则表达式引擎解析。所以，在其他的语言中（如Perl），一个反斜杠 \ 就足以具有转义的作用，而在 Java 中正则表达式中则需要有两个反斜杠才能被解析为其他语言中的转义作用。也可以简单的理解在 Java 的正则表达式中，两个 \\ 代表其他语言中的一个 \，这也就是为什么表示一位数字的正则表达式是 \\d，而表示一个普通的反斜杠是 \\\\。

所以Java正则表达式中匹配一个普通的反斜杠是\\\\。所以如果在[]内表示一个]，要写两个\，即[\\]]。例如，我要在前面不是0-9，也不是） ] }三个反括号的后面位置中，匹配 - 的后面是数字或者正括号( [ { 的 - 前面的位置，须写成:(?

如果设置了 RegExp 对象的 Multiline 属性，^ 还会与"\n"或"\r"之后的位置匹配。$ 匹配输入字符串结尾的位置。如果设置了 RegExp 对象的 Multiline 属性，$ 还会与"\n"或"\r"之前的位置匹配。* 零次或多次匹配前面的字符或子表达式。

例如，zo* 匹配"z"和"zoo"。* 等效于 {0,}。+ 一次或多次匹配前面的字符或子表达式。例如，"zo+"与"zo"和"zoo"匹配，但与"z"不匹配。

+ 等效于 {1,}。? 零次或一次匹配前面的字符或子表达式。例如，"do(es)?“匹配"do"或"does"中的"do”。

? 等效于 {0,1}。{n} n 是非负整数。正好匹配 n 次。

例如，"o{2}"与"Bob"中的"o"不匹配，但与"food"中的两个"o"匹配。{n,} n 是非负整数。至少匹配 n 次。例如，"o{2,}“不匹配"Bob"中的"o”，而匹配"foooood"中的所有 o。

"o{1,}“等效于"o+”。"o{0,}“等效于"o*”。{n,m} m 和 n 是非负整数，其中 n <= m。

匹配至少 n 次，至多 m 次。例如，"o{1,3}"匹配"fooooood"中的头三个 o。‘o{0,1}’ 等效于 ‘o?’。注意：您不能将空格插入逗号和数字之间。

x y[xyz] 字符集。匹配包含的任一字符。例如，"[abc]“匹配"plain"中的"a”。

[ ^xyz] 反向字符集。匹配未包含的任。

正则表达式，匹配逗号

String str = "a:122,,122,,,21,,2,,,343"; str = str.replaceAll("(?<=\\d+),{2,}(?=\\d+)", ","); System.out.println(str); 正则表达式的"鼻祖"或许可一直追溯到科学家对人类神经系统工作原理的早期研究。美国新泽西州的Warren McCulloch和出生在美国底特律的Walter Pitts这两位神经生理方面的科学家，研究出了一种用数学方式来描述神经网络的新方法，他们创造性地将神经系统中的神经元描述成了小而简单的自动控制元，从而作出了一项伟大的工作革新。

在1951 年,一位名叫Stephen Kleene的数学科学家，他在Warren McCulloch和Walter Pitts早期工作的基础之上，发表了一篇题目是《神经网事件的表示法》的论文，利用称之为正则集合的数学符号来描述此模型，引入了正则表达式的概念。

正则表达式被作为用来描述其称之为"正则集的代数"的一种表达式，因而采用了"正则表达式"这个术语。 之后一段时间，人们发现可以将这一工作成果应用于其他方面。Ken Thompson就把这一成果应用于计算搜索算法的一些早期研究，Ken Thompson是 Unix的主要发明人，也就是大名鼎鼎的Unix之父。Unix之父将此符号系统引入编辑器QED，然后是Unix上的编辑器ed，并最终引入grep。

Jeffrey Friedl 在其著作《Mastering Regular Expressions (2nd edition)》(中文版译作:精通正则表达式，已出到第三版)中对此作了进一步阐述讲解，如果你希望更多了解正则表达式理论和历史，推荐你看看这本书。 自此以后，正则表达式被广泛地应用到各种UNIX或类似于UNIX的工具中，如大家熟知的Perl。Perl的正则表达式源自于Henry Spencer编写的regex，之后已演化成了pcre(Perl兼容正则表达式Perl Compatible Regular Expressions)，pcre是一个由Philip Hazel开发的、为很多现代工具所使用的库。

正则表达式的第一个实用应用程序即为Unix中的 qed 编辑器。

编译原理正则表达式化简

你好，语言L={a}{a,b}∗({ϵ}∪({.,_}{a,b}{a,b}∗))L={a}{a,b} ∗ ({ϵ}∪({.,_}{a,b}{a,b} ∗ ))这个语言是指，由a开头，后接任意长度的a、b串，然后再接空串（代表结束）。或者是接以.或_开头的，后接长度大于等于1的a、b串。

正则表达式（Regular Expression, RE）是一种用来描述正则语言的更紧凑的表示方法。