编译器笔记5-词法分析-正则表达式

正则表达式

语言 L={a}{a,b} * ({ε} ∪ ({ .,_ }{ a,b }{ a,b }*))

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

例

r = a(a|b) * ( ε | (.| _)(a|b)(a|b) * )

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

• 正则表达式的定义

ε 是一个RE ，L(ε) = {ε}
如果 a ∈∑ ，则a 是一个RE ，L(a) = {a}
假设 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)

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

1. 例
   令 ∑ = {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} * = {ε, a, b, aa, ab, ba, bb, aaa, ...}
L(a|a* b) = { a, b, ab, aab, aaab, . . .}

2. 例 C语言无符号整数的RE

十进制整数的RE
(1|...|9)(0|...|9) * |0

八进制整数的RE
0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7) *

十六进制整数的RE
0x(0|1|...|9|a|...| f |A|…|F)(0|...|9|a|...| f |A|…|F ) *

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

• RE的代数定律

RE的代数定律.png

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

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

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

正则定义（Regular Definition)

正则定义.png

• 例1

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

digit → 0|1|2|…|9
letter_ → A|B|…|Z|a|b|…|z|_
id → letter_(letter_|digit) *

• 例2

（整型或浮点型）无符号数的正则定义

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