--- a/ChengsongTanPhdThesis/Chapters/Bitcoded1.tex Tue Jul 25 17:28:29 2023 +0100
+++ b/ChengsongTanPhdThesis/Chapters/Bitcoded1.tex Wed Aug 23 03:02:31 2023 +0100
@@ -44,288 +44,351 @@
\end{tabular}
\end{center}
\noindent
-The first problem with this algorithm is that
-for the function $\inj$ to work properly
-we cannot destroy the structure of a regular expression,
-and therefore cannot simplify too aggressively.
-For example,
-\[
- r + (r + a) \rightarrow r + a
-\]
-cannot be applied because that would require
-breaking up the inner alternative.
-The $\lexer$ plus $\textit{simp}$ therefore only enables
-same-level de-duplications like
-\[
- r + r \rightarrow r.
-\]
-Secondly, the algorithm recursively calls $\lexer$ on
-each new character input,
-and before starting a child call
-it stores information of previous lexing steps
-on a stack, in the form of regular expressions
-and characters: $r_0$, $c_0$, $r_1$, $c_1$, etc.
-Each descent into deeper recursive calls in $\lexer$
-causes a new pair of $r_i, c_i$ to be pushed to the call stack.
-\begin{figure}[H]
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
-%\draw (-6,-6) grid (6,6);
-\node [ circle ] (r) at (-6, 5) {$r$};
+This algorithm works nicely as a functional program that utilizes Brzozowski derivatives:
+each derivative character is remembered and stacked up, and
+injected back in reverse order as they have been taken derivative of.
+The derivative operation $\backslash$ and its reverse operation
+$\inj$ is of similar shape and compexity, and work in lockstep with each other.
+However if we take a closer look into the example run
+of $\lexer$ we have shown in chapter \ref{Inj},
+many inefficiencies exist:
+\begin{center}
+ \begin{tabular}{lcl}
+ $(a+\textcolor{magenta}{a}\textcolor{blue}{a})^* \cdot \textcolor{red}{c}$ & $\stackrel{\backslash \textcolor{magenta}{a}}{\rightarrow}$ & $((\ONE + \textcolor{magenta}{\ONE} \textcolor{blue}{a})\cdot (a+aa)^*)\cdot \textcolor{red}{c}+\ZERO$\\
+ %& $\stackrel{\rightarrow}{\backslash a}$ & $((\ONE + \ONE a)\cdot (a+aa)^*)\cdot c + \ZERO$\\
+ & $\stackrel{\backslash \textcolor{blue}{a}}{\rightarrow}$ &
+ $(((\ZERO+(\ZERO a+ \textcolor{blue}{\ONE}))\cdot (a+aa)^* + (\ONE+\ONE a)\cdot (a+aa)^* )\cdot \textcolor{red}{\mathbf{c}} + \ZERO)+\ZERO$\\
+ & $\stackrel{\backslash \textcolor{red}{c}}{\rightarrow}$ &
+ $((r_{=0}\cdot c + \textcolor{red}{\ONE})+\ZERO)+\ZERO$\\
+ & $\stackrel{\mkeps}{\rightarrow}$ & $\Left (\Left \; (\Right \; \textcolor{red}{\Empty}))$ \\
+ & $\stackrel{\inj \;\textcolor{red}{c} }{\rightarrow}$ &
+ $\Left \; (\Left \; (\Seq \;(\Left \; (\Seq \; (\Right \; (\Right\; \textcolor{blue}{\Empty})) \; \Stars \, [])) \; \textcolor{red}{c}))$\\
+ & $\stackrel{\inj \;\textcolor{blue}{a}}{\rightarrow}$ &
+ $\Left\; (\Seq \; (\Seq\; (\Right \; (\Seq \; \textcolor{magenta}{\Empty }\; \textcolor{blue}{ \mathbf{a}}) )
+ \;\Stars \,[]) \; \textcolor{red}{c})$\\
+ & $\stackrel{\inj \;\textcolor{magenta}{a}}{\rightarrow}$ & $\Seq \; (\Stars \; [\Right \; (\Seq \; \mathbf{\textcolor{magenta}{a}} \; \textcolor{blue}{a})]) \; \textcolor{red}{ c}$
-%\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
-\node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$};
-%
-%\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
-\node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$};
-
-\node [minimum width = 2cm, rectangle, draw] (stack) at (0, 3) {Stack};
+ %$\inj \; r \; c\A$
+ %$\inj \; (a\cdot b)\cdot c \; \Seq \; \ONE \; b$ & $=$ & $(a+e)$\\
+ \end{tabular}
+\end{center}
+\noindent
+For the un
-\path
- (r)
- edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
-
-\path (r1)
- edge [bend right, dashed] node {saved} (stack);
-\path (c1)
- edge [bend right, dashed] node {} (stack);
-
-
-\end{tikzpicture}
-\caption{First derivative taken}
-\end{figure}
+\begin{center}
+ \begin{tabular}{lcl}
+$\inj$ & $\quad ((\ONE + {\ONE}
+ \textcolor{blue}{a})\cdot (a+aa)^*)\cdot
+ + \ZERO \; \quad \textcolor{blue}{a} \; $ & \\
+$\quad \Left \;
+(\Left \; (\Seq \;(\Left \; (\Seq \; (\Right \; (\Right\;
+ \textcolor{blue}{\Empty})) \; \Stars \, [])) \; c))$ & \\$=$\\
+ $\Left \; (\inj \; ((\ONE + \ONE
+ \textcolor{blue}{a})\cdot (a+aa)^*)\cdot
+ c \quad \textcolor{blue}{a} \quad (\Left \; (\Seq\; ( \Left \; (\Seq \; (\Right \; (\Right\;
+ \textcolor{blue}{\Empty})) \; \Stars \, []) ) \; c ) )\;\;)$ &\\ $=$\\
+ $\Left \; (\Seq \; (\inj \; (\ONE + \ONE \textcolor{blue}{a})\cdot(a+aa)^* \quad \textcolor{blue}{a} \quad
+ (\Left \; (\Seq \; (\Right \; (\Right\;\textcolor{blue}{\Empty})))) ) \; c ) $ & \\$=$\\
+ $\Left \; (\Seq \; (\Seq \; (\inj \quad (\ONE + \ONE \textcolor{blue}{a}) \quad \textcolor{blue}{a}\quad \Right \;(\Right \; \textcolor{blue}{\Empty}) ) \; \Stars \,[])\; c)$ &\\ $=$ \\
+ $\Left \; (\Seq \; (\Seq \; (\Right \; (\inj \; \ONE \textcolor{blue}{a} \quad \textcolor{blue}{a}\quad (\Right \;\textcolor{blue}{\Empty})))) \; \Stars \, [])$
+ & \\ $=$\\
+ $\Left \; (\Seq \; (\Seq \; (\Right \; (\Seq \; (\mkeps \; \ONE)\;(\inj \;\textcolor{blue}{a} \; \textcolor{blue}{a} \; \textcolor{blue}{\Empty})) ) ) \; \Stars \, [] )$
+ & \\ $=$\\
+ $\Left \; (\Seq \; (\Seq \; (\Right \; (\Seq \; \Empty \; \textcolor{blue}{a}) ) ) \; \Stars \, [] )$
+ \end{tabular}
+\end{center}
-\begin{figure}[H]
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
-%\draw (-6,-6) grid (6,6);
-\node [ circle ] (r) at (-6, 5) {$r$};
-%\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
-\node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$};
-%
-%\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
-\node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$};
-
-
-\node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$};
-%
-%\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
-\node [circle, draw] (r2) at (2, 5) {$r_2$};
-\node [minimum width = 3cm, minimum height = 1cm, rectangle, draw] (stack) at (0, 2) {\large Stack};
-
-\path
- (r)
- edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
-
-\path (r2)
- edge [bend right, dashed] node {} (stack);
-\path (c2)
- edge [bend right, dashed] node {} (stack);
-
-\path (r1)
- edge [] node {} (r2);
-
-\end{tikzpicture}
-\caption{Second derivative taken}
-\end{figure}
-\noindent
-As the number of derivative steps increases,
-the stack would increase:
-
-\begin{figure}[H]
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
-%\draw (-6,-6) grid (6,6);
-\node [ circle ] (r) at (-6, 5) {$r$};
-
-%\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
-\node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$};
-%
-%\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
-\node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$};
-
-
-\node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$};
-%
-%\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
-\node [circle, ] (r2) at (2, 5) {$r_2$};
-\node [minimum width = 4cm, minimum height = 2.5cm, rectangle, draw] (stack) at (0, 1) { \large Stack};
-
-\node [] (ldots) at (3.5, 5) {};
-%\node (6, 5) (rn) circle [radius = 0.5] {$r_n$};
-
-\node [minimum size = 0.5, circle, ] (rn) at (6, 5) {};
-
-\node (rldots) at ($(ldots)!.4!(rn)$) {\ldots};
-
-\path
- (r)
- edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
-
-\path (rldots)
- edge [bend left, dashed] node {} (stack);
-
-\path (r1)
- edge [] node {} (r2);
-
-\path (r2)
- edge [] node {} (ldots);
-\path (ldots)
- edge [bend left, dashed] node {} (stack);
-\path (5.03, 4.9)
- edge [bend left, dashed] node {} (stack);
-\end{tikzpicture}
-\caption{More derivatives taken}
-\end{figure}
-
-
-\begin{figure}[H]
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
-%\draw (-6,-6) grid (6,6);
-\node [radius = 0.5, circle, draw] (r) at (-6, 5) {$r$};
-
-%\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
-\node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$};
-%
-%\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
-\node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$};
-%
-%\node (0, 6) (c2) circle [radius = 0.3] {$c_2$};
-\node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$};
-%
-%\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
-\node [circle, draw] (r2) at (2, 5) {$r_2$};
-%
-%
-\node [] (ldots) at (4.5, 5) {};
-%\node (6, 5) (rn) circle [radius = 0.5] {$r_n$};
-
-\node [minimum size = 0.5, circle, draw] (rn) at (6, 5) {$r_n$};
-
-\node at ($(ldots)!.4!(rn)$) {\ldots};
-\node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack};
-
-\path
- (r)
- edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
-\path
- (r1)
- edge [] node {} (r2);
-\path (r2)
- edge [] node {} (ldots);
-\path (r)
- edge [dashed, bend right] node {} (stack);
-
-\path (r1)
- edge [dashed, ] node {} (stack);
+% The first problem with this algorithm is that
+% for the function $\inj$ to work properly
+% we cannot destroy the structure of a regular expression,
+% and therefore cannot simplify along the way without mechanisms
+% that restores the values during the simplification process.
+% %too aggressively.
+% For example,
+% \[
+% r + (r + a) \rightarrow r + a
+% \]
+% cannot be applied because that would require
+% breaking up the inner alternative.
+% The $\lexer$ plus $\textit{simp}$ therefore only enables
+% same-level de-duplications like
+% \[
+% r + r \rightarrow r.
+% \]
+% Secondly, the algorithm recursively calls $\lexer$ on
+% each new character input,
+% and before starting a child call
+% it stores information of previous lexing steps
+% on a stack, in the form of regular expressions
+% and characters: $r_0$, $c_0$, $r_1$, $c_1$, etc.
+% Each descent into deeper recursive calls in $\lexer$
+% causes a new pair of $r_i, c_i$ to be pushed to the call stack.
+% \begin{figure}[H]
+% \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
+% %\draw (-6,-6) grid (6,6);
+% \node [ circle ] (r) at (-6, 5) {$r$};
-\path (c1)
- edge [dashed, bend right] node {} (stack);
+% %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
+% \node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$};
+% %
+% %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
+% \node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$};
+
+% \node [minimum width = 2cm, rectangle, draw] (stack) at (0, 3) {Stack};
+
+% \path
+% (r)
+% edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
+
+% \path (r1)
+% edge [bend right, dashed] node {saved} (stack);
+% \path (c1)
+% edge [bend right, dashed] node {} (stack);
-\path (c2)
- edge [dashed] node {} (stack);
-\path (4.5, 5)
- edge [dashed, bend left] node {} (stack);
-\path (4.9, 5)
- edge [dashed, bend left] node {} (stack);
-\path (5.3, 5)
- edge [dashed, bend left] node {} (stack);
-\path (r2)
- edge [dashed, ] node {} (stack);
-\path (rn)
- edge [dashed, bend left] node {} (stack);
-\end{tikzpicture}
-\caption{Before injection phase starts}
-\end{figure}
+
+% \end{tikzpicture}
+% \caption{First derivative taken}
+% \end{figure}
+
+
+
+% \begin{figure}[H]
+% \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
+% %\draw (-6,-6) grid (6,6);
+% \node [ circle ] (r) at (-6, 5) {$r$};
+
+% %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
+% \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$};
+% %
+% %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
+% \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$};
-\noindent
+% \node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$};
+% %
+% %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
+% \node [circle, draw] (r2) at (2, 5) {$r_2$};
+% \node [minimum width = 3cm, minimum height = 1cm, rectangle, draw] (stack) at (0, 2) {\large Stack};
+
+% \path
+% (r)
+% edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
+
+% \path (r2)
+% edge [bend right, dashed] node {} (stack);
+% \path (c2)
+% edge [bend right, dashed] node {} (stack);
+
+% \path (r1)
+% edge [] node {} (r2);
+
+% \end{tikzpicture}
+% \caption{Second derivative taken}
+% \end{figure}
+% \noindent
+% As the number of derivative steps increases,
+% the stack would increase:
+
+% \begin{figure}[H]
+% \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
+% %\draw (-6,-6) grid (6,6);
+% \node [ circle ] (r) at (-6, 5) {$r$};
+
+% %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
+% \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$};
+% %
+% %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
+% \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$};
+
+
+% \node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$};
+% %
+% %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
+% \node [circle, ] (r2) at (2, 5) {$r_2$};
+% \node [minimum width = 4cm, minimum height = 2.5cm, rectangle, draw] (stack) at (0, 1) { \large Stack};
+
+% \node [] (ldots) at (3.5, 5) {};
+% %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$};
+
+% \node [minimum size = 0.5, circle, ] (rn) at (6, 5) {};
+
+% \node (rldots) at ($(ldots)!.4!(rn)$) {\ldots};
+
+% \path
+% (r)
+% edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
+
+% \path (rldots)
+% edge [bend left, dashed] node {} (stack);
+
+% \path (r1)
+% edge [] node {} (r2);
+
+% \path (r2)
+% edge [] node {} (ldots);
+% \path (ldots)
+% edge [bend left, dashed] node {} (stack);
+% \path (5.03, 4.9)
+% edge [bend left, dashed] node {} (stack);
+% \end{tikzpicture}
+% \caption{More derivatives taken}
+% \end{figure}
+
+
+% \begin{figure}[H]
+% \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
+% %\draw (-6,-6) grid (6,6);
+% \node [radius = 0.5, circle, draw] (r) at (-6, 5) {$r$};
+
+% %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
+% \node [circle, minimum size = 0.1, draw] (c1) at (-4, 5.4) {$c_1$};
+% %
+% %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
+% \node [minimum size = 0.5, circle, draw] (r1) at (-2, 5) {$r_1$};
+% %
+% %\node (0, 6) (c2) circle [radius = 0.3] {$c_2$};
+% \node [circle, minimum size = 0.1, draw] (c2) at (0, 5.4) {$c_2$};
+% %
+% %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
+% \node [circle, draw] (r2) at (2, 5) {$r_2$};
+% %
+% %
+% \node [] (ldots) at (4.5, 5) {};
+% %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$};
+
+% \node [minimum size = 0.5, circle, draw] (rn) at (6, 5) {$r_n$};
+
+% \node at ($(ldots)!.4!(rn)$) {\ldots};
+
+
+
+
+% \node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack};
+
+% \path
+% (r)
+% edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
+% \path
+% (r1)
+% edge [] node {} (r2);
+% \path (r2)
+% edge [] node {} (ldots);
+% \path (r)
+% edge [dashed, bend right] node {} (stack);
+
+% \path (r1)
+% edge [dashed, ] node {} (stack);
+
+% \path (c1)
+% edge [dashed, bend right] node {} (stack);
+
+% \path (c2)
+% edge [dashed] node {} (stack);
+% \path (4.5, 5)
+% edge [dashed, bend left] node {} (stack);
+% \path (4.9, 5)
+% edge [dashed, bend left] node {} (stack);
+% \path (5.3, 5)
+% edge [dashed, bend left] node {} (stack);
+% \path (r2)
+% edge [dashed, ] node {} (stack);
+% \path (rn)
+% edge [dashed, bend left] node {} (stack);
+% \end{tikzpicture}
+% \caption{Before injection phase starts}
+% \end{figure}
+
+
+% \noindent
After all derivatives have been taken, the stack grows to a maximum size
and the pair of regular expressions and characters $r_i, c_{i+1}$
are then popped out and used in the injection phase.
-\begin{figure}[H]
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
-%\draw (-6,-6) grid (6,6);
-\node [radius = 0.5, circle, ] (r) at (-6, 5) {$r$};
+% \begin{figure}[H]
+% \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,thick]
+% %\draw (-6,-6) grid (6,6);
+% \node [radius = 0.5, circle, ] (r) at (-6, 5) {$r$};
-%\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
-\node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$};
-%
-%\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
-\node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$};
-%
-%\node (0, 6) (c2) circle [radius = 0.3] {$c_2$};
-\node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$};
-%
-%\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
-\node [circle, ] (r2) at (2, 5) {$r_2$};
-%
-%
-\node [] (ldots) at (4.5, 5) {};
-%\node (6, 5) (rn) circle [radius = 0.5] {$r_n$};
+% %\node (-4, 6) (c1) circle [radius = 0.3] {$c_1$};
+% \node [circle, minimum size = 0.1, ] (c1) at (-4, 5.4) {$c_1$};
+% %
+% %\node (-2, 5) (r1) circle [radius = 0.5] {$r_1$};
+% \node [minimum size = 0.5, circle, ] (r1) at (-2, 5) {$r_1$};
+% %
+% %\node (0, 6) (c2) circle [radius = 0.3] {$c_2$};
+% \node [circle, minimum size = 0.1, ] (c2) at (0, 5.4) {$c_2$};
+% %
+% %\node (2, 5) (r2) circle [radius = 0.5] {$r_2$};
+% \node [circle, ] (r2) at (2, 5) {$r_2$};
+% %
+% %
+% \node [] (ldots) at (4.5, 5) {};
+% %\node (6, 5) (rn) circle [radius = 0.5] {$r_n$};
-\node [minimum size = 0.5, circle, ] (rn) at (6, 5) {$r_n$};
+% \node [minimum size = 0.5, circle, ] (rn) at (6, 5) {$r_n$};
-\node at ($(ldots)!.4!(rn)$) {\ldots};
+% \node at ($(ldots)!.4!(rn)$) {\ldots};
-\node [minimum size = 0.5, circle, ] (vn) at (6, -5) {$v_n$};
+% \node [minimum size = 0.5, circle, ] (vn) at (6, -5) {$v_n$};
-\node [] (ldots2) at (3.5, -5) {};
+% \node [] (ldots2) at (3.5, -5) {};
-\node [minimum size = 0.5, circle, ] (v2) at (2, -5) {$v_2$};
+% \node [minimum size = 0.5, circle, ] (v2) at (2, -5) {$v_2$};
-\node at ($(ldots2)!.4!(v2)$) {\ldots};
+% \node at ($(ldots2)!.4!(v2)$) {\ldots};
-\node [circle, ] (v1) at (-2, -5) {$v_1$};
+% \node [circle, ] (v1) at (-2, -5) {$v_1$};
-\node [radius = 0.5, circle, ] (v) at (-6, -5) {$v$};
+% \node [radius = 0.5, circle, ] (v) at (-6, -5) {$v$};
-\node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack};
+% \node [minimum size = 6cm, rectangle, draw] (stack) at (0, 0) {\Huge Stack};
-\path
- (r)
- edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
-\path
- (r1)
- edge [] node {} (r2);
-\path (r2)
- edge [] node {} (ldots);
-\path (rn)
- edge [] node {$\mkeps$} (vn);
-\path (vn)
- edge [] node {} (ldots2);
-\path (v2)
- edge [] node {$\inj \; r_1 \; c_2\;v_2$} (v1);
+% \path
+% (r)
+% edge [->, >=stealth',shorten >=1pt] node[left] {} (r1);
+% \path
+% (r1)
+% edge [] node {} (r2);
+% \path (r2)
+% edge [] node {} (ldots);
+% \path (rn)
+% edge [] node {$\mkeps$} (vn);
+% \path (vn)
+% edge [] node {} (ldots2);
+% \path (v2)
+% edge [] node {$\inj \; r_1 \; c_2\;v_2$} (v1);
-\path (v1)
- edge [] node {$\inj \; r \; c_1 \; v_1$} (v);
+% \path (v1)
+% edge [] node {$\inj \; r \; c_1 \; v_1$} (v);
-\path (stack)
- edge [dashed] node {} (-4.2, -5.2);
-\path (stack)
- edge [dashed] node {} (-4, -5.2);
-\path (stack)
- edge [dashed] node {} (-0.1, -5.2);
-\path (stack)
- edge [dashed] node {} (0.2, -5.26);
-\path (stack)
- edge [dashed] node {} (3.2, -5);
-\path (stack)
- edge [dashed] node {} (2.7, -5);
-\path (stack)
- edge [dashed] node {} (3.7, -5);
-\end{tikzpicture}
-\caption{Stored $r_i, c_{i+1}$ Used by $\inj$}
-\end{figure}
-\noindent
+% \path (stack)
+% edge [dashed] node {} (-4.2, -5.2);
+% \path (stack)
+% edge [dashed] node {} (-4, -5.2);
+% \path (stack)
+% edge [dashed] node {} (-0.1, -5.2);
+% \path (stack)
+% edge [dashed] node {} (0.2, -5.26);
+% \path (stack)
+% edge [dashed] node {} (3.2, -5);
+% \path (stack)
+% edge [dashed] node {} (2.7, -5);
+% \path (stack)
+% edge [dashed] node {} (3.7, -5);
+% \end{tikzpicture}
+% \caption{Stored $r_i, c_{i+1}$ Used by $\inj$}
+% \end{figure}
+% \noindent
Storing all $r_i, c_{i+1}$ pairs recursively
allows the algorithm to work in an elegant way, at the expense of
storing quite a bit of verbose information on the stack.