说到正则表达式（Regular Expression）不得不提到正则文法，这俩是等价的可以互相转换。同时，他俩与有限状态自动机（Finite State Automaton）也是等价的，实际上那些支持正则表达式的工具，比如grep、awk内部都是使用有限状态自动机来识别正则表达式的。这里厘清一下它们之间的关系：
- 0型文法，即无限制文法，可以被图灵机识别（能使图灵机停机的字符串）。
- 1型文法，即上下文相关文法，产生规则为 αAβ → αγβ 1，可以被线性有界非确定图灵机识别。
- 2型文法，即上下文无关文法，产生规则为 A → γ 2，可以使用巴科斯范式（BNF）表达，可以被下推自动机识别，包括LL(1)、LR(1)等语法分析器，基本所有的编程语言都是属于2型文法。
- 3型文法，即正则文法，产生规则为 A → aB, A → a 3，可以用正则表达式表达，可以被有限状态自动机识别，包括非确定有限自动机（NFA, Nondeterministic Finite Automaton）和确定有限自动机（DFA, Deterministic Finite Automaton）。
正则文法和正则表达式
正则文法分为左线性文法和右线性文法，对于文法 G = (N, Σ, P, S)，如果产生形式如下：
A → aB
A → a
C → ε
则称为右线性文法，其中A, B, C属于N的非终结符，a, ε属于Σ的终结符，ε表示空串。反之，为左线性文法。
正则表达式基本的定义如下：
字母表中的任意字母是正则表达式，空串和空集也是正则表达式； 如果r, s是正则表达式，那么r|s, rs, r*, (r)也是正则表达式。
正则文法和正则表达式之间可以互相转换，比如：
一个右线性文法 G = (N, Σ, P, S)，其中 N = {S, A}，Σ = {a, b, c}，S 是起始符号，P 包含下述规则：
S → aS
S → bA
A → ε
A → cA
对应的正则表达式为 a*bc*。
将正则表达式转换成NFA
参考龙书 词法分析 章节
自顶向下解析正则表达式
正则表达式备忘
元字符表
| Perl类 | POSIX类 | 说明 |
|---|---|---|
\a |
[:alpha:] |
英文字母 [a-zA-Z] |
\l |
[:lower:] |
小写英文字母 [a-z] |
\u |
[:upper:] |
大写英文字母 [A-Z] |
\d |
[:digit:] |
数字 [0-9] |
\D |
[^[:digit:]] |
非数字 |
\x |
[:xdigit:] |
十六进制数字 [0-9a-fA-F] |
[:alnum:] |
英文字母和数字 [0-9a-zA-Z] |
|
\w |
[[:alnum:]_] |
英文字母、数字和下划线 |
\W |
[^[:alnum:]_] |
非英文字母、数字和下划线 |
[:graph:] |
可打印的非空白字符 | |
\p |
[:print:] |
可打印字符 |
[:blank:] |
空白字符（空格和tab） | |
\s |
[:space:] |
所有空白字符（还包括回车、换行等） |
\S |
[^[:space:]] |
非空白字符 |
常用表达式
| 表达式 | 说明 |
|---|---|
[\u4e00-\u9fa5] |
匹配中文字符（unicode） |
[^\x00-\xff] |
匹配双字节字符（包括汉字在内） |
\n[\s│ ]*\r |
匹配空行 |
/<(.*)>.*<\/\1>│<(.*) \/>/ |
匹配HTML标记 |
(^\s*)│(\s*$) |
匹配首尾空格 |
\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)* |
匹配Email地址 |
http://(/</a>[\w-]+\.)+[\w-]+(/[\w- ./?%&=]*)? |
匹配URL |