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

概念

正则表达式 是一种用来描述正则语言的更紧凑的表示方法

比如某个语言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的代数定律

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

任何正则文法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