编译原理(八)之正则表达式

编译原理(八) 之 正则表达式

概念

正则表达式 是一种用来描述正则语言的更紧凑的表示方法
比如某个语言L = {a}{a, b} * ( {ε} ∪ ( { . , _ } {a , b} { a, b }* ) )
利用正则表达式:
r = a (a | b) * (ε | (. | _) (a | b) (a | b)* )
正则表达式可以由较小的正则表达式按照特定规则 递归 地构建 , 每个正则表达式r 定义一个语言, 记为 L ® .这个语言也是根据r的子表达式所表示的语言递归定义的.

定义

ε 是一个正则表达式(RE) L (ε) = { ε }
如果a ∈ ∑ , 则a是一个RE, L(a) = {a}
假设r 和 s都是RE, 表示的语言分别是 L® 和 L (s) , 则:
r | s 是一个RE, L(r | s) = L ® ∪ L(s)
r s是一个RE, L(rs) = L®L(s)
r* 是一个RE, L(r*) = (L®)*
® 是一个正则表达式 L( ® ) = L®

优先级 * , 连接, |

例:
∑ = {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} = {aa, ab, ba, bb}

L(a*) = (L(a))* = {a}* = {ε, a, aa, aaa, .....}
L((a | b) *) = (L(a | b))* = {ε, a, b, aa, ab, ba, bb, .......} 

L(a | a* b) = {a, b, ab, aab, aaab , .....}

C语言中的 无符号整数的正则表达式
十进制整数
(1 | … | 9) (0 | … | 9)* | 0

八进制整数:
0 (1 | …| 7) (0 | …| 7)*

十六进制整数:
0x (1 | … | 9 | a | …| f) (0 | …| 9 | a | … | f)*

用正则表达式表示的语言叫做正则语言或者正则集合

RE的代数定律

定律	描述
r | s = s | r	| 是可以交换的
r | (s | t ) = (r | s) | t	|是可以结合的
r (s t)| (r s) t	连接是可以结合的
r (s| t) = r s | r t 或者 (s | t) r = sr | tr	链接对是可以分配的
εr = rε = r	ε四连接的单位元
r* = (r | ε)*	闭包一定包含ε
r** = r*	*具有幂等性

正则文法与正则表达式等价

任何正则文法G 存在定义同一语言的正则表达式r
任何正则表达式r, 存在生成同一语言的正则文法G

正则定义

正则定义是具有以下形式的定义序列
他们给一些RE命名, 并在之后的RE 中像使用字母表中符号一样使用这些名字
d1 -> r1
d2 -> r2
…
dn -> rn
每个di都是一个新符号, 他们都不在字母表∑中,并且各不相同
每个ri是字母表∑∪ {d1, d2, …di-1}上的正则表达式

C语言中的标识符正则定义

digit  -> 0 | 1 | 2 | .... | 9
letter_  -> A | B | ...| Z | a | b | ...| z | _
id -> letter_ (letter_ | dight) *

(整数或者浮点数) 无符号数的正则定义
digit -> 0 | 1 | 2 | … | 9
digits -> digit digit *
小数部分 -> .dights | ε
指数部分 -> ( E(+|-|ε)digits ) | ε
数字 -> digits 小数部分 指数部分
2 2.15 2.15E-3 2.15E3