\documentclass[private]{ipsjpapers}
\usepackage[dvipdfm]{graphicx}

% 巻数，号数などの設定
\setcounter{巻数}{0}
\setcounter{号数}{0}
\setcounter{volpageoffset}{0}
\受付{2010}{12}{03}
\採録{0}{0}{0}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
        $\backslash$#1\fi}

%\checklines    % 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[動的なコード生成を用いた正規表現エンジンの実装]%
        {動的なコード生成を用いた正規表現エンジンの実装}

% 英文表題
\etitle{Implimentation of Regular Expression Engine with Dynamic Code Generation.}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{新屋 良磨\affiref{URYUKYU}\and
        河野 真治\affiref{URYUKYU}\member{19841765}}

% 英文著者名
\eauthor{Ryoma SHINYA\affiref{URYUKYU}\and
        Shinji KONO\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{新屋 良磨\\
903-0213 沖縄県中頭郡西原町字千原1\\
琉球大学情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
        email: shinya@firefly.cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
当研究室では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
オートマトンにおける状態遷遷移をC言語等のコンパイル型言語での関数遷移に
変換する正規表現コンパイラを Python で開発している.
本実験では, その正規表現コンパイラを元に, テキストファイルに対しパターン
マッチを行いマッチする行を出力するツールである grep に相当するソフトウェ
アを実装した.
\end{abstract}
% 英文概要
\begin{eabstract}
上の英訳.
\end{eabstract}

% 表題などの出力
\maketitle

%}{

% 本文はここから始まる

\section{はじめに}
コンパイラ理論の発展と共に, コンパイルにかかる時間はより短く, また得られ
るプログラムはアセンブラレベルで最適化が施され, より高速になってきている.

完全に静的なコンパイルが可能な対象として, 正規表現エンジンに着目した.
現在,正規表現のエンジンは, プログラミング言語の組み込み機能やライブラリ等,
さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\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つの演算によって定義され
る表現は, 数学的には正則表現と定義されている.
本論文では,特に区別のない限り,正則表現と正規表現を同じものとして扱う.

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

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

\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の
元となる正規表現と同等である.

\subsection{DFAからの実行バイナリ生成}\label{subsection:compile}
DFAからの実行バイナリ生成には, 生成するコードについて3種類の実装を行った.

\begin{enumerate}
\item DFA $\rightarrow$ Continuation based C $\rightarrow$ GCCによるコンパ
      イル
\item DFA $\rightarrow$ C $\rightarrow$ GCCによるコンパイル
\item DFA $\rightarrow$ LLVM中間表現 $\rightarrow$ LLVMによるコンパイル
\end{enumerate}
%

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

\subsubsection{Continuation based C}
Continuation based C(以下CbC)は, プログラミングの基本単位としてコードセ
グメントを持ち, コードセグメント間の軽量継続を基本としたCの下位言語であ
る. 本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装さ
れており\cite{Y}, GCCの末尾再帰最適化を強制することで, 関数と同様の記述
が可能で, かつ関数呼び出しに伴なうリターンアドレスの保存や,スタックの成
長のない, ``引数付きgoto''として継続を実装している.本研究ではgcc-4.5上に
実装されたCbCコンパイラを用いた.

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

\begin{figure}[h]
\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{C}
Cによる実装では, CbCのコードセグメントに代わり関数を用いてDFAを実装した.
DFAによる遷移を関数呼び出しで行っているため,実行時のスタックの使用領域や,ス
タック操作によるオーバーヘッドが予想される.

\subsubsection{LLVM}
LLVM(Low Level Virtual Machine) は, さまざまなコード最適化/分析機能を備
えた, モジュール単位で利用可能なコンパイラ基盤である\cite{L}.

CbC/Cによる実装では,DFAからCbC/Cのソースコードに変換し,GCCによってコンパ
イルを行っている. LLVMによる実装では, LLVMの中間表現であるLLVM-IRを,提供
されているAPIを用いて直接操作を行い, コンパイルを経て実行バイナリを得る.
PythonからLLVM APIの利用は, LLVM APIのPythonラッパーであるllvm-py\footnote{http://www.mdevan.org/llvm-py/}を使用した.

\begin{figure}[h]
\begin{center}
\scalebox{0.60}{\includegraphics{fig7.eps}}
\caption{LLVMを用いた実装}
\label{figure:llvm-impl}
\end{center}
\end{figure}

LLVMによる実装でも, Cによる実装と同様に,DFAの状態遷移をswitch文と関数呼
び出しによって表現している.

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

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

\section{評価}
\subsection{実験}
本実験で実装した正規表現エンジンのCbC/C/LLVMによる三つの実装に対して,
コンパイル時間及びマッチングにかかる時間の比較を行った.
なお, GCCによるコンパイルには最適化オプション ``-O3'' を, LLVMのも同様の
最適化オプションを用いてコンパイル/マッチングを行っている.

{\bf 実験環境}
\begin{itemize}
\item CPU : Core 2 Duo 950 @3.0GHz
\item Memory : 16GB
\item GCC : 4.5.0
\item LLVM: 2.4
\end{itemize}

{\bf コンパイル}\\
n個の単語を正規表現の和集合演算 ``$|$''で繋げたパターンに対し, 各実装のコンパイル時
間の比較を行った.

\begin{table}[h]
\caption{ベンチマーク:compile}
\label{table:benchmark1}
\begin{tabular}[t]{l|l|l|l|l}
\hline\hline
n (単語数)& 1 & 10 & 50 & 100 \\
\hline
DFA変換[ms] & 0.19 & 3.28 & 22.2 & 73.8\\
DFAの状態数 & 8 & 50 & 187 & 381\\
\hline
GCC-C  [s] & 0.34 & 0.78 & 2.18 & 4.27\\
\hline
GCC-CbC[s] & 0.75 & 1.03 & 9.14 & 9.43\\
\hline
LLVM   [s] & 0.044 & 0.08 & 0.246 & 0.472\\
\hline
\end{tabular}
\end{table}

表\ref{table:benchmark1}から, LLVMによるコンパイルがGCCに比べ10倍程高速
に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作
することで, ファイルI/Oやパース等のオーバーヘッドもない.

{\bf マッチング}\\
マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実
装でマッチング時間にあまり差が見られなかった. 生成されるコードはコードセ
グメント/関数と, switch文によるシンプルな実装であることから, コンパイル
されたバイナリの性能にあまり差が出ていないものだと思われる.

本実装の中で最もマッチングが高速だったGCC-Cで生成した正規表現エンジンを用
いてgrep に相当するプログラムを実装し,実際にテキストファイルからのパター
ンマッチを行い, それぞれの評価を行う. 本実装との比較対象として,

\begin{description}
\item[GNU grep] hoge
\item[cgrep] fuga
\item[Google RE2] piyo
\end{description}

{\bf 実験環境}\\
\begin{itemize}
\item CPU : Core i7 950 @3.0GHz
\item Memory : 16GB
\item GCC : 4.4.1
\item Text : Wikipedia 日本語版全記事\\ (XML, UTF-8, 4.7GB, 8000万行)
\end{itemize}

表\ref{table:benchmark2}に結果を示す.

\begin{table}[h]
\caption{ベンチマーク:grep}
\label{table:benchmark2}
\begin{tabular}[t]{l|l|l|l}
\hline\hline
テストケース & fixed-string & complex-regex\\
\hline
本実装(GCC-C)[s] & 1.69 & 4.51 \\
(コンパイル[s]) & 0.20 & 0.41 \\
\hline
GNU grep 2.6.3[s] & 2.93 & 16.08\\
\hline
GNU grep 2.5.4[s] & 2.96 & 188.51\\
\hline
cgrep 8.15 [s] & 1.85 & 6.48 \\
\hline
Google RE2 [s] & 30.10 & 16.92\\
\hline
\end{tabular}
\end{table}

以下に, それぞれのテストケースのパターン, grepにマッチした行数,
および考察を記す. なお,ここで扱う正規表現の ``複雑さ''とは, DFAに
変換した時点の状態数, 遷移規則の多さを基準としている.

\begin{description}
\item[fixed-string]固定文字列によるマッチング\\
パターン  : ``$Wikipedia$''\\
マッチ行数: 348936行\\
GNU grep では, 与えられたパターン内に, 確実に含まれる文字列(固定文字列)
が存在する場合は, Boyer-Moore-Horspool法 等の高速な文字列探索アルゴリズムを用いて
フィルタをかけることで, DFAによるマッチングを減らし,高速化している. 本実
装の grep でも, 同様に固定文字列フィルタによる高速化を行っているが, 単純
な固定文字列の検索でも, コンパイルすることによる高速化が結果に出ている.

\item[complex-regex]複雑な正規表現でのマッチング\\
パターン  :``$(Python|Perl|Pascall|Prolog|\\
PHP|Ruby|Haskell|Lisp|Scheme)$''\\
マッチ行数: 15030行\\
このパターンは,9個の単語を和集合演算 ``$|$''で並べたもので,確実に含まれ
る文字列は存在せず, fixed-stringに比べてGNU grep はマッチングに時間がか
かっている.

さらに, GNU grep 2.5.4 は190秒と, 本実装及びGNU grep 2.6.3に対して非常に
低速な結果となっているが, これは後述する mbrtowc(3) によるマルチバイト文
字の変換処理によるオーバーヘッドによるものである.
\end{description}

2つのテストケースの結果を見てみると, 本実装はそれぞれGNU grep と比べて高
速な結果となっており, コンパイル時間はマッチングにかかる時間と比べて無視
できるほど短い時間である.

\subsection{特徴}
本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ
みながら説明する.

{\bf 正規表現からの動的なコード生成}\\
本実装による一番の特徴として, 正規表現から変換を行うことで得られる等価な
DFAを, C/CbC/LLVM に変換しコンパイルすることで正規表現に応じた実行バイナ
リを生成することが挙げられる. またコンパイラ理論におけるさまざまな最適化
が期待される.
grepによる検索のような, 与えられるパターン(正規表現)に対してマッチ対象の
テキストファイルが十分に大きい場合, 正規表現のコンパイルにかかる時間はマッ
チングにかかる時間によって隠される.

GNU grep では, 本実装と同様にDFAベースのマッチングを行うが, DFAの各状態
は構造体よって表され, 状態遷移は各状態毎に保持している遷移先ポインタによ
る配列を,1Byte単位でテーブルルックアップを行うことで実装されている.

{\bf UTF-8対応}

本実装は, マルチバイト文字の代表的な符号化方式であるUTF-8に内部的に対応しており,
正規表現の演算は1Byte単位ではなく,1文字単位で適用される.
マルチバイト文字を含む正規表現のサンプルとして, ``(あ$|$い)*う''をDFAに
変換した図\ref{figure:multibyte-dfasample}を載せる. 図における
\verb|'\x'|に始まる文字は16進数表記で, \verb|'\x82'|は16進数82を表す.

\begin{figure}[h]
\begin{center}
\scalebox{0.40}{\includegraphics{fig6.eps}}
\caption{正規表現``(あ$|$い)*う''に対応するDFA}
\label{figure:multibyte-dfasample}
\end{center}
\end{figure}

GNU grep 2.5.x では, マルチバイト文字に対応しているものの, プログラム内
部でlibc mbrtowc(3)を用いて固定サイズであるワイド文字に変換して処理を行っ
ており, テストケース complex-regex ではそのオーバーヘッドが顕著に現れて
いる.
2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に
内部的に対応することで, mbrtowc(3)による変換コストが無くなっている.

{\bf 柔軟な実装}\\
本実験で実装した正規表現評価器は, Pythonによって実装されており,全体
で3000行程度の軽量なプログラムとなっている. 比較対象のGNU grep は,
C言語によって実装されており, プログラム全体は15000行程度の規模と
なっている.

さらに,本実装から動的に生成されるコードも,コードセグメント/関数とswitch
を基準としたシンプルな記述で高い可読性を持ちつつ, 細かい最適化をGCC/LLVMの最適
化技術を利用することで実行速度も非常に高速であることが実験結果から分かった.

\section{途中報告と課題}
本研究では, 現段階で正規表現をコードセグメント/関数による状態遷移を行う
コードに変換する手法で正規表現エンジンを実装し, GNU grep との比較を行い
, 非常に良好な結果が得られた.

今後の課題として, 正規表現マッチングのデータ並列な並列アルゴリズムの実装
を目指している.

\begin{thebibliography}{9}

\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{L} Lattner, Chris. Adve, Vikram : The LLVM Compiler Framework
        and Infrastructure, 2004

\bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968

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

\end{thebibliography}

\begin{biography}
\member{新屋 良磨}
1988年生
%
\member{河野 真治}
1959年生．
1989年東京大学大学院情報工学課程修了 (工学博士)
同年Sony Computer Science Laboratory, Inc.   入社．
1996年より琉球大学工学部准教授
工学博士． ACM会員.
\end{biography}
\end{document}