編譯原理 - 正則表示式

詞法分析器需要掃描並識別屬於當前語言的有限集合的有效字串/標記/詞素。它搜尋由語言規則定義的模式。

正則表示式能夠透過定義有限符號串的模式來表達有限語言。由正則表示式定義的語法稱為正則語法。由正則語法定義的語言稱為正則語言。

正則表示式是指定模式的重要表示法。每個模式匹配一組字串，因此正則表示式充當一組字串的名稱。程式語言標記可以用正則語言來描述。正則表示式的規範是遞迴定義的一個例子。正則語言易於理解且具有高效的實現。

正則表示式遵循許多代數定律，這些定律可用於將正則表示式操作成等價形式。

運算

語言上的各種運算有：

• 兩個語言L和M的並集寫成

  L U M = {s | s屬於L或s屬於M}

• 兩個語言L和M的連線寫成

  LM = {st | s屬於L且t屬於M}

• 語言L的克林閉包寫成

  L* = 語言L的零次或多次出現。

表示法

如果r和s是表示語言L(r)和L(s)的正則表示式，則

• 並集：(r)|(s)是表示L(r) U L(s)的正則表示式

• 連線：(r)(s)是表示L(r)L(s)的正則表示式

• 克林閉包：(r)*是表示(L(r))*的正則表示式

• (r)是表示L(r)的正則表示式

優先順序和結合性

• *, 連線(.)和|（豎線）都是左結合的
• *具有最高優先順序
• 連線(.)具有第二高優先順序。
• |（豎線）具有最低優先順序。

用正則表示式表示語言的有效標記

如果x是正則表示式，則

• x*表示x的零次或多次出現。

  即，它可以生成{ e, x, xx, xxx, xxxx, … }

• x+表示x的一次或多次出現。

  即，它可以生成{ x, xx, xxx, xxxx … } 或 x.x*

• x?表示x最多出現一次

  即，它可以生成{x}或{e}。

[a-z]是英語語言的所有小寫字母。

[A-Z]是英語語言的所有大寫字母。

[0-9]是數學中使用的一切自然數字。

使用正則表示式表示符號的出現

字母 = [a-z] 或 [A-Z]

數字 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或 [0-9]

符號 = [ + | - ]

使用正則表示式表示語言標記

十進位制 = (符號)^?(數字)⁺

識別符號 = (字母)(字母 | 數字)*

詞法分析器剩下的唯一問題是如何驗證用於指定語言關鍵字模式的正則表示式的有效性。一個被廣泛接受的解決方案是使用有限自動機進行驗證。