正規表現ライブラリ 一般的なもの GNU regex GNU rx pcre Henry Spencer’s regex.

Slides:



Advertisements
Similar presentations
FxUG in Toyama # Presented by wacky. 最近 AMF 3 の Encode/Decode を実装してみました。 そこで得た知識を共有したいと思います! 30分後には … AMF の基本構造が分かっている AMF の得手不得手が分かっている BlazeDS.
Advertisements

正規表現からのDFA直接構成.
文法と言語 ー字句解析とオートマトンlexー
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
The Perl Conference Japan ’98 朝日奈アンテナによる コンテンツ情報の取得と利用
Regex takatosi.
プログラミング基礎I(再) 山元進.
コンパイラ 2011年10月17日
プログラミング言語としてのR 情報知能学科 白井 英俊.
2008/03/01 D-BOF k.inaba はじめての initial D 2008/03/01 D-BOF k.inaba
基礎プログラミングおよび演習 第9回
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
情報科学1(G1) 2016年度.
SWAT I18N 概要 付け足した機能(実行時に言語の切り替え-i18nの範囲で) 問題点(細かい技術的問題、根本的問題) 今後
条件式 (Conditional Expressions)
プログラミング演習II 2004年12月 21日(第8回) 理学部数学科・木村巌.
日本大学 文理学部 情報システム解析学科 谷研究室 益田真太郎
計算の理論 I -講義について+αー 月曜3校時 大月美佳.
コンパイラ 2012年10月15日
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
補足説明.
岩村雅一 知能情報工学演習I 第8回(後半第2回) 岩村雅一
初めてのTSF 囚人.
関数とポインタ 値呼び出しと参照呼び出し swapのいろいろ 関数引数 数値積分
プログラミング言語論 第3回 BNF記法について(演習付き)
文法と言語 ー字句解析とオートマトンlexー
勉強会その3    2016/5/1 10 8分35秒 データの表現 演算.
文法と言語 ー字句解析とオートマトンlexー
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
東京工科大学 コンピュータサイエンス学部 亀田弘之
独習XML 第2章 XML文書の構成要素 2.1 XMLの文字と文字列 2.2 コメント
プログラミング 4 記憶の割り付け.
プログラミング言語入門.
画像処理プログラムの説明.
プログラミング演習I 2003年5月7日(第4回) 木村巌.
第7回 プログラミングⅡ 第7回
初めてのTSF 囚人.
プログラミング基礎B 文字列の扱い.
平成20年10月5日(月) 東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
プログラミング 4 整列アルゴリズム.
計算の理論 I 正則表現とFAとの等価性 月曜3校時 大月 美佳 平成15年6月16日 佐賀大学知能情報システム学科.
フロントエンドとバックエンドのインターフェース
東京工科大学 コンピュータサイエンス学部 亀田弘之
プログラミング演習I 2004年5月19日(第5回) 理学部数学科・木村巌.
長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
形式言語とオートマトン 中間試験解答例 2016年11月15実施 中島毅.
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
プログラミング 3 2 次元配列.
地域情報学 C言語プログラミング 第2回 変数・配列、型変換、入力 2017年10月20日
日本語独特のL10N問題とは? 各社仕様の拡張文字 複数の符号化 規格の混乱など Unicodeとのマッピング
情報処理Ⅱ 第2回 2005年10月14日(金).
情報処理Ⅱ 第2回 2006年10月13日(金).
アルゴリズムとデータ構造1 2009年6月15日
文法と言語 ー字句解析とオートマトンlexー
情報処理Ⅱ 2006年11月24日(金).
情報処理Ⅱ 第7回 2004年11月16日(火).
~sumii/class/proenb2009/ml6/
情報処理Ⅱ 2007年12月3日(月) その1.
コンパイラ 2012年10月11日
アルゴリズムとデータ構造 2010年6月17日
PROGRAMMING IN HASKELL
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
情報処理Ⅱ 第2回 2004年10月12日(火).
情報処理Ⅱ 2005年11月25日(金).
情報処理Ⅱ 小テスト 2005年2月1日(火).
ネットワーク勉強会 SSH パケット詳細 2001年10月24日 データベース研究室 学部4年 石川 卓司.
Presentation transcript:

正規表現ライブラリ 一般的なもの GNU regex GNU rx pcre Henry Spencer’s regex

GNU regex GNU Rx gawk、GNU grepなどで使用されている rubyの正規表現ルーチンはこれに修整を加えたものである GNU regexの置き換えを目指したもので、GNU sed(2.05)や Guile などで使われている

pcre (Perl Compatible Regular Expression) 1.5以降のPythonで使われている Perlのものと同様の正規表現演算子をサポートしている ftp://ftp.cus.cam.ac.uk/pub/software/programs/pcres Henry Spencer’s regex Tcl等で使われている Perlで使っている正規表現ルーチンの基となった ftp://ftp.zoo.toronto.edu/pub/bookregexp.shar ftp;//ftp.zoo.toronto.edu/pub/regex.shar

その他 mawk ftp://ftp.whidbey.net/pub/brennan/

正規表現エンジンの一般的動作 入力として与えられた正規表現を内部表現の「バイトコード」に変換する 変換されたバイトコードとマッチ対象文字列を使ってマッチングを行う マッチングに使用するエンジンの種類には大きくNFAとDFAの二種類がある

正規表現ルーチンの多バイト 文字対応のポイント 一文字が1バイトであると決め打ちしない 多バイト文字をまたがってマッチしたりしない 多バイト文字の一部分のみにマッチしない []の中に多バイト文字がくることを考慮する 繰り返し(* , +, ?)の対象で泣き別れを起こさない

[]の実装における違い serowさん方式 …単純列挙 t^2さん方式 …昇順に並べられた範囲のリスト ビットベクター方式 …8bit幅256文字分のビットベクターを16bit幅に拡張する

op 文字 文字指定 範囲指定の上下限 範囲指定 serowさん方式 op 下限 上限 256ビットのベクター等 範囲指定の上下限 ・一文字分でも範囲指定を使用する ・上下限のペアは常にソートされた状態にする t^2さん方式

jperlでの正規表現実装例の詳細 オペコードに対応する 引数(あれば) オペコード 次のノードへのポインタ 上の図のようなノードを組み合わせたものが「コンパイル 済み正規表現」

パターンの例   /あ*/ compiling RE `あ*' size 7 first at 1 1: CURLYX {0,32767}(6) 3: EXACT <あ>(5) 5: WHILEM(0) 6: NOTHING(7) 7: END(0) minlen 0 Omitting $` $& $' support.

パターンの例その2  /ab+/ compiling RE `ab+' size 6 first at 1 rarest char b at 0 rarest char b at 1 1: EXACT <a>(3) 3: PLUS(6) 4: EXACT <b>(0) 6: END(0) anchored `ab' at 0 floating `b' at 1..2147483647 (checking anchored) minlen 2 Omitting $` $& $' support.

jperlにおけるキャラクタークラスの実装 オリジナル op 次のノードへの ポインタ フラグ ビットベクター jperl op ビットベクターへのポインタ

今後の課題 UNICODE対応 (特にサロゲートペアの扱い) locale対応 (同一視する文字の環境による変化)