changeset 14:bd07b27b2b97

edit
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Fri, 27 Aug 2010 22:52:54 +0900
parents c113bb7d6381
children b3b5bcbba089
files paper.pdf paper.tex
diffstat 2 files changed, 13 insertions(+), 11 deletions(-) [+]
line wrap: on
line diff
Binary file paper.pdf has changed
--- a/paper.tex	Fri Aug 27 22:06:23 2010 +0900
+++ b/paper.tex	Fri Aug 27 22:52:54 2010 +0900
@@ -86,8 +86,8 @@
 仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお
 り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装した評価器の
 ``コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規
-表現 から実行バイナリーを生成することを指す(\ref{subsection:compile}節).
-本研究では, 実行バイナリーの生成にはコンパイラ基盤であるLLVM, GCC を用い
+表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節).
+本研究では, 実行バイナリの生成にはコンパイラ基盤であるLLVM, GCC を用い
 ており,評価器全体の実装としてはPythonで実装した.
 
 本論文では, まず正規表現のコンパイル方法について説明し, 実装した評価器の
@@ -236,8 +236,8 @@
 この方法によって得られたDFA $D$はNFA $E$と同等の言語を認識し, またNFAの
 元となる正規表現と同等である.
 
-\subsection{DFAから実行バイナリの生成}\label{subsection:compile}
-DFAからの実行バイナリ生成には, 3種類の実装を行った.
+\subsection{DFAからの実行バイナリ生成}\label{subsection:compile}
+DFAからの実行バイナリ生成には, 生成するコードについて3種類の実装を行った.
 
 \begin{enumerate}
 \item DFA $\rightarrow$ Continuation based C $\rightarrow$ GCCによるコンパ
@@ -472,6 +472,15 @@
 る配列を,1Byte単位でテーブルルックアップを行うことで実装されている.
 
 {\bf UTF-8対応}\\
+
+\begin{figure}[!t]
+\begin{center}
+\scalebox{0.40}{\includegraphics{fig6.eps}}
+\caption{正規表現``(あ$|$い)*う''に対応するDFA}
+\label{figure:multibyte-dfasample}
+\end{center}
+\end{figure}
+
 本実装は, マルチバイト文字の代表的な符号化方式であるUTF-8に対応しており,
 正規表現の演算は1Byte単位ではなく,1文字単位で適用される.
 マルチバイト文字を含む正規表現のサンプルとして, ``(あ$|$い)*う''をDFAに
@@ -484,13 +493,6 @@
 いる.
 2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に
 内部的に対応することで, mbrtowc(3)による変換コストが無くなっている.
-\begin{figure}[!t]
-\begin{center}
-\scalebox{0.40}{\includegraphics{fig6.eps}}
-\caption{正規表現``(あ$|$い)*う''に対応するDFA}
-\label{figure:multibyte-dfamaple}
-\end{center}
-\end{figure}
 
 {\bf 柔軟な実装}\\
 本実験で実装した正規表現評価器は, Pythonによって実装されており,全体