# HG changeset patch # User Christian Urban # Date 1540393387 -3600 # Node ID 451a95e1bc25594a1478952964dffb39f83ec4b5 # Parent 6ee22f196884badf748a158f889315bd6bb9c8ef typos diff -r 6ee22f196884 -r 451a95e1bc25 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 6ee22f196884 -r 451a95e1bc25 handouts/ho06.tex --- 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. diff -r 6ee22f196884 -r 451a95e1bc25 progs/comb1.scala --- 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} || diff -r 6ee22f196884 -r 451a95e1bc25 progs/cw1.scala --- 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 diff -r 6ee22f196884 -r 451a95e1bc25 progs/nfa.scala --- 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]() diff -r 6ee22f196884 -r 451a95e1bc25 progs/re1.scala --- 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 diff -r 6ee22f196884 -r 451a95e1bc25 progs/thompson.scala --- 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