正則表達式
語言 L={a}{a,b} * ({ε} ∪ ({ .,_ }{ a,b }{ a,b }*))
正則表達式 (Regular Expression)是一種用來描述正則語言的更緊湊的表示方法
例
r = a(a|b) * ( ε | (.| _)(a|b)(a|b) * )
正則表達式可以由較小的正則表達式按照特定規(guī)則遞歸地構(gòu)建胚吁。每個正則表達式 r 定義（表示）一個語言蒿褂，記為L(r)秆麸。這個語言也是根據(jù)r 的子表達式所表示的語言遞歸定義的。
- 正則表達式的定義
ε 是一個RE 舌厨，L(ε) = {ε}
如果 a ∈∑ ，則a 是一個RE 悉默，L(a) = {a}
假設(shè) r和 和 s 都是 RE 曲梗，表示 的 語言分別是 L(r) 和L(s) ，則
r|s 是一個RE弄跌，L(r|s) = L(r)∪L(s)
rs 是一個RE 甲喝，L(rs) = L(r) L(s)
r* 是一個RE，L(r*)= (L(r)) *
(r) 是一個RE铛只，L((r)) = L(r)
運算的優(yōu)先級：*埠胖、連接糠溜、|
-
例
令 ∑ = {a, b} ，則
L(a|b) = L(a) ∪ L(b) ={a} ∪直撤 = {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} * = {ε, a, b, aa, ab, ba, bb, aaa, ...}
L(a|a* b) = { a, b, ab, aab, aaab, . . .}
- 例 C語言無符號整數(shù)的RE
十進制整數(shù)的RE
(1|...|9)(0|...|9) * |0
八進制整數(shù)的RE
0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7) *
十六進制整數(shù)的RE
0x(0|1|...|9|a|...| f |A|…|F)(0|...|9|a|...| f |A|…|F ) *
正則語言
可以用RE定義的語言叫做
正則語言 (regular language) 或 正則集合 (regular set)RE的代數(shù)定律
RE的代數(shù)定律.png
- 正則文法與正則表達式等價
對任何正則文法 G 非竿，存在定義同一語言的
正則表達式 r
對任何正則表達式 r ，存在生成同一語言的
正則文法 G
正則定義（Regular Definition)
正則定義.png
- 例1
C 語言中標(biāo)識符的正則定義
digit → 0|1|2|…|9
letter_ → A|B|…|Z|a|b|…|z|_
id → letter_(letter_|digit) *
- 例2
（整型或浮點型）無符號數(shù)的正則定義
digit → 0|1|2|…|9
digits → digit digit *
optionalFraction → .digits|ε
optionalExponent → ( E(+|-|ε)digits )|ε
number → digits optionalFraction optionalExponent
2 2.15 2.15E+3 2.15E-3 2.15E3 2E-3
