编译原理--正则表达式

文章目录

定义
RE的代数定理
正则文法与正则表达式等价

语言 L = { a } { a , b } ∗ ( { ϵ } ∪ ( { . , _ } { a , b } { a , b } ∗ ) ) L=\{a\}\{a,b\}^*(\{\epsilon \} \cup (\{.,\_\}\{a,b\}\{a,b\}^*)) L={ a}{ a,b}∗({ ϵ}∪({ .,_}{ a,b}{ a,b}∗))

这个语言是指，由a开头，后接任意长度的a、b串，然后再接空串（代表结束）。或者是接以.或_开头的，后接长度大于等于1的a、b串。

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

以上面的语言举例，写成正则表达式则可表示成： r = a ( a ∣ b ) ∗ ( ϵ ∣ ( . ∣ ) ( a ∣ b ) ( a ∣ b ) ∗ ) r=a(a|b)^*(\epsilon | (.|_)(a|b)(a|b)^*) r=a(a∣b)∗(ϵ∣(.∣)(a∣b)(a∣b)∗)

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式r定义一个语言。记为L(r)。这个语言也是根据r的子表达式所表示的语言递归定义的。

定义

如果 ϵ \epsilon ϵ是一个RE， L ( ϵ ) = { ϵ } L(\epsilon) = \{\epsilon\} L(ϵ)={ ϵ}
如果 α ∈ ∑ \alpha \in \sum α∈∑，则 α \alpha α是一个RE, L ( α ) = { α } L(\alpha)=\{\alpha\} L(α)={ α}
假设r和s都是RE，表示的语言分别是L(r)和L(s)，则
- r ∣ s r|s r∣s是一个RE， L ( r ∣ s ) = L ( r ) ∪ L ( s ) L(r|s) = L(r) \cup L(s) L(r∣s)=L(r)∪L(s)
- rs（r连接s）是一个RE， L ( r ∣ s ) = L ( r ) L ( s ) L(r|s) = L(r)L(s) L(r∣s)=L(r)L(s)
- r ∗ r^* r∗是一个RE， L ( r ∗ ) = ( L ( r ) ) ∗ L(r^*) = (L(r))^* L(r∗)=(L(r))∗
- ( r ) (r) (r)是一个RE， L ( ( r ) ) = L ( r ) L((r)) = L(r) L((r))=L(r)

注：运算的优先级：*、连接、|

例： ∑ = { a , b } \sum = \{a,b\} ∑={ a,b}，则

L ( a ∣ b ) = L ( a ) ∪ L ( b ) = { a } ∪ { b } = { a , b } L(a|b) = L(a) \cup L(b) = \{a\} \cup \{b\} = \{a,b\} L(a∣b)=L(a)∪L(b)={ a}∪{ b}={ a,b}
L ( ( a ∣ b ) ( a ∣ b ) ) = L ( a ∣ b ) L ( a ∣ b ) = { a , b } { a , b } = { a a , a b , b a , b b } L((a|b)(a|b)) = L(a|b)L(a|b) = \{a,b\}\{a,b\} = \{aa,ab,ba,bb\} L((a∣b)(a∣b))=L(a∣b)L(a∣b)={ a,b}{ a,b}={ aa,ab,ba,bb}
L ( a ∗ ) = ( L ( a ) ) ∗ = { a } ∗ = { ϵ , a , a a , a a a , . . . } L(a^*) = (L(a))^* = \{a\}^* = \{\epsilon,a,aa,aaa,…\} L(a∗)=(L(a))∗={ a}∗={ ϵ,a,aa,aaa,…}
L ( ( a ∣ b ) ∗ ) = ( L ( a ∣ b ) ) ∗ = a , b ∗ = { ϵ , a , b , a a , a b , b a , b b , . . . } L((a|b)^*) = (L(a|b))^* = {a,b}^* = \{\epsilon,a,b,aa,ab,ba,bb,…\} L((a∣b)∗)=(L(a∣b))∗=a,b∗={ ϵ,a,b,aa,ab,ba,bb,…}
L ( a ∣ a ∗ b ) = L ( a ) ∪ L ( a ∗ b ) = L ( a ) ∪ L ( a ∗ ) L ( b ) = { a , b , a b , a a b , a a a b , . . . } L(a|a^*b) = L(a) \cup L(a^*b) = L(a) \cup L(a^*)L(b) = \{a,b,ab,aab,aaab,…\} L(a∣a∗b)=L(a)∪L(a∗b)=L(a)∪L(a∗)L(b)={ a,b,ab,aab,aaab,…}

注：可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)。

RE的代数定理

定律	描述
r \| s = s \| r	\| 是可以交换的
r \| (s \| t) = (r \| s) \| t	\| 是可以结合的
r ( s t ) = ( r s ) t	连接是可以结合的
r (s \| t) = rs \| rt	连接对 \| 是可分配的
ϵ r = r ϵ = r \epsilon r = r \epsilon = r ϵr=rϵ=r	ϵ \epsilon ϵ是连接的单位元
$r^ = (r	\epsilon)^$
r ∗ ∗ = r ∗ r^{*} = r^ r∗∗=r∗	*具有幂等性