111 年 國立臺灣大學語言學研究所《語言與計算方法》

這是一題關於正規表示式 (regex) 的應用題，主要測試考生對 regex 語法、組成原理的理解，以及如何設計 regex 來匹配特定模式並避免過度匹配 (overgeneration)。

1.1 題目核心概念：正規表示式的基本語法與元字元 (metacharacters) 的意義

給定的正規表示式為：(\\w+),\\s(Mr|Ms|Mrs|Dr).?\\s(\\w+)

這個 regex 的目的是匹配「姓, 稱謂 名」這樣的姓名格式。我們逐一解釋其中每個字元的意義：

• ( 和 ): 這是一對括號，用於分組。在此，它將 \\w+、(Mr|Ms|Mrs|Dr) 和 \\w+ 分別視為獨立的組，以便後續處理或計數。
• \\w: 這是一個預定義的字元類，代表任何字母數字字元（字母、數字）以及底線 (_)。在很多 regex 引擎中，它也包含一些 Unicode 字元。
• +: 這是一個量詞，表示它前面的元素（在這裡是 \\w）必須出現一次或多次。所以 \\w+ 表示匹配一個或多個字母數字字元或底線。
• ,: 這是一個字面字元，表示匹配逗號。
• \\s: 這是一個預定義的字元類，代表任何空白字元，包括空格、定位符 (tab)、換行符等。
• |: 這是一個邏輯「或」運算子，用於選項。例如，(Mr|Ms|Mrs|Dr) 表示匹配 "Mr" 或 "Ms" 或 "Mrs" 或 "Dr"。
• .: 這是一個萬用字元，代表匹配除了換行符以外的任何單一字元。
• ?: 這是一個量詞，表示它前面的元素（在這裡是 .）可以出現零次或一次。

綜合解釋：

1. (\\w+): 匹配並捕捉一個或多個字母數字字元（通常是姓氏）。
2. ,: 匹配字面上的逗號。
3. \\s: 匹配一個空白字元。
4. (Mr|Ms|Mrs|Dr): 匹配並捕捉 "Mr"、"Ms"、"Mrs" 或 "Dr" 中的任一個。
5. .?: 匹配一個句號（.）零次或一次。這裡的句號是稱謂後面的標點符號，例如 "Mr."。? 使得這個句號成為可選的。
6. \\s: 匹配一個空白字元。
7. (\\w+): 再次匹配並捕捉一個或多個字母數字字元（通常是名字）。

範例對應：

• Smith, Mr. John：Smith 匹配 (\\w+)，, 匹配 ,，\\s 匹配空格，Mr 匹配 (Mr|Ms|Mrs|Dr)，. 匹配 .，\\s 匹配空格，John 匹配 (\\w+)。
• Davis, Ms Nicole：Davis 匹配 (\\w+)，, 匹配 ,，\\s 匹配空格，Ms 匹配 (Mr|Ms|Mrs|Dr)，\\s 匹配空格，Nicole 匹配 (\\w+)。（此處稱謂後無句號，.? 匹配零次）。

【答案】

• ( 和 ): 分組符號，用於將部分模式組合起來。
• \\w: 匹配字母數字字元和底線。
• +: 量詞，表示前一個字元或群組出現一次或多次。
• ,: 匹配字面上的逗號。
• \\s: 匹配任何空白字元。
• |: 「或」運算子，用於列出多個可能的選項。
• .: 萬用字元，匹配除了換行符以外的任何單一字元。
• ?: 量詞，表示前一個字元或群組出現零次或一次。

1.2 題目核心概念：設計 regex 匹配特定構式，並處理過度蔓生問題

第一部分：抽取【一X-Y】構式

我們要設計一個 regex 來匹配形如「一心一意」、「一來一往」、「一步一腳印」的構式。
這些構式的特點是：

1. 開頭是「一」。
2. 中間是某個詞 (X)。
3. 接著是「-」。
4. 結尾是某個詞 (Y)。
5. X 和 Y 可以是超過一個漢字。

一個基本的 regex 可以是：一.*?-.?
這個 regex 的解釋：

• 一: 匹配字面上的「一」。
• .*?: 匹配任意字元 (.) 零次或多次 (*)，並且是「非貪婪」模式 (?)。非貪婪模式會盡可能少地匹配字元，直到遇到下一個模式。這很重要，因為我們不希望它匹配到句子的結尾，而是盡快找到下一個 -。
• -: 匹配字面上的連字號。
• .*?: 再次匹配任意字元零次或多次，非貪婪模式。

然而，題目要求 X 和 Y 可以是「超過一個漢字」。在中文語境下，通常我們將詞語視為連續的漢字。因此，更精確的 regex 應該是：
一[\u4e00-\u9fff]+-[\u4e00-\u9fff]+

解釋：

• 一: 匹配字面上的「一」。
• [\u4e00-\u9fff]+: 這是 Unicode 範圍表示法，匹配一個或多個（+）中文字符（從 Unicode 的 U+4E00 到 U+9FFF）。這部分用來匹配 X。
• -: 匹配字面上的連字號。
• [\u4e00-\u9fff]+: 再次匹配一個或多個中文字符，用來匹配 Y。

進一步考量（避免過度蔓生）

題目要求避免「過度蔓生」，並舉例「一天一餐」、「一張一塊錢」、「一天又一天」是偽構式。
這些偽構式與我們想要匹配的「一心一意」、「一來一往」的區別在於：

• 「一心一意」、「一來一往」：結構是「一 + 詞 + - + 詞」。這裡的「詞」通常是單音節或雙音節的，且有相對固定的搭配語義。
• 「一天一餐」、「一張一塊錢」：結構是「一 + 時間單位 + 一 + 單位」。或者「一 + 單位 + 一 + 單位」。它們的語義結構是「每隔一段時間/空間就發生一次」的感覺，不是「同樣的狀態/行為反覆」的感覺。
• 「一天又一天」：結構是「一 + 時間單位 + 又 + 一 + 時間單位」。這表示時間的持續推進，也不同於「一心一意」的重複。

如何避免過度蔓生？

1. 更嚴格的詞語定義/詞性限制:

   • 如果我們有詞典或詞性標記，可以限制 X 和 Y 必須是特定類型的詞（例如名詞、動詞），或者必須是已知的固定搭配中的詞。
   • 例如，一(心|來|步)-((心|意)|(來|往)|(腳|印)) 這樣的 regex 只能匹配特定幾個詞。但這就失去了靈活性。

2. 利用上下文信息:

   • 最有效的方法是結合外部知識，例如詞典、語法規則，或者通過機器學習模型來判斷。
   • 對於 regex 本身，可以嘗試加入一些「負向預測」（negative lookarounds），但對於中文構式的區分，這會非常複雜。

核心觀念

本題資料不足，無法唯一求出句子與 A–H 的對應，也無法確定空格 $(a)$–$(i)$ 或錯誤訊息。

題目只說甲、乙、丙、丁、戊是五個「小模組」，但沒有定義各模組所代表的語言關係。例如：

• 甲是否表示主詞關係？
• 乙是否表示受詞關係？
• $x>y$ 的方向代表「$x$ 支配 $y$」或「$y$ 支配 $x$」？
• 模組是否依照詞性、句法依存、語意角色或詞序產生連結？

上述規則均未提供。

題目所給的例子：

$$3>1,\quad 3>4,\quad \text{none},\quad 3>2,\quad \text{none}$$

只說明某句輸入會產生五個模組的輸出，卻沒有說明五個模組各自的判斷標準。因此，例子不能用來建立唯一的推理規則。

解題方法

若將五個模組視為未定義的黑箱，則對任意一個句子排列，都可以設計出相應的模組規則，使表二的非空連結成立；同樣地，空白欄位也可以填入任意合法索引連結。

例如，句子 2 與句子 4 都包含表 A、C 中出現的大部分索引，因此僅憑索引形式無法判斷：

$$A\leftrightarrow 2,\ C\leftrightarrow 4$$

或