2011年8月13日 星期六

Balancing Group in Regular Expressions

先來看看這個字串:
$AAA(BBB $(CCC($(DDD))),$(EEE($(FFF)))),$GGG(HHH) 

我們稱它為字串 X 好了, 在此字串中有個規則 - $token(argument), 然而 argument 除了有一般的字串外, 又可以有更多的 $token(argument), 以此類推. 如果只單看第一層級, 亦即先不看 argument 裡更多層的 $token(argument), 我們應該要得到:
    token    argument
    -----    --------
    AAA      BBB $(CCC($(DDD))),$(EEE($(FFF)))
    GGG      HHH

如果我們不想要動用到 lexical analyzer 及 parser, 我們也絕對也不會想要使用土方法來解析它, 那我們就用 regular expressions 吧.

要取出 tag 很簡單, 但要取出 argument 就不是那麼容易了. 幸好在 regular expressions 中可使用 balancing group 語法, 用以 "捕捉" 字串中成對符號裡的字串, 舉例來說, pattern (?<open>\().*(?<close-open>\)) 可取出成對的左括號(第一個找到的左括號)及右括號(在左括號後最後一個右括號)中的字串, 放入名為 close 的字串組.
利用 balancing group 的語法, 我們最後寫出了如下的 pattern:
[\$](?<tag>\w*)(?<start>\()((?<s>\().*(?<a-s>\))|[^\(\)])*(?<arg-start>\))

以此 pattern, 就可將第一層的 token 及 argument 抓出, 分別放入名為 tag 及 arg 的字串組. 我們可以將此 pattern 拆開來解釋:
[\$]                # 一個 $
(?<tag>\w*)         # 任意長度的英文字母, 放入 tag 字串組
(?<start>\()        # 一個左括號, 開始 balancing group
(
  (?<s>\()          #
  .*                # 左括號+任意長度的字元+右括號
  (?<a-s>\))        #
|
  [^\(\)]           # 非左/右括號的字元
)*
(?<arg-start>\))    # 一個右括號, 並將 start 至 arg 中的字串放入 arg

然而這個 pattern 的重點是在 start 與 arg 中的 pattern ((?<s>\().*(?<a-s>\))|[^\(\)])*, 它會比對兩種 pattern, 一是看到左括號後, 就一定要找到相對應的右括號, 二是非左右括號的字元.


更多資訊:
Regular Expressions Reference
Expresso - The premier regular expression development tool
Flagrant Badassery - Fun With .NET Regex Balancing Groups
Wes' Puzzling Blog - Matching Balanced Constructs with .NET Regular Expressions

沒有留言:

張貼留言