From 8d67caae222e1652936ecc6cc7a237f67fc320c5 Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Tue, 29 Jun 2010 09:11:38 +0200 Subject: presentation done --- presentation/aabc.pdf | Bin 45129 -> 46443 bytes presentation/ab.pdf | Bin 37400 -> 37507 bytes presentation/aorb.pdf | Bin 39395 -> 39824 bytes presentation/astar.pdf | Bin 38651 -> 39039 bytes presentation/demo.txt | 8 +++++ presentation/simianer-regexvis.bib | 8 ++++- presentation/simianer-regexvis.pdf | Bin 458848 -> 791825 bytes presentation/simianer-regexvis.tex | 61 ++++++++++++++++++++++--------------- 8 files changed, 52 insertions(+), 25 deletions(-) create mode 100644 presentation/demo.txt (limited to 'presentation') diff --git a/presentation/aabc.pdf b/presentation/aabc.pdf index 5b006cc..7706b0f 100644 Binary files a/presentation/aabc.pdf and b/presentation/aabc.pdf differ diff --git a/presentation/ab.pdf b/presentation/ab.pdf index c697ad3..acaa184 100644 Binary files a/presentation/ab.pdf and b/presentation/ab.pdf differ diff --git a/presentation/aorb.pdf b/presentation/aorb.pdf index e2268f1..818582a 100644 Binary files a/presentation/aorb.pdf and b/presentation/aorb.pdf differ diff --git a/presentation/astar.pdf b/presentation/astar.pdf index 46c5f9c..30580c6 100644 Binary files a/presentation/astar.pdf and b/presentation/astar.pdf differ diff --git a/presentation/demo.txt b/presentation/demo.txt new file mode 100644 index 0000000..085b9f6 --- /dev/null +++ b/presentation/demo.txt @@ -0,0 +1,8 @@ +a* +(a|b) +abcd +(a|b)* +a(a|b)c* +a*b|b*a +abc*d + diff --git a/presentation/simianer-regexvis.bib b/presentation/simianer-regexvis.bib index 4f30f9f..5c49236 100644 --- a/presentation/simianer-regexvis.bib +++ b/presentation/simianer-regexvis.bib @@ -8,7 +8,7 @@ @book{UBHD-66019710, author={Aho, Alfred V. and Sethi, Ravi and Ullman, Jeffrey David}, - title={Compilers}, + title={Compilers. Principles, Techniques \& Tools}, subtitle={principles, techniques, and tools}, edition={Repr. with corr.}, address={Reading, Mass. [u.a.]}, @@ -50,5 +50,11 @@ publisher = {} } +@MISC{Navarro01compactdfa, + author = {Gonzalo Navarro and Mathieu Raffinot}, + title = {Compact DFA Representation for Fast Regular Expression Search}, + year = {2001} +} + diff --git a/presentation/simianer-regexvis.pdf b/presentation/simianer-regexvis.pdf index 8a42438..a845ffa 100644 Binary files a/presentation/simianer-regexvis.pdf and b/presentation/simianer-regexvis.pdf differ diff --git a/presentation/simianer-regexvis.tex b/presentation/simianer-regexvis.tex index a232673..d8fc777 100644 --- a/presentation/simianer-regexvis.tex +++ b/presentation/simianer-regexvis.tex @@ -74,13 +74,13 @@ \item[] Wie soll die Visualisierung aussehen? \begin{enumerate} \item Hervorheben von \textit{\textbf{Matches}} oder \textbf{Gruppen} in einem String oder Text - \item Darstellung und Simulation durch einen \textbf{Automaten} + \item Darstellung und Simulation anhand eines \textbf{Automaten} \end{enumerate} \item[] \end{itemize} \begin{enumerate} - \item Es existieren bereits viele Implementierungen, \\ basierend auf RE-Implementierung der jeweiligen Sprache\\ $\rightarrow$ keine ``\textit{step by step}''-Visualisierung m"oglich - \item Grafische Umsetzung schwierig,\\ eigene RE-Implementierung n"otig\\ $\rightarrow$ jeder Schritt nachvollziehbar + \item Es existieren bereits viele Implementierungen, \\ basierend auf RE-Implementierung der jeweiligen Sprache.\\ $\rightarrow$ Keine "`\textit{step by step}"'-Visualisierung m"oglich + \item Grafische Umsetzung schwierig,\\ eigene RE-Implementierung n"otig\\ $\rightarrow$ Jeder Schritt der Erkennung nachvollziehbar \end{enumerate} \end{frame} @@ -91,18 +91,18 @@ \begin{enumerate} \item Wie k"onnen regul"are Ausdr"ucke m"oglichst einfach und effizient implementiert werden? \begin{itemize} - \item ``Herk"ommliche'' \textbf{Backtracking}-Methode (\textit{Perl}, \textit{PCRE}) + \item "`Herk"ommliche"' \textit{backtracking}-Methode (\textit{Perl}, \textit{PCRE}) \item[$\Rightarrow$] Direkte Konstruktion eines \textbf{endlichen Automaten} \end{itemize} \item[] - \item Soll der Automat dargestellt werden und wenn ja, wie? + \item Soll der Automat dargestellt werden -- und wenn ja, wie? \begin{itemize} \item[$\Rightarrow$] \textbf{Ja}, im besten Fall mit Animationen... \end{itemize} \item[] \item In welcher Umgebung k"onnen alle Teile (1. Parser, 2. GUI, 3. Visualisierung) gut implementiert werden? \begin{itemize} - \item[$\Rightarrow$] \textbf{Browser}-basiert (1. \textit{JavaScript}, 2. \textit{HTML}, 3. \textit{SVG}) + \item[$\Rightarrow$] Im \textbf{Browser} (1. \textit{JavaScript}, 2. \textit{HTML}, 3. \textit{SVG}) \end{itemize} \end{enumerate} \end{frame} @@ -115,10 +115,10 @@ \begin{enumerate} \item \textbf{Parsen} des Ausdrucks \item Umsetzung in einen \textbf{nichtdeterministischen endlichen Automaten} - \item Übersetzung eine NDEA in einen \textbf{deterministischen} endlichen Automaten - \item Grafische \textbf{Darstellung} des Automaten und dessen \textbf{Simulation} + \item Übersetzung des NDEA in einen \textbf{deterministischen} endlichen Automaten + \item Grafische \textbf{Darstellung} des Automaten und dessen \textbf{Simulation} durch Animation \item[] - \item[] Umsetzung im \textbf{Browser}: \textit{JavaScript} (\textit{Rapha\"el} f"ur \textit{SVG}, \textit{jQuery}), \textit{HTML}+\textit{CSS} + \item[] Umsetzung im Browser: \textit{JavaScript} (\textit{Rapha\"el} f"ur \textit{SVG}, \textit{jQuery}), \textit{HTML}+\textit{CSS} \end{enumerate} \end{frame} @@ -168,7 +168,7 @@ \end{tabular}} \column{7.5cm} -\lstset{language=C++, emph={RegexParser}} +\lstset{language=C++, emph={RegexParser,expr}} \begin{lstlisting} RegexParser.prototype.expr = function() { var nfa = this.term(); @@ -181,19 +181,19 @@ RegexParser.prototype.expr = function() { \end{columns} \begin{itemize} - \item Nahezu direktes "Ubersetzen einer Grammatik\footnote{keine Links-Rekursionen, sonst: Endlosschleife} in den Quelltext des Parsers (LL(1)) + \item Nahezu direktes "Ubersetzen einer Grammatik\footnote{keine Links-Rekursionen, sonst: Endlosschleife} in den Quelltext des Parsers, \textit{top-down} (LL(1)) \item $\forall$ Nichtterminale $\exists$ Funktion, welche die rechte Seite der jeweiligen Regel behandelt - \item Direkte Erzeugung des NDEA, mittels Konstruktion nach Thompson - \item Max. $2m$ Zust"ande, $4m$ Transitionen ($m$ L"ange des Alphabets) + \item Direkte Erzeugung des NDEA, mittels Konstruktion nach Thompson in $O(|r|)$ ($|r|$ L"ange des regul"aren Ausdrucks) + \item Ergebnis: Automat mit max. $2|r|$ Zust"anden, $4|r|$ Transitionen %\item Schnell, einfach und effizient \end{itemize} \end{frame} -\subsection{Thompson's Algorithmus} +\subsection{Konstruktion nach Thompson} \begin{frame} - \frametitle{Thompson's Algorithmus} + \frametitle{Konstruktion nach Thompson} \begin{itemize} \item[{\color{red}Konkatenation: \texttt{ab}}] @@ -210,7 +210,7 @@ RegexParser.prototype.expr = function() { \subsection{Beispiel} \begin{frame} - \frametitle{Thompson's Algorithmus: Beispiel} + \frametitle{Thompsons Algorithmus: Beispiel} Regulärer Ausdruck: \texttt{a(a|b)c*} \vspace{0.5cm} @@ -235,14 +235,17 @@ RegexParser.prototype.expr = function() { \begin{itemize} \item[] Warum den erzeugten NDEA in einen DEA "uberf"uhren? \item[] - \item \textit{trade-off}: + \item[] \textit{trade-off}: \begin{tabular}{rll} - Platzbedarf & $-$NDEA & \textbf{$\mathbf{+}$DEA}\\ - Erstellungszeit & \textbf{$\mathbf{+}$NDEA} & $-$DEA\\ - Ausf"uhrungszeit & $-$NDEA & \textbf{$\mathbf{+}$DEA}\\ + & NDEA & DEA\\ + Platzbedarf & $2|r| = m$, $4|r| = n$ & $2^{m}$\\ + Erstellungszeit & $O(|r|)$ & $O(|r|^2 2^{|r|})$, $O(|r|^3)$\\ + Simulation & $O(|x|(m+n))$ & $O(|x|)$ \\ + & $\approx O(|x|*|r|)$ & \\ \end{tabular} + \item[]\footnotesize $|x|$ L"ange des Eingabe-Strings; bei Erstellungszeit DEA: links \textit{worst-case}, rechts der Durchschnitsfall\normalsize \item[] - \item NDEAs\footnote{insbesondere die hier erzeugten} umfassen f"ur gew"ohnlich sehr viele Zust"ande, die Darstellung eines DEA ist praktikabler + \item Die hier erzeugten NDEA umfassen f"ur gew"ohnlich sehr viele Zust"ande, die Darstellung eines DEA ist praktikabler \end{itemize} \end{frame} @@ -295,8 +298,10 @@ return d \end{columns} \begin{itemize} - \item $\forall p \in Q : E(\{p\}) = \{ q \in Q : p \rightarrow_\epsilon q \}$ - \item \textbf{Laufzeit:} $O(nm^2)$ (bei Vorberechung aller $\epsilon$-Abschl"usse: $O(m)$) + \item[] \footnotesize \texttt{a e> b}: $\epsilon$-"Ubergang von Z. \texttt{a} nach \texttt{b}; \texttt{a ch> b}: "Ubergang mit Zeichen \texttt{ch} + \item[$\bullet$] \textbf{Formal:} $\forall p \in Q : E(\{p\}) = \{ q \in Q : p \rightarrow_\epsilon q \}$ ($\epsilon$-Abschl. v. a. $p$ aus $Q$) + \item[$\bullet$] \textbf{Simulation} des NDEA, oder vollst"andige Erzeugung eines \textbf{DEA} + %\item \textbf{Laufzeit:} $O(k(n +m))$, $k$ L"ange der Eingabe, $n$ NFA Zust"ande, $m$ NFA "Uberg"ange \end{itemize} \end{frame} @@ -340,6 +345,14 @@ return d %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\section*{Fragen} +\begin{frame}[plain] + \begin{center} + \Huge{Fragen?} + \end{center} +\end{frame} + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[allowframebreaks] \frametitle{Literatur} @@ -379,7 +392,7 @@ return d \item Zeichenklassen: \texttt{.}, \texttt{\textbackslash w}, \texttt{\textbackslash d}, \lbrack\ \rbrack, $\hdots$ $\rightarrow$ Einfach implementierbar, Vorverarbeitung der Eingabe \item Operatoren: $+$, ?, \{$m$, $n$\}, $\hdots$ $\rightarrow$ Ebenfalls durch Vorverarbeitung l"osbar, beziehungsweise durch Anpassung des Automaten \item[] - \item \textit{Lookahead} oder \textit{lookbehind} sind leider nicht mit endlichen Automaten zu implementieren, da die zugrunde liegenden Grammatiken nicht mehr regul"ar w"aren. + \item \textit{Lookahead} oder \textit{lookbehind} sind leider nicht ohne Weiteres mit endlichen Automaten zu implementieren, da die zugrunde liegenden Grammatiken nicht mehr regul"ar w"aren. \end{itemize} \end{frame} -- cgit v1.2.3