Master Regular Expressions
1 Introduction to Regular Expression
The Language Analogy
Full regular expressions are composed of two types of characters:
1. The special characters are called metacharacters
2. The rest are called literal or normal text characters.
文件名模式的元字符要少于正则表达式。
单词分界符
在egrep分界符为\<和\>.
区分元字符和元字符序列，<和>本身不是元字符.
流派
指每样工具支持的元字符和其他特性各不相同.
2 Extended Introductory Examples
Perl 和 egrep 不属于同一个流派，而且 Perl 提供的元字符远远多于 egrep.
1 | |
在 Perl 中，变量不需要事先声明就能使用.
把=~读做match会比较省事。
Perl 一般不区分整数和浮点数.
Adding Commas to a Number with Lookaround
Lookaround match position within the text. 环视比 anchors 更通用.
Lookahead 从左向右查看文本. 是从head看，那就是从左往右.
Positive lookaround, 从左向右查看文本，查看当前位置右边。使用 special sequence (?=...)表示。
lookbehind, 从behind开始看，从右往左查看文本. 查看当前文本左边。Using special sequence (?<=...). 可以把<=看作箭头指向左边所以匹配左侧.
环视表示的是找到一个位置并从这里开始匹配，如:
1 | |
使用(?=Jeffrey)Jeff, 即从(?=Jeffrey)一个字符的右边是Jeffrey的位置开始匹配Jeff. 也就是从by后面的那个空格字符开始匹配.
环视匹配的内容不是匹配文本.
1 | |
结合非捕获型括号:
1 | |
Negtive lookahead (?!...) 和 negtive lookbehind (?<!...), 就是把等号 = 换成了 ! .
当 their subexpression is not able to match, 成功的位置. 即周围不是什么时匹配的位置.
可以处理一侧匹配，一侧不匹配的情况.
Using (?<!\w)(?=\w)|(?<=\w)(?!\w) as a replacement for \b.
Commafication without lookbehind
注意 Lookbehind is not as widely supported as lookahead.
Text-to-HTML 转换
3 Overview of Regular Expression Features and Flavors
“Global Regular Expression Print” 即 grep.
egrep 即 “extend grep”.
POSIX 标准化的尝试
POSIX 把常见的流派分为两大类:
1. Basic Regular Expresion (BREs)
2. Extended Regular Expresion (EREs)
PCRE 正则表达式库。
字符串， 字符编码和匹配模式
作为正则表达式的字符串
除了 Perl, awk, sed 之外的大多数语言的正则引擎接收的是以普通字符串形式提供的正则表达式.
在字符串文字中，必须使用两个紧挨在一起的反斜线才能表示正则表达式中的反斜线。如为了表示正则表达式中的\n, 必须在字符串中使用\\n.
处理分为了两部分，语言的字符串处理和正则引擎处理.
字符编码
规定了不同数值的字节应该如何解释.
Unicode
It’s a logical mapping between a number and a character.
这里的 number 称为 code point 常为 hexadecimal 加上“U+” 在前面. 如U+c0B5.
Characters versus combining-character sequences
一个字符，可能由两个 code point 来表示. 一个 base character, 一个 combining character.
Unicode offers a number of combining characters that are intended to follow a base character.
两个代码点的字符后面跟一个量词，量词可能作用与第二个代码点.
4 The Mechanics of Expression Processing
Regex Engine Types
分为两类:
1. DFA
2. NFA
测试了一下，Vim使用的是传统型NFA. egrep 是DFA。
Two all-encompassing rules:
1. The match that begins earliest (leftmost) wins.
2. The standard quantifiers (*, +, ?, and {m,n}) are greedy.
如果不能在最开始的位置匹配成功，就会从字符串下一个位置重新开始匹配.
Backreference 只对NFA引擎有效.
DFA引擎匹配速度更快。
Regex-Directed Versus Text-Directed
The two basic engine types 反映了算法的差异.
NFA engine “regex-directed”.
DFA engine “text-directed”.
First Thoughts: NFA and DFA in Comparison
NFA, Nondeterministic Finite Automaton, 字符串中的字符可能会匹配多次。
DFA, Deterministic Finite Automaton, 字符串中的字符只会匹配一次.
不同的表达式会以不同的方式控制引擎.
DFA keeps track of all matches simultaneously.
Backtracking
It’s the essence of an NFA engine. 在面临作出选择的情形是会记住未选的结构. 如量词和多选结构(|).
Two Important Points on Backtracking
1.The engine always choose to first make the attempt for greedy quantifiers, and to first skip the attempt for lazy ones. 当量词是greedy时，会尝试匹配，是lazy时会跳过.
2.The most recently saved option is the one returned to when a local failure forces backtracking. They’re used LIFO(last in first out).
Saved State
This is the basis for NFA matching.
greedy 量词和 lazy 量词的保存状态不同. 前者在量词作用的pattern后面，后者在前面.
Backtracking and Greediness
Star, plus, and their backtracking
每测试一项都会保留一个状态.
需注意:
1. Backtracking 机制不但需要重新计算正则表达式和文本的对应位置，也需要维护括号内的子表达式所匹配的文本状态.
2. 星号(或其他人和greedy量词)限定的部分不受后面元素的影响，而是匹配尽可能多的内容.
DFA 只有 greedy 的量词.
Problem of Greediness
不要过分依赖.*, 可能会出问题.
忽略量词有时可以替代排除类.
使用排除环视，可以得到与排除型字符组相当的结果.
The Essence of Greediness, Laziness, and Backtracing
在匹配失败后，就会尝试另外的分支.
无论是匹配优先还是忽略优先，只要引擎报告匹配失败，它就必然尝试了所有的可能.
匹配优先和忽略优先区别于测试路径的先后顺序。
Possessive Quantifiers and Atomic Grouping
Atomic grouping with (?>…)
Atomic grouping 即放弃其中的 saved state.
The essence of atomic grouping
匹配优先和忽略优先都不会影响需要检测路径的本身，而只会影响检测的顺序。如果不能匹配，无论是匹配优先还是忽略优先的顺序，最终每条路径都会被测试.
Possessive Quantifiers, ?+, *+, ++, and {m,n}+
Possessive quantifiers are much like greedy quantifiers 但是它们从不交还已经匹配的字符.
每当做选择时都会创建 saved state.
Possessive quantifiers 不会创建 saved state.
The Backtracking of Lookaround
Lookaround is closely related to atomic grouping and possessive quantifiers.
There are four types of lookaround:
1. positive
2. negetive flavors of lookahead and lookbehind
在NFA的世界中包含了 saved state 和 backtracking.
只要环视结构的匹配尝试结束，它就不会留下任何 saved state.
Is Alternation Greedy
多选结构是按顺序排列的。
如果多选分支是有序的，而能够匹配同样文本的多选分支又不止一个，就要小心安排多选分支的先后顺序.
匹配日期时的拆分方法.
NFA, DFA and POSIX
The Longest-Leftmost
POSIX and the Longest-Leftmost Rule
POSIX标准规定，如果在字符串的某个位置存在多个可能的匹配，应当返回的是最长的匹配.
Summary: NFA and DFA in Comparison
DFA versus NFA: Differences in the pre-use compile
NFA 的编译过程通常1要快一些，需要的内存也更少一些.
DFA versus NFA: Differences in match speed
一般来说，DFA 的速度和正则表达式无关，而NFA 中两者直接关联.
DFA versus NFA: Differences in what is matched
DFA(或者POSIX NFA) 返回最左边的最长的匹配文本. 传统型NFA 可能返回同样的结果，当然也可能是别的文本.
DFA versus NFA: Differences in capabilities
NFA 能提供一些 DFA 不支持的功能.
DFA versus NFA: Differences in ease of implementation
The soul of NFA matching is backtracking.