progs/while1.scala
author Christian Urban <urbanc@in.tum.de>
Sat, 07 Jan 2017 14:52:26 +0000
changeset 471 9476086849ad
parent 93 4794759139ea
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
85
1a4065f965fb added packages
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 83
diff changeset
     1
// A parser and evaluator for the WHILE language
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
     2
// 
471
9476086849ad updated
Christian Urban <urbanc@in.tum.de>
parents: 93
diff changeset
     3
9476086849ad updated
Christian Urban <urbanc@in.tum.de>
parents: 93
diff changeset
     4
9476086849ad updated
Christian Urban <urbanc@in.tum.de>
parents: 93
diff changeset
     5
85
1a4065f965fb added packages
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 83
diff changeset
     6
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     7
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     8
// some regular expressions
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
     9
val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")
68
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 66
diff changeset
    10
val DIGIT = RANGE("0123456789")
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    11
val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    12
val NUM = PLUS(DIGIT)
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
    13
val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") 
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    14
val SEMI: Rexp = ";"
80
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
    15
val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!=", "<", ">")
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    16
val WHITESPACE = PLUS(RANGE(" \n"))
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    17
val RPAREN: Rexp = ")"
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    18
val LPAREN: Rexp = "("
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    19
val BEGIN: Rexp = "{"
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    20
val END: Rexp = "}"
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
    21
val COMMENT = SEQS("/*", NOT(SEQS(STAR(ALLC), "*/", STAR(ALLC))), "*/")
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    22
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
    23
// tokens for classifying the strings that have been recognised
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    24
abstract class Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    25
case object T_WHITESPACE extends Token
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
    26
case object T_COMMENT extends Token
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    27
case object T_SEMI extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    28
case object T_LPAREN extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    29
case object T_RPAREN extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    30
case object T_BEGIN extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    31
case object T_END extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    32
case class T_ID(s: String) extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    33
case class T_OP(s: String) extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    34
case class T_NUM(s: String) extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    35
case class T_KWD(s: String) extends Token
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    36
85
1a4065f965fb added packages
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 83
diff changeset
    37
val lexing_rules: List[(Rexp, List[Char] => Token)] = 
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    38
  List((KEYWORD, (s) => T_KWD(s.mkString)),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    39
       (ID, (s) => T_ID(s.mkString)),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    40
       (OP, (s) => T_OP(s.mkString)),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    41
       (NUM, (s) => T_NUM(s.mkString)),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    42
       (SEMI, (s) => T_SEMI),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    43
       (LPAREN, (s) => T_LPAREN),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    44
       (RPAREN, (s) => T_RPAREN),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    45
       (BEGIN, (s) => T_BEGIN),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    46
       (END, (s) => T_END),
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
    47
       (WHITESPACE, (s) => T_WHITESPACE),
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
    48
       (COMMENT, (s) => T_COMMENT))
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    49
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    50
// the tokenizer
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
    51
val Tok = Tokenizer(lexing_rules, List(T_WHITESPACE, T_COMMENT))
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    52
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    53
// the abstract syntax trees
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    54
abstract class Stmt
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    55
abstract class AExp
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    56
abstract class BExp 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    57
type Block = List[Stmt]
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    58
case object Skip extends Stmt
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    59
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    60
case class While(b: BExp, bl: Block) extends Stmt
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    61
case class Assign(s: String, a: AExp) extends Stmt
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
    62
case class Write(s: String) extends Stmt
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
    63
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    64
case class Var(s: String) extends AExp
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    65
case class Num(i: Int) extends AExp
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    66
case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
    67
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    68
case object True extends BExp
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    69
case object False extends BExp
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    70
case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    71
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
    72
// atomic parsers
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    73
case class TokParser(tok: Token) extends Parser[List[Token], Token] {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    74
  def parse(ts: List[Token]) = ts match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    75
    case t::ts if (t == tok) => Set((t, ts)) 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    76
    case _ => Set ()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    77
  }
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    78
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    79
implicit def token2tparser(t: Token) = TokParser(t)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    80
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    81
case object NumParser extends Parser[List[Token], Int] {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    82
  def parse(ts: List[Token]) = ts match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    83
    case T_NUM(s)::ts => Set((s.toInt, ts)) 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    84
    case _ => Set ()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    85
  }
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    86
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    87
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    88
case object IdParser extends Parser[List[Token], String] {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    89
  def parse(ts: List[Token]) = ts match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    90
    case T_ID(s)::ts => Set((s, ts)) 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    91
    case _ => Set ()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    92
  }
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    93
}
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    94
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    95
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
    96
// arithmetic expressions
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    97
lazy val AExp: Parser[List[Token], AExp] = 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    98
  (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
    99
  (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T  
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   100
lazy val T: Parser[List[Token], AExp] = 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   101
  (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || F
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   102
lazy val F: Parser[List[Token], AExp] = 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   103
  (T_LPAREN ~> AExp <~ T_RPAREN) || 
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
   104
  IdParser ==> Var || 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
   105
  NumParser ==> Num
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   106
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   107
// boolean expressions
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   108
lazy val BExp: Parser[List[Token], BExp] = 
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   109
  (T_KWD("true") ==> ((_) => True: BExp)) || 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   110
  (T_KWD("false") ==> ((_) => False: BExp)) ||
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   111
  (T_LPAREN ~> BExp <~ T_RPAREN) ||
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   112
  (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || 
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   113
  (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   114
  (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   115
  (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x): BExp }
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   116
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   117
lazy val Stmt: Parser[List[Token], Stmt] =
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   118
  (T_KWD("skip") ==> ((_) => Skip: Stmt)) ||
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   119
  (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   120
  (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==>
71
7717f20f0504 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 70
diff changeset
   121
    { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   122
  (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || 
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   123
  (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } 
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   124
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   125
lazy val Stmts: Parser[List[Token], Block] =
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   126
  (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   127
  (Stmt ==> ((s) => List(s) : Block))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   128
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   129
lazy val Block: Parser[List[Token], Block] =
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   130
  (T_BEGIN ~> Stmts <~ T_END) || 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   131
  (Stmt ==> ((s) => List(s)))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   132
70
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 69
diff changeset
   133
// interpreter
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   134
type Env = Map[String, Int]
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   135
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   136
def eval_bexp(b: BExp, env: Env) : Boolean = b match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   137
  case True => true
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   138
  case False => false
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   139
  case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   140
  case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   141
  case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
66
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   142
}
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   143
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   144
def eval_aexp(a: AExp, env : Env) : Int = a match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   145
  case Num(i) => i
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   146
  case Var(s) => env(s)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   147
  case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   148
  case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   149
  case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   150
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   151
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   152
def eval_stmt(s: Stmt, env: Env) : Env = s match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   153
  case Skip => env
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   154
  case Assign(x, a) => env + (x -> eval_aexp(a, env))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   155
  case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   156
  case While(b, bl) => 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   157
    if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   158
    else env
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   159
  case Write(x) => { println(env(x)); env }
69
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   160
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   161
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   162
def eval_bl(bl: Block, env: Env) : Env = bl match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   163
  case Nil => env
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   164
  case s::bl => eval_bl(bl, eval_stmt(s, env))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   165
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 68
diff changeset
   166
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   167
def eval_prog(name: String) : Env = {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   168
  val tks = Tok.fromFile(name)
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   169
  val ast = Stmts.parse_single(tks)
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   170
  eval_bl(ast, Map.empty)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   171
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   173
72
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 71
diff changeset
   174
//examples
75
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 74
diff changeset
   175
80
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   176
//eval_prog("loops.while")
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 80
diff changeset
   177
eval_prog("fib.while")
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   179
80
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   180
def time_needed[T](i: Int, code: => T) = {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   181
  val start = System.nanoTime()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   182
  for (j <- 1 to i) code
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   183
  val end = System.nanoTime()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   184
  (end - start)/(i * 1.0e9)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   185
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   186
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   187
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   188
val test_prog = """
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   189
start := XXX;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   190
x := start;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   191
y := start;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   192
z := start;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   193
while 0 < x do {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   194
 while 0 < y do {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   195
  while 0 < z do {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   196
    z := z - 1
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   197
  };
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   198
  z := start;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   199
  y := y - 1
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   200
 };     
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   201
 y := start;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   202
 x := x - 1
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   203
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   204
"""
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   205
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   206
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   207
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   208
def eval_test(n: Int) : Unit = {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   209
  val tks = Tok.fromString(test_prog.replaceAllLiterally("XXX", n.toString))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   210
  val ast = Stmts.parse_single(tks)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   211
  println(n + " " + time_needed(2, eval_bl(ast, Map.empty)))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   212
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   213
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   214
List(1, 200, 400, 600, 800, 1000, 1200, 1400, 1600).map(eval_test(_))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   215
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 76
diff changeset
   216
76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   217
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   218
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   219
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   220
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   221