編譯器設計中正則表示式的規則是什麼？

有限自動機接受的語言可以用簡單的表示式（稱為正則表示式）簡單地定義。它是一種描述任何語言的有效方法。正則表示式也可以表示為表示字串的一系列模式。正則表示式用於連線字串中的字元序列。字串搜尋演算法使用此模式來發現字串上的操作。

正則表示式有各種規則，如下所示：

  • ε 是一個正則表示式。

  • 兩個正則表示式R1 和 R2 的並集。

即，R1 + R2 或 R1|R2 也是一個正則表示式。

  • 兩個正則表示式R1 和 R2 的連線。

即，R1 R2 也是一個正則表示式。

  • 正則表示式 R 的閉包，即 R* 也是一個正則表示式。

  • 如果 R 是一個正則表示式，則 (R) 也是一個正則表示式。

代數法則

R1|R2=R2|R1 or R1+ R2=R2+ R1 (Commutative)
R1| (R2|R3)=(R1| R2)|R3 (Associative)
Or
R1+ (R2+ R3)=(R1+ R2)+R3
R1 (R2|R3)=(R1R2)R3 (Associative)
R1| (R2|R3)=R1R2| R1R3 (Distributive)
Or
R1 (R2+ R3)=R1R2+R1R3
ε R=R ε=R (Concatenation)

示例1 - 為在 Σ={a,b} 上的以下語言編寫正則表示式

  • 長度為零或一的字串。

答案：ε | a | b 或 (ε+a+b)

  • 長度為二的字串。

答案：aa | ab | bb 或 (aa+ab+ba+bb)

  • 偶數長度的字串

答案：(aa|ab|ba|bb)* 或 (aa+ab+ba+bb)*

  • 所有 a 和 b 字串的集合，至少出現兩次 aa。

答案 -(a+b)*aa(a+b)aa(a+b)*

示例2 - 為以下語言查詢正則表示式。

  • L={ε,1,11,111,….}
{∴ 10=ε,11=1,12=11,13=111…..}

答案：1*

  • L={ε,11,1111,111111,…..}

答案：(11) $\ast$

  • L = 0 和 1 的所有字串集合 = {ε,0,1,01,11,00,000,101,……}

答案：(0+1) $\ast$ 或 (0|1) $\ast$

  • L = 以 11 結尾的所有 0 和 1 字串的集合。

答案：(0+1) $\ast$ 11

  • L = 以 0 開頭並以 1 結尾的所有 0 和 1 字串的集合。

答案：0(0+1) $\ast$ 1

示例3 - 編寫正則表示式，其中字串右端第二個字母為 1，其中 Σ={0,1}。

答案：(0+1) $\ast$ 1(0+1)

示例4 - 為在 Σ={a,b} 上的以下語言編寫正則表示式

  • L=至少出現一次雙字母的字串集合

答案：(a+b)*(aa+bb)(a+b)*

  • L = 字串開頭和結尾都有雙字母的字串集合。

答案：(aa+bb)(a+b)*(aa+bb)

  • L = 字串開頭或結尾有雙字母的字串集合。

答案：(aa+bb)(a+b)*+ (a+b)*(aa+bb)+(aa+bb)(a+b)*(aa+bb)

更新於：2021年10月26日

4K+ 次檢視

啟動您的職業生涯

透過完成課程獲得認證

開始
廣告