--- a/Spiral.scala Sat Apr 13 16:18:23 2019 +0100
+++ b/Spiral.scala Sun May 05 22:02:29 2019 +0100
@@ -441,8 +441,8 @@
def correctness_proof_convenient_path(){
for(i <- 1 to 10000)
{
- val s = rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3)
- val r = internalise(random_struct_gen(4))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7)
+ val s = "abab"//rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3)
+ val r = ("ab"| SEQ(ONE, "ab"))//internalise(random_struct_gen(4))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7)
for(j <- 0 to s.length - 1){
val ss = s.slice(0, j+ 1)
val nangao = ders_simp(r, ss.toList)
@@ -490,35 +490,77 @@
}
*/
def retrieve_experience(){
- val rg = ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b"))))
- val st = "abaab"
- val r_der_s = ders(st.toList, erase(rg))
- val unsimplified_vl = mkeps(r_der_s)
- val r_bder_s = bders( st.toList, rg)
- val s_r_bder_s = bsimp(r_bder_s)
- val bits1 = retrieve(r_bder_s, unsimplified_vl)
- println(r_bder_s)
- println(erase(r_bder_s))
- println(s_r_bder_s)
- println(erase(s_r_bder_s))
- println(code(unsimplified_vl))
- val bits2 = retrieve(s_r_bder_s, decode(erase(s_r_bder_s), code(unsimplified_vl)))
- if(bits1 == bits2){
- println("retrieve ar v = retrieve (bsimp ar) (decode erase(bsimp(ar)) code(v)) if |- v : r")
- println("Here v == mkeps r\\s and r == r\\s")
- println(r_der_s, unsimplified_vl)
- println(s_r_bder_s, erase(s_r_bder_s), code(unsimplified_vl))
+ for(i <- 1 to 100){
+ val rg = internalise(balanced_struct_gen(1))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b"))))
+ val st = "ab"//"abaab"
+ val r_der_s = ders(st.toList, erase(rg))
+ if(nullable(r_der_s)){
+ val unsimplified_vl = mkeps(r_der_s)
+ val r_bder_s = bders( st.toList, rg)
+ val s_r_bder_s = bsimp(r_bder_s)
+ val bits1 = retrieve(internalise(r_der_s), unsimplified_vl)
+ println("The property: ")
+ println("retrieve ar v = retrieve (bsimp ar) (decode erase(bsimp(ar)) code(v)) if |- v : r")
+ println("does not hold.")
+ println("Here v == mkeps r\\s and r == r\\s")
+ println("regular expression is")
+ println(rg)
+ println("string is")
+ println(st)
+ println("derivative without simplification is ")
+
+ println(r_bder_s)
+
+ println("after erase of this derivative")
+ println(erase(r_bder_s))
+ println("simplification of derivative (bsimp(ar))")
+ println(s_r_bder_s)
+ println("after erase of simplified derivative (erase(bsimp(ar))")
+ println(erase(s_r_bder_s))
+ println("decode says the above regex and the below bits(code(v)) are not decodable")
+ println(unsimplified_vl)
+ println(code(unsimplified_vl))
+ println(bits1)
+ val bits2 = retrieve(s_r_bder_s, decode(erase(s_r_bder_s), code(unsimplified_vl)))
+ if(bits1 == bits2){
+ println("retrieve ar v = retrieve (bsimp ar) (decode erase(bsimp(ar)) code(v)) if |- v : r")
+ println("Here v == mkeps r\\s and r == r\\s")
+ println(r_der_s, unsimplified_vl)
+ println(s_r_bder_s, erase(s_r_bder_s), code(unsimplified_vl))
+ }
+ }
+ }
}
- }
def radical_correctness(){
enum(3, "abc").map(tests_blexer_simp(strs(3, "abc"))).toSet
random_pool(1, 5).map(tests_blexer_simp(strs(5, "abc"))).toSet
}
+ def christian_def(){
+ val r = ALTS(List(SEQ(ZERO,CHAR('b')), ONE))
+ val v = Right(Empty)
+ val a = internalise(r)
+ val as = bsimp(a)
+ println(s"Testing ${r} and ${v}")
+ println(s"internalise(r) = ${a}")
+ val bs1 = retrieve(a, v)
+ println(bs1)
+ println(s"as = ${as}")
+ //val bs2 = retrieve(as, decode(erase(as), bs1))
+ val bs3 = retrieve(as, decode(erase(as), bs1.tail))
+ println(decode(erase(as), bs1.tail))
+ println(bs3)
+ }
+ def essence_posix(){
+ val s = "abab"//rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3)
+ val r = STAR("ab"| SEQ(ONE, "ab"))//internalise(random_struct_gen(4))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7)
+ ders(s.toList, r)
+ }
def main(args: Array[String]) {
//check_all()
//radical_correctness()
//correctness_proof_convenient_path()
- retrieve_experience()
+ //retrieve_experience()
+ christian_def()
}
}
--- a/lex_blex_Frankensteined.scala Sat Apr 13 16:18:23 2019 +0100
+++ b/lex_blex_Frankensteined.scala Sun May 05 22:02:29 2019 +0100
@@ -383,7 +383,42 @@
case AZERO :: rs1 => flats(rs1)
case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)
case r1 :: rs2 => r1 :: flats(rs2)
+ }
+ def remove(v: Val): Val = v match{
+ case Right(v1) => v1
+ case Left(v1) => v1
+ case _ => throw new Exception("Not removable")
+ }
+ def augment(v: Val, i: Int): Val = if(i > 1) augment(Right(v), i - 1) else Right(v)
+//an overly complex version
+/*
+ if(rel_dist >0){//the regex we are dealing with is not what v points at
+ rs match{
+ case Nil => throw new Exception("Trying to simplify a non-existent value")
+ case AZERO :: rs1 => flats_vsimp(rs1, rel_dist - 1, remove(v))
+ case AALTS(bs, rs1) :: rs2 => flats_vsimp(rs2, rel_dist - 1, augment(v, rs1.length - 1))//rs1 is guaranteed to have a len geq 2
+ case r1 :: rs2 => flats_vsimp(rs2, rel_dist - 1, v)
+ }
}
+ else if(rel_dist == 0){//we are dealing with regex v is pointing to -- "v->r itself"
+ rs match{//r1 cannot be zero
+ AALTS(bs, rs1) :: rs2 => flats_vsimp( )
+ AZERO::rs2 => throw new Exception("Value corresponds to zero")
+ r1::rs2 => flats_vsimp(rs2, rel_dist - 1, v)
+ }
+
+ }
+ else{
+
+ }
+ */
+ def flats_vsimp(rs: List[ARexp], position: Int): Int = (rs, position) match {
+ case (_, 0) => 0
+ case (Nil, _) => 0
+ case (ZERO :: rs1, _) => flats_vsimp(rs1, position - 1) - 1
+ case (AALTS(bs, rs1) :: rs2, _) => rs1.length - 1 + flats_vsimp(rs2, position - 1)
+ case (r1 :: rs2, _) => flats_vsimp(rs2, position - 1)
+ }
def rflats(rs: List[Rexp]): List[Rexp] = rs match {
case Nil => Nil
case ZERO :: rs1 => rflats(rs1)
@@ -413,6 +448,69 @@
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r))
case r => r
}
+ def find_pos(v: Val, rs: List[Rexp]): Int = (rs, v) match{
+ case (Right(v), r::Nil) => 1
+ case (Left(v), r::rs) => 0
+ case (Right(v), r::rs) => find_pos(v, rs) + 1
+ case (v, _) => 0
+ }
+ def remove(v: Val, rs: List[Rexp]) : Val = (rs,v) match {//remove the outmost layer of ALTS's Left and Right
+ case (Right(v), r::Nil) => v
+ case (Left(v), r::rs) => v
+ case (Right(v), r::rs) => remove(v, rs)
+ }
+ def simple_end(v: Value): Boolean = v match {
+ case Left(v) => return false
+ case Right(v) => return simple_end(v)
+ case v => return true
+ }
+ def isend(v: Val, rs: List[Rexp], position: Int): Boolean = {
+ val rsbh = rs.slice(position, rs.length)
+ val out_end = if(flats(rsbh) == Nil) true else false
+ val inner_end = simple_end(v)
+ inner_end && out_end
+ }
+ def get_coat(v: Val, rs: List[Rexp], vs: Val): Val = (rs, v) match{//the dual operation of remove(so-called by myself)
+ case (Right(v), r::Nil) => Right(vs)
+ case (Left(v), r::rs) => Left(vs)
+ case (Right(v), r::rs) => Right(get_coat(v, rs, vs))
+ }
+ def coat(v: Val, i: Int) : Val = i match {
+ case 0 => v
+ case i => coat(Right(v), i - 1)
+ }
+ def bsimp2(r: ARexp, v: Val): (ARexp, Val => Val) = (r,v) match{
+ case (ASEQ(bs1, r1, r2), v) => (bsimp2(r1), bsimp2(r2)) match {
+ case ((AZERO, _), (_, _) )=> (AZERO, undefined)
+ case ((_, _), (AZERO, _)) => (AZERO, undefined)
+ case ((AONE(bs2), f1) , (r2s, f2)) => (fuse(bs1 ++ bs2, r2s), lambda v => v match { case Sequ(_, v) => f2(v) } )
+ case ((r1s, f1), (r2s, f2)) => (ASEQ(bs1, r1s, r2s), lambda v => v match {case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))}
+ }
+ case AALTS(bs1, rs) => {
+ val init_ind = find_pos(v, rs)
+ val vs = bsimp2(rs[init_ind], remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i]
+ val rs_simp = rs.map(bsimp)
+ val vs_kernel = rs_simp[init_ind] match {
+ case AALTS(bs2, rs2) => remove(vs, rs_simp[init_ind])//remove the secondary layer of left and right
+ case r => vs
+ }
+ val vs_for_coating = if(isend(vs, rs_simp, init_ind)) vs_kernel else Left(vs_kernel)
+
+ val r_s = rs_simp[init_ind]
+ val shift = flats_vsimp(vs, rs_simp, init_ind) + find_pos(vs, rs_simp[init_ind])
+ val vf = coat(vs_for_coating, shift + init_ind)
+
+ val flat_res = flats(rs_simp)//flats2 returns a list of regex and a single v
+ val dist_res = distinctBy(flat_res, erase)
+ dist_res match {
+ case Nil => AZERO
+ case s :: Nil => fuse(bs1, s)
+ case rs => AALTS(bs1, rs)
+ }
+ }
+ //case ASTAR(bs, r) => ASTAR(bs, bsimp(r))
+ case r => r
+ }
def super_bsimp(r: ARexp): ARexp = r match {
case ASEQ(bs1, r1, r2) => (super_bsimp(r1), super_bsimp(r2)) match {
case (AZERO, _) => AZERO
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slides01.tex Sun May 05 22:02:29 2019 +0100
@@ -0,0 +1,914 @@
+\documentclass[dvipsnames,14pt,t,xelatex]{beamer}
+\usepackage{./slides}
+\usepackage{./graph}
+\usepackage{./langs}
+\usepackage{./data}
+
+\hfuzz=220pt
+
+\lstset{language=Scala,
+ style=mystyle,
+ numbersep=0pt,
+ numbers=none,
+ xleftmargin=0mm}
+
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}
+
+% beamer stuff
+\renewcommand{\slidecaption}{CFL 01, King's College London}
+
+
+\begin{filecontents}{re-python2.data}
+1 0.033
+5 0.036
+10 0.034
+15 0.036
+18 0.059
+19 0.084
+20 0.141
+21 0.248
+22 0.485
+23 0.878
+24 1.71
+25 3.40
+26 7.08
+27 14.12
+28 26.69
+\end{filecontents}
+
+\begin{filecontents}{re-java.data}
+5 0.00298
+10 0.00418
+15 0.00996
+16 0.01710
+17 0.03492
+18 0.03303
+19 0.05084
+20 0.10177
+21 0.19960
+22 0.41159
+23 0.82234
+24 1.70251
+25 3.36112
+26 6.63998
+27 13.35120
+28 29.81185
+\end{filecontents}
+
+\begin{filecontents}{re-java9.data}
+1000 0.01410
+2000 0.04882
+3000 0.10609
+4000 0.17456
+5000 0.27530
+6000 0.41116
+7000 0.53741
+8000 0.70261
+9000 0.93981
+10000 0.97419
+11000 1.28697
+12000 1.51387
+14000 2.07079
+16000 2.69846
+20000 4.41823
+24000 6.46077
+26000 7.64373
+30000 9.99446
+34000 12.966885
+38000 16.281621
+42000 19.180228
+46000 21.984721
+50000 26.950203
+60000 43.0327746
+\end{filecontents}
+
+
+
+\begin{document}
+
+
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{%
+ \begin{tabular}{@ {}c@ {}}
+ \\[-3mm]
+ \LARGE Compilers and \\[-1mm]
+ \LARGE Formal Languages (1)\\[-3mm]
+ \end{tabular}}
+
+ \begin{center}
+ %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}
+ %\includegraphics[scale=0.31]{pics/ante2.jpg}\\
+ %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
+ \end{center}
+
+ \normalsize
+ \begin{center}
+ \begin{tabular}{ll}
+ Email: & christian.urban at kcl.ac.uk\\
+ Office: & N\liningnums{7.07} (North Wing, Bush House)\\
+ Slides: & KEATS
+ \end{tabular}
+ \end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Why Study Compilers?}
+
+John Regehr {\small(Univ.~Utah, LLVM compiler hacker)}\smallskip\\
+
+\begin{bubble}[10.5cm]
+ \bf ``\ldots{}It’s effectively a perpetual
+ employment act for solid compiler hackers.''
+\end{bubble}
+
+\onslide<1->{
+\only<2>{
+\begin{itemize}
+\item {\bf Hardware is getting weirder
+ rather than getting clocked faster}
+
+\begin{itemize}
+\item Almost all processors are
+ multicores nowadays and it looks like there is increasing asymmetry in
+ resources across cores. Processors come with vector units, crypto
+ accelerators etc. We have DSPs, GPUs,
+ ARM big.little, and Xeon Phi. This is only scratching the
+ surface.
+\end{itemize}
+\end{itemize}}
+\only<3>{
+\begin{itemize}
+\item {\bf We’re getting tired of low-level languages and
+ their associated security disasters}
+
+\begin{itemize}
+\item
+ We want to write new code, to
+ whatever extent possible, in safer, higher-level
+ languages. Compilers are caught right in the middle of these
+ opposing trends: one of their main jobs is to help bridge the large
+ and growing gap between increasingly high-level languages and
+ increasingly wacky platforms.
+\end{itemize}
+\end{itemize}}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Why Bother?}
+
+\begin{columns}[t]
+\begin{column}{.5\textwidth}
+Ruby, Python, Java 8\medskip\\
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4cm,
+ legend entries={Python,Ruby},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
+\end{axis}
+\end{tikzpicture}
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4cm,
+ legend entries={Python, Java 8},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+
+\end{column}
+\begin{column}{.5\textwidth}
+Us (after next lecture)\medskip\\
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.07,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5000,...,10000},
+ xmax=11000,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4cm]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
+\begin{tikzpicture}\footnotesize
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.07,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4cm]
+\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+\end{axis}
+\end{tikzpicture}
+\end{column}
+\end{columns}\bigskip
+
+\small\centering
+matching \texttt{[a?]\{n\}[a]\{n\}} and \texttt{(a*)*b}
+against $\underbrace{\texttt{a}...\texttt{a}}_n$
+\end{frame}
+
+\begin{frame}
+\begin{column}{.5\textwidth}
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ y label style={at={(0.06,0.5)}},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=45,
+ ytick={0,10,...,40},
+ scaled ticks=false,
+ axis lines=left,
+ width=6cm,
+ height=4.5cm,
+ legend entries={Python, Java 8},
+ legend pos=north west]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ y label style={at={(0.06,0.5)}},
+ %enlargelimits=false,
+ %xtick={0,5000,...,30000},
+ xmax=65000,
+ ymax=45,
+ ytick={0,10,...,40},
+ scaled ticks=false,
+ axis lines=left,
+ width=6cm,
+ height=4.5cm,
+ legend entries={Java 9},
+ legend pos=north west]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
+\end{axis}
+\end{tikzpicture}
+\end{column}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Evil Regular Expressions}
+
+\begin{itemize}
+\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\medskip
+\item Evil regular expressions\medskip
+\begin{itemize}
+\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
+\item \bl{$(a^*)^*\cdot b$}
+\item \bl{$([a$\,-\,$z]^+)^*$}
+\item \bl{$(a + a \cdot a)^*$}
+\item \bl{$(a + a^?)^*$}
+\end{itemize}
+
+\item sometimes also called \alert{catastrophic backtracking}
+\item this is a problem for \alert{N}etwork \alert{I}ntrusion
+ \alert{D}etection systems, StackExchange, Atom editor
+\item \url{https://vimeo.com/112065252}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Goal of this Module}
+
+\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 [above=5mm of 0]
+ {\makebox[0mm]{\footnotesize
+ \begin{tabular}{@{}l@{}}input\\[-1mm]program\end{tabular}}};
+
+ \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) {};
+ \node [above=5mm of 1]
+ {\makebox[0mm]{\footnotesize
+ \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};
+
+ \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}
+
+\only<2,3,4>{
+\begin{textblock}{1}(1,2.1)
+\begin{bubble}[9.8cm]
+\normalsize
+lexer input: a string\smallskip\\
+\hspace{5mm}\code{"read(n);"}\medskip\\
+lexer output: a sequence of tokens\smallskip\\
+\hspace{5mm}\code{key(read) lpar id(n) rpar semi}
+\end{bubble}
+\end{textblock}}
+
+\only<3,4>{
+\begin{textblock}{1}(6,7.8)
+\begin{tabular}{c}
+\includegraphics[scale=0.2]{rosetta.jpg}\\[-2mm]
+\footnotesize lexing $\Rightarrow$ recognising words (Stone of Rosetta)
+\end{tabular}
+\end{textblock}}
+
+\only<4>{
+\begin{textblock}{1}(0.5,12)\small
+\begin{tabular}{l@{}c@{}l}
+ \pcode{if} & $\;\Rightarrow\;$ & keyword\\
+ \pcode{iffoo} & $\;\Rightarrow\;$ & identifier\\
+\end{tabular}
+\end{textblock}}
+
+\only<5>{
+\begin{textblock}{1}(1,1.5)
+\begin{bubble}[8.5cm]
+\normalsize
+parser input: a sequence of tokens\smallskip\\
+
+{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\
+
+parser output: an abstract syntax tree\smallskip\\
+\footnotesize
+\hspace{2cm}\begin{tikzpicture}
+ \node {\code{read}}
+ child {node {\code{lpar}}}
+ child {node {\code{n}}}
+ child {node {\code{rpar}}};
+\end{tikzpicture}
+\end{bubble}
+\end{textblock}}
+
+\only<6,7>{
+\begin{textblock}{1}(1,1.5)
+\begin{bubble}[4cm]
+\normalsize
+code generator:\smallskip\\
+\hspace{5mm}\code{istore 2}\\
+\hspace{5mm}\code{iload 2}\\
+\hspace{5mm}\code{ldc 10}\\
+\hspace{5mm}\code{isub}\\
+\hspace{5mm}\code{ifeq Label2}\\
+\hspace{5mm}\code{iload 2}\\
+\hspace{5mm}\code{...}\\
+\end{bubble}
+\end{textblock}}
+
+\only<7>{
+\begin{textblock}{6}(8.4,7)
+\begin{bubble}[5cm]
+\mbox{\begin{tikzpicture}[scale=0.58,rounded corners=0mm]
+\begin{axis}[axis x line=bottom, axis y line=left, ylabel=secs,
+ xlabel=n,
+ enlargelimits=0.05,
+ ybar interval=0.7, legend style=small]
+\addplot file {interpreted2.data};
+\addplot file {compiled2.data};
+%\legend{interpreted, compiled}
+\end{axis}
+\end{tikzpicture}}
+\end{bubble}
+\end{textblock}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Acad.~Subject is Mature}
+
+\begin{itemize}
+\item Turing Machines, 1936
+\item Regular Expressions, 1956\\
+\item The first compiler for COBOL, 1957\\ (Grace Hopper)
+\item But surprisingly research papers are still published nowadays\\
+\item ``Parsing: The Solved Problem That Isn't''
+\end{itemize}
+
+\begin{flushright}
+\includegraphics[scale=0.3]{hopper.jpg}\\
+\footnotesize\textcolor{gray}{Grace Hopper}
+\end{flushright}
+
+
+\begin{flushright}
+\mbox{}\\[-6mm]
+{\footnotesize\textcolor{gray}{(she made it to David Letterman's Tonight Show,\\[-2mm]
+ \url{http://www.youtube.com/watch?v=aZOxtURhfEU})}}
+\end{flushright}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lectures 1 - 5}
+
+transforming strings into structured data\\[10mm]
+
+{\LARGE\bf Lexing} {\hfill{}based on regular expressions}\medskip\\
+\hspace{5mm}(recognising ``words'')\\[6mm]
+
+{\LARGE\bf Parsing}\medskip\\
+\hspace{5mm}(recognising ``sentences'')
+
+\begin{textblock}{1}(10,9.1)
+\begin{tabular}{c}
+\includegraphics[scale=0.1]{rosetta.jpg}\\[-2mm]
+\footnotesize Stone of Rosetta
+\end{tabular}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Familiar Regular Expr.}
+\small
+\begin{center}
+\texttt{[a-z0-9\_$\backslash{}$.-]+ @ [a-z0-9$\backslash{}$.-]+ . [a-z$\backslash{}$.]\{2,6\}}
+\end{center}\smallskip
+
+\begin{center}
+\begin{tabular}{@{}lp{8.5cm}@{}}
+\pcode{re*} & matches 0 or more times\\
+\pcode{re+} & matches 1 or more times\\
+\pcode{re?} & matches 0 or 1 times\\
+\pcode{re\{n\}} & matches exactly \pcode{n} number of times\\
+\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} times\\
+\pcode{[...]} & matches any single character inside the brackets\\
+\pcode{[^...]} & matches any single character not inside the
+brackets\\
+\pcode{a-z A-Z} & character ranges\\
+\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\
+\pcode{.} & matches every character except newline\\
+\pcode{(re)} & groups regular expressions and remembers
+the matched text
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Today}
+
+\begin{itemize}
+\item While the ultimate goal is to implement a small compiler for the JVM
+ \ldots\bigskip
+\end{itemize}
+
+Let's start with:
+
+\begin{itemize}
+\item a web-crawler
+\item an email harvester
+%\item \textcolor{gray}{(a web-scraper)}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{A Web-Crawler}
+
+\mbox{}\\[10mm]
+
+\begin{enumerate}
+\item given an URL, read the corresponding webpage
+\item extract all links from it
+\item call the web-crawler again for all these links
+\end{enumerate}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{A Web-Crawler}
+
+\mbox{}\\[10mm]
+
+
+\begin{enumerate}
+\item given an URL, read the corresponding webpage
+\item if not possible print, out a problem
+\item if possible, extract all links from it
+\item call the web-crawler again for all these links
+\end{enumerate}\bigskip\pause
+
+\small (we need a bound for the number of recursive calls)
+
+\small (the purpose is to check all links on my own webpage)
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{1}(2,5)
+\begin{tabular}{c}
+\includegraphics[scale=0.15]{servers.png}\\[-2mm]
+\small Server
+\end{tabular}
+\end{textblock}
+
+\begin{textblock}{1}(5.6,4)
+ \begin{tikzpicture}[scale=1.1]
+ \draw[white] (0,1) node (X) {};
+ \draw[white] (2,1) node (Y) {};
+ \draw[white] (0,0) node (X1) {};
+ \draw[white] (2,0) node (Y1) {};
+ \draw[white] (0,-1) node (X2) {};
+ \draw[white] (2,-1) node (Y2) {};
+ \draw[red, <-, line width = 2mm] (X) -- (Y);
+ \node [inner sep=5pt,label=above:\textcolor{black}{GET request}] at ($ (X)!.5!(Y) $) {};
+ \draw[red, ->, line width = 2mm] (X1) -- (Y1);
+ \node [inner sep=5pt,label=above:\textcolor{black}{webpage}] at ($ (X1)!.5!(Y1) $) {};
+ \draw[red, <-, line width = 2mm] (X2) -- (Y2);
+ \node [inner sep=7pt,label=above:\textcolor{black}{POST data}] at ($ (X2)!.5!(Y2) $) {};
+ \end{tikzpicture}
+\end{textblock}
+
+
+\begin{textblock}{1}(9,5.5)
+\begin{tabular}{c}
+\includegraphics[scale=0.15]{laptop.png}\\[-2mm]
+\small Browser
+\end{tabular}
+\end{textblock}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{A Regular Expression}
+
+\begin{itemize}
+\item \ldots{} is a pattern or template for specifying strings
+\end{itemize}\bigskip
+
+\begin{center}
+\only<1>{\scode{"https?://[^"]*"}}%
+\only<2>{\scode{""""https?://[^"]*"""".r}}
+\end{center}\bigskip\bigskip
+
+matches for example\smallskip\\
+\hspace{2mm}\code{"http://www.foobar.com"}\\
+\hspace{2mm}\code{"https://www.tls.org"}\smallskip\\
+
+but not\smallskip\\
+\hspace{2mm}\code{"http://www."foo"bar.com"}\\
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Finding Operations in Scala}
+
+{\bf\code{rexp.findAllIn(string)}}\medskip
+
+returns a list of all (sub)strings that match the
+regular expression
+\bigskip\bigskip
+
+
+{\bf\code{rexp.findFirstIn(string)}}\medskip
+
+returns either
+
+\begin{itemize}
+\item \code{None} if no (sub)string matches or
+\item \code{Some(s)} with the first (sub)string
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Regular Expressions}
+
+Their inductive definition:
+
+
+\begin{textblock}{6}(2,7.5)
+ \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
+ \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\
+ & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\
+ & \bl{$\mid$} & \bl{$c$} & character\\
+ & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\
+ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
+ & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
+ \end{tabular}
+ \end{textblock}
+
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[t]
+%\frametitle{Regular Expressions}
+%
+%\small
+%In Scala:\bigskip
+%
+%\footnotesize
+%\lstinputlisting{../progs/app51.scala}
+%
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Strings}
+
+\ldots are lists of characters. For example \code{"hello"}
+
+\begin{center}
+\bl{$[h, e, l, l, o]$} or just \bl{$hello$}
+\end{center}
+
+the empty string: \bl{$[]$} or \bl{\pcode{""}}\bigskip\\
+
+the concatenation of two strings:
+
+\begin{center}
+\bl{$s_1 \,@\, s_2$}
+\end{center}
+
+\bl{\textit{foo $@$ bar = foobar}, \textit{baz $@\, []$ = baz}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Languages, Strings}
+
+\begin{itemize}
+\item \alert{\bf Strings} are lists of characters, for example
+\begin{center}
+\bl{$[]$},\;\bl{$abc$} \hspace{2cm}(Pattern match: \bl{$c\!::\!s$})
+\end{center}\bigskip
+
+
+\item A \alert{\bf language} is a set of strings, for example\medskip
+\begin{center}
+\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
+\end{center}\bigskip
+
+\item \alert{\bf Concatenation} of strings and languages
+
+\begin{center}
+\begin{tabular}{rcl}
+\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
+\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+\end{tabular}
+\end{center}
+
+%\item The \alert{\bf meaning} of a regular expression is a set of
+% strings, or language.
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm]
+ Regular Expression\end{tabular}}
+
+\begin{textblock}{15}(1,4)
+ \begin{tabular}{rcl}
+ \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\
+ \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
+ \bl{$L(r^*)$} & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{0 \le n} L(r)^n$}}\\
+ \end{tabular}\bigskip
+
+\onslide<2->{
+\hspace{5mm}\bl{$L(r)^0 \;\dn\; \{[]\}$}\\
+\bl{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\
+\small\hspace{5cm}\textcolor{gray}{$\{ s_1 @ s_2 \;|\; s_1\in L(r) \wedge s_2 \in L(r)^n \}$}}
+}
+ \end{textblock}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Meaning of Matching}
+
+\begin{bubble}[10cm]
+\large\bf
+A regular expression \bl{$r$} matches a string~\bl{$s$}
+provided
+
+\begin{center}
+\bl{$s \in L(r)$}\\
+\end{center}
+\end{bubble}\bigskip\bigskip
+
+\ldots and the point of the next lecture is
+to decide this problem as fast as possible (unlike Python,
+Ruby, Java)
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Written Exam}
+
+\begin{itemize}
+\item Accounts for 80\%.\bigskip
+
+\item The question ``\textit{Is this relevant for
+ the exam?}'' is very demotivating for the lecturer!\bigskip\\
+
+\item Deal: Whatever is in the homework (and is not marked
+ ``\textit{optional}'') is relevant for the exam.\bigskip
+
+\item Each lecture has also a handout. There are also handouts about
+notation and Scala.
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Coursework}
+
+\begin{itemize}
+\item Accounts for 20\%. Two strands. Choose \alert{\bf one}!\bigskip
+\end{itemize}
+
+\begin{columns}[t]
+\begin{column}{.5\textwidth}
+\underline{\bf Strand 1}\medskip
+\begin{itemize}
+\item four programming tasks:
+\begin{itemize}
+\item matcher (4\%, 12.10.)
+\item lexer (5\%, 02.11.)
+\item parser (5\%, 23.11.)
+\item compiler (6\%, 14.12.)
+\end{itemize}
+\item in any lang.~you like,\\ but I want to see the code
+\end{itemize}
+\end{column}
+
+\hspace{-45pt}\vrule{}\hspace{10pt}
+\begin{column}{.5\textwidth}
+\underline{\bf Strand 2}\smallskip\begin{itemize}
+\item one task: prove the correctness of a regular expression matcher in
+the \underline{Isabelle} theorem prover
+\item 20\%, submission on~14.12.\hspace{-5mm}\mbox{}
+\end{itemize}
+\end{column}
+\end{columns}\medskip
+
+\small
+\begin{itemize}
+\item Solving more than one strand will {\bf not} give you more
+marks.
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lecture Capture}
+
+\begin{itemize}
+\item Hope it works\ldots\pause actually no, it does not!\medskip\pause
+\item It is important to use lecture capture wisely\\ (it is only the ``baseline''):
+\begin{itemize}
+\item Lecture recordings are a study and revision aid.
+\item Statistically, there is a clear and direct link between attendance and
+ attainment: Students who do not attend lectures, do less well in exams.
+\end{itemize}
+
+\item Attending a lecture is more than watching it online -- if you do not
+attend, you miss out!
+
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}}
+
+\mbox{}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
+