From 8d67caae222e1652936ecc6cc7a237f67fc320c5 Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Tue, 29 Jun 2010 09:11:38 +0200 Subject: presentation done --- javascripts/globals.js | 2 ++ javascripts/graph.js | 2 +- javascripts/uifunc.js | 44 +++++++++++++++++------ 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 +++++++++++++++++++------------- resources/literature/10.1.1.21.1679.pdf | Bin 0 -> 259747 bytes 12 files changed, 88 insertions(+), 37 deletions(-) create mode 100644 presentation/demo.txt create mode 100644 resources/literature/10.1.1.21.1679.pdf diff --git a/javascripts/globals.js b/javascripts/globals.js index 56b31d8..e48018d 100644 --- a/javascripts/globals.js +++ b/javascripts/globals.js @@ -9,3 +9,5 @@ var REDELIMITER = '$'; var ttable = new Object(); var g; var graphit = true; +var lock = false; + diff --git a/javascripts/graph.js b/javascripts/graph.js index 6b8fbf4..70b67d8 100644 --- a/javascripts/graph.js +++ b/javascripts/graph.js @@ -116,7 +116,7 @@ Raphael.fn.aNode = function(x, y, r, isFinal, hasSelfConn, // arrow head var ahSize = r/8; var ahRef = selfConn.getPointAtLength(selfConn.getTotalLength()-1) - var ahAngle = Math.atan2(ahRef.x-p2.x,p2.x-ahRef.y); + var ahAngle = Math.atan2(ahRef.x-p2.x,p2.x-(-ahRef.y)); ahAngle = (ahAngle / (2 * Math.PI)) * 360; var ah = this.path("M" + ahRef.x + " " + ahRef.y + " L" + (ahRef.x - ahSize) + " " + (ahRef.y - ahSize) + diff --git a/javascripts/uifunc.js b/javascripts/uifunc.js index 99b975d..f14b6b2 100644 --- a/javascripts/uifunc.js +++ b/javascripts/uifunc.js @@ -20,7 +20,7 @@ function graph_inprogress() { $('#word').removeClass('success'); $('#word').removeClass('failure'); $('#word').addClass('inprogress'); - window.g.mover.attr({fill: '#ffff88'}); + window.g.mover.attr({fill: 'yellow'});//'#ffff88'}); }; function graph_success() { $('#checkMessage').html('Word accepted'); @@ -30,7 +30,7 @@ function graph_success() { $('#word').removeClass('inprogress'); $('#word').addClass('success'); $('#checkMessage').effect("highlight", {}, 1000); - window.g.mover.attr({fill: '#cdeb8b'}); + window.g.mover.attr({fill: 'green'});//'#cdeb8b'}); }; function graph_failure() { $('#checkMessage').html('Word not accepted'); @@ -40,7 +40,7 @@ function graph_failure() { $('#word').removeClass('inprogress'); $('#word').addClass('failure'); $('#checkMessage').effect("highlight", {}, 1000); - window.g.mover.animate({fill: '#b02b2c'}, 250); + window.g.mover.animate({fill: 'red'});//'#b02b2c'}, 250); }; // Call of RegexParser.parse() from UI. @@ -108,6 +108,19 @@ function getKey(e, set) { // Moving inside the graph by input symbols. // setTimeout ? function graphMoveByInput(e) { + if (lock) { + if (failedInputs) { + lock = false; + } else { + //var w = $('#word').attr('value'); + //$('#word').attr('value', w.substr(0, w.length-1)); + lock = false; + return false; + } + } else { + lock = true; + } + // no graph if(!graphit) return; @@ -138,7 +151,7 @@ function graphMoveByInput(e) { var mx = g.mover.attr('cx'); var my = g.mover.attr('cy'); var ll = g.paper.path('M'+mx+','+my+' '+mx+','+(my-25)+'Z').attr({stroke: 0}); - g.mover.animateAlong(ll, 250, "bounce"); + window.setTimeout(function() { g.mover.animateAlong(ll, 250, "bounce"); }, 250); window.inSameState.pop(); if (ttable[window.gCurrentState.name].isFinal) { graph_success(); @@ -150,10 +163,10 @@ function graphMoveByInput(e) { // go back one state window.gPrevState = gPrevStates.pop(); - g.mover.animate( - {cx:gPrevState.node[1][0].cx.baseVal.value, cy:gPrevState.node[1][0].cy.baseVal.value}, - 750, "bounce" - ); + window.setTimeout(function() { + g.mover.animate({cx:gPrevState.node[1][0].cx.baseVal.value, cy:gPrevState.node[1][0].cy.baseVal.value}, 250); + lock = false; + }, 250); window.gCurrentState = gPrevState; if (ttable[window.gCurrentState.name].isFinal) { graph_success(); @@ -178,8 +191,15 @@ function graphMoveByInput(e) { // no state change if(gNextState.name == gCurrentState.name) { - g.mover.animateAlong(gCurrentState.node[4], 500); + window.setTimeout(function() { + g.mover.animateAlong(gCurrentState.node[4], 350);lock = false; + }, 125); window.inSameState.push(true); + if (ttable[window.gCurrentState.name].isFinal) { + graph_success(); + } else { + graph_inprogress(); + }; return; } else { // state change @@ -198,9 +218,10 @@ function graphMoveByInput(e) { ).attr({stroke:'none'}); (function(g, line) { setTimeout(function() { - g.mover.animateAlong(line, 500) + g.mover.animateAlong(line, 250); + lock = false; return line; - }, 1); + }, 250); })(g, line); }; window.gPrevStates.push(gCurrentState); @@ -210,3 +231,4 @@ function graphMoveByInput(e) { graph_success(); }; }; + 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} diff --git a/resources/literature/10.1.1.21.1679.pdf b/resources/literature/10.1.1.21.1679.pdf new file mode 100644 index 0000000..2b7d75a Binary files /dev/null and b/resources/literature/10.1.1.21.1679.pdf differ -- cgit v1.2.3