# HG changeset patch
# User Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
# Date 1454831557 -32400
# Node ID 2ed354dadc69feb2683d763021648c917db6369d
# Parent  e18d8b4b364449d202b8bab657bc722b1d911cdd
write parser

diff -r e18d8b4b3644 -r 2ed354dadc69 c4.tex
--- a/c4.tex	Sat Feb 06 18:41:49 2016 +0900
+++ b/c4.tex	Sun Feb 07 16:52:37 2016 +0900
@@ -149,7 +149,6 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-      \label{table:search}
       \small
       \begin{tabular}[t]{c|r}
         \hline
@@ -161,6 +160,7 @@
         \hline
       \end{tabular}
       \caption{文字列検索アルゴリズムの比較}
+      \label{table:search}
     \end{center}
   \end{table}
 \end{tiny}
@@ -170,7 +170,7 @@
 \section{正規表現}
 (正規表現の簡単な概要をここに)
 
-本研究で実装した正規表現マッチャのアルゴリズムは、
+実装した正規表現マッチャのアルゴリズムは、
 
 \begin{enumerate}
 \item 与えられた正規表現を構文解析し、正規表現木に変換する。
@@ -180,7 +180,63 @@
 \item 状態遷移のリストを元に文字列検索を行ない結果を返す。
 \end{enumerate}
 
+となる。本項はそれぞれのアルゴリズムについて述べていく。
+
 \subsection{正規表現木の生成}
+与えられた正規表現から正規表現木を生成していく。
+本実装でサポートするメタ文字は、正規表現の基本三演算子\cite{regex}に文字クラスとグループを加えている。
+(表\ref{table:metachar})
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{c|l}
+        \hline
+        AB & 連続した文字(連接)\\
+        \hline
+        A* & 直前の文字の 0 回以上の繰返し\\
+        \hline
+        A\textbar B & A または B(選択)\\
+        \hline
+        [A-Z] & A-Zの範囲の任意の一文字(文字クラス)\\
+        \hline
+        ( )& 演算の優先度の明示(グループ) \\
+        \hline
+      \end{tabular}
+      \caption{サポートしているメタ文字一覧}
+      \label{table:metachar}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+また、それぞれの記号の結合順位を表\ref{table:bond}のようになっている。
+
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \begin{tabular}[t]{l|l}
+        \hline
+        結合順位 & メタ文字\\
+        \hline
+        高 & () (グループ化)\\
+        \hline
+         & [ ] (文字クラス) \\
+        \hline
+         & * 繰返し\\
+        \hline
+         & 連接\\
+        \hline
+        低 & \textbar 選択\\
+        \hline
+      \end{tabular}
+      \caption{サポートしているメタ文字一覧}
+      \label{table:bond}
+    \end{center}
+  \end{table}
+\end{tiny}
+
+
+
 \subsection{正規表現木から DFA・NFA の生成}
 \subsection{Subset Construction による NFA から DFA の変換}
 \subsection{DFA から状態遷移リストの生成}
diff -r e18d8b4b3644 -r 2ed354dadc69 master_paper.pdf
Binary file master_paper.pdf has changed