Binary file paper.pdf has changed

--- a/paper.tex	Sun Aug 15 09:51:05 2010 +0900
+++ b/paper.tex	Tue Aug 17 16:29:16 2010 +0900
@@ -34,30 +34,32 @@
 \begin{document}
 
 % 論文のタイトル
-\title{実行時コンパイルを用いた正規表現評価器の実装}
+\title{実行時コンパイルを用いた正規表現検査器の実装}
 
 % 著者
 % 和文論文の場合，姓と名の間には半角スペースを入れ，
 % 複数の著者の間は全角スペースで区切る
 %
-\author{新屋 良磨
+\author{新屋 良磨\and
+  河野 真治
+
 %
 % ここにタイトル英訳 (英文の場合は和訳) を書く．
 %
-\ejtitle{Implimentation of Regular Expression Engine with Just-In-Time Compilation.}
+\ejtitle{Implementation of Regular Expression Checker with Just-In-Time Compilation.}
 %
 % ここに著者英文表記 (英文の場合は和文表記) および
 % 所属 (和文および英文) を書く．
 % 複数著者の所属はまとめてよい．
 %
-\shozoku{Shinya Ryoma}{琉球大学工学部情報工学学科}%
+\shozoku{Shinya RYOMA, Shinji KONO}{琉球大学工学部情報工学学科}%
 {Dept.\ of Information Engineering, Ryukyu University}
 %
 % 出典情報は \shutten とすれば出力される．
 \shutten
 %
 % 受付年月日，記事カテゴリなどは自動的に生成される．
-\uketsuke{1999}{8}{3}
+\uketsuke{2010}{8}{27}
 %
 % その他，脚注に入れるものがあれば，\note に記述する．
 %\note{脚注に入れる内容}
@@ -67,13 +69,16 @@
 % 和文アブストラクト
 % 和文アブストラクト
 \Jabstract{%
-当研究室では, Concinuation based C という, 状態遷移記述に適した C の下位
-言語を提案している.Continuous bsed C は ステートメントより大きく, 関数よりも小さなプログラ
-ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている.
-本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
-オートマトンにおける状態遷遷移を Continuous based Cによる継続に変換する
-正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルは,
-内部形式/中 間表現への変換だけでなく,実行時バイナリの生成までを指す.}
+当研究室では, Concinuation based C (CbC)という, 状態遷移記述に適した C の下位
+言語を提案している. CbC は ステートメントより大きく, 関数よりも小さな
+プログラミング単位, コードセグメントの継続に接続を基本要素としている.
+本研究では, 与えられた正規表現を等価な有限状態オートマトンに変換し,
+それを Continuous based Cによる継続, LLVMバイトコード、Cに変換する
+正規表現コンパイラ を Python で実装し、速度やプログラミングのしやすさなどの比較を行なった. 
+特にマルチバイト文字の正規表現検査の高速化は実用的にも重要であり、
+現状で使われているgrepの評価の行なった。
+% なお, ここで言うコンパイルは,内部形式/中間表現への変換だけでなく,実行時バイナリの生成までを指す.
+}
 %
 \maketitle
 
@@ -85,17 +90,17 @@
 ば Java の HotSpot や Python の PyPy など, 仮想マシンを持つ言語処理系の
 最適化技術として利用されている.
 
-実行時コンパイルが可能な対象として, 正規表現評価器に着目した.
-現在,正規表現の評価器は, プログラミング言語の組み込み機能やライブラリ等,
+実行時コンパイルが可能な対象として, 正規表現検査器に着目した.
+現在,正規表現の検査器は, プログラミング言語の組み込み機能やライブラリ等,
 さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}.
 仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお
-り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した評価器の
+り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した検査器の
 ``実行時コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規
 表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節). 本研究では, 実行バイナリの生
-成にはコンパイラ基盤であるLLVM, GCC を用いており,評価器全体の実装として
-はPythonで実装した.
+成にはコンパイラ基盤であるLLVM, GCC を用いており,検査器全体の実装として
+はPythonで実装した. CbC は gcc 4.5 上の実装(\ref{cbc-gcc}) を用いた.
 
-本論文では, まず正規表現のコンパイル方法について説明し, 実装した評価器の
+本論文では, まず正規表現のコンパイル方法について説明し, 実装した検査器の
 性能調査のために, 正規表現を用いてテキストマッチ処理を行う grep と同等の
 機能を実装し, GNU grep との比較を行う.
 
@@ -141,7 +146,11 @@
 り返しを受理する正規表現であり, 空文字も受理するので, grep は全ての行を
 出力することになる.
 
-\section{正規表現評価器の実装}
+\subsection{マルチバイト文字を含む正規表現}
+
+   なんか書いて
+
+\section{正規表現検査器の実装}
 正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以
 下にその変換手方を説明する.
 
@@ -194,16 +203,16 @@
 複数の遷移先をもつことがあるので, テキストのマッチング途中で複数の状態を
 保持することがある.
 
-現在実装されている正規表現評価器の多くは, 正規表現を内部的にNFAに変換し
+現在実装されている正規表現検査器の多くは, 正規表現を内部的にNFAに変換し
 て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致
 に対応しやすいが, 同時に遷移する可能性のある複数の状態を保持する必要があ
 るため, 正規表現の複雑度に多じてマッチングの時間が多くなってしまう場合が
 ある. 文献\cite{R1}では, ``$a?a?a?aaa$'' のような ``$a?^na^n$'' のように
 表現(``$a?$''は''a``か空文字''``を認識する拡張された正規表現お一つ)の評
-価において, NFAベースの正規表現評価器では遷移する状態の数が増えてしまう
+価において, NFAベースの正規表現検査器では遷移する状態の数が増えてしまう
 でマッチングにかかる処理時間が$n$の指数的に増加する問題をベンチマーク
 結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースで効率的な
-マッチング処理を行う評価器をIBM 7094 機械語で生成する例が紹介されている.
+マッチング処理を行う検査器をIBM 7094 機械語で生成する例が紹介されている.
 
 \subsection{NFAからDFAへの変換}
 非決定的な遷移を行うNFAから, 決定的な遷移を行うDFA({\it Deterministic
@@ -310,9 +319,19 @@
 \subsubsection{LLVM}
 LLVM(Low Level Virtual Machine) は
 
-\section{評価}
+\section{比較}
+
+C, CbC, LLVM の記述の比較をここに書く
+
+    記述
+    デバッグ
+    速度
+
+
 \section{まとめと今後の課題}
 
+%% jbibtex 使わないの?
+
 \begin{adjustvboxheight} % needed only when Appendix follows
 \begin{thebibliography}{99}
 \bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And