% 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/Cによる継続/関数呼び出
しに変換する正規表現コンパイラを Python で実装した.}
%
\maketitle

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

実行時コンパイルが可能な対象として, 正規表現評価器に着目し,コンパイラ基
盤である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{grep}

\section{正規表現の実行時コンパイル}
\subsection{正規表現からNFAへの変換}
\subsection{NFAからDFAへの変換}
は

\begin{figure}[!tb]
\begin{center}
\scalebox{0.80}{\includegraphics{fig1.eps}}
\end{center}
\end{figure}

\begin{figure}[tb]
\begin{center}
\scalebox{0.80}{\includegraphics{fig2.eps}}
\end{center}
\end{figure}

\begin{figure}[tb]
\begin{center}
\scalebox{0.80}{\includegraphics{fig3.eps}}
\end{center}
\end{figure}

\subsection{DFAからContinuous base Cへの変換}
%

\section{評価}

...

\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{K} Ken Thompson : Regular Expression Search Algorithm, 1968

\bibitem{R1} Russ Cox : Regular Expression Matching Can Be Simple And
        Fast, 2007
\bibitem{R2} Russ Cox : Regular Expression Matching: the Virtual Machine
        Approach, 2009
\bibitem{R3} Russ Cox : Regular Expression Matching in the Wild, 2010

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

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

\end{document}