研究目的

• 当研究室では並列プログラミングフレームワーク Cerium Task Manager でプログラミングを行っている。

今日の話題

• 正規表現について
• オートマトンについて
• 正規表現の基本三演算
• 正規表現の他の演算

正規表現について

• 文字列の一部をパターン化して表現する手法
• 文章からあるパターン文字列を検索したいときに使用する
  (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)
• 正規表現は有限オートマトンで表現できる

オートマトンについて

正規表現の基本三演算

• 正規表現は「連接」「選択」「繰返し」の演算が備えられている R,S という 2 つの正規表現が存在すると仮定する。
  連接 「RS」: R の直後に S が続くパターン
  
  (e.g.) RS, RRS, RSS, RRSS, ...
  
  選択 「R|S」: R もしくは S が出現するパターン
  
  (e.g.) R, S, RS, ...
  
  繰返し 「R*S」: 「*」の直前(R)が 0 回以上出現するパターン
  
  (e.g.) S, RS, RRS, RRRS, ...
• 基本三演算は結合順位が存在する
  
  繰返し > 連接 > 選択

正規表現の他の演算

• 「R+S」: 「+」の直前のパターンが 1 回以上出現するパターン
  
  (e.g.) RS, RRS, RRRS, ...
  R+S ≡ R(R*)S
• 「R?S」: 「?」の直前のパターンが 0 or 1 回出現するパターン
  
  (e.g.) S, RS
• 「R{1,3}」: 「{}」の直前のパターンが 1 or 3 回出現するパターン
  
  (e.g.) R, RR, RRR
• 「R{1,}」: 「{}」の直前のパターンが 1 回以上出現するパターン
  
  (e.g.) R, RR, RRR, ...
  R+S ≡ R(R*)S ≡ R{1,}S