Mercurial > hg > Papers > 2010 > jsst-shinya

changeset 4:22ad03d59b3f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ver:3
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Sun, 15 Aug 2010 09:51:05 +0900
parents b00e4e5b5368
children 4f3747c18585 336542485a9b
files fig5.eps paper.pdf paper.tex
diffstat 3 files changed, 464 insertions(+), 43 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fig5.eps	Sun Aug 15 09:51:05 2010 +0900
@@ -0,0 +1,329 @@
+%!PS-Adobe-3.0 EPSF-3.0
+%%Creator: graphviz version 2.26.3 (20100126.1600)
+%%Title: G
+%%Pages: 1
+%%BoundingBox: 36 36 294 187
+%%EndComments
+save
+%%BeginProlog
+/DotDict 200 dict def
+DotDict begin
+
+/setupLatin1 {
+mark
+/EncodingVector 256 array def
+ EncodingVector 0
+
+ISOLatin1Encoding 0 255 getinterval putinterval
+EncodingVector 45 /hyphen put
+
+% Set up ISO Latin 1 character encoding
+/starnetISO {
+        dup dup findfont dup length dict begin
+        { 1 index /FID ne { def }{ pop pop } ifelse
+        } forall
+        /Encoding EncodingVector def
+        currentdict end definefont
+} def
+/Times-Roman starnetISO def
+/Times-Italic starnetISO def
+/Times-Bold starnetISO def
+/Times-BoldItalic starnetISO def
+/Helvetica starnetISO def
+/Helvetica-Oblique starnetISO def
+/Helvetica-Bold starnetISO def
+/Helvetica-BoldOblique starnetISO def
+/Courier starnetISO def
+/Courier-Oblique starnetISO def
+/Courier-Bold starnetISO def
+/Courier-BoldOblique starnetISO def
+cleartomark
+} bind def
+
+%%BeginResource: procset graphviz 0 0
+/coord-font-family /Times-Roman def
+/default-font-family /Times-Roman def
+/coordfont coord-font-family findfont 8 scalefont def
+
+/InvScaleFactor 1.0 def
+/set_scale {
+       dup 1 exch div /InvScaleFactor exch def
+       scale
+} bind def
+
+% styles
+/solid { [] 0 setdash } bind def
+/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def
+/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def
+/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def
+/bold { 2 setlinewidth } bind def
+/filled { } bind def
+/unfilled { } bind def
+/rounded { } bind def
+/diagonals { } bind def
+
+% hooks for setting color 
+/nodecolor { sethsbcolor } bind def
+/edgecolor { sethsbcolor } bind def
+/graphcolor { sethsbcolor } bind def
+/nopcolor {pop pop pop} bind def
+
+/beginpage {	% i j npages
+	/npages exch def
+	/j exch def
+	/i exch def
+	/str 10 string def
+	npages 1 gt {
+		gsave
+			coordfont setfont
+			0 0 moveto
+			(\() show i str cvs show (,) show j str cvs show (\)) show
+		grestore
+	} if
+} bind def
+
+/set_font {
+	findfont exch
+	scalefont setfont
+} def
+
+% draw text fitted to its expected width
+/alignedtext {			% width text
+	/text exch def
+	/width exch def
+	gsave
+		width 0 gt {
+			[] 0 setdash
+			text stringwidth pop width exch sub text length div 0 text ashow
+		} if
+	grestore
+} def
+
+/boxprim {				% xcorner ycorner xsize ysize
+		4 2 roll
+		moveto
+		2 copy
+		exch 0 rlineto
+		0 exch rlineto
+		pop neg 0 rlineto
+		closepath
+} bind def
+
+/ellipse_path {
+	/ry exch def
+	/rx exch def
+	/y exch def
+	/x exch def
+	matrix currentmatrix
+	newpath
+	x y translate
+	rx ry scale
+	0 0 1 0 360 arc
+	setmatrix
+} bind def
+
+/endpage { showpage } bind def
+/showpage { } def
+
+/layercolorseq
+	[	% layer color sequence - darkest to lightest
+		[0 0 0]
+		[.2 .8 .8]
+		[.4 .8 .8]
+		[.6 .8 .8]
+		[.8 .8 .8]
+	]
+def
+
+/layerlen layercolorseq length def
+
+/setlayer {/maxlayer exch def /curlayer exch def
+	layercolorseq curlayer 1 sub layerlen mod get
+	aload pop sethsbcolor
+	/nodecolor {nopcolor} def
+	/edgecolor {nopcolor} def
+	/graphcolor {nopcolor} def
+} bind def
+
+/onlayer { curlayer ne {invis} if } def
+
+/onlayers {
+	/myupper exch def
+	/mylower exch def
+	curlayer mylower lt
+	curlayer myupper gt
+	or
+	{invis} if
+} def
+
+/curlayer 0 def
+
+%%EndResource
+%%EndProlog
+%%BeginSetup
+14 default-font-family set_font
+1 setmiterlimit
+% /arrowlength 10 def
+% /arrowwidth 5 def
+
+% make sure pdfmark is harmless for PS-interpreters other than Distiller
+/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse
+% make '<<' and '>>' safe on PS Level 1 devices
+/languagelevel where {pop languagelevel}{1} ifelse
+2 lt {
+    userdict (<<) cvn ([) cvn load put
+    userdict (>>) cvn ([) cvn load put
+} if
+
+%%EndSetup
+setupLatin1
+%%Page: 1 1
+%%PageBoundingBox: 36 36 294 187
+%%PageOrientation: Portrait
+0 0 1 beginpage
+gsave
+36 36 258 151 boxprim clip newpath
+1 1 set_scale 0 rotate 40 41 translate
+% regex
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+8 12.9 moveto 50 (\(A|B\)*C) alignedtext
+grestore
+% q0
+gsave
+0 0 1 nodecolor
+125 56 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+125 56 20.8 20.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+117 50.9 moveto 16 (q0) alignedtext
+grestore
+% q0->q0
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 121.32 76.86 moveto
+120.92 86.54 122.15 95 125 95 curveto
+126.74 95 127.87 91.86 128.4 87.22 curveto
+stroke
+0 0 0 edgecolor
+newpath 131.91 86.95 moveto
+128.68 76.86 lineto
+124.91 86.77 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 131.91 86.95 moveto
+128.68 76.86 lineto
+124.91 86.77 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+115.5 97.4 moveto 19 ('A') alignedtext
+grestore
+% q0->q0
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 111.79 72.34 moveto
+102.41 91.18 106.81 113 125 113 curveto
+140.2 113 145.78 97.75 141.72 81.74 curveto
+stroke
+0 0 0 edgecolor
+newpath 144.98 80.49 moveto
+138.21 72.34 lineto
+138.43 82.93 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 144.98 80.49 moveto
+138.21 72.34 lineto
+138.43 82.93 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+116 115.4 moveto 18 ('B') alignedtext
+grestore
+% q1
+gsave
+0 0 1 nodecolor
+225 56 20.8 20.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+225 56 20.8 20.8 ellipse_path stroke
+1 setlinewidth
+filled
+0 0 0 nodecolor
+225 56 24.8 24.8 ellipse_path stroke
+0 0 0 nodecolor
+14 /Times-Roman set_font
+217 50.9 moveto 16 (q1) alignedtext
+grestore
+% q0->q1
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 146.21 56 moveto
+158.85 56 175.21 56 189.75 56 curveto
+stroke
+0 0 0 edgecolor
+newpath 189.94 59.5 moveto
+199.94 56 lineto
+189.94 52.5 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 189.94 59.5 moveto
+199.94 56 lineto
+189.94 52.5 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+164 58.4 moveto 18 ('C') alignedtext
+grestore
+% start
+gsave
+0 0 0 nodecolor
+33 56 1.8 1.8 ellipse_path fill
+1 setlinewidth
+filled
+0 0 0 nodecolor
+33 56 1.8 1.8 ellipse_path stroke
+grestore
+% start->q0
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 34.92 56 moveto
+42.48 56 70.91 56 93.83 56 curveto
+stroke
+0 0 0 edgecolor
+newpath 93.88 59.5 moveto
+103.88 56 lineto
+93.88 52.5 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 93.88 59.5 moveto
+103.88 56 lineto
+93.88 52.5 lineto
+closepath stroke
+grestore
+endpage
+showpage
+grestore
+%%PageTrailer
+%%EndPage: 1
+%%Trailer
+end
+restore
+%%EOF
Binary file paper.pdf has changed
--- a/paper.tex	Sat Aug 14 01:33:24 2010 +0900
+++ b/paper.tex	Sun Aug 15 09:51:05 2010 +0900
@@ -71,8 +71,9 @@
 言語を提案している.Continuous bsed C は ステートメントより大きく, 関数よりも小さなプログラ
 ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている.
 本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
-オートマトンにおける状態遷遷移を Continuous based C/Cによる継続/関数呼び出
-しに変換する正規表現コンパイラを Python で実装した.}
+オートマトンにおける状態遷遷移を Continuous based Cによる継続に変換する
+正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルは,
+内部形式/中 間表現への変換だけでなく,実行時バイナリの生成までを指す.}
 %
 \maketitle
 
@@ -144,45 +145,50 @@
 正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以
 下にその変換手方を説明する.
 
-\subsection{正規表現からNFAへの変換}
-NFA({\it Non-deterministic finite-state machine}) は, 入力に対して複数の
-遷移先持つ状態の集合であり, 遷移先が非決定的(Non-deterministic)である.
-
-正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義
-した3つの演算について対応するNFAに変換できることから示す.
-
-\begin{enumerate}
-\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFAとなる.
-\item {集合和} 図\ref{figure:union}は正規表現 ``$A|B$''に対応するNFAとなる.
-\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFAとなる.
-\end{enumerate}
-
-\begin{figure}[tH]
+\begin{figure}[b]
 \begin{center}
-\scalebox{0.60}{\includegraphics{fig1.eps}}
+\scalebox{0.50}{\includegraphics{fig1.eps}}
 \end{center}
 \caption{``$A$''と``$B$''の連接}
 \label{figure:concat}
 \end{figure}
-
-\begin{figure}[tb]
+\begin{figure}[b]
 \begin{center}
-\scalebox{0.60}{\includegraphics{fig2.eps}}
+\scalebox{0.50}{\includegraphics{fig2.eps}}
 \end{center}
 \caption{``$A$''と``$B$''の集合和}
 \label{figure:union}
 \end{figure}
-
-\begin{figure}[tb]
+\begin{figure}[b]
 \begin{center}
-\scalebox{0.60}{\includegraphics{fig3.eps}}
+\scalebox{0.50}{\includegraphics{fig3.eps}}
 \end{center}
 \caption{``$A$''の閉包}
 \label{figure:star}
 \end{figure}
 
+\subsection{正規表現からNFAへの変換}
+NFA({\it Non-deterministic Finite Automaton}) は, 入力に対して複数の
+遷移先持つ状態の集合であり, 遷移先が非決定的(Non-deterministic)である.
+ここでは, NFAを5個組$(Q, \Sigma,, \delta, q_0, F)$で定義する.ただし,
+\begin{enumerate}
+\item $Q$は状態の有限集合.
+\item $\Sigma$は入力記号の有限集合.
+\item $q_0$は$Q$の要素で, 開始状態と呼ぶ.
+\item $F$は$Q$の部分集合で,受理状態と呼ぶ.
+\item $\delta$は,状態と入力記号に対して状態の集合を返す遷移関
+      数.($\varepsilon$遷移を許す)
+\end{enumerate}
+正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義
+した3つの演算について対応するNFAに変換できることから示す.
+\begin{enumerate}
+\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFA.
+\item {集合和} 図\ref{figure:union}は正規表現 ``$A|B$''に対応するNFA.
+\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFA.
+\end{enumerate}
+
 図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件
-の遷移を現しており,$\varepsilon$-動作と呼ばれる. また, 二重丸で囲まれた
+の遷移を現しており,$\varepsilon$遷移と呼ばれる. また, 二重丸で囲まれた
 状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保
 持している場合に限り, その文字列を受理したことになる. なお, NFAは同時に
 複数の遷移先をもつことがあるので, テキストのマッチング途中で複数の状態を
@@ -196,40 +202,119 @@
 表現(``$a?$''は''a``か空文字''``を認識する拡張された正規表現お一つ)の評
 価において, NFAベースの正規表現評価器では遷移する状態の数が増えてしまう
 でマッチングにかかる処理時間が$n$の指数的に増加する問題をベンチマーク
-結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースのマッチン
-グ処理を行う IBM 7094 の機械語を生成する例が紹介されている.
+結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースで効率的な
+マッチング処理を行う評価器をIBM 7094 機械語で生成する例が紹介されている.
 
 \subsection{NFAからDFAへの変換}
 非決定的な遷移を行うNFAから, 決定的な遷移を行うDFA({\it Deterministic
-finite-state machine})に変換する手法を説明する. なお, 遷移が決定的である
+Finite Automaton})に変換する手法を説明する. なお, 遷移が決定的である
 ということは, 1つの入力に対して, 遷移する状態がただ1つであるということを
 指す.
+DFAは, NFAと同様な5個組で$(Q, \Sigma,, \delta, q_0, F)$定義できる. ただ
+し,DFAにおいて$\delta$において$\varepsilon$遷移は認められず, また任意
+の状態$q$と入力$\sigma$について, $\delta(q, \sigma) = q'$となる$q'$は$Q$
+の要素となる. つまり, 遷移先が決定的であるということに他ならない.
 
-NFAからDFAの変換には, 部分集合構成法(\it{subset construction})と呼ばれる
-方法を利用する. 部分集合構成法では, NFAの ``同時に遷移する可能性のある状
-態の集合''をDFAにおける ``状態''として扱う.
-
-!NFA, DFA の説明をもっと形式的に行います....!
+以下に$\varepsilon$遷移を許す$\varepsilon$-NFA $E = (Q_E,
+\Sigma,\delta_E, q_0, F_E)$ から等価なDFA $D = (Q_D, \Sigma,
+\delta_D, q_D, F_D)$を構成する手順を示す.
 
-\subsection{DFAから実行バイナリの生成}\label{subsection:compile}
-DFAからの実行バイナリ生成には, 3種類の実装を行った.
 \begin{enumerate}
-\item ({\bf DFA -> Continuous based C -> gccによるコンパイル})
-\item ({\bf DFA -> C -> gccによるコンパイル })
-\item ({\bf DFA -> LLVM 中間表現 -> LLVMによるコンパイル})
+\item $Q_D$は$Q_E$の部分集合全から成る集合であり, おの中で$D$において
+      到達可能な状態は, $\varepsilon$遷移に関して閉じている$Q_E$の部分
+      集合$S$に限られる. ここで, 状態$q$において$\varepsilon$遷移に関し
+      て閉じている集合全体を$ECLOSE(q)$と表す. $ECLOSE$を使って$S$を定義
+      すると, $S = \displaystyle\bigcup_{q\in{S}}ECLOSE(q)$を満たす$S$.
+\item $q_D = ECLOSE(q_0)$. すなわち, $E$の開始状態の$\varepsilon$閉包.
+\item $F_D$は$E$の状態の集合で,受理状態を少なくとも一つ含むもの全体から
+      なる集合である. すなわち,$F_D = \{S | S \in Q_D \wedge S \cap F_E \ne
+      \emptyset\}$
+\item $\delta_D(S, a)$は$Q_D$の要素$S$と$\Sigma$の要素$a$に対して次のよ
+      うに計算される.
+      \begin{enumerate}
+       \item $S = \{p_1,p_2,...,p_k\}$とする.
+       \item $\displaystyle\bigcup^{k}_{i=1}\delta(p_i,a)$を求め, その結
+             果を$\{r_1,r_2,...,r_m\}$とする.
+       \item このとき, $\delta_D(S, a) = \displaystyle\bigcup^{m}_{j=1}ECLOSE(r_j)$
+      \end{enumerate}
+\end{enumerate}
+この方法によって得られたDFA $D$はNFA $E$と同等の言語を認識し, またNFAの
+元となる正規表現と同等である.
+
+\subsubsection{DFAから実行バイナリの生成}\label{subsection:compile}
+DFAからの実行バイナリ生成には, 2種類の実装を行った.
+
+\begin{enumerate}
+\item DFA $\rightarrow$ Continuous based C $\rightarrow$ gccによるコンパイル
+\item DFA $\rightarrow$ LLVM-API $\rightarrow$ LLVMによるコンパイル
 \end{enumerate}
 %
 
+以下, Continuous based C, LLVMそれ自身の説明と, それを利用したDFAからの
+実行バイナリ生成の方法を説明する.
+
+\subsubsection{Continous based C}
+Continous based C(以下CbC)は, ...
+本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装されて
+いる\cite{Y},本研究ではgcc-4.5上に実装されたCbCコンパイラを用いた.
+
+以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC
+のコードセグメントの生成例を示す.
+
+\newpage
+\begin{figure}[t]
+\begin{center}
+\scalebox{0.60}{\includegraphics{fig5.eps}}
+\caption{正規表現``$(A|B)*C$''に対応するDFA}
+\label{figure:dfasmaple}
+\end{center}
+\end{figure}
+
+\begin{center}
+\begin{small}
+\begin{verbatim}
+__code state_0(unsigned char *s, unsigned
+        char* cur, unsigned char* buf, FILE
+        *f, char* filename) {
+  switch(*s++) {
+    case 65: /* match A */
+      goto state_0(s, cur, buf, f, filename);
+    case 66: /* match B */
+      goto state_0(s, cur, buf, f, filename);
+    case 67: /* match C */
+      goto state_1(s, cur, buf, f, filename);
+    default: goto reject(s, cur, buf, f, filename);
+  }
+}
+__code state_1(unsigned char *s, unsigned
+        char* cur, unsigned char* buf, FILE
+         *f, char* filename) {
+  goto accept(s, cur, buf, f, filename);
+}
+\end{verbatim}
+\end{small}
+{\bf 図\ref{figure:dfasmaple}のDFAに対応するCbCコードセグメント}
+\end{center}
+DFAの遷移とは直接関係のない引数(ファイル名やバッファへのポインタ等) が目
+立が, CbCでは環境をコードセグメント間で引数として明示的に持ち運ぶ軽量継
+続を基盤としたプログラミングスタイルが望ましい. 今回コンパイラによって生
+成したCbCソースコードでは,大域変数は持たず,必要な変数は全て引数に載せて
+いる.
+CbCのstate\_1, state\_0から呼ばれているaccept, rejectはそれぞれ受理状れ受
+理と非受理を表す. accept ではテキスト行を出力して次の行へ, rejectでは次
+の文字へと処理を移すコードセグメントへ継続を行う.
+
+生成したCbCソースコードを, GCC上に実装したCbCコンパイラによってコンパイルす
+ることで実行バイナリを得る.
+
+\subsubsection{LLVM}
+LLVM(Low Level Virtual Machine) は
+
 \section{評価}
-
+\section{まとめと今後の課題}
 
 \begin{adjustvboxheight} % needed only when Appendix follows
 \begin{thebibliography}{99}
-\bibitem{U} Hopcroft, J, E. Motowani, R. D, Ullman. : オートマトン言
-        語理論計算論I (第二版), pp.~39--90.
-
-\bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968
-
 \bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And
         Fast, 2007
 
@@ -238,8 +323,15 @@
 
 \bibitem{R3} Cox, R : Regular Expression Matching in the Wild, 2010
 
+\bibitem{U} Hopcroft, J, E. Motowani, R. Ullman, J. : オートマトン言
+        語理論計算論I (第二版), pp.~39--90.
+
+\bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968
+
 \bibitem{H} 長谷川 勇 : 国際正規表現ライブラリの開発
 
+\bibitem{Y} 与儀 健人 : 組込み向け言語Continuation based CのGCC上の実装, 2010
+
 \end{thebibliography}
 \end{adjustvboxheight} % needed only when Appendix follows