# HG changeset patch # User Christian Urban # Date 1444981341 -3600 # Node ID 1e1b0fe6610751c17dca115106692bed97cd1c7a # Parent ccfce105e36b64197ad988c8b132da4842b003dd updated diff -r ccfce105e36b -r 1e1b0fe66107 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r ccfce105e36b -r 1e1b0fe66107 handouts/ho04.tex --- a/handouts/ho04.tex Fri Oct 09 14:48:06 2015 +0100 +++ b/handouts/ho04.tex Fri Oct 16 08:42:21 2015 +0100 @@ -90,7 +90,7 @@ \pcode{Empty}. {\small\lstinputlisting[language=Scala,numbers=none] -{../progs/app03.scala}} +{../progs/app01.scala}} {\small\lstinputlisting[language=Scala,numbers=none] diff -r ccfce105e36b -r 1e1b0fe66107 progs/token-bak.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/token-bak.scala Fri Oct 16 08:42:21 2015 +0100 @@ -0,0 +1,145 @@ +import scala.language.implicitConversions +import scala.language.reflectiveCalls +import scala.util._ +import scala.annotation.tailrec + +sealed abstract class Rexp + +case object NULL extends Rexp +case object EMPTY extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp + +def charlist2rexp(s : List[Char]) : Rexp = s match { + case Nil => EMPTY + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) + + +implicit def RexpOps(r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps(s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) +} + +def Range(s : List[Char]) : Rexp = s match { + case Nil => NULL + case c::Nil => CHAR(c) + case c::s => ALT(CHAR(c), Range(s)) +} +def RANGE(s: String) = Range(s.toList) + +def PLUS(r: Rexp) = SEQ(r, STAR(r)) + +val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") +val DIGIT = RANGE("0123456789") +val ID = SYM ~ (SYM | DIGIT).% +val NUM = PLUS(DIGIT) +val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" +val SEMI: Rexp = ";" +val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">" +val WHITESPACE = PLUS(RANGE(" \n")) +val RPAREN: Rexp = ")" +val LPAREN: Rexp = "(" +val BEGIN: Rexp = "{" +val END: Rexp = "}" + +//regular expressions ranked by position in the list +val regs: List[Rexp] = + List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE) + +def nullable (r: Rexp) : Boolean = r match { + case NULL => false + case EMPTY => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true +} + +def zeroable (r: Rexp) : Boolean = r match { + case NULL => true + case EMPTY => false + case CHAR(_) => false + case ALT(r1, r2) => zeroable(r1) && zeroable(r2) + case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) + case STAR(_) => false +} + +def der (c: Char, r: Rexp) : Rexp = r match { + case NULL => NULL + case EMPTY => NULL + case CHAR(d) => if (c == d) EMPTY else NULL + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r) => SEQ(der(c, r), STAR(r)) +} + + +// calculates derivatives until all of them are zeroable +@tailrec +def munch(s: List[Char], + pos: Int, + rs: List[Rexp], + last: Option[Int]): Option[Int] = rs match { + case Nil => last + case rs if (s.length <= pos) => last + case rs => { + val ders = rs.map(der(s(pos), _)) + val rs_nzero = ders.filterNot(zeroable(_)) + val rs_nulls = ders.filter(nullable(_)) + val new_last = if (rs_nulls != Nil) Some(pos) else last + munch(s, 1 + pos, rs_nzero, new_last) + } +} + +// iterates the munching function and prints +// out the component strings +@tailrec +def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, 0, rs, None) match { + case None if (s == "") => println("EOF") + case None => println(s"Lexing error: $s") + case Some(n) => { + val (head, tail) = s.splitAt(n + 1) + print(s"|${head.replaceAll("\n","RET")}|") + tokenize(tail, rs) + } +} + + +val test_prog = """ +start := XXX; +x := start; +y := start; +z := start; +while 0 < x do { + while 0 < y do { + while 0 < z do { + z := z - 1 + }; + z := start; + y := y - 1 + }; + y := start; + x := x - 1 +}; +write x; +write y; +write z +""" + +tokenize(test_prog, regs) diff -r ccfce105e36b -r 1e1b0fe66107 progs/token.scala --- a/progs/token.scala Fri Oct 09 14:48:06 2015 +0100 +++ b/progs/token.scala Fri Oct 16 08:42:21 2015 +0100 @@ -1,25 +1,33 @@ -import scala.language.implicitConversions +import scala.language.implicitConversions import scala.language.reflectiveCalls -import scala.util._ -import scala.annotation.tailrec +import scala.annotation.tailrec -sealed abstract class Rexp - +abstract class Rexp case object NULL extends Rexp case object EMPTY extends Rexp case class CHAR(c: Char) extends Rexp -case class ALT(r1: Rexp, r2: Rexp) extends Rexp -case class SEQ(r1: Rexp, r2: Rexp) extends Rexp -case class STAR(r: Rexp) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp +case class RECD(x: String, r: Rexp) extends Rexp -def charlist2rexp(s : List[Char]) : Rexp = s match { +abstract class Val +case object Void extends Val +case class Chr(c: Char) extends Val +case class Sequ(v1: Val, v2: Val) extends Val +case class Left(v: Val) extends Val +case class Right(v: Val) extends Val +case class Stars(vs: List[Val]) extends Val +case class Rec(x: String, v: Val) extends Val + +// some convenience for typing in regular expressions +def charlist2rexp(s : List[Char]): Rexp = s match { case Nil => EMPTY case c::Nil => CHAR(c) case c::s => SEQ(CHAR(c), charlist2rexp(s)) } implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) - implicit def RexpOps(r: Rexp) = new { def | (s: Rexp) = ALT(r, s) def % = STAR(r) @@ -32,34 +40,11 @@ def % = STAR(s) def ~ (r: Rexp) = SEQ(s, r) def ~ (r: String) = SEQ(s, r) + def $ (r: Rexp) = RECD(s, r) } -def Range(s : List[Char]) : Rexp = s match { - case Nil => NULL - case c::Nil => CHAR(c) - case c::s => ALT(CHAR(c), Range(s)) -} -def RANGE(s: String) = Range(s.toList) - -def PLUS(r: Rexp) = SEQ(r, STAR(r)) - -val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") -val DIGIT = RANGE("0123456789") -val ID = SYM ~ (SYM | DIGIT).% -val NUM = PLUS(DIGIT) -val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" -val SEMI: Rexp = ";" -val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">" -val WHITESPACE = PLUS(RANGE(" \n")) -val RPAREN: Rexp = ")" -val LPAREN: Rexp = "(" -val BEGIN: Rexp = "{" -val END: Rexp = "}" - -//regular expressions ranked by position in the list -val regs: List[Rexp] = - List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE) - +// nullable function: tests whether the regular +// expression can recognise the empty string def nullable (r: Rexp) : Boolean = r match { case NULL => false case EMPTY => true @@ -67,79 +52,224 @@ case ALT(r1, r2) => nullable(r1) || nullable(r2) case SEQ(r1, r2) => nullable(r1) && nullable(r2) case STAR(_) => true + case RECD(_, r1) => nullable(r1) } -def zeroable (r: Rexp) : Boolean = r match { - case NULL => true - case EMPTY => false - case CHAR(_) => false - case ALT(r1, r2) => zeroable(r1) && zeroable(r2) - case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) - case STAR(_) => false -} - +// derivative of a regular expression w.r.t. a character def der (c: Char, r: Rexp) : Rexp = r match { case NULL => NULL - case EMPTY => NULL + case EMPTY => NULL case CHAR(d) => if (c == d) EMPTY else NULL case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) case SEQ(r1, r2) => if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) else SEQ(der(c, r1), r2) case STAR(r) => SEQ(der(c, r), STAR(r)) + case RECD(_, r1) => der(c, r1) +} + +// derivative w.r.t. a string (iterates der) +def ders (s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, der(c, r)) +} + +// extracts a string from value +def flatten(v: Val) : String = v match { + case Void => "" + case Chr(c) => c.toString + case Left(v) => flatten(v) + case Right(v) => flatten(v) + case Sequ(v1, v2) => flatten(v1) + flatten(v2) + case Stars(vs) => vs.map(flatten).mkString + case Rec(_, v) => flatten(v) +} + +// extracts an environment from a value +def env(v: Val) : List[(String, String)] = v match { + case Void => Nil + case Chr(c) => Nil + case Left(v) => env(v) + case Right(v) => env(v) + case Sequ(v1, v2) => env(v1) ::: env(v2) + case Stars(vs) => vs.flatMap(env) + case Rec(x, v) => (x, flatten(v))::env(v) +} + +// injection part +def mkeps(r: Rexp) : Val = r match { + case EMPTY => Void + case ALT(r1, r2) => + if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) + case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) + case STAR(r) => Stars(Nil) + case RECD(x, r) => Rec(x, mkeps(r)) } -// calculates derivatives until all of them are zeroable -@tailrec -def munch(s: List[Char], - pos: Int, - rs: List[Rexp], - last: Option[Int]): Option[Int] = rs match { - case Nil => last - case rs if (s.length <= pos) => last - case rs => { - val ders = rs.map(der(s(pos), _)) - val rs_nzero = ders.filterNot(zeroable(_)) - val rs_nulls = ders.filter(nullable(_)) - val new_last = if (rs_nulls != Nil) Some(pos) else last - munch(s, 1 + pos, rs_nzero, new_last) +def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { + case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) + case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) + case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) + case (CHAR(d), Void) => Chr(c) + case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) +} + +// main lexing function (produces a value) +def lex(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") + case c::cs => inj(r, c, lex(der(c, r), cs)) +} + +def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) + +// some "rectification" functions for simplification +def F_ID(v: Val): Val = v +def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) +def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) +def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Right(v) => Right(f2(v)) + case Left(v) => Left(f1(v)) +} +def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) +} +def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v)) +def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void)) +def F_RECD(f: Val => Val) = (v:Val) => v match { + case Rec(x, v) => Rec(x, f(v)) +} +def F_ERROR(v: Val): Val = throw new Exception("error") + +// simplification of regular expressions returning also an +// rectification function; no simplification under STAR +def simp(r: Rexp): (Rexp, Val => Val) = r match { + case ALT(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (NULL, _) => (r2s, F_RIGHT(f2s)) + case (_, NULL) => (r1s, F_LEFT(f1s)) + case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) + else (ALT (r1s, r2s), F_ALT(f1s, f2s)) + } + } + case SEQ(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (NULL, _) => (NULL, F_ERROR) + case (_, NULL) => (NULL, F_ERROR) + case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s)) + case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s)) + case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) + } + } + case RECD(x, r1) => { + val (r1s, f1s) = simp(r1) + (RECD(x, r1s), F_RECD(f1s)) + } + case r => (r, F_ID) +} + +def lex_simp(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") + case c::cs => { + val (r_simp, f_simp) = simp(der(c, r)) + inj(r, c, f_simp(lex_simp(r_simp, cs))) } } -// iterates the munching function and prints -// out the component strings -@tailrec -def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, 0, rs, None) match { - case None if (s == "") => println("EOF") - case None => println(s"Lexing error: $s") - case Some(n) => { - val (head, tail) = s.splitAt(n + 1) - print(s"|${head.replaceAll("\n","RET")}|") - tokenize(tail, rs) - } +def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) + +lexing_simp(("a" + "ab") | ("b" + ""), "ab") + +// Lexing Rules for a Small While Language + +def PLUS(r: Rexp) = r ~ r.% +val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" +val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" +val ID = SYM ~ (SYM | DIGIT).% +val NUM = PLUS(DIGIT) +val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" +val SEMI: Rexp = ";" +val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" +val WHITESPACE = PLUS(" " | "\n" | "\t") +val RPAREN: Rexp = ")" +val LPAREN: Rexp = "(" +val BEGIN: Rexp = "{" +val END: Rexp = "}" +val STRING: Rexp = "\"" ~ SYM.% ~ "\"" + + +val WHILE_REGS = (("k" $ KEYWORD) | + ("i" $ ID) | + ("o" $ OP) | + ("n" $ NUM) | + ("s" $ SEMI) | + ("str" $ STRING) | + ("p" $ (LPAREN | RPAREN)) | + ("b" $ (BEGIN | END)) | + ("w" $ WHITESPACE)).% + +// Testing +//============ + +def time[T](code: => T) = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println((end - start)/1.0e9) + result +} + +val r1 = ("a" | "ab") ~ ("bcd" | "c") +println(lexing(r1, "abcd")) + +val r2 = ("" | "a") ~ ("ab" | "b") +println(lexing(r2, "ab")) + + +// Two Simple While Tests +//======================== +println("prog0 test") + +val prog0 = """read n""" +println(env(lexing_simp(WHILE_REGS, prog0))) + +println("prog1 test") + +val prog1 = """read n; write (n)""" +println(env(lexing_simp(WHILE_REGS, prog1))) + + +// Big Test +//========== + +val prog2 = """ +write "fib"; +read n; +minus1 := 0; +minus2 := 1; +while n > 0 do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1 +}; +write "result"; +write minus2 +""" + +println("Tokens") +println(env(lexing_simp(WHILE_REGS, prog2))) + +for (i <- 1 to 80) { + print(i.toString + ": ") + time(lexing_simp(WHILE_REGS, prog2 * i)) } -val test_prog = """ -start := XXX; -x := start; -y := start; -z := start; -while 0 < x do { - while 0 < y do { - while 0 < z do { - z := z - 1 - }; - z := start; - y := y - 1 - }; - y := start; - x := x - 1 -}; -write x; -write y; -write z -""" - -tokenize(test_prog, regs) diff -r ccfce105e36b -r 1e1b0fe66107 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r ccfce105e36b -r 1e1b0fe66107 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r ccfce105e36b -r 1e1b0fe66107 slides/slides04.tex --- a/slides/slides04.tex Fri Oct 09 14:48:06 2015 +0100 +++ b/slides/slides04.tex Fri Oct 16 08:42:21 2015 +0100 @@ -49,7 +49,9 @@ \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); -\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); +%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); +\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); + \end{tikzpicture}\\ \end{center} @@ -58,9 +60,8 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[t] -\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} +\frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}} \begin{tikzpicture} \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, @@ -85,10 +86,9 @@ \end{axis} \end{tikzpicture} -\end{frame}} +\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{DFA to Rexp} @@ -118,18 +118,16 @@ \end{tabular} \end{center} -\onslide<2->{ Arden's Lemma: \begin{center} If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} \end{center} -} + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ \begin{frame}[c] \frametitle{DFA Minimisation} @@ -145,65 +143,6 @@ \item All unmarked pairs can be merged. \end{enumerate} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\begin{center} -\begin{tikzpicture}[>=stealth',very thick,auto, - every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -\node[state,initial] (q_0) {$q_0$}; -\node[state] (q_1) [right=of q_0] {$q_1$}; -\node[state] (q_2) [below right=of q_0] {$q_2$}; -\node[state] (q_3) [right=of q_2] {$q_3$}; -\node[state, accepting] (q_4) [right=of q_1] {$q_4$}; -\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); -\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); -\path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); -\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); -\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); -\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); -\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); -\path[->] (q_2) edge [loop left] node {\alert{$b$}} (); -\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); -\end{tikzpicture} -\end{center} - -\mbox{}\\[-20mm]\mbox{} - -\begin{center} -\begin{tikzpicture}[scale=0.8,line width=0.8mm] -\draw (0,0) -- (4,0); -\draw (0,1) -- (4,1); -\draw (0,2) -- (3,2); -\draw (0,3) -- (2,3); -\draw (0,4) -- (1,4); - -\draw (0,0) -- (0, 4); -\draw (1,0) -- (1, 4); -\draw (2,0) -- (2, 3); -\draw (3,0) -- (3, 2); -\draw (4,0) -- (4, 1); - -\draw (0.5,-0.5) node {$q_0$}; -\draw (1.5,-0.5) node {$q_1$}; -\draw (2.5,-0.5) node {$q_2$}; -\draw (3.5,-0.5) node {$q_3$}; - -\draw (-0.5, 3.5) node {$q_1$}; -\draw (-0.5, 2.5) node {$q_2$}; -\draw (-0.5, 1.5) node {$q_3$}; -\draw (-0.5, 0.5) node {$q_4$}; - -\draw (0.5,0.5) node {\large$\star$}; -\draw (1.5,0.5) node {\large$\star$}; -\draw (2.5,0.5) node {\large$\star$}; -\draw (3.5,0.5) node {\large$\star$}; -\end{tikzpicture} -\end{center} - \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -288,56 +227,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Alternatives} -\mbox{}\\[-17mm]\mbox{} - -\begin{center} -\begin{tikzpicture}[>=stealth',very thick,auto, - every state/.style={minimum size=0pt, - inner sep=2pt,draw=blue!50,very thick,fill=blue!20}] -\only<1>{\node[state,initial] (q_0) {$q_0$};} -\only<2->{\node[state,accepting] (q_0) {$q_0$};} -\node[state] (q_1) [right=of q_0] {$q_1$}; -\node[state] (q_2) [below right=of q_0] {$q_2$}; -\node[state] (q_3) [right=of q_2] {$q_3$}; -\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};} -\only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};} -\only<1-2>{ -\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); -\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); -\path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); -\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); -\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); -\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); -\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); -\path[->] (q_2) edge [loop left] node {\alert{$b$}} (); -\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} -\only<3->{ -\path[<-] (q_0) edge node [above] {\alert{$a$}} (q_1); -\path[<-] (q_1) edge node [above] {\alert{$a$}} (q_4); -\path[<-] (q_4) edge [loop above] node {\alert{$a, b$}} (); -\path[<-] (q_3) edge node [right] {\alert{$a$}} (q_4); -\path[<-] (q_2) edge node [above] {\alert{$a$}} (q_3); -\path[<-] (q_1) edge node [right] {\alert{$b$}} (q_2); -\path[<-] (q_0) edge node [above] {\alert{$b$}} (q_2); -\path[<-] (q_2) edge [loop left] node {\alert{$b$}} (); -\path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);} -\end{tikzpicture} -\end{center} -\mbox{}\\[-18mm] - -\begin{itemize} -\item<2-> exchange initial / accepting states -\item<3-> reverse all edges -\item<4-> subset construction $\Rightarrow$ DFA -\item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA} -\end{itemize} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] \frametitle{Regular Languages} Two equivalent definitions:\bigskip @@ -382,13 +271,77 @@ \end{tikzpicture} \end{center}\bigskip\bigskip -\onslide<2>{But requires that the automaton is \alert{completed}!} +But requires that the automaton is \alert{completed}! \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] +\frametitle{The Goal of this Course} +\mbox{}\\[-26mm]\mbox{} + +\begin{center} + \begin{tikzpicture}[scale=1, + node/.style={ + rectangle,rounded corners=3mm, + very thick,draw=black!50, + minimum height=18mm, minimum width=20mm, + top color=white,bottom color=black!20}] + + \node at (3.05, 1.8) {\Large\bf Write A Compiler}; + + \node (0) at (-2.3,0) {}; + + \node (A) at (0,0) [node] {}; + \node [below right] at (A.north west) {lexer}; + + \node (B) at (3,0) [node] {}; + \node [below right=1mm] at (B.north west) + {\mbox{}\hspace{-1mm}parser}; + + \node (C) at (6,0) [node] {}; + \node [below right] at (C.north west) + {\mbox{}\hspace{-1mm}code gen}; + + \node (1) at (8.4,0) {}; + + \draw [->,line width=4mm] (0) -- (A); + \draw [->,line width=4mm] (A) -- (B); + \draw [->,line width=4mm] (B) -- (C); + \draw [->,line width=4mm] (C) -- (1); + \end{tikzpicture} + \end{center} + +Today a lexer. + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Survey: Thanks!} +\small + +\begin{itemize} +\item {\bf My Voice} ``lecturer speaks in a low voice and + is hard to hear him'' ``please use mic'' ``please use mic + \& lecture recording'' +\item {\bf Pace} ``faster pace'' ``a bit quick for me +personally'' +\item {\bf Recording} ``please use recording class'' +\item {\bf Module Name} ``misleading'' +\item {\bf Examples} ``more examples'' +\item {\bf Assessment} ``really appreciate extension of + first coursework'' +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Lexing} \mbox{\lstinputlisting[language=While]{../progs/fib.while}} @@ -405,29 +358,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{A Compiler} - -\begin{tikzpicture}[scale=1] - \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2); - \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); - \draw (4.4,1) node {Code Gen}; - \draw (0.6,1.7) node {\small Parser}; - \draw (-2.7,1.7) node {\small Lexer}; - - \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1); - \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1); - \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1); - - \draw (-4.6,1.7) node {\small string}; - \draw (-1.1,1.7) node {\small tokens}; - \draw ( 2.3,1.7) node {\small AST}; -\end{tikzpicture} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \tt @@ -518,6 +448,19 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +The same problem with\medskip + +\[ +\bl{(ab + a) \cdot (c + bc)} +\]\bigskip + +and the string $\bl{abc}$ + +\end{frame} + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{POSIX: Two Rules} @@ -616,6 +559,17 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\small + +{\small\lstinputlisting[language=Scala,numbers=none, +xleftmargin=-5mm] {../progs/app01.scala}} + +{\small\lstinputlisting[language=Scala,numbers=none, +xleftmargin=-5mm] {../progs/app02.scala}} + +\end{frame} + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Mkeps} @@ -659,6 +613,153 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{textblock}{10}(3,5) +\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] +\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} + +\only<2->{ +\begin{textblock}{6}(1,0.8) +\begin{bubble}[6cm] +\small +\begin{tabular}{ll} +\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ +\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} + +\only<2->{ +\begin{textblock}{6}(5,11.4) +\begin{bubble}[7.6cm] +\small +\begin{tabular}{ll} +\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ +\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ +\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ +\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ +\end{tabular} +\end{bubble} +\end{textblock}} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Flatten} + +Obtaining the string underlying a value: + +\begin{center} +\begin{tabular}{lcl} + \bl{$|Empty|$} & \bl{$\dn$} & \bl{$[]$}\\ + \bl{$|Char(c)|$} & \bl{$\dn$} & \bl{$[c]$}\\ + \bl{$|Left(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\ + \bl{$|Right(v)|$} & \bl{$\dn$} & \bl{$|v|$}\\ + \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\ + \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{textblock}{10}(3,5) +\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] +\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{textblock}{6}(1,0.8) +\begin{bubble}[6cm] +\small +\begin{tabular}{ll} +\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ +\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ +\end{tabular} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(1,11.4) +\begin{bubble}[7.6cm] +\small +\begin{tabular}{ll} +\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ +\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ +\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ +\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ +\end{tabular} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(12,11.4) +\begin{bubble}[2cm] +\small +\begin{tabular}{ll} +\bl{$|v_1|$}: & \bl{$abc$}\\ +\bl{$|v_2|$}: & \bl{$bc$}\\ +\bl{$|v_3|$}: & \bl{$c$}\\ +\bl{$|v_4|$}: & \bl{$[]$} +\end{tabular} +\end{bubble} +\end{textblock} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Lexing} @@ -719,6 +820,57 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Records} + +\begin{itemize} +\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause + +\item \bl{$nullable(x:r) \dn nullable(r)$} +\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$} +\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} +\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} +\end{itemize}\bigskip\bigskip\pause + +\small +for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{itemize} +\item Regular expression for email addresses + +\begin{center} +\begin{tabular}{l} +(name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ +\qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ +\qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$}) +\end{tabular} +\end{center} + +\bl{\[ +\texttt{christian.urban@kcl.ac.uk} +\]} + +\item result environment: + +\begin{center} +\begin{tabular}{l} +\bl{$[(name:\texttt{christian.urban}),$}\\ +\bl{$\phantom{[}(domain:\texttt{kcl}),$}\\ +\bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$} +\end{tabular} +\end{center} +\end{itemize} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -740,6 +892,8 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Simplification} @@ -775,6 +929,11 @@ \end{tikzpicture} \end{center} +\small +\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$} +$\mapsto$ +\bl{$\epsilon$} + \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -803,6 +962,94 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Rectification} + +\begin{center} +\begin{tabular}{l} +\bl{$simp(r)$}:\\ +\quad case \bl{$r = r_1 + r_2$}\\ +\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ +\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ +\qquad case \bl{$r_{1s} = \varnothing$}: + return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\ +\qquad case \bl{$r_{2s} = \varnothing$}: + return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ +\qquad case \bl{$r_{1s} = r_{2s}$}: + return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ +\qquad otherwise: + return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\ +\end{tabular} +\end{center} + +\small +\begin{center} +\begin{tabular}{l@{\hspace{1mm}}l} +\bl{$f_{alt}(f_1, f_2) \dn$}\\ +\qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}: + & return \bl{$Left(f_1(v'))$}\\ +\qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}: + & return \bl{$Right(f_2(v'))$}\\ +\end{tabular} +\end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\begin{frame}[c] + +{\footnotesize\lstinputlisting[language=Scala,numbers=none, +xleftmargin=-5mm] {../progs/app05.scala}} + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Rectification} + +\begin{center} +\begin{tabular}{@{\hspace{-3mm}}l} +\bl{$simp(r)$}:\ldots\\ +\quad case \bl{$r = r_1 \cdot r_2$}\\ +\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ +\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ +\qquad case \bl{$r_{1s} = \varnothing$}: + return \bl{$(\varnothing, f_{error})$}\\ +\qquad case \bl{$r_{2s} = \varnothing$}: + return \bl{$(\varnothing, f_{error})$}\\ +\qquad case \bl{$r_{1s} = \epsilon$}: +return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\ +\qquad case \bl{$r_{2s} = \epsilon$}: +return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\ +\qquad otherwise: + return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\ +\end{tabular} +\end{center} + +\small +\begin{center} +\begin{tabular}{l@{\hspace{1mm}}l} +\bl{$f_{seq}(f_1, f_2) \dn$}\\ +\qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}: + & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\ +\end{tabular} +\end{center} +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +\begin{frame}[c] + +{\footnotesize\lstinputlisting[language=Scala,numbers=none, +xleftmargin=-5mm] {../progs/app06.scala}} + +\end{frame} + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Lexing with Simplification} @@ -844,6 +1091,29 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\begin{center} +\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +$zeroable(\varnothing)$ & $\dn$ & $true$\\ +$zeroable(\epsilon)$ & $\dn$ & $f\!alse$\\ +$zeroable (c)$ & $\dn$ & $f\!alse$\\ +$zeroable (r_1 + r_2)$ & $\dn$ & $zeroable(r_1) \wedge zeroable(r_2)$ \\ +$zeroable (r_1 \cdot r_2)$ & $\dn$ & $zeroable(r_1) \vee zeroable(r_2)$ \\ +$zeroable (r^*)$ & $\dn$ & $f\!alse$\\ +\end{tabular} +\end{center} + +\begin{center} +$zeroable(r)$ if and only if $L(r) = \varnothing$ +\end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \end{document} %%% Local Variables: