% Sample file for the use of compsoft style file.
%
\documentclass{compsoft}
% \documentclass[L]{compsoft}
% \documentclass[S]{compsoft}
% \documentclass[S,L]{compsoft}
% \documentclass[K]{compsoft}
% \documentclass[K,L]{compsoft}
% \documentclass[U]{compsoft}
% \documentclass[U,L]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
% \taikai{2009}

% ここに，使用するパッケージを列挙する．
\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{実行時コンパイルを用いた正規表現評価器の実装}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{新屋 良磨
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Implimentation of Regular Expression Engine with Just-In-Time Compilation.}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Shinya Ryoma}{琉球大学工学部情報工学学科}%
{Dept.\ of Information Engineering, Ryukyu University}
%
% 出典情報は \shutten とすれば出力される．
\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
% 和文アブストラクト
\Jabstract{%
当研究室では, Concinuation based C という, 状態遷移記述に適した C の下位
言語を提案している.Continuous bsed C は ステートメントより大きく, 関数よりも小さなプログラ
ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている.
本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
オートマトンにおける状態遷遷移を Continuous based Cによる継続に変換する
正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルは,
内部形式/中 間表現への変換だけでなく,実行時バイナリの生成までを指す.}
%
\maketitle

\section{はじめに}
近年, 実行時コンパイルによる高速化(Just-in-Time Compile)が様々
なプログラムで用いられている. これらは, コンパイラ理論の発展により
実行時コンパイルにかかるオーバーヘッドよりも, コンパイルによって得られる
機械語レベルのプログラムの実行速度が上回る場合において有効であり, たとえ
ば Java の HotSpot や Python の PyPy など, 仮想マシンを持つ言語処理系の
最適化技術として利用されている.

実行時コンパイルが可能な対象として, 正規表現評価器に着目した.
現在,正規表現の評価器は, プログラミング言語の組み込み機能やライブラリ等,
さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}.
仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお
り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した評価器の
``実行時コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規
表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節). 本研究では, 実行バイナリの生
成にはコンパイラ基盤であるLLVM, GCC を用いており,評価器全体の実装として
はPythonで実装した.

本論文では, まず正規表現のコンパイル方法について説明し, 実装した評価器の
性能調査のために, 正規表現を用いてテキストマッチ処理を行う grep と同等の
機能を実装し, GNU grep との比較を行う.

\section{正規表現}
\subsection{正規表現によるテキストマッチ}
正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン
グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用
されている. 正規表現には定められた文法によって記述され, 例えば,正規表現
``$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$の中から有限個の列を重複を許して取り出し,
      それらを連接してできる列全体の集合である.
\end{enumerate}

正規表現は,この3つの演算について閉じておリ,この3つの演算によって定義され
る表現は, 数学的には正則表現と定義されている.
本論文では,特に区別のない限り,正則表現と正規表現を同じものとして扱う.

\subsection{grep}
正規表現は, テキストのパターンをシンプルに記述できるという利点から, テキ
ストファイルから, 任意のパターンにマッチするテキストを検索するなどの用途
に使用される.

GNU grep は, それを実現するソフトウェアの一つであり, 引数として与えられ
たファイルから, 与えられた正規表現にマッチするテキストを含む行を出力する
機能を持っている.

``与えられた正規表現にマッチするテキストを含む''というのは, 行の先頭から
末尾まで正規表現によるマッチングを行い, 正規表現が受理状態になった時点で
``含む'' という解釈を行う.つまり, 正規表現 ''$(a|s)t$'' は, ''$at$''または''
$st$``を受理する正規表現であり, テキスト行''$math.$``の2~3文字目の''$at$''に一致す
るので grep は ``$math.$'' を出力する. また正規表現''$a*$''は, ``$a$''の0回以上の繰
り返しを受理する正規表現であり, 空文字も受理するので, grep は全ての行を
出力することになる.

\section{正規表現評価器の実装}
正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以
下にその変換手方を説明する.

\begin{figure}[b]
\begin{center}
\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}}
\end{center}
\caption{``$A$''と``$B$''の集合和}
\label{figure:union}
\end{figure}
\begin{figure}[b]
\begin{center}
\scalebox{0.50}{\includegraphics{fig3.eps}}
\end{center}
\caption{``$A$''の閉包}
\label{figure:star}
\end{figure}

\subsection{正規表現からNFAへの変換}
NFA({\it Non-deterministic Finite Automaton}) は, 入力に対して複数の
遷移先持つ状態の集合であり, 遷移先が非決定的(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$遷移を許す)
\end{enumerate}
正規表現が, 等価な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.
\end{enumerate}

図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件
の遷移を現しており,$\varepsilon$遷移と呼ばれる. また, 二重丸で囲まれた
状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保
持している場合に限り, その文字列を受理したことになる. なお, NFAは同時に
複数の遷移先をもつことがあるので, テキストのマッチング途中で複数の状態を
保持することがある.

現在実装されている正規表現評価器の多くは, 正規表現を内部的にNFAに変換し
て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致
に対応しやすいが, 同時に遷移する可能性のある複数の状態を保持する必要があ
るため, 正規表現の複雑度に多じてマッチングの時間が多くなってしまう場合が
ある. 文献\cite{R1}では, ``$a?a?a?aaa$'' のような ``$a?^na^n$'' のように
表現(``$a?$''は''a``か空文字''``を認識する拡張された正規表現お一つ)の評
価において, NFAベースの正規表現評価器では遷移する状態の数が増えてしまう
でマッチングにかかる処理時間が$n$の指数的に増加する問題をベンチマーク
結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースで効率的な
マッチング処理を行う評価器を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$遷移は認められず, また任意
の状態$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)$を構成する手順を示す.

\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
      \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 このとき, $\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種類の実装を行った.

\begin{enumerate}
\item DFA $\rightarrow$ Continuous based C $\rightarrow$ gccによるコンパイル
\item DFA $\rightarrow$ LLVM-API $\rightarrow$ LLVMによるコンパイル
\end{enumerate}
%

以下, Continuous based C, LLVMそれ自身の説明と, それを利用したDFAからの
実行バイナリ生成の方法を説明する.

\subsubsection{Continous based C}
Continous based C(以下CbC)は, ...
本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装されて
いる\cite{Y},本研究ではgcc-4.5上に実装されたCbCコンパイラを用いた.

以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC
のコードセグメントの生成例を示す.

\newpage
\begin{figure}[t]
\begin{center}
\scalebox{0.60}{\includegraphics{fig5.eps}}
\caption{正規表現``$(A|B)*C$''に対応するDFA}
\label{figure:dfasmaple}
\end{center}
\end{figure}

\begin{center}
\begin{small}
\begin{verbatim}
__code state_0(unsigned char *s, unsigned
        char* cur, unsigned char* buf, FILE
        *f, char* filename) {
  switch(*s++) {
    case 65: /* match A */
      goto state_0(s, cur, buf, f, filename);
    case 66: /* match B */
      goto state_0(s, cur, buf, f, filename);
    case 67: /* match C */
      goto state_1(s, cur, buf, f, filename);
    default: goto reject(s, cur, buf, f, filename);
  }
}
__code state_1(unsigned char *s, unsigned
        char* cur, unsigned char* buf, FILE
         *f, char* filename) {
  goto accept(s, cur, buf, f, filename);
}
\end{verbatim}
\end{small}
{\bf 図\ref{figure:dfasmaple}のDFAに対応するCbCコードセグメント}
\end{center}
DFAの遷移とは直接関係のない引数(ファイル名やバッファへのポインタ等) が目
立が, CbCでは環境をコードセグメント間で引数として明示的に持ち運ぶ軽量継
続を基盤としたプログラミングスタイルが望ましい. 今回コンパイラによって生
成したCbCソースコードでは,大域変数は持たず,必要な変数は全て引数に載せて
いる.
CbCのstate\_1, state\_0から呼ばれているaccept, rejectはそれぞれ受理状れ受
理と非受理を表す. accept ではテキスト行を出力して次の行へ, rejectでは次
の文字へと処理を移すコードセグメントへ継続を行う.

生成したCbCソースコードを, GCC上に実装したCbCコンパイラによってコンパイルす
ることで実行バイナリを得る.

\subsubsection{LLVM}
LLVM(Low Level Virtual Machine) は

\section{評価}
\section{まとめと今後の課題}

\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And
        Fast, 2007

\bibitem{R2} Cox, R : Regular Expression Matching: the Virtual Machine
        Approach, 2009

\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{K} Thompson, K : Regular Expression Search Algorithm, 1968

\bibitem{H} 長谷川 勇 : 国際正規表現ライブラリの開発

\bibitem{Y} 与儀 健人 : 組込み向け言語Continuation based CのGCC上の実装, 2010

\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\end{document}