# HG changeset patch # User Shinji KONO # Date 1282031056 -32400 # Node ID 8ed65d68caba3ff185c7ded0ab48c284f7523744 # Parent 336542485a9bdaf85a2a237e36d4a5cd8d6a5a9e . diff -r 336542485a9b -r 8ed65d68caba paper.tex --- a/paper.tex Tue Aug 17 16:29:16 2010 +0900 +++ b/paper.tex Tue Aug 17 16:44:16 2010 +0900 @@ -1,13 +1,13 @@ -% Sample file for the use of compsoft style file. +% Sample file for the use of compsoft style file. % \documentclass{compsoft} % \documentclass[L]{compsoft} % \documentclass[S]{compsoft} -% \documentclass[S,L]{compsoft} +% \documentclass[S, L]{compsoft} % \documentclass[K]{compsoft} -% \documentclass[K,L]{compsoft} +% \documentclass[K, L]{compsoft} % \documentclass[U]{compsoft} -% \documentclass[U,L]{compsoft} +% \documentclass[U, L]{compsoft} % Preamble % @@ -46,14 +46,14 @@ % % ここにタイトル英訳 (英文の場合は和訳) を書く． % -\ejtitle{Implementation of Regular Expression Checker with Just-In-Time Compilation.} +\ejtitle{Implementation of Regular Expression Checker with Just-In-Time Compilation. } % % ここに著者英文表記 (英文の場合は和文表記) および % 所属 (和文および英文) を書く． % 複数著者の所属はまとめてよい． % \shozoku{Shinya RYOMA, Shinji KONO}{琉球大学工学部情報工学学科}% -{Dept.\ of Information Engineering, Ryukyu University} +{Dept. \ of Information Engineering, Ryukyu University} % % 出典情報は \shutten とすれば出力される． \shutten @@ -71,13 +71,13 @@ \Jabstract{% 当研究室では, Concinuation based C (CbC)という, 状態遷移記述に適した C の下位 言語を提案している. CbC は ステートメントより大きく, 関数よりも小さな -プログラミング単位, コードセグメントの継続に接続を基本要素としている. -本研究では, 与えられた正規表現を等価な有限状態オートマトンに変換し, +プログラミング単位, コードセグメントの継続に接続を基本要素としている. +本研究では, 与えられた正規表現を等価な有限状態オートマトンに変換し, それを Continuous based Cによる継続, LLVMバイトコード、Cに変換する 正規表現コンパイラ を Python で実装し、速度やプログラミングのしやすさなどの比較を行なった. 特にマルチバイト文字の正規表現検査の高速化は実用的にも重要であり、 現状で使われているgrepの評価の行なった。 -% なお, ここで言うコンパイルは,内部形式/中間表現への変換だけでなく,実行時バイナリの生成までを指す. +% なお, ここで言うコンパイルは, 内部形式/中間表現への変換だけでなく, 実行時バイナリの生成までを指す. } % \maketitle @@ -88,63 +88,63 @@ 実行時コンパイルにかかるオーバーヘッドよりも, コンパイルによって得られる 機械語レベルのプログラムの実行速度が上回る場合において有効であり, たとえ ば Java の HotSpot や Python の PyPy など, 仮想マシンを持つ言語処理系の -最適化技術として利用されている. +最適化技術として利用されている. -実行時コンパイルが可能な対象として, 正規表現検査器に着目した. -現在,正規表現の検査器は, プログラミング言語の組み込み機能やライブラリ等, -さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}. +実行時コンパイルが可能な対象として, 正規表現検査器に着目した. +現在, 正規表現の検査器は, プログラミング言語の組み込み機能やライブラリ等, +さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}. 仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお -り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した検査器の +り, それらを ``コンパイル'' と呼ぶことが多い. 本研究で実装した検査器の ``実行時コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規 表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節). 本研究では, 実行バイナリの生 -成にはコンパイラ基盤であるLLVM, GCC を用いており,検査器全体の実装として -はPythonで実装した. CbC は gcc 4.5 上の実装(\ref{cbc-gcc}) を用いた. +成にはコンパイラ基盤であるLLVM, GCC を用いており, 検査器全体の実装として +はPythonで実装した. CbC は gcc 4. 5 上の実装(\ref{cbc-gcc}) を用いた. 本論文では, まず正規表現のコンパイル方法について説明し, 実装した検査器の 性能調査のために, 正規表現を用いてテキストマッチ処理を行う grep と同等の -機能を実装し, GNU grep との比較を行う. +機能を実装し, GNU grep との比較を行う. \section{正規表現} \subsection{正規表現によるテキストマッチ} 正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用 -されている. 正規表現には定められた文法によって記述され, 例えば,正規表現 -``$a*b$''は''$a$''の0回以上の繰り返し直後, ``$b$'' で終わる文字列(``$b$'' , ``$ab$'', -``$aaaab$'')を受理し, ``$a(b|c)$'' は ``$a$''で始まり,直後が ``$b$'' または -``$c$''で終わる文字列(``$ab$'', ``$ac$'') を受理する. +されている. 正規表現には定められた文法によって記述され, 例えば, 正規表現 +``$a*b$''は''$a$''の0回以上の繰り返し直後, ``$b$'' で終わる文字列(``$b$'' , ``$ab$'', +``$aaaab$'')を受理し, ``$a(b|c)$'' は ``$a$''で始まり, 直後が ``$b$'' または +``$c$''で終わる文字列(``$ab$'', ``$ac$'') を受理する. \subsection{正規表現の演算}\label{subsection:regex} -本論文では, 以下に定義された演算をサポートする表現を正規表現として扱う. +本論文では, 以下に定義された演算をサポートする表現を正規表現として扱う. \begin{enumerate} \item {連接} 二つの言語$L$と$M$の連接($LM$)は, $L$に属する列を一つとり, そのあとに$M$に族する列を連 -接することによってできる列全体から成る集合である. +接することによってできる列全体から成る集合である. \item {集合和} 二つの言語$L$と$M$集合和($L|M$)は, $L$または$M$(もしくはその両方)に属する列全体からなる -集合である. -\item {閉包} 言語$L$の閉包($L*$)とは, $L$の中から有限個の列を重複を許して取り出し, - それらを連接してできる列全体の集合である. +集合である. +\item {閉包} 言語$L$の閉包($L*$)とは, $L$の中から有限個の列を重複を許して取り出し, + それらを連接してできる列全体の集合である. \end{enumerate} -正規表現は,この3つの演算について閉じておリ,この3つの演算によって定義され -る表現は, 数学的には正則表現と定義されている. -本論文では,特に区別のない限り,正則表現と正規表現を同じものとして扱う. +正規表現は, この3つの演算について閉じておリ, この3つの演算によって定義され +る表現は, 数学的には正則表現と定義されている. +本論文では, 特に区別のない限り, 正則表現と正規表現を同じものとして扱う. \subsection{grep} 正規表現は, テキストのパターンをシンプルに記述できるという利点から, テキ ストファイルから, 任意のパターンにマッチするテキストを検索するなどの用途 -に使用される. +に使用される. GNU grep は, それを実現するソフトウェアの一つであり, 引数として与えられ たファイルから, 与えられた正規表現にマッチするテキストを含む行を出力する -機能を持っている. +機能を持っている. ``与えられた正規表現にマッチするテキストを含む''というのは, 行の先頭から 末尾まで正規表現によるマッチングを行い, 正規表現が受理状態になった時点で -``含む'' という解釈を行う.つまり, 正規表現 ''$(a|s)t$'' は, ''$at$''または'' -$st$``を受理する正規表現であり, テキスト行''$math.$``の2~3文字目の''$at$''に一致す -るので grep は ``$math.$'' を出力する. また正規表現''$a*$''は, ``$a$''の0回以上の繰 +``含む'' という解釈を行う. つまり, 正規表現 ''$(a|s)t$'' は, ''$at$''または'' +$st$``を受理する正規表現であり, テキスト行''$math. $``の2~3文字目の''$at$''に一致す +るので grep は ``$math. $'' を出力する. また正規表現''$a*$''は, ``$a$''の0回以上の繰 り返しを受理する正規表現であり, 空文字も受理するので, grep は全ての行を -出力することになる. +出力することになる. \subsection{マルチバイト文字を含む正規表現} @@ -152,25 +152,25 @@ \section{正規表現検査器の実装} 正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以 -下にその変換手方を説明する. +下にその変換手方を説明する. \begin{figure}[b] \begin{center} -\scalebox{0.50}{\includegraphics{fig1.eps}} +\scalebox{0. 50}{\includegraphics{fig1. eps}} \end{center} \caption{``$A$''と``$B$''の連接} \label{figure:concat} \end{figure} \begin{figure}[b] \begin{center} -\scalebox{0.50}{\includegraphics{fig2.eps}} +\scalebox{0. 50}{\includegraphics{fig2. eps}} \end{center} \caption{``$A$''と``$B$''の集合和} \label{figure:union} \end{figure} \begin{figure}[b] \begin{center} -\scalebox{0.50}{\includegraphics{fig3.eps}} +\scalebox{0. 50}{\includegraphics{fig3. eps}} \end{center} \caption{``$A$''の閉包} \label{figure:star} @@ -178,30 +178,30 @@ \subsection{正規表現からNFAへの変換} NFA({\it Non-deterministic Finite Automaton}) は, 入力に対して複数の -遷移先持つ状態の集合であり, 遷移先が非決定的(Non-deterministic)である. -ここでは, NFAを5個組$(Q, \Sigma,, \delta, q_0, F)$で定義する.ただし, +遷移先持つ状態の集合であり, 遷移先が非決定的(Non-deterministic)である. +ここでは, NFAを5個組$(Q, \Sigma, , \delta, q_0, F)$で定義する. ただし, \begin{enumerate} -\item $Q$は状態の有限集合. -\item $\Sigma$は入力記号の有限集合. -\item $q_0$は$Q$の要素で, 開始状態と呼ぶ. -\item $F$は$Q$の部分集合で,受理状態と呼ぶ. -\item $\delta$は,状態と入力記号に対して状態の集合を返す遷移関 - 数.($\varepsilon$遷移を許す) +\item $Q$は状態の有限集合. +\item $\Sigma$は入力記号の有限集合. +\item $q_0$は$Q$の要素で, 開始状態と呼ぶ. +\item $F$は$Q$の部分集合で, 受理状態と呼ぶ. +\item $\delta$は, 状態と入力記号に対して状態の集合を返す遷移関 + 数. ($\varepsilon$遷移を許す) \end{enumerate} -正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義 -した3つの演算について対応するNFAに変換できることから示す. +正規表現が, 等価なNFAに変換できるということを, \ref{subsection:regex}で定義 +した3つの演算について対応するNFAに変換できることから示す. \begin{enumerate} -\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFA. -\item {集合和} 図\ref{figure:union}は正規表現 ``$A|B$''に対応するNFA. -\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFA. +\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFA. +\item {集合和} 図\ref{figure:union}は正規表現 ``$A|B$''に対応するNFA. +\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFA. \end{enumerate} 図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件 -の遷移を現しており,$\varepsilon$遷移と呼ばれる. また, 二重丸で囲まれた -状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保 +の遷移を現しており, $\varepsilon$遷移と呼ばれる. また, 二重丸で囲まれた +状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で, 受理状態を保 持している場合に限り, その文字列を受理したことになる. なお, NFAは同時に 複数の遷移先をもつことがあるので, テキストのマッチング途中で複数の状態を -保持することがある. +保持することがある. 現在実装されている正規表現検査器の多くは, 正規表現を内部的にNFAに変換し て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致 @@ -212,46 +212,46 @@ 価において, NFAベースの正規表現検査器では遷移する状態の数が増えてしまう でマッチングにかかる処理時間が$n$の指数的に増加する問題をベンチマーク 結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースで効率的な -マッチング処理を行う検査器をIBM 7094 機械語で生成する例が紹介されている. +マッチング処理を行う検査器をIBM 7094 機械語で生成する例が紹介されている. \subsection{NFAからDFAへの変換} 非決定的な遷移を行うNFAから, 決定的な遷移を行うDFA({\it Deterministic Finite Automaton})に変換する手法を説明する. なお, 遷移が決定的である ということは, 1つの入力に対して, 遷移する状態がただ1つであるということを -指す. -DFAは, NFAと同様な5個組で$(Q, \Sigma,, \delta, q_0, F)$定義できる. ただ -し,DFAにおいて$\delta$において$\varepsilon$遷移は認められず, また任意 +指す. +DFAは, NFAと同様な5個組で$(Q, \Sigma, , \delta, q_0, F)$定義できる. ただ +し, DFAにおいて$\delta$において$\varepsilon$遷移は認められず, また任意 の状態$q$と入力$\sigma$について, $\delta(q, \sigma) = q'$となる$q'$は$Q$ -の要素となる. つまり, 遷移先が決定的であるということに他ならない. +の要素となる. つまり, 遷移先が決定的であるということに他ならない. -以下に$\varepsilon$遷移を許す$\varepsilon$-NFA $E = (Q_E, -\Sigma,\delta_E, q_0, F_E)$ から等価なDFA $D = (Q_D, \Sigma, -\delta_D, q_D, F_D)$を構成する手順を示す. +以下に$\varepsilon$遷移を許す$\varepsilon$-NFA $E = (Q_E, +\Sigma, \delta_E, q_0, F_E)$ から等価なDFA $D = (Q_D, \Sigma, +\delta_D, q_D, F_D)$を構成する手順を示す. \begin{enumerate} \item $Q_D$は$Q_E$の部分集合全から成る集合であり, おの中で$D$において 到達可能な状態は, $\varepsilon$遷移に関して閉じている$Q_E$の部分 集合$S$に限られる. ここで, 状態$q$において$\varepsilon$遷移に関し て閉じている集合全体を$ECLOSE(q)$と表す. $ECLOSE$を使って$S$を定義 - すると, $S = \displaystyle\bigcup_{q\in{S}}ECLOSE(q)$を満たす$S$. -\item $q_D = ECLOSE(q_0)$. すなわち, $E$の開始状態の$\varepsilon$閉包. -\item $F_D$は$E$の状態の集合で,受理状態を少なくとも一つ含むもの全体から - なる集合である. すなわち,$F_D = \{S | S \in Q_D \wedge S \cap F_E \ne + すると, $S = \displaystyle\bigcup_{q\in{S}}ECLOSE(q)$を満たす$S$. +\item $q_D = ECLOSE(q_0)$. すなわち, $E$の開始状態の$\varepsilon$閉包. +\item $F_D$は$E$の状態の集合で, 受理状態を少なくとも一つ含むもの全体から + なる集合である. すなわち, $F_D = \{S | S \in Q_D \wedge S \cap F_E \ne \emptyset\}$ \item $\delta_D(S, a)$は$Q_D$の要素$S$と$\Sigma$の要素$a$に対して次のよ - うに計算される. + うに計算される. \begin{enumerate} - \item $S = \{p_1,p_2,...,p_k\}$とする. - \item $\displaystyle\bigcup^{k}_{i=1}\delta(p_i,a)$を求め, その結 - 果を$\{r_1,r_2,...,r_m\}$とする. + \item $S = \{p_1, p_2, . . . , p_k\}$とする. + \item $\displaystyle\bigcup^{k}_{i=1}\delta(p_i, a)$を求め, その結 + 果を$\{r_1, r_2, . . . , r_m\}$とする. \item このとき, $\delta_D(S, a) = \displaystyle\bigcup^{m}_{j=1}ECLOSE(r_j)$ \end{enumerate} \end{enumerate} この方法によって得られたDFA $D$はNFA $E$と同等の言語を認識し, またNFAの -元となる正規表現と同等である. +元となる正規表現と同等である. \subsubsection{DFAから実行バイナリの生成}\label{subsection:compile} -DFAからの実行バイナリ生成には, 2種類の実装を行った. +DFAからの実行バイナリ生成には, 2種類の実装を行った. \begin{enumerate} \item DFA $\rightarrow$ Continuous based C $\rightarrow$ gccによるコンパイル @@ -260,20 +260,20 @@ % 以下, Continuous based C, LLVMそれ自身の説明と, それを利用したDFAからの -実行バイナリ生成の方法を説明する. +実行バイナリ生成の方法を説明する. \subsubsection{Continous based C} -Continous based C(以下CbC)は, ... +Continous based C(以下CbC)は, . . . 本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装されて -いる\cite{Y},本研究ではgcc-4.5上に実装されたCbCコンパイラを用いた. +いる\cite{Y}, 本研究ではgcc-4. 5上に実装されたCbCコンパイラを用いた. 以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC -のコードセグメントの生成例を示す. +のコードセグメントの生成例を示す. \newpage \begin{figure}[t] \begin{center} -\scalebox{0.60}{\includegraphics{fig5.eps}} +\scalebox{0. 60}{\includegraphics{fig5. eps}} \caption{正規表現``$(A|B)*C$''に対応するDFA} \label{figure:dfasmaple} \end{center} @@ -307,14 +307,14 @@ DFAの遷移とは直接関係のない引数(ファイル名やバッファへのポインタ等) が目 立が, CbCでは環境をコードセグメント間で引数として明示的に持ち運ぶ軽量継 続を基盤としたプログラミングスタイルが望ましい. 今回コンパイラによって生 -成したCbCソースコードでは,大域変数は持たず,必要な変数は全て引数に載せて -いる. +成したCbCソースコードでは, 大域変数は持たず, 必要な変数は全て引数に載せて +いる. CbCのstate\_1, state\_0から呼ばれているaccept, rejectはそれぞれ受理状れ受 理と非受理を表す. accept ではテキスト行を出力して次の行へ, rejectでは次 -の文字へと処理を移すコードセグメントへ継続を行う. +の文字へと処理を移すコードセグメントへ継続を行う. 生成したCbCソースコードを, GCC上に実装したCbCコンパイラによってコンパイルす -ることで実行バイナリを得る. +ることで実行バイナリを得る. \subsubsection{LLVM} LLVM(Low Level Virtual Machine) は @@ -342,8 +342,7 @@ \bibitem{R3} Cox, R : Regular Expression Matching in the Wild, 2010 -\bibitem{U} Hopcroft, J, E. Motowani, R. Ullman, J. : オートマトン言 - 語理論計算論I (第二版), pp.~39--90. +\bibitem{U} Hopcroft, J, E. Motowani, R. Ullman, J. : オートマトン言語理論計算論I (第二版), pp. ~39--90. \bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968