正则表达式备忘

说到正则表达式(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

  1. 其中 α 和 β 是由终结符与非终结符构成的字串,A 是非终结符,γ 是终结符或非终结符。
    [^2]: 其中 A 是非终结符,γ 是终结符或非终结符。即允许 A 被重写为 γ,但不像1型文法那样与 A 的上下文有关。
    [^3]: 其中 A 和 B 是非终结符,a 是终结符。 

2006-03-03 00:19
status: part
comments powered by Disqus