# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1353740931 0
# Node ID 373cf55a3ca58718dfe68831042ce09681b0ac27
# Parent  898c25a4e39965fb51bc8b8a1ecda51aee781097
tuned

diff -r 898c25a4e399 -r 373cf55a3ca5 compile.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/compile.scala	Sat Nov 24 07:08:51 2012 +0000
@@ -0,0 +1,253 @@
+// A parser and evaluator for teh while language
+// 
+//:load matcher.scala
+//:load parser3.scala
+
+// some regular expressions
+val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")
+val DIGIT = RANGE("0123456789")
+val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) 
+val NUM = PLUS(DIGIT)
+val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") 
+val SEMI: Rexp = ";"
+val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!", "<", ">")
+val WHITESPACE = PLUS(RANGE(" \n"))
+val RPAREN: Rexp = ")"
+val LPAREN: Rexp = "("
+val BEGIN: Rexp = "{"
+val END: Rexp = "}"
+val COMMENT = SEQS("/*", NOT(SEQS(STAR(ALLC), "*/", STAR(ALLC))), "*/")
+
+// tokens for classifying the strings that have been recognised
+abstract class Token
+case object T_WHITESPACE extends Token
+case object T_COMMENT extends Token
+case object T_SEMI extends Token
+case object T_LPAREN extends Token
+case object T_RPAREN extends Token
+case object T_BEGIN extends Token
+case object T_END extends Token
+case class T_ID(s: String) extends Token
+case class T_OP(s: String) extends Token
+case class T_NUM(s: String) extends Token
+case class T_KWD(s: String) extends Token
+
+val lexing_rules: List[Rule[Token]] = 
+  List((KEYWORD, (s) => T_KWD(s.mkString)),
+       (ID, (s) => T_ID(s.mkString)),
+       (OP, (s) => T_OP(s.mkString)),
+       (NUM, (s) => T_NUM(s.mkString)),
+       (SEMI, (s) => T_SEMI),
+       (LPAREN, (s) => T_LPAREN),
+       (RPAREN, (s) => T_RPAREN),
+       (BEGIN, (s) => T_BEGIN),
+       (END, (s) => T_END),
+       (WHITESPACE, (s) => T_WHITESPACE),
+       (COMMENT, (s) => T_COMMENT))
+
+// the tokenizer
+val Tok = Tokenizer(lexing_rules, List(T_WHITESPACE, T_COMMENT))
+
+// the abstract syntax trees
+abstract class Stmt
+abstract class AExp
+abstract class BExp 
+type Block = List[Stmt]
+case object Skip extends Stmt
+case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
+case class While(b: BExp, bl: Block) extends Stmt
+case class Assign(s: String, a: AExp) extends Stmt
+case class Write(s: String) extends Stmt
+
+case class Var(s: String) extends AExp
+case class Num(i: Int) extends AExp
+case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
+
+case object True extends BExp
+case object False extends BExp
+case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
+
+// atomic parsers
+case class TokParser(tok: Token) extends Parser[List[Token], Token] {
+  def parse(ts: List[Token]) = ts match {
+    case t::ts if (t == tok) => Set((t, ts)) 
+    case _ => Set ()
+  }
+}
+implicit def token2tparser(t: Token) = TokParser(t)
+
+case object NumParser extends Parser[List[Token], Int] {
+  def parse(ts: List[Token]) = ts match {
+    case T_NUM(s)::ts => Set((s.toInt, ts)) 
+    case _ => Set ()
+  }
+}
+
+case object IdParser extends Parser[List[Token], String] {
+  def parse(ts: List[Token]) = ts match {
+    case T_ID(s)::ts => Set((s, ts)) 
+    case _ => Set ()
+  }
+}
+
+
+// arithmetic expressions
+lazy val AExp: Parser[List[Token], AExp] = 
+  (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||
+  (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T  
+lazy val T: Parser[List[Token], AExp] = 
+  (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || F
+lazy val F: Parser[List[Token], AExp] = 
+  (T_LPAREN ~> AExp <~ T_RPAREN) || 
+  IdParser ==> Var || 
+  NumParser ==> Num
+
+// boolean expressions
+lazy val BExp: Parser[List[Token], BExp] = 
+  (T_KWD("true") ==> ((_) => True: BExp)) || 
+  (T_KWD("false") ==> ((_) => False: BExp)) ||
+  (T_LPAREN ~> BExp <~ T_RPAREN) ||
+  (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || 
+  (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
+  (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
+  (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } 
+
+lazy val Stmt: Parser[List[Token], Stmt] =
+  (T_KWD("skip") ==> ((_) => Skip: Stmt)) ||
+  (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||
+  (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==>
+    { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
+  (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || 
+  (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } 
+
+lazy val Stmts: Parser[List[Token], Block] =
+  (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||
+  (Stmt ==> ((s) => List(s) : Block))
+
+lazy val Block: Parser[List[Token], Block] =
+  (T_BEGIN ~> Stmts <~ T_END) || 
+  (Stmt ==> ((s) => List(s)))
+
+// interpreter
+val beginning = """
+.class public examples/HelloWorld
+.super java/lang/Object
+
+.method public <init>()V
+   aload_0
+   invokenonvirtual java/lang/Object/<init>()V
+   return
+.end method
+
+.method public static write(I)V 
+    .limit locals 5 
+    .limit stack 5 
+    iload 0 
+    getstatic java/lang/System/out Ljava/io/PrintStream; 
+    swap 
+    invokevirtual java/io/PrintStream/println(I)V 
+    return 
+.end method
+
+
+.method public static main([Ljava/lang/String;)V
+   .limit locals 200
+   .limit stack 200
+
+"""
+
+val ending = """
+
+   return
+
+.end method
+"""
+
+// for generating new labels
+var counter = -1
+
+def Fresh(x: String) = {
+  counter += 1
+  x ++ "_" ++ counter.toString()
+}
+
+type Env = Map[String, String]
+
+def compile_aexp(a: AExp, env : Env) : List[String] = a match {
+  case Num(i) => List("ldc " + i.toString + "\n")
+  case Var(s) => List("iload " + env(s) + "\n")
+  case Aop("+", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("iadd\n")
+  case Aop("-", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n")
+  case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n")
+}
+
+def compile_bexp(b: BExp, env : Env, jmp: String) : List[String] = b match {
+  case Bop("=", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpne " + jmp + "\n")
+  case Bop("<", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpge " + jmp + "\n")
+}
+
+
+def compile_stmt(s: Stmt, env: Env) : (List[String], Env) = s match {
+  case Skip => (Nil, env)
+  case Assign(x, a) => {
+    val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString
+    (compile_aexp(a, env) ++ List("istore " + index + "\n"), env + (x -> index))
+  } 
+  case If(b, bl1, bl2) => {
+    val if_else = Fresh("If_else")
+    val if_end = Fresh("If_end")
+    val (instrs1, env1) = compile_bl(bl1, env)
+    val (instrs2, env2) = compile_bl(bl2, env1)
+    (compile_bexp(b, env, if_else) ++
+     instrs1 ++
+     List("goto " + if_end + "\n") ++
+     List("\n" + if_else + ":\n\n") ++
+     instrs2 ++
+     List("\n" + if_end + ":\n\n"), env2)
+  }
+  case While(b, bl) => {
+    val loop_begin = Fresh("Loop_begin")
+    val loop_end = Fresh("Loop_end")
+    val (instrs1, env1) = compile_bl(bl, env)
+    (List("\n" + loop_begin + ":\n\n") ++
+     compile_bexp(b, env, loop_end) ++
+     instrs1 ++
+     List("goto " + loop_begin + "\n") ++
+     List("\n" + loop_end + ":\n\n"), env1)
+  }
+  case Write(x) => 
+    (List("iload " + env(x) + "\n" + "invokestatic examples/HelloWorld/write(I)V\n"), env)
+}
+
+def compile_bl(bl: Block, env: Env) : (List[String], Env) = bl match {
+  case Nil => (Nil, env)
+  case s::bl => {
+    val (instrs1, env1) = compile_stmt(s, env)
+    val (instrs2, env2) = compile_bl(bl, env1)
+    (instrs1 ++ instrs2, env2)
+  }
+}
+
+def compile(name: String) : String = {
+  val tks = Tok.fromFile(name)
+  val ast = Stmts.parse_single(tks)
+  val instructions = compile_bl(ast, Map.empty)._1
+  beginning ++ instructions.mkString ++ ending
+}
+
+
+//examples
+
+println(compile("loops.while"))
+//println(compile("fib.while"))
+
+
+
+
+
+
+
+
+
diff -r 898c25a4e399 -r 373cf55a3ca5 compile1.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/compile1.scala	Sat Nov 24 07:08:51 2012 +0000
@@ -0,0 +1,266 @@
+// A parser and evaluator for teh while language
+// 
+//:load matcher.scala
+//:load parser3.scala
+
+// some regular expressions
+val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")
+val DIGIT = RANGE("0123456789")
+val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) 
+val NUM = PLUS(DIGIT)
+val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") 
+val SEMI: Rexp = ";"
+val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!=", "<", ">")
+val WHITESPACE = PLUS(RANGE(" \n"))
+val RPAREN: Rexp = ")"
+val LPAREN: Rexp = "("
+val BEGIN: Rexp = "{"
+val END: Rexp = "}"
+val COMMENT = SEQS("/*", NOT(SEQS(STAR(ALLC), "*/", STAR(ALLC))), "*/")
+
+// tokens for classifying the strings that have been recognised
+abstract class Token
+case object T_WHITESPACE extends Token
+case object T_COMMENT extends Token
+case object T_SEMI extends Token
+case object T_LPAREN extends Token
+case object T_RPAREN extends Token
+case object T_BEGIN extends Token
+case object T_END extends Token
+case class T_ID(s: String) extends Token
+case class T_OP(s: String) extends Token
+case class T_NUM(s: String) extends Token
+case class T_KWD(s: String) extends Token
+
+val lexing_rules: List[Rule[Token]] = 
+  List((KEYWORD, (s) => T_KWD(s.mkString)),
+       (ID, (s) => T_ID(s.mkString)),
+       (OP, (s) => T_OP(s.mkString)),
+       (NUM, (s) => T_NUM(s.mkString)),
+       (SEMI, (s) => T_SEMI),
+       (LPAREN, (s) => T_LPAREN),
+       (RPAREN, (s) => T_RPAREN),
+       (BEGIN, (s) => T_BEGIN),
+       (END, (s) => T_END),
+       (WHITESPACE, (s) => T_WHITESPACE),
+       (COMMENT, (s) => T_COMMENT))
+
+// the tokenizer
+val Tok = Tokenizer(lexing_rules, List(T_WHITESPACE, T_COMMENT))
+
+// the abstract syntax trees
+abstract class Stmt
+abstract class AExp
+abstract class BExp 
+type Block = List[Stmt]
+case object Skip extends Stmt
+case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
+case class While(b: BExp, bl: Block) extends Stmt
+case class Assign(s: String, a: AExp) extends Stmt
+case class Write(s: String) extends Stmt
+
+case class Var(s: String) extends AExp
+case class Num(i: Int) extends AExp
+case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
+
+case object True extends BExp
+case object False extends BExp
+case class Relop(o: String, a1: AExp, a2: AExp) extends BExp
+
+// atomic parsers
+case class TokParser(tok: Token) extends Parser[List[Token], Token] {
+  def parse(ts: List[Token]) = ts match {
+    case t::ts if (t == tok) => Set((t, ts)) 
+    case _ => Set ()
+  }
+}
+implicit def token2tparser(t: Token) = TokParser(t)
+
+case object NumParser extends Parser[List[Token], Int] {
+  def parse(ts: List[Token]) = ts match {
+    case T_NUM(s)::ts => Set((s.toInt, ts)) 
+    case _ => Set ()
+  }
+}
+
+case object IdParser extends Parser[List[Token], String] {
+  def parse(ts: List[Token]) = ts match {
+    case T_ID(s)::ts => Set((s, ts)) 
+    case _ => Set ()
+  }
+}
+
+
+// arithmetic expressions
+lazy val AExp: Parser[List[Token], AExp] = 
+  (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||
+  (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T  
+lazy val T: Parser[List[Token], AExp] = 
+  (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || F
+lazy val F: Parser[List[Token], AExp] = 
+  (T_LPAREN ~> AExp <~ T_RPAREN) || 
+  IdParser ==> Var || 
+  NumParser ==> Num
+
+// boolean expressions
+lazy val BExp: Parser[List[Token], BExp] = 
+  (T_KWD("true") ==> ((_) => True: BExp)) || 
+  (T_KWD("false") ==> ((_) => False: BExp)) ||
+  (T_LPAREN ~> BExp <~ T_RPAREN) ||
+  (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Relop("=", x, z): BExp } || 
+  (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Relop("!=", x, z): BExp } || 
+  (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Relop("<", x, z): BExp } || 
+  (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Relop("<", z, x): BExp } 
+
+lazy val Stmt: Parser[List[Token], Stmt] =
+  (T_KWD("skip") ==> ((_) => Skip: Stmt)) ||
+  (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||
+  (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==>
+    { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
+  (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || 
+  (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } 
+
+lazy val Stmts: Parser[List[Token], Block] =
+  (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||
+  (Stmt ==> ((s) => List(s) : Block))
+
+lazy val Block: Parser[List[Token], Block] =
+  (T_BEGIN ~> Stmts <~ T_END) || 
+  (Stmt ==> ((s) => List(s)))
+
+// compiler
+val beginning = """
+.class public examples/HelloWorld
+.super java/lang/Object
+
+.method public <init>()V
+   aload_0
+   invokenonvirtual java/lang/Object/<init>()V
+   return
+.end method
+
+.method public static write(I)V 
+    .limit locals 5 
+    .limit stack 5 
+    iload 0 
+    getstatic java/lang/System/out Ljava/io/PrintStream; 
+    swap 
+    invokevirtual java/io/PrintStream/println(I)V 
+    return 
+.end method
+
+
+.method public static main([Ljava/lang/String;)V
+   .limit locals 200
+   .limit stack 200
+
+"""
+
+val ending = """
+
+   return
+
+.end method
+"""
+
+// for generating new labels
+var counter = -1
+
+def Fresh(x: String) = {
+  counter += 1
+  x ++ "_" ++ counter.toString()
+}
+
+type Env = Map[String, String]
+type Instrs = List[String]
+
+def compile_aexp(a: AExp, env : Env) : Instrs = a match {
+  case Num(i) => List("ldc " + i.toString + "\n")
+  case Var(s) => List("iload " + env(s) + "\n")
+  case Aop("+", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("iadd\n")
+  case Aop("-", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n")
+  case Aop("*", a1, a2) => compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n")
+}
+
+def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match {
+  case True => Nil
+  case False => List("goto " + jmp + "\n")
+  case Relop("=", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpne " + jmp + "\n")
+  case Relop("!=", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpeq " + jmp + "\n")
+  case Relop("<", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("if_icmpge " + jmp + "\n")
+}
+
+
+def compile_stmt(s: Stmt, env: Env) : (Instrs, Env) = s match {
+  case Skip => (Nil, env)
+  case Assign(x, a) => {
+    val index = if (env.isDefinedAt(x)) env(x) else env.keys.size.toString
+    (compile_aexp(a, env) ++ 
+     List("istore " + index + "\n"), env + (x -> index))
+  } 
+  case If(b, bl1, bl2) => {
+    val if_else = Fresh("If_else")
+    val if_end = Fresh("If_end")
+    val (instrs1, env1) = compile_bl(bl1, env)
+    val (instrs2, env2) = compile_bl(bl2, env1)
+    (compile_bexp(b, env, if_else) ++
+     instrs1 ++
+     List("goto " + if_end + "\n") ++
+     List("\n" + if_else + ":\n\n") ++
+     instrs2 ++
+     List("\n" + if_end + ":\n\n"), env2)
+  }
+  case While(b, bl) => {
+    val loop_begin = Fresh("Loop_begin")
+    val loop_end = Fresh("Loop_end")
+    val (instrs1, env1) = compile_bl(bl, env)
+    (List("\n" + loop_begin + ":\n\n") ++
+     compile_bexp(b, env, loop_end) ++
+     instrs1 ++
+     List("goto " + loop_begin + "\n") ++
+     List("\n" + loop_end + ":\n\n"), env1)
+  }
+  case Write(x) => 
+    (List("iload " + env(x) + "\n" + "invokestatic examples/HelloWorld/write(I)V\n"), env)
+}
+
+def compile_bl(bl: Block, env: Env) : (Instrs, Env) = bl match {
+  case Nil => (Nil, env)
+  case s::bl => {
+    val (instrs1, env1) = compile_stmt(s, env)
+    val (instrs2, env2) = compile_bl(bl, env1)
+    (instrs1 ++ instrs2, env2)
+  }
+}
+
+def compile(input: String) : String = {
+  val tks = Tok.fromFile(input)
+  val ast = Stmts.parse_single(tks)
+  val instructions = compile_bl(ast, Map.empty)._1
+  beginning ++ instructions.mkString ++ ending
+}
+
+
+def compile_to(input: String, output: String) = {
+  val fw = new java.io.FileWriter(output) 
+  fw.write(compile(input)) 
+  fw.close()
+}
+
+
+//examples
+
+compile_to("loops.while", "loops.j")
+compile_to("fib.while", "fib.j")
+
+
+
+
+
+
+
+
+
diff -r 898c25a4e399 -r 373cf55a3ca5 fib.while
--- a/fib.while	Fri Nov 23 21:21:27 2012 +0000
+++ b/fib.while	Sat Nov 24 07:08:51 2012 +0000
@@ -7,7 +7,7 @@
 
 */
 
-n := 9;
+n := 90;
 minus1 := 0;
 minus2 := 1;
 temp := 0;
@@ -18,5 +18,5 @@
        n := n - 1
 };
 fib_res := minus2;
-print fib_res 
+write fib_res 
 
diff -r 898c25a4e399 -r 373cf55a3ca5 hw08.tex
--- a/hw08.tex	Fri Nov 23 21:21:27 2012 +0000
+++ b/hw08.tex	Sat Nov 24 07:08:51 2012 +0000
@@ -16,48 +16,30 @@
 \item Suppose the following grammar for the WHILE-language:
 
 \begin{center}
-\begin{tabular}{l}
-$S \rightarrow N\cdot P$\\
-$P \rightarrow V\cdot N$\\
-$N \rightarrow N\cdot N$\\
-$N \rightarrow A \cdot N$\\
-$N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\
-$V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\
-$A \rightarrow \texttt{The} \;|\; \texttt{the}$\\
+\begin{tabular}{lcl}
+$Stmt$ & $\rightarrow$ &  $\text{skip}$\\
+              & $|$ & $Id := AExp$\\
+              & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
+              & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\
+$Stmt$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
+              & $|$ & $Stmt$\medskip\\
+$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
+                & $|$ & $Stmt$\medskip\\
+$AExp$ & $\rightarrow$ & $AExp + AExp$\\
+               & $|$ & $AExp * AExp$\\
+               & $|$ & $( AExp )$\\
+                & $|$ & $Num$\\
+                & $|$ & $Id$\medskip\\
+$BExp$ & $\rightarrow$ & $AExp = AExp$\\
+                 & $|$ & $AExp \not= AExp$\\
+                  & $|$ & $\text{false}$\\
+                  & $|$ & $\text{true}$\\
+
 \end{tabular}
 \end{center}
 
-
-\item Consider the following grammar 
-
-\begin{center}
-\begin{tabular}{l}
-$S \rightarrow N\cdot P$\\
-$P \rightarrow V\cdot N$\\
-$N \rightarrow N\cdot N$\\
-$N \rightarrow A \cdot N$\\
-$N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\
-$V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\
-$A \rightarrow \texttt{The} \;|\; \texttt{the}$\\
-\end{tabular}
-\end{center}
+Transform this grammar into Chomsky normalform.
 
-where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals.
-Using the CYK-algorithm, check whether or not the following string can be parsed
-by the grammar:
-
-\begin{center}
-\texttt{The trainer trains the student team}
-\end{center}
-
-\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, 
-\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example
-\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!
-See:
-
-\begin{center}
-\url{http://callumacrae.github.com/regex-tuesday/challenge11.html}
-\end{center}
 \end{enumerate}
 
 \end{document}
diff -r 898c25a4e399 -r 373cf55a3ca5 parser3.scala
--- a/parser3.scala	Fri Nov 23 21:21:27 2012 +0000
+++ b/parser3.scala	Sat Nov 24 07:08:51 2012 +0000
@@ -7,6 +7,11 @@
   def parse_all(ts: I) : Set[T] =
     for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head
 
+  def parse_single(ts: I) : T = parse_all(ts).toList match {
+    case t::Nil => t
+    case _ => { println ("Parse Error") ; sys.exit(-1) }
+  }
+    
   def || (right : => Parser[I, T]) : Parser[I, T] = new AltParser(this, right)
   def ==>[S] (f: => T => S) : Parser [I, S] = new FunParser(this, f)
   def ~[S] (right : => Parser[I, S]) : Parser[I, (T, S)] = new SeqParser(this, right)
diff -r 898c25a4e399 -r 373cf55a3ca5 slides08.pdf
Binary file slides08.pdf has changed
diff -r 898c25a4e399 -r 373cf55a3ca5 slides08.tex
--- a/slides08.tex	Fri Nov 23 21:21:27 2012 +0000
+++ b/slides08.tex	Sat Nov 24 07:08:51 2012 +0000
@@ -629,7 +629,7 @@
               & $|$ & $Id := AExp$\\
               & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
               & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\
-$Stmt$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
+$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
               & $|$ & $Stmt$\medskip\\
 $Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
                 & $|$ & $Stmt$\medskip\\
diff -r 898c25a4e399 -r 373cf55a3ca5 slides09.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/slides09.tex	Sat Nov 24 07:08:51 2012 +0000
@@ -0,0 +1,676 @@
+\documentclass[dvipsnames,14pt,t]{beamer}
+\usepackage{beamerthemeplainculight}
+\usepackage[T1]{fontenc}
+\usepackage[latin1]{inputenc}
+\usepackage{mathpartir}
+\usepackage[absolute,overlay]{textpos}
+\usepackage{ifthen}
+\usepackage{tikz}
+\usepackage{pgf}
+\usepackage{calc} 
+\usepackage{ulem}
+\usepackage{courier}
+\usepackage{listings}
+\renewcommand{\uline}[1]{#1}
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{shapes}
+\usetikzlibrary{shadows}
+\usetikzlibrary{positioning}
+\usetikzlibrary{calc}
+\usetikzlibrary{plotmarks}
+\usepackage{graphicx} 
+
+\definecolor{javared}{rgb}{0.6,0,0} % for strings
+\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
+\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
+\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
+
+\lstset{language=Java,
+	basicstyle=\ttfamily,
+	keywordstyle=\color{javapurple}\bfseries,
+	stringstyle=\color{javagreen},
+	commentstyle=\color{javagreen},
+	morecomment=[s][\color{javadocblue}]{/**}{*/},
+	numbers=left,
+	numberstyle=\tiny\color{black},
+	stepnumber=1,
+	numbersep=10pt,
+	tabsize=2,
+	showspaces=false,
+	showstringspaces=false}
+
+\lstdefinelanguage{scala}{
+  morekeywords={abstract,case,catch,class,def,%
+    do,else,extends,false,final,finally,%
+    for,if,implicit,import,match,mixin,%
+    new,null,object,override,package,%
+    private,protected,requires,return,sealed,%
+    super,this,throw,trait,true,try,%
+    type,val,var,while,with,yield},
+  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+  sensitive=true,
+  morecomment=[l]{//},
+  morecomment=[n]{/*}{*/},
+  morestring=[b]",
+  morestring=[b]',
+  morestring=[b]"""
+}
+
+\lstset{language=Scala,
+	basicstyle=\ttfamily,
+	keywordstyle=\color{javapurple}\bfseries,
+	stringstyle=\color{javagreen},
+	commentstyle=\color{javagreen},
+	morecomment=[s][\color{javadocblue}]{/**}{*/},
+	numbers=left,
+	numberstyle=\tiny\color{black},
+	stepnumber=1,
+	numbersep=10pt,
+	tabsize=2,
+	showspaces=false,
+	showstringspaces=false}
+
+% beamer stuff 
+\renewcommand{\slidecaption}{AFL 09, King's College London, 28.~November 2012}
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}       
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
+
+% The data files, written on the first run.
+\begin{filecontents}{s-grammar1.data}
+1 0.01152
+51 0.07973
+101 0.09726
+151 0.09320
+201 0.10010
+251 0.16997
+301 0.26662
+351 0.46118
+401 0.62516
+451 0.87247
+501 1.16334
+551 1.71152
+601 2.10958
+651 2.44360
+701 2.98488
+751 3.50326
+801 4.11036
+851 4.93394
+901 5.77465
+951 7.39123
+\end{filecontents}
+
+\begin{filecontents}{s-grammar2.data}
+1 0.01280
+2 0.00064
+3 0.00173
+4 0.00355
+5 0.00965
+6 0.02674
+7 0.06953
+8 0.11166
+9 0.18707
+10 0.09189
+11 0.12724
+12 0.24337
+13 0.59304
+14 1.53594
+15 4.01195
+16 10.73582
+17 29.51587
+#18 73.14163
+\end{filecontents}
+
+
+\begin{document}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}<1>[t]
+\frametitle{%
+  \begin{tabular}{@ {}c@ {}}
+  \\[-3mm]
+  \LARGE Automata and \\[-2mm] 
+  \LARGE Formal Languages (9)\\[3mm] 
+  \end{tabular}}
+
+  \normalsize
+  \begin{center}
+  \begin{tabular}{ll}
+  Email:  & christian.urban at kcl.ac.uk\\
+  Of$\!$fice: & S1.27 (1st floor Strand Building)\\
+  Slides: & KEATS (also home work is there)\\
+  \end{tabular}
+  \end{center}
+
+
+\end{frame}}
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}}
+
+Using a lexer: assume the following regular expressions
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\
+$W\!O\!RD$ & $\dn$ & $SY\!M^+$\\
+$BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\
+$ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\
+$W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}
+
+\begin{itemize}
+\item the text should be formatted consistently up to a specified width, say 60 characters 
+\item potential linebreaks are inserted by the formatter (not the input)
+\item repeated whitespaces are ``condensed'' to a single whitepace
+\item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$}  start/end paragraph
+\item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$}  start/end bold
+\item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$}  start/end red (cyan, etc)
+
+
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}
+
+The lexer cannot prevent errors like
+
+\begin{center}
+\bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$} 
+\end{center}
+
+or
+
+\begin{center}
+\bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}
+
+Parser combinators: \bigskip
+
+\begin{minipage}{1.1\textwidth}
+\begin{center}
+\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 
+$\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$
+\end{center}
+\end{minipage}\bigskip
+
+\begin{itemize}
+\item sequencing
+\item alternative
+\item semantic action
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Alternative parser (code \bl{$p\;||\;q$})\bigskip
+
+\begin{itemize}
+\item apply \bl{$p$} and also \bl{$q$}; then combine the outputs
+\end{itemize}
+
+\begin{center}
+\large \bl{$p(\text{input}) \cup q(\text{input})$}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Sequence parser (code \bl{$p\sim q$})\bigskip
+
+\begin{itemize}
+\item apply first \bl{$p$} producing a set of pairs
+\item then apply \bl{$q$} to the unparsed parts
+\item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part)
+\end{itemize}
+
+\begin{center}
+\begin{tabular}{l}
+\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 
+\large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]
+\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}
+\end{tabular}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Function parser (code \bl{$p \Longrightarrow f$})\bigskip
+
+\begin{itemize}
+\item apply \bl{$p$} producing a set of pairs
+\item then apply the function \bl{$f$} to each first component
+\end{itemize}
+
+\begin{center}
+\begin{tabular}{l}
+\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}
+\end{tabular}
+\end{center}\bigskip\bigskip\pause
+
+\bl{$f$} is the semantic action (``what to do with the parsed input'')
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Token parser:\bigskip
+
+\begin{itemize}
+\item if the input is
+
+\begin{center}
+\large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$}
+\end{center}
+
+then return
+
+\begin{center}
+\large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$}
+\end{center}
+
+or
+
+\begin{center}
+\large \bl{$\{\}$}
+\end{center}
+
+if \bl{$tok_1$} is not the right token we are looking for
+\end{itemize}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Number-Token parser:\bigskip
+
+\begin{itemize}
+\item if the input is
+
+\begin{center}
+\large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$}
+\end{center}
+
+then return
+
+\begin{center}
+\large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$}
+\end{center}
+
+or
+
+\begin{center}
+\large \bl{$\{\}$}
+\end{center}
+
+if \bl{$tok_1$} is not the right token we are looking for
+\end{itemize}\pause
+
+\begin{center}
+list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens)
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{itemize}
+\item if the input is
+
+\begin{center}
+\begin{tabular}{l}
+\large \bl{$num\_tok(42)::$}\\
+\hspace{7mm}\large \bl{$num\_tok(3) ::$}\\
+\hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$}
+\end{tabular}
+\end{center}
+
+and the parser is 
+
+\begin{center}
+\bl{$ntp \sim ntp$}
+\end{center}
+
+the successful output will be
+
+\begin{center}
+\large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$}
+\end{center}\pause
+
+Now we can form
+\begin{center}
+\bl{$(ntp \sim ntp) \Longrightarrow f$}
+\end{center}
+
+where \bl{$f$} is the semantic action (``what to do with the pair'')
+
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
+
+Addition
+
+\begin{center}
+\bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
+\end{center}\pause
+
+Multiplication
+
+\begin{center}
+\bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}
+\end{center}\pause
+
+Parenthesis
+
+\begin{center}
+\bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}}
+
+\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 \Longrightarrow f$} returns results of type
+
+\begin{center}
+\bl{$S$}
+\end{center}
+
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}
+
+\begin{itemize}
+\item input: \alert{list of tokens}
+\item output: set of (output\_type, \alert{list of tokens})
+\end{itemize}\bigskip\pause
+
+actually it can be any input type as long as it is a kind of sequence
+(for example a string)
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}
+
+\begin{itemize}
+\item input: \alert{string}
+\item output: set of (output\_type, \alert{string})
+\end{itemize}\bigskip
+
+but lexers are better when whitespaces or comments need to be filtered out
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Successful Parses\end{tabular}}
+
+\begin{itemize}
+\item input: string
+\item output: \alert{set of} (output\_type, string)
+\end{itemize}\bigskip
+
+a parse is successful whenever the input has been
+fully ``consumed'' (that is the second component is empty)
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app7.scala}}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app7.scala}}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+{\lstset{language=Scala}\fontsize{10}{12}\selectfont
+\texttt{\lstinputlisting{app8.scala}}}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}
+
+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}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}
+
+\mbox{}\\[-25mm]\mbox{}
+
+\begin{center}
+\begin{tikzpicture}[y=.2cm, x=.009cm]
+ 	%axis
+	\draw (0,0) -- coordinate (x axis mid) (1000,0);
+    	\draw (0,0) -- coordinate (y axis mid) (0,30);
+    	%ticks
+    	\foreach \x in {0, 20, 100, 200,...,1000}
+     		\draw (\x,1pt) -- (\x,-3pt)
+			node[anchor=north] {\small \x};
+    	\foreach \y in {0,5,...,30}
+     		\draw (1pt,\y) -- (-3pt,\y) 
+     			node[anchor=east] {\small\y}; 
+	%labels      
+	\node[below=0.6cm] at (x axis mid) {\bl{1}s};
+	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+
+	%plots
+	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
+		file {s-grammar1.data};
+         \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
+                  file {s-grammar2.data};}
+	%legend
+	\begin{scope}[shift={(400,20)}] 
+	\draw[color=blue] (0,0) -- 
+		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
+		node[right]{\small unambiguous};
+	\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 
+                plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
+                node[right]{\small ambiguous};}  
+	\end{scope}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}What about Left-Recursion?\end{tabular}}
+
+\begin{itemize}
+\item we record when we recursively called a parser\bigskip
+\item whenever the is a recursion, the parser must have consumed something --- so
+we can decrease the input string/list of token by one (at the end)
+\end{itemize}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}While-Language\end{tabular}}
+
+
+\begin{center}
+\bl{\begin{tabular}{@{}lcl@{}}
+$Stmt$ & $\rightarrow$ &  $\text{skip}$\\
+              & $|$ & $Id := AExp$\\
+              & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\
+              & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\
+$Stmts$ & $\rightarrow$ &  $Stmt \;\text{;}\; Stmts$\\
+              & $|$ & $Stmt$\medskip\\
+$Block$ & $\rightarrow$ &  $\{ Stmts \}$\\
+                & $|$ & $Stmt$\medskip\\
+$AExp$ & $\rightarrow$ & \ldots\\
+$BExp$ & $\rightarrow$ & \ldots\\
+\end{tabular}}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}}
+
+\begin{center}
+\bl{\begin{tabular}{l}
+$\{$\\
+\;\;$x := 5 \text{;}$\\
+\;\;$y := x * 3\text{;}$\\
+\;\;$y := x * 4\text{;}$\\
+\;\;$x := u * 3$\\
+$\}$
+\end{tabular}}
+\end{center}
+
+\begin{itemize}
+\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause
+\item \bl{\text{eval}(stmt, env)}
+\end{itemize}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+\end{document}
+
+%%% Local Variables:  
+%%% mode: latex
+%%% TeX-master: t
+%%% End: 
+
diff -r 898c25a4e399 -r 373cf55a3ca5 while1.scala
--- a/while1.scala	Fri Nov 23 21:21:27 2012 +0000
+++ b/while1.scala	Sat Nov 24 07:08:51 2012 +0000
@@ -8,7 +8,7 @@
 val DIGIT = RANGE("0123456789")
 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) 
 val NUM = PLUS(DIGIT)
-val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "print") 
+val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") 
 val SEMI: Rexp = ";"
 val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!", "<", ">")
 val WHITESPACE = PLUS(RANGE(" \n"))
@@ -57,7 +57,7 @@
 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
 case class While(b: BExp, bl: Block) extends Stmt
 case class Assign(s: String, a: AExp) extends Stmt
-case class Print(s: String) extends Stmt
+case class Write(s: String) extends Stmt
 
 case class Var(s: String) extends AExp
 case class Num(i: Int) extends AExp
@@ -104,12 +104,13 @@
 
 // boolean expressions
 lazy val BExp: Parser[List[Token], BExp] = 
+  (T_KWD("true") ==> ((_) => True: BExp)) || 
+  (T_KWD("false") ==> ((_) => False: BExp)) ||
+  (T_LPAREN ~> BExp <~ T_RPAREN) ||
   (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || 
   (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
   (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
-  (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z): BExp } || 
-  (T_KWD("true") ==> ((_) => True)) || 
-  (T_KWD("false") ==> ((_) => False: BExp))
+  (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x): BExp }
 
 lazy val Stmt: Parser[List[Token], Stmt] =
   (T_KWD("skip") ==> ((_) => Skip: Stmt)) ||
@@ -117,7 +118,7 @@
   (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==>
     { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
   (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || 
-  (T_KWD("print") ~ IdParser) ==> { case (x, y) => Print(y) } 
+  (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } 
 
 lazy val Stmts: Parser[List[Token], Block] =
   (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||
@@ -135,8 +136,9 @@
   case False => false
   case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
   case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
-  case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
   case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
+  case Bop("&&", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
+  case Bop("||", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
 }
 
 def eval_aexp(a: AExp, env : Env) : Int = a match {
@@ -154,7 +156,7 @@
   case While(b, bl) => 
     if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
     else env
-  case Print(x) => { println(env(x)); env }
+  case Write(x) => { println(env(x)); env }
 }
 
 def eval_bl(bl: Block, env: Env) : Env = bl match {
@@ -164,11 +166,21 @@
 
 def eval_prog(name: String) : Env = {
   val tks = Tok.fromFile(name)
-  val ast = Stmts.parse_all(tks).head
+  val ast = Stmts.parse_single(tks)
   eval_bl(ast, Map.empty)
 }
 
 
 //examples
 
-eval_prog("fib.while")
+eval_prog("loops.while")
+//eval_prog("fib.while")
+
+
+
+
+
+
+
+
+