编译原理--正则表达式

不念不忘少年蓝@ 2022-03-22 08:58 486阅读 0赞

### 文章目录 ###

*  定义
 *  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的代数定理 #

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

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

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