# HG changeset patch # User Masataka Kohagura # Date 1430219287 -32400 # Node ID e456138b7b1e46e8c4cbc712ef87a234b77393ff # Parent a4227cbaa7b3009a297fc105941e33f252606053 add 0504.html diff -r a4227cbaa7b3 -r e456138b7b1e 2015/0504.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/0504.html Tue Apr 28 20:08:07 2015 +0900 @@ -0,0 +1,228 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium での正規表現の実装

+
+
+ Masataka Kohagura 28th, April , 2015 +
+
+ +
+

研究目的

+
    +
  • + 当研究室では並列プログラミングフレームワーク 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
    +
    • +
+
+ + + +
+ +