正規表示式與 Kleene 定理

運算子優先序(operator precedence)

當你讀 2 + 3 × 4 時,你知道乘法先算,得到 14 而不是 20,因為乘法的結合力比加法強。正規表示式也需要同樣的不成文慣例,好讓像 ab+c 這樣的表示式只有一種意義。運算子優先序就是在省略括號時,決定什麼與什麼結合的那組規則。

標準的優先序由結合最緊到最鬆依序是:Kleene 星號最先,然後串接,再來才是聯集。所以 ab* 意指 a(b*),而非 (ab)*,因為星號只抓住它旁邊的那個 b。而 ab+c 意指 (ab)+(c),也就是字串 ab 與 c 的聯集,而非 a(b+c),因為串接的結合力比聯集強。要推翻這些預設,你就用括號,與算術中完全一樣:(ab)* 強迫星號作用在整個群組 ab 上,而 a(b+c) 強迫聯集在串接之前發生。

搞錯優先序是書寫或閱讀正規表示式時最常見的錯誤來源之一,因為差別是無聲的:ab* 與 (ab)* 都合法,卻標示完全不同的語言。猶豫時就加括號,它們從不改變一個已正確的表示式的意義,卻能讓你的意圖毫不含糊。優先序純粹是剖析上的方便,並不改變那三個基本運算本身。

ab* 標示 { a, ab, abb, abbb, ... }(一個 a,後接任意數量的 b),但 (ab)* 標示 { ε, ab, abab, ... }(任意數量的區塊 ab)。相同的符號、不同的分組、不同的語言。

星號結合最緊,其次串接,再來聯集。

優先序是無聲的、容易誤讀;ab* 不是 (ab)*。不確定時就加括號:多餘的括號絕不會改變一個正確表示式的意義。

又称
precedence rulesbinding strength優先權結合強度