summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--javascripts/globals.js2
-rw-r--r--javascripts/graph.js2
-rw-r--r--javascripts/uifunc.js44
-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
-rw-r--r--resources/literature/10.1.1.21.1679.pdfbin0 -> 259747 bytes
12 files changed, 88 insertions, 37 deletions
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
--- 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}
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
--- /dev/null
+++ b/resources/literature/10.1.1.21.1679.pdf
Binary files differ
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 23:59:48 +0000