--- a/progs/comb1.scala Wed Nov 01 11:44:23 2017 +0000
+++ b/progs/comb1.scala Wed Nov 08 12:54:39 2017 +0000
@@ -77,9 +77,9 @@
// a parse palindromes
lazy val Pal : Parser[String, String] =
(("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
- ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "")
+ ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "a" || "b" || "")
-println("Palindrome: " + Pal.parse_all("ababbaba"))
+println("Palindrome: " + Pal.parse_all("abaaaba"))
// well-nested parenthesis parser
lazy val P : Parser[String, String] =
@@ -103,8 +103,17 @@
println(E.parse_all("4*2+3"))
println(E.parse("1 + 2 * 3"))
println(E.parse_all("(1+2)+3"))
-println(E.parse_all("1+2+3")) // this is not parsed, because of
- // how the grammar is set up
+println(E.parse_all("1+2+3"))
+
+// no left-recursion allowed, otherwise will loop
+lazy val EL: Parser[String, Int] =
+ ((EL ~ "+" ~ EL) ==> { case ((x, y), z) => x + z} ||
+ (EL ~ "*" ~ EL) ==> { case ((x, y), z) => x * z} ||
+ ("(" ~ EL ~ ")") ==> { case ((x, y), z) => y} ||
+ NumParser)
+
+//println(E.parse_all("1+2+3"))
+
// a repetition parser
@@ -124,15 +133,18 @@
lazy val S : Parser[String, String] =
("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""
-S.parse_all("1" * 15)
+S.parse("1" * 15)
lazy val U : Parser[String, String] =
("1" ~ U) ==> { case (x, y) => x + y } || ""
+U.parse("1" * 15)
+
U.parse("11")
U.parse("11111")
U.parse("11011")
+U.parse_all("1" * 100)
U.parse_all("1" * 100 + "0")
lazy val UCount : Parser[String, Int] =
@@ -168,6 +180,8 @@
yield (x.toString + y)
+
+// Example section for lazy evaluation
def square(n: Int) = {
n * n
}
@@ -179,19 +193,13 @@
3
}
+//would loop
+square(bar())
+// lazy
def foo(n: => Int) = {
print("finished")
}
foo(bar())
-square(12) + square(10)
-
-
-def time_needed[T](i: Int, code: => T) = {
- val start = System.nanoTime()
- for (j <- 1 to i) code
- val end = System.nanoTime()
- (end - start)/(i * 1.0e9)
-}
--- a/slides/slides06.tex Wed Nov 01 11:44:23 2017 +0000
+++ b/slides/slides06.tex Wed Nov 08 12:54:39 2017 +0000
@@ -38,51 +38,51 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\small
-\mbox{}\\[5mm]
-%\begin{textblock}{10}(3,5)
-\begin{tikzpicture}[scale=1.5,
- node distance=1cm,
- every node/.style={minimum size=7mm}]
-\node (r1) {\bl{$r_1$}};
-\node (r2) [right=of r1] {\bl{$r_2$}};
-\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
-\node (r3) [right=of r2] {\bl{$r_3$}};
-\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
-\node (r4) [right=of r3] {\bl{$r_4$}};
-\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
-\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
-\node (v4) [below=of r4] {\bl{$v_4$}};
-\draw[->,line width=1mm] (r4) -- (v4);
-\node (v3) [left=of v4] {\bl{$v_3$}};
-\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
-\node (v2) [left=of v3] {\bl{$v_2$}};
-\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
-\node (v1) [left=of v2] {\bl{$v_1$}};
-\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
-\draw[->,line width=0.5mm] (r3) -- (v3);
-\draw[->,line width=0.5mm] (r2) -- (v2);
-\draw[->,line width=0.5mm] (r1) -- (v1);
-\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
-\end{tikzpicture}
-%\end{textblock}
+% \begin{frame}[c]
+% \small
+% \mbox{}\\[5mm]
+% %\begin{textblock}{10}(3,5)
+% \begin{tikzpicture}[scale=1.5,
+% node distance=1cm,
+% every node/.style={minimum size=7mm}]
+% \node (r1) {\bl{$r_1$}};
+% \node (r2) [right=of r1] {\bl{$r_2$}};
+% \draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+% \node (r3) [right=of r2] {\bl{$r_3$}};
+% \draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+% \node (r4) [right=of r3] {\bl{$r_4$}};
+% \draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+% \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+% \node (v4) [below=of r4] {\bl{$v_4$}};
+% \draw[->,line width=1mm] (r4) -- (v4);
+% \node (v3) [left=of v4] {\bl{$v_3$}};
+% \draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+% \node (v2) [left=of v3] {\bl{$v_2$}};
+% \draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+% \node (v1) [left=of v2] {\bl{$v_1$}};
+% \draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+% \draw[->,line width=0.5mm] (r3) -- (v3);
+% \draw[->,line width=0.5mm] (r2) -- (v2);
+% \draw[->,line width=0.5mm] (r1) -- (v1);
+% \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+% \end{tikzpicture}
+% %\end{textblock}
-\begin{center}
-\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
- \\[-10mm]
- \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
-\end{tabular}
-\end{center}
+% \begin{center}
+% \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+% \\[-10mm]
+% \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+% \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+% \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+% \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+% \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+% \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+% \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
+% \end{tabular}
+% \end{center}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -106,28 +106,7 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Two Grammars}
-
-Which languages are recognised by the following two grammars?
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\
- & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}\bigskip
-
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$U$ & $\rightarrow$ & $1 \cdot U$\\
- & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -208,6 +187,62 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Types of Parsers}
+
+\begin{itemize}
+\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
+then \bl{$p \sim q$} returns results of type
+
+\begin{center}
+\bl{$T \times S$}
+\end{center}\pause
+
+\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$},
+and \bl{$p \;||\; q$} returns results of type
+
+\begin{center}
+\bl{$T$}
+\end{center}\pause
+
+\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
+\bl{$T$} to \bl{$S$}, then
+\bl{$p \Rightarrow f$} returns results of type
+
+\begin{center}
+\bl{$S$}
+\end{center}
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Two Grammars}
+
+Which languages are recognised by the following two grammars?
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\
+ & $|$ & $\epsilon$
+\end{tabular}}
+\end{center}\bigskip
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$U$ & $\rightarrow$ & $1 \cdot U$\\
+ & $|$ & $\epsilon$
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]