--- /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"))
+
+
+
+
+
+
+
+
+
--- /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")
+
+
+
+
+
+
+
+
+
--- 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
--- 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}
--- 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)
Binary file slides08.pdf has changed
--- 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\\
--- /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:
+
--- 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")
+
+
+
+
+
+
+
+
+