# HG changeset patch # User Ryoma SHINYA # Date 1282917174 -32400 # Node ID bd07b27b2b9791ffa183911eb7e55c98d4f9665c # Parent c113bb7d63818d85a9456f6ac5b1d09a51ea20b7 edit diff -r c113bb7d6381 -r bd07b27b2b97 paper.pdf Binary file paper.pdf has changed diff -r c113bb7d6381 -r bd07b27b2b97 paper.tex --- 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によって実装されており,全体