astl2.tex

一个类似STL的自动机的源代码库

  const char *w = "word";
  if (is_in(w, w + 4, forwardc(A))) std::cout << "recognized";

}
\end{verbatim}
\subsection{Using a Depth-First Cursor}
\subsection{Language Extraction}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <language.h>
#include <cursor.h>
#include <iostream>

int main()
{
  DFA_matrix<> A;
  // Construction...
  language(std::cout, dfirstc(A));
}
\end{verbatim}
\subsection{Copying}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <language.h>
#include <cursor.h>
#include <ccopy.h>
#include <iostream>

int main()
{
  DFA_matrix<> A, B;
  // Construction...
  DFA_matrix<>::state_type i = ccopy(A, dfirstc(B));
  A.initial(i);

  DFA_matrix<> C, D;
  // Construction...
  C.initial(clone(C, dfirstc(D)));
}
\end{verbatim}
\subsection{Streams Input/Output}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <ccopy.h>
#include <stream.h>

int main()
{
  DFA_matrix<> A;
  // Construction...
  DFA_stream out(cout);
  clone(out, dfirstc(A));

  DFA_matrix<> B;
  clone_cursor<plain> c(cin);
  B.initial(clone(B, c));
}
\end{verbatim}
\subsection{On-the-fly Processing}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <language.h>
#include <set_operation.h>
#include <cursor.h>
#include <string>
#include <iostream>

int main()
{
  DFA_matrix<> A, B;
  // Constructions
  std::string w = "word";
  if (is_in(w.begin(), w.end(), 
            intersectionc(forwardc(A), forwardc(B))))
     std::cout << "recognized";
}
\end{verbatim}
\subsection{By-copy Processing}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <language.h>
#include <set_operation.h>
#include <cursor.h>
#include <neighbor.h>

int main()
{
  DFA_matrix<> A, B;
  // Constructions
  ccopy(A, dfirstc(neighborc(B, "word", 2)));

  DFA_matrix<> C;
  clone(C, dfirstc(notc(diffc(forwardc(A), forwardc(B)))));
}
\end{verbatim}
\subsection{Lazy-construction Processing}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <lazy.h>
#include <regexp.h>
#include <language.h>
#include <iostream>

int main()
{
  regexp_cursor e("a|b*");
  const char *w = "aaabb";
  if (is_in(w, w + 5, lazyc(e))) std::cout "recognized";

  lazy_cursor<regexp_cursor> c(e);
  if (is_in(w, w + 5, c)) std::cout "recognized too";
}
\end{verbatim}
\subsection{Virtual-traversal Processing}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <stream.h>
#include <iostream>

int main()
{
  DFA_matrix<> A;
  // Construction...
  DFA_stream out(std::cout);
  clone(out, dfirstc(A));
}
\end{verbatim}

\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <ccopy.h>
#include <language.h>
#include <iostream>

int main()
{
  clone_cursor<plain> c(std::cin);
  language(std::cout, c);
}
\end{verbatim}
\subsection{Determinizing}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <nfa.h>
#include <determinize.h>
#include <ccopy.h>

int main()
{
  NFA_mmap<> N;
  // Construction...
  DFA_matrix<> A;
  A.initial(clone(A, dfirstc(forwarddc(N))));
}
\end{verbatim}
\subsection{Displaying and Printing}
\begin{verbatim}
#include <astl.h>
#include <dfa.h>
#include <dot.h>
#include <ccopy.h>
#include <iostream>

int main()
{
  DFA_map<> A, B;
  // Construction...
  dot(std::cout, dfirstc(A));
  
  DFA_dot out(cout);
  clone(out, dfirstc(B));
}
\end{verbatim}
\section{Coding Standards}
\subsection{Namespace}
ASTL components may optionally be enclosed in a namespace \verb+astl+
by defining the symbol \verb+ASTL_USES_NAMESPACE+.
\subsection{Exceptions \& RTTI}
So far, ASTL makes no use of the C++ exceptions mechanism nor RTTI
(RunTime Type Information). They can be
safely turned off on the compiler command line
({\tt g++ -fno-exceptions -fno-rtti}).
\subsection{Types and Functions Naming}
ASTL follows the C++ standard way for types naming:
types and functions names contain only lower-case letters and compound
words contain underscores separating components. Most of the time,
words are used literaly without any abbreviation. Examples:
\verb+forward_cursor+, \verb+acyclic_minimization+. \\
For formal template parameters, upper-case letters are used and no
underscore appears, thus minimizing the probability for
names collision between real types and formal parameters. For instance,
the definition:
\begin{verbatim}
template <typename ForwardCursor>
class A
{ };
\end{verbatim}
should avoid any
confusion between the symbol \verb+ForwardCursor+ and the existing type
\verb+forward_cursor+.
% \subsection{Algorithms}
\subsection{Helper Functions}
Whenever it is possible and useful, a helper function is provided to
make component building and initializing easier.
\subsection{Testing \& Debugging}
\verb+src/check_dfa.cc+ \\
\verb+src/check_nfa.cc+ \\
\verb+src/check_cursor.cc+ \\
\verb+check.h+ (coverage test) \\
\verb+debug.h+ debug cursor and trace cursor \\
\section{Concepts}
\subsection{Alphabet}
\subsection{Edges}
\subsection{Container}
\subsection{Cursor}
\section{Models}
\subsection{Alphabets}
\subsection{Containers}
\subsection{Cursors}
%\small
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf cursor$<$DFA$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright 
{\bf Component Type : {\Large Type}} 
\end{tabular} \\
\paragraph{Description \\}
A cursor is a pointer to an automaton state that is able to move along
defined transitions. Its purpose is to implement simple traversals
testing if a word is in the language recognized by an automaton.
\paragraph{Example}
\begin{verbatim}
DFA_matrix<> A;
const char *w = "word";
tree_build(A, w, w + 4);
cursor<DFA_matrix<> > c(A);
for(c = A.initial(); *w && c.forward(*w); ++w);
assert (*w == 0 && c.src_final());
\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+
\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|l|p{8cm}|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+DFA+ & the automaton type & \\ \hline
\end{tabular}
\paragraph{Model of \\}
plain cursor.
\paragraph{Type requirements}
\begin{itemize}
\item \verb+DFA+ is a model of DFA
\end{itemize}
\paragraph{Public base classes \\}
\verb+plain_cursor_concept+
\paragraph{Members \\}
\begin{longtable}[h]{|l|p{1.3cm}|p{5.8cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{cursor}
\end{longtable}
\paragraph{New members \\}
These members are not defined in the plain cursor requirements but are
specific to \verb+cursor+. \\ [1ex]
\begin{tabular}{|l|p{8.5cm}|} \hline
\bf Member & \bf Description \\ \hline
\verb+cursor(const DFA &A)+ & Construct a cursor pointing to a DFA
            {\tt A} \\ \hline
\verb+cursor(const DFA &A, state_type q)+ & Construct a cursor
pointing to the state {\tt q} of the DFA {\tt A} \\ \hline
\end{tabular}
\paragraph{Helper functions}
\begin{verbatim}
template <typename DFA>
cursor<DFA> plainc(const DFA &A, DFA::state_type q = A.initial());
\end{verbatim}
\paragraph{Notes \\}
A default-constructed cursor, or a cursor that has not been set to
point to a valid state has a singular value which means the only
operation allowed is the assignment. The sink state is not considered
as a valid state.
\paragraph{See also \\}
\verb+forward_cursor+, DFA.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%%%%%%%%%%%% FORWARD_CURSOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf forward\_cursor$<$DFA$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright {\bf Component Type :
{\Large Type}} 
\end{tabular} \\
\paragraph{Description \\} 
A \verb+forward_cursor+ is a pointer to an automaton transition, that
is, a triple (source state, letter, aim state). It provides all the
functionnalities of the plain cursor and some means to iterate through
the sequence of the outgoing transitions of the source state.
\paragraph{Example}
\begin{verbatim}
string w[4] = { "forward", "cursor", "code", "example" };
DFA_bin a;
tree_build(a, w, w + 4);
forward_cursor c(a, a.initial());
assert(c.first_transition());
do cout << "src " << c.src() << " letter " << c.letter
        << " aim " << c.aim();
while (c.next_transition());
\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+
\paragraph{Template parameters \\ [1ex]}
\begin{tabular}{|l|l|p{8cm}|} \hline
\bf Parameter & \bf Description & \bf Default \\ \hline
\verb+DFA+ & The automaton type & \\ \hline
\end{tabular}
\paragraph{Model of \\}
plain cursor, forward cursor.
\paragraph{Type requirements}
\begin{itemize}
\item \verb+DFA+ is a model of DFA.
\end{itemize}
\paragraph{Public base classes \\}
\verb+forward_cursor_concept+.
\paragraph{Members \\ [1ex]}
\begin{longtable}[h]{|l|p{1.3cm}|p{5.8cm}|} \hline
\bf Member & \bf Where defined & \bf Description \\ \hline
\endhead
\input{forward_cursor}
\end{longtable}
\paragraph{New members \\}
These members are not defined in the forward cursor requirements but are
specific to \verb+forward_cursor+. \\ [1ex]
\begin{tabular}{|l|p{7cm}|} \hline
\bf Member & \bf Description \\ \hline
\verb+forward_cursor(const DFA &A)+ & Construct a forward cursor
pointing to a DFA {\tt A} \\ \hline
\verb+forward_cursor(const DFA &A, state_type q)+ & Construct a
forward cursor pointing to the state {\tt q} of the DFA {\tt A} \\
\hline 
\end{tabular}
\paragraph{Helper functions}
\begin{verbatim}
template <typename DFA>
forward_cursor<DFA> forwardc(const DFA &A, DFA::state_type q = A.initial());
\end{verbatim}
\paragraph{Notes \\}
A default-constructed forward cursor, or a forward cursor that has not
been set to point to a valid state and a valid transition has a
singular value which means the only operation allowed is the
assignment. The sink state is not considered as a valid state.
\paragraph{See also \\}
DFA, \verb+cursor+, \verb+stack_cursor+, \verb+queue_cursor+.

%%%%%%%%%%%%%%%%%%%%%%%%% STACK_CURSOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\noindent {\huge {\bf stack\_cursor$<$ForwardCursor, Container$>$}} \\
\noindent \begin{tabular}{p{7.25cm}p{7.25cm}} \hline
\flushleft {\bf Category : {\Large cursors}} & \flushright {\bf Component Type :
{\Large Type}} 
\end{tabular} \\
\paragraph{Description \\} 
A \verb+stack_cursor+ is a forward cursor storing its path in a stack
of cursors. Each forward move along a transition pushes a new forward
cursor onto the stack top and an extra method \verb+backward+ allows
to pop. The depth-first traversal cursor \verb+dfirst_cursor+
relies on the \verb+stack_cursor+.
%\paragraph{Example}
%\begin{verbatim}
%\end{verbatim}
\paragraph{Definition \\}
\verb+cursor.h+