# HG changeset patch # User Christian Urban # Date 1510145679 0 # Node ID f6e937ed03327400ab0a83ddb3bd24d4db4c901a # Parent cec95ad3a8378a00692592b8dba7aa777bedefe7 added diff -r cec95ad3a837 -r f6e937ed0332 coursework/cw03.pdf Binary file coursework/cw03.pdf has changed diff -r cec95ad3a837 -r f6e937ed0332 progs/comb1.scala --- 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) -} diff -r cec95ad3a837 -r f6e937ed0332 progs/comb2.scala --- a/progs/comb2.scala Wed Nov 01 11:44:23 2017 +0000 +++ b/progs/comb2.scala Wed Nov 08 12:54:39 2017 +0000 @@ -64,30 +64,6 @@ new SeqParser[String, String, String](s, r) } -lazy val E: Parser[String, Int] = - (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z} || T -lazy val T: Parser[String, Int] = - (F ~ "*" ~ T) ==> { case ((x, y), z) => x * z} || F -lazy val F: Parser[String, Int] = - ("(" ~ E ~ ")") ==> { case ((x, y), z) => y} || NumParser - -println(E.parse_all("123")) -println(E.parse_all("1*2+3")) -println(E.parse_all("1+2*3")) -println(E.parse_all("1+2+3")) -println(E.parse_all("1+2+3")) -println(E.parse_all("1+2*3+1")) - - -// no left-recursion allowed -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")) - // the abstract syntax trees for the WHILE language abstract class Stmt @@ -154,7 +130,7 @@ (Stmt ==> ((s) => List(s)))) -Stmt.parse_all("x2:=5") +Stmt.parse_all("x2:=5+3") Block.parse_all("{x:=5;y:=8}") Block.parse_all("if(false)then{x:=5}else{x:=10}") diff -r cec95ad3a837 -r f6e937ed0332 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r cec95ad3a837 -r f6e937ed0332 slides/slides06.tex --- 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]