Binary file handouts/ho06.pdf has changed
--- a/handouts/ho06.tex Wed Oct 24 13:07:13 2018 +0100
+++ b/handouts/ho06.tex Wed Oct 24 16:03:07 2018 +0100
@@ -85,7 +85,7 @@
grammar for arithmetic expressions we might be interested in the
actual integer number the arithmetic expression, say \texttt{1 + 2 *
3}, stands for. In this way we can use parser combinators to
-implement relativaley easily a calculator.
+implement relatively easily a calculator.
The main idea of parser combinators is that we can easily build parser
combinators out of smaller components following very closely the
@@ -230,7 +230,7 @@
\end{center}
\noindent Later on we will use again Scala mechanism for introducing some
-more readable shorthand notation for this, like \texttt{"a" || "b"}. Let us look in detail at what this parser combinator produces with some somple strings
+more readable shorthand notation for this, like \texttt{"a" || "b"}. Let us look in detail at what this parser combinator produces with some sample strings
\begin{center}
\begin{tabular}{rcl}
@@ -314,7 +314,7 @@
\end{center}
\noindent Later on we will use again Scala mechanism for introducing some
-more readable shorthand notation for this, like \texttt{"a" || "b"}. Let us look in detail at what this parser combinator produces with some somple strings
+more readable shorthand notation for this, like \texttt{"a" || "b"}. Let us look in detail at what this parser combinator produces with some sample strings
\begin{center}
\begin{tabular}{rcl}
@@ -353,7 +353,7 @@
unprocessed parts of both parsers is the unprocessed parts the second
parser $q$ produces as left-over. The processed parts of both parsers
is just the pair of the outputs
-$(\textit{output}_1, \textit{output}_2)$. This behavious can be
+$(\textit{output}_1, \textit{output}_2)$. This behaviour can be
implemented in Scala as follows:
\begin{center}
@@ -393,7 +393,7 @@
the empty set, then \texttt{parse} will also produce the empty set.
Notice that we have now two output types for the sequence parser
combinator, because in general \textit{p} and \textit{q} might produce
-differetn things (for example first we recognise a number and then a
+different things (for example first we recognise a number and then a
string corresponding to an operator).
@@ -413,13 +413,13 @@
\end{tabular}
\end{center}
-\noindent In the first line we have a sucessful parse, because the
+\noindent In the first line we have a successful parse, because the
string started with \texttt{ab}, which is the prefix we are looking
for. But since the parsing combinator is constructed as sequence of
the two simple (atomic) parsers for \texttt{a} and \texttt{b}, the
result is a nested pair of the form \texttt{((a, b), cde)}. It is
-\emph{not} a simple pair \texttt{(ab, cde)} as one might errorneously
-expects. The parser returns the ampty set in the other examples,
+\emph{not} a simple pair \texttt{(ab, cde)} as one might erroneously
+expects. The parser returns the empty set in the other examples,
because they do not fit with what the parser is supposed to parse.
--- a/progs/comb1.scala Wed Oct 24 13:07:13 2018 +0100
+++ b/progs/comb1.scala Wed Oct 24 16:03:07 2018 +0100
@@ -79,6 +79,8 @@
(("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "a" || "b" || "")
+Pal.parse_all("abaaaba")
+
println("Palindrome: " + Pal.parse_all("abaaaba"))
// well-nested parenthesis parser
@@ -91,6 +93,7 @@
P.parse_all("()")
// arithmetic expressions
+
lazy val E: Parser[String, Int] =
(T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } ||
(T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } || T
@@ -99,12 +102,15 @@
lazy val F: Parser[String, Int] =
("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser
+
println(E.parse("4*2+3"))
-println(E.parse_all("4*2+3"))
+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"))
+
+
// no left-recursion allowed, otherwise will loop
lazy val EL: Parser[String, Int] =
((EL ~ "+" ~ EL) ==> { case ((x, y), z) => x + z} ||
--- a/progs/cw1.scala Wed Oct 24 13:07:13 2018 +0100
+++ b/progs/cw1.scala Wed Oct 24 16:03:07 2018 +0100
@@ -19,6 +19,14 @@
case class NOT(r: Rexp) extends Rexp // not
case class CFUN(f: Char => Boolean) extends Rexp // subsuming CHAR and RANGE
+def CHAR(c: Char) = CFUN(d => c == d)
+val ALL = CFUN(_ => true)
+def RANGE(cs: Set[Char]) = CFUN(d => cs.contains(d))
+
+def CHAR(c: Char) = CFUN(c == _)
+val ALL = CFUN(_ => true)
+def RANGE(cs: Set[Char]) = CFUN(cs.contains(_))
+
// nullable function: tests whether the regular
// expression can recognise the empty string
--- a/progs/nfa.scala Wed Oct 24 13:07:13 2018 +0100
+++ b/progs/nfa.scala Wed Oct 24 16:03:07 2018 +0100
@@ -7,7 +7,7 @@
// type abbreviation for partial functions
type :=>[A, B] = PartialFunction[A, B]
-// return an empty set when not defined
+// return an empty set, when parial function is not defined
def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] =
Try(f(x)) getOrElse Set[B]()
--- a/progs/re1.scala Wed Oct 24 13:07:13 2018 +0100
+++ b/progs/re1.scala Wed Oct 24 16:03:07 2018 +0100
@@ -10,7 +10,7 @@
// nullable function: tests whether a regular
// expression can recognise the empty string
-def nullable (r: Rexp) : Boolean = r match {
+def nullable(r: Rexp) : Boolean = r match {
case ZERO => false
case ONE => true
case CHAR(_) => false
@@ -40,7 +40,8 @@
}
// main matcher function
-def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
+def matches(r: Rexp, s: String) : Boolean =
+ nullable(ders(s.toList, r))
//examples from the homework
--- a/progs/thompson.scala Wed Oct 24 13:07:13 2018 +0100
+++ b/progs/thompson.scala Wed Oct 24 16:03:07 2018 +0100
@@ -162,7 +162,7 @@
-// while my thompson-enfa-subset-partial-function-chain
+// while my thompson->enfa->subset->partial-function-chain
// is probably not the most effcient way to obtain a fast DFA
// (the test below should be much faster with a more direct
// construction), in general the DFAs can be slow because of