summaryrefslogtreecommitdiff
path: root/presentation
diff options
context:
space:
mode:
Diffstat (limited to 'presentation')
-rw-r--r--presentation/aabc.pdfbin45129 -> 46443 bytes
-rw-r--r--presentation/ab.pdfbin37400 -> 37507 bytes
-rw-r--r--presentation/aorb.pdfbin39395 -> 39824 bytes
-rw-r--r--presentation/astar.pdfbin38651 -> 39039 bytes
-rw-r--r--presentation/demo.txt8
-rw-r--r--presentation/simianer-regexvis.bib8
-rw-r--r--presentation/simianer-regexvis.pdfbin458848 -> 791825 bytes
-rw-r--r--presentation/simianer-regexvis.tex61
8 files changed, 52 insertions, 25 deletions
diff --git a/presentation/aabc.pdf b/presentation/aabc.pdf
index 5b006cc..7706b0f 100644
--- a/presentation/aabc.pdf
+++ b/presentation/aabc.pdf
Binary files differ
diff --git a/presentation/ab.pdf b/presentation/ab.pdf
index c697ad3..acaa184 100644
--- a/presentation/ab.pdf
+++ b/presentation/ab.pdf
Binary files differ
diff --git a/presentation/aorb.pdf b/presentation/aorb.pdf
index e2268f1..818582a 100644
--- a/presentation/aorb.pdf
+++ b/presentation/aorb.pdf
Binary files differ
diff --git a/presentation/astar.pdf b/presentation/astar.pdf
index 46c5f9c..30580c6 100644
--- a/presentation/astar.pdf
+++ b/presentation/astar.pdf
Binary files 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
--- a/presentation/simianer-regexvis.pdf
+++ b/presentation/simianer-regexvis.pdf
Binary files 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}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-18 14:29:14 +0000