# HG changeset patch
# User Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
# Date 1282914383 -32400
# Node ID c113bb7d63818d85a9456f6ac5b1d09a51ea20b7
# Parent  c2aaa766746a2c6bc9addca5aeae404df3e3b6ad
modify preamble. correct typo.

diff -r c2aaa766746a -r c113bb7d6381 paper.pdf
Binary file paper.pdf has changed
diff -r c2aaa766746a -r c113bb7d6381 paper.tex
--- a/paper.tex	Fri Aug 27 19:52:22 2010 +0900
+++ b/paper.tex	Fri Aug 27 22:06:23 2010 +0900
@@ -1,6 +1,6 @@
 % Sample file for the use of compsoft style file.
 %
-\documentclass{compsoft}
+\documentclass[T]{compsoft}
 % \documentclass[L]{compsoft}
 % \documentclass[S]{compsoft}
 % \documentclass[S,L]{compsoft}
@@ -13,7 +13,7 @@
 %
 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
 % 巻数，号数，開始ページ，終了ページを指定する．
-\volNoPp{16}{5}{78}{83}
+% \volNoPp{16}{5}{78}{83}
 
 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
 % \suisen{ワークショップ名}
@@ -23,7 +23,7 @@
 
 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
 % 大会の回数は計算される．
-% \taikai{2009}
+\taikai{2010}
 
 % ここに，使用するパッケージを列挙する．
 \usepackage[dvips]{graphics}
@@ -57,7 +57,7 @@
 \shutten
 %
 % 受付年月日，記事カテゴリなどは自動的に生成される．
-\uketsuke{2010}{8}{25}
+\uketsuke{2010}{8}{27}
 %
 % その他，脚注に入れるものがあれば，\note に記述する．
 %\note{脚注に入れる内容}
@@ -71,8 +71,8 @@
 ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている.
 本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
 オートマトンにおける状態遷遷移を Continuation based Cによる継続に変換する
-正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルは,
-内部形式/中 間表現への変換だけでなく,実行時バイナリの生成までを指す.}
+正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルとは,
+プログラム内部での中間表現への変換だけでなく,実行時バイナリの生成までを指す.}
 %
 \maketitle
 
@@ -240,9 +240,9 @@
 DFAからの実行バイナリ生成には, 3種類の実装を行った.
 
 \begin{enumerate}
-\item DFA $\rightarrow$ Continuation based C $\rightarrow$ gccによるコンパ
+\item DFA $\rightarrow$ Continuation based C $\rightarrow$ GCCによるコンパ
       イル
-\item DFA $\rightarrow$ C $\rightarrow$ gccによるコンパイル
+\item DFA $\rightarrow$ C $\rightarrow$ GCCによるコンパイル
 \item DFA $\rightarrow$ LLVM中間表現 $\rightarrow$ LLVMによるコンパイル
 \end{enumerate}
 %
@@ -251,14 +251,17 @@
 実行バイナリ生成の方法を説明する.
 
 \subsubsection{Continuation based C}
-Continuation based C(以下CbC)は, ...
-本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装されて
-いる\cite{Y},本研究ではgcc-4.5上に実装されたCbCコンパイラを用いた.
+Continuation based C(以下CbC)は, プログラミングの基本単位としてコードセ
+グメントを持ち, コードセグメント間の軽量継続を基本としたCの下位言語であ
+る. 本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装さ
+れており\cite{Y}, GCCの末尾再帰最適化を強制することで, 関数と同様の記述
+が可能で, かつ関数呼び出しに伴なうリターンアドレスの保存や,スタックの成
+長のない, ``引数付きgoto''として継続を実装している.本研究ではgcc-4.5上に
+実装されたCbCコンパイラを用いた.
 
 以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC
 のコードセグメントの生成例を示す.
 
-\newpage
 \begin{figure}[t]
 \begin{center}
 \scalebox{0.60}{\includegraphics{fig5.eps}}
@@ -316,7 +319,7 @@
 CbC/Cによる実装では,DFAからCbC/Cのソースコードに変換し,GCCによってコンパ
 イルを行っている. LLVMによる実装では, LLVMの中間表現であるLLVM-IRを,提供
 されているAPIを用いて直接操作を行い, コンパイルを経て実行バイナリを得る.
-PythonからLLVM APIの利用は, LLVM APIのPythonラッパーであるllvm-pyを使用した.
+PythonからLLVM APIの利用は, LLVM APIのPythonラッパーであるllvm-py\footnote{http://www.mdevan.org/llvm-py/}を使用した.
 
 \begin{figure}[t]
 \begin{center}
@@ -342,12 +345,12 @@
 \begin{itemize}
 \item CPU : Core 2 Duo 950 @3.0GHz
 \item Memory : 16GB
-\item GCC (c) : 4.0.1
+\item GCC : 4.5.0
 \item LLVM: 2.4
 \end{itemize}
 
 {\bf コンパイル}\\
-n個の単語を正規表現のOR演算で繋げたパターンに対し, 各実装のコンパイル時
+n個の単語を正規表現の和集合演算 ``$|$''で繋げたパターンに対し, 各実装のコンパイル時
 間の比較を行った.
 
 \begin{table}[h]
@@ -358,7 +361,7 @@
 n (単語数)& 1 & 10 & 50 & 100 \\
 \hline
 DFA変換[ms] & 0.19 & 3.28 & 22.2 & 73.8\\
-状態数[個]& 8 & 50 & 187 & 381\\
+DFAの状態数 & 8 & 50 & 187 & 381\\
 \hline
 GCC-C  [s] & 0.34 & 0.78 & 2.18 & 4.27\\
 \hline
@@ -371,7 +374,7 @@
 
 表\ref{table:benchmark1}から, LLVMによるコンパイルがGCCに比べ10倍程高速
 に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作
-することで, I/Oやパース等のオーバーヘッドもない.
+することで, ファイルI/Oやパース等のオーバーヘッドもない.
 
 {\bf マッチング}\\
 マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実
@@ -437,7 +440,7 @@
 パターン  :``$(Python|Perl|Pascall|Prolog|\\
 PHP|Ruby|Haskell|Lisp|Scheme)$''\\
 マッチ行数: 1503行\\
-このパターンは,9個の単語をORで並べたもので,確実に含まれる文字列は存在せ
+このパターンは,9個の単語を和集合演算 ``$|$''で並べたもので,確実に含まれる文字列は存在せ
 ず,先の二つに比べてGNU grep は遅い結果となっている.
 
 GNU grep 2.5.4 は188秒と, 本実装及びGNU grep 2.6.3に対して非常に遅い結
@@ -446,11 +449,10 @@
 \end{description}
 
 3つのテストケースの結果を見てみると, 本実装はそれぞれ実行時間にあまり差
-がなく, またコンパイル時間はマッチングにかかる時間と比べて無視できるなっ
-ている. また, complex-regexのテストケースではGNU grepよりも高速な結果が
-出ており, 本実装は(フィルタリングを用いない)純粋なDFAマッチングにおいて
-パターンに比べて検索対テキストファイルが十分に大きな場合の検索にコンパイ
-ルの効果が発揮されていることが分かる.
+がなく, またコンパイル時間はマッチングにかかる時間と比べて無視できるほど
+短い時間である. また, complex-regexのテストケースではGNU grepよりも高速
+な結果が出ており, 本実装は(フィルタリングを用いない)純粋なDFAマッチング
+において, 本実装によって動的に生成されたコードの性能が高いことが分かる.
 
 \subsection{特徴}
 本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ
@@ -484,7 +486,7 @@
 内部的に対応することで, mbrtowc(3)による変換コストが無くなっている.
 \begin{figure}[!t]
 \begin{center}
-\scalebox{0.50}{\includegraphics{fig6.eps}}
+\scalebox{0.40}{\includegraphics{fig6.eps}}
 \caption{正規表現``(あ$|$い)*う''に対応するDFA}
 \label{figure:multibyte-dfamaple}
 \end{center}