Mercurial Mercurial > hg > afl-material / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
progs/comb2.scala
changeset 627 f5214da1976e
parent 624 8d0af38389bc
child 628 8067d0a8ba04
equal deleted inserted replaced
626:2d91b2107656 627:f5214da1976e 
    74 
    74 
    75 case object Skip extends Stmt
 
    75 case object Skip extends Stmt
 
    76 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
 
    76 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
 
    77 case class While(b: BExp, bl: Block) extends Stmt
 
    77 case class While(b: BExp, bl: Block) extends Stmt
 
    78 case class Assign(s: String, a: AExp) extends Stmt
 
    78 case class Assign(s: String, a: AExp) extends Stmt
 
       
    79 case class Write(s: String) extends Stmt
 
       
    80 
    79 
    81 
    80 case class Var(s: String) extends AExp
 
    82 case class Var(s: String) extends AExp
 
    81 case class Num(i: Int) extends AExp
 
    83 case class Num(i: Int) extends AExp
 
    82 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
 
    84 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
 
    83 
    85 
    84 case object True extends BExp
 
    86 case object True extends BExp
 
    85 case object False extends BExp
 
    87 case object False extends BExp
 
    86 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
 
    88 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
 
    87 
    89 case class And(b1: BExp, b2: BExp) extends BExp
 
       
    90 case class Or(b1: BExp, b2: BExp) extends BExp
 
    88 
    91 
    89 case object IdParser extends Parser[String, String] {
 
    92 case object IdParser extends Parser[String, String] {
 
    90   val reg = "[a-z][a-z,0-9]*".r
 
    93   val reg = "[a-z][a-z,0-9]*".r
 
    91   def parse(sb: String) = reg.findPrefixOf(sb) match {
 
    94   def parse(sb: String) = reg.findPrefixOf(sb) match {
 
    92     case None => Set()
 
    95     case None => Set()
 
    93     case Some(s) => Set(sb.splitAt(s.length))
 
    96     case Some(s) => Set(sb.splitAt(s.length))
 
    94   }
 
    97   }
 
    95 }
 
    98 }
 
    96 
    99 
    97 lazy val AExp: Parser[String, AExp] = 
   100 lazy val AExp: Parser[String, AExp] = 
    98   ((Te ~ "+" ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z):AExp } ||
 
   101   (Te ~ "+" ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||
 
    99    (Te ~ "-" ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z):AExp } || Te)  
   102   (Te ~ "-" ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || Te 
   100 lazy val Te: Parser[String, AExp] = 
   103 lazy val Te: Parser[String, AExp] = 
   101   (Fa ~ "*" ~ Te) ==> { case ((x, y), z) => Aop("*", x, z):AExp } || Fa
 
   104   (Fa ~ "*" ~ Te) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || 
       
   105   (Fa ~ "/" ~ Te) ==> { case ((x, y), z) => Aop("/", x, z): AExp } || Fa  
   102 lazy val Fa: Parser[String, AExp] = 
   106 lazy val Fa: Parser[String, AExp] = 
   103   (("(" ~ AExp ~ ")") ==> { case ((x, y), z) => y } || 
   107    ("(" ~ AExp ~ ")") ==> { case ((x, y), z) => y } || 
   104    IdParser ==> Var || 
   108    IdParser ==> Var || 
   105    NumParser ==> Num)
 
   109    NumParser ==> Num
 
   106 
   110 
   107 // boolean expressions
 
   111 // boolean expressions with some simple nesting
 
   108 lazy val BExp: Parser[String, BExp] = 
   112 lazy val BExp: Parser[String, BExp] = 
   109   ((AExp ~ "=" ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z):BExp } || 
   113    (AExp ~ "==" ~ AExp) ==> { case ((x, y), z) => Bop("==", x, z) }: Bexp || 
   110    (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z):BExp } || 
   114    (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
   111    (AExp ~ "<" ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z):BExp } || 
   115    (AExp ~ "<" ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
   112    (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z):BExp } || 
   116    (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z): BExp } ||
 
   113    ("true" ==> ((_) => True:BExp )) || 
   117    ("(" ~ BExp ~ ")" ~ "&&" ~ BExp) ==> { case ((((x, y), z), u), v) => And(y, v): BExp } ||
 
   114    ("false" ==> ((_) => False:BExp )) ||
 
   118    ("(" ~ BExp ~ ")" ~ "||" ~ BExp) ==> { case ((((x, y), z), u), v) => Or(y, v): BExp } ||
 
   115    ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y})
 
   119    ("true" ==> ((_) => True: BExp )) || 
   116 
   120    ("false" ==> ((_) => False: BExp )) ||
 
       
   121    ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y}
 
       
   122 
       
   123 // statements
 
   117 lazy val Stmt: Parser[String, Stmt] =
 
   124 lazy val Stmt: Parser[String, Stmt] =
 
   118   (("skip" ==> ((_) => Skip: Stmt)) ||
 
   125   (("skip" ==> ((_) => Skip: Stmt)) ||
 
   119    (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||
 
   126    (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||
 
       
   127    ("write(" ~ IdParser ~ ")") ==> { case ((x, y), z) => Write(y): Stmt } ||
 
   120    ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==>
 
   128    ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==>
 
   121     { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
 
   129     { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
 
   122    ("while" ~ BExp ~ "do" ~ Block) ==> { case (((x, y), z), w) => While(y, w) }) 
   130    ("while" ~ BExp ~ "do" ~ Block) ==> { case (((x, y), z), w) => While(y, w) }) 
   123  
   131  
   124 lazy val Stmts: Parser[String, Block] =
 
   132 lazy val Stmts: Parser[String, Block] =
 
   132 
   140 
   133 Stmts.parse_all("x2:=5+3;")
 
   141 Stmts.parse_all("x2:=5+3;")
 
   134 Block.parse_all("{x:=5;y:=8}")
 
   142 Block.parse_all("{x:=5;y:=8}")
 
   135 Block.parse_all("if(false)then{x:=5}else{x:=10}")
 
   143 Block.parse_all("if(false)then{x:=5}else{x:=10}")
 
   136 
   144 
   137 val fib = """{n:=10;minus1:=0;minus2:=1;temp:=0;while(n>0)do{temp:=minus2;minus2:=minus1+minus2;minus1:=temp;n:=n-1};result:=minus2}"""
 
   145 val fib = """{n := 10;
 
       
   146               minus1 := 0;
 
       
   147               minus2 := 1;
 
       
   148               temp := 0;
 
       
   149               while (n > 0) do {
 
       
   150                  temp := minus2;
 
       
   151                  minus2 := minus1 + minus2;
 
       
   152                  minus1 := temp;
 
       
   153                  n := n - 1
 
       
   154               };
 
       
   155               result := minus2}""".replaceAll("\\s+", "")
 
   138 
   156 
   139 Block.parse_all(fib)
 
   157 Block.parse_all(fib)
 
   140 
   158 
   141 // an interpreter for the WHILE language
 
   159 // an interpreter for the WHILE language
 
   142 type Env = Map[String, Int]
 
   160 type Env = Map[String, Int]
 
   145   case Num(i) => i
 
   163   case Num(i) => i
 
   146   case Var(s) => env(s)
 
   164   case Var(s) => env(s)
 
   147   case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
 
   165   case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
 
   148   case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
 
   166   case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
 
   149   case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
 
   167   case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
 
       
   168   case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)
 
   150 }
 
   169 }
 
   151 
   170 
   152 def eval_bexp(b: BExp, env: Env) : Boolean = b match {
 
   171 def eval_bexp(b: BExp, env: Env) : Boolean = b match {
 
   153   case True => true
 
   172   case True => true
 
   154   case False => false
 
   173   case False => false
 
   155   case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
 
   174   case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
 
   156   case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
 
   175   case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
 
   157   case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
 
   176   case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
 
   158   case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
 
   177   case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
 
       
   178   case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env)
 
       
   179   case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env)
 
   159 }
 
   180 }
 
   160 
   181 
   161 def eval_stmt(s: Stmt, env: Env) : Env = s match {
 
   182 def eval_stmt(s: Stmt, env: Env) : Env = s match {
 
   162   case Skip => env
 
   183   case Skip => env
 
   163   case Assign(x, a) => env + (x -> eval_aexp(a, env))
 
   184   case Assign(x, a) => env + (x -> eval_aexp(a, env))
 
   164   case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 
   185   case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 
   165   case While(b, bl) => 
   186   case While(b, bl) => 
   166     if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
 
   187     if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
 
   167     else env
 
   188     else env
 
       
   189   case Write(x) => { println(env(x)) ; env }  
   168 }
 
   190 }
 
   169 
   191 
   170 def eval_bl(bl: Block, env: Env) : Env = bl match {
 
   192 def eval_bl(bl: Block, env: Env) : Env = bl match {
 
   171   case Nil => env
 
   193   case Nil => env
 
   172   case s::bl => eval_bl(bl, eval_stmt(s, env))
 
   194   case s::bl => eval_bl(bl, eval_stmt(s, env))
 
   175 def eval(bl: Block) : Env = eval_bl(bl, Map())
 
   197 def eval(bl: Block) : Env = eval_bl(bl, Map())
 
   176 
   198 
   177 // parse + evaluate fib program; then lookup what is
 
   199 // parse + evaluate fib program; then lookup what is
 
   178 // stored under the variable result 
   200 // stored under the variable result 
   179 println(eval(Block.parse_all(fib).head)("result"))
 
   201 println(eval(Block.parse_all(fib).head)("result"))
 
       
   202 
       
   203 
       
   204 // more examles
 
       
   205 
       
   206 // calculate and print all factors bigger 
       
   207 // than 1 and smaller than n
 
       
   208 println("Factors")
 
       
   209 
       
   210 val factors =  
       
   211    """{n := 12;
 
       
   212       f := 2;
 
       
   213       while (f < n / 2 + 1) do {
 
       
   214         if ((n / f) * f == n) then  { write(f) } else { skip };
 
       
   215         f := f + 1
 
       
   216       }}""".replaceAll("\\s+", "")
 
       
   217 
       
   218 eval(Block.parse_all(factors).head)
 
       
   219 
       
   220 // calculate all prime numbers up to a number 
       
   221 println("Primes")
 
       
   222 
       
   223 val primes =  
       
   224    """{end := 100;
 
       
   225       n := 2;
 
       
   226       while (n < end) do {
 
       
   227         f := 2;
 
       
   228         tmp := 0;
 
       
   229         while ((f < n / 2 + 1) && (tmp == 0)) do {
 
       
   230           if ((n / f) * f == n) then  { tmp := 1 } else { skip };
 
       
   231           f := f + 1
 
       
   232         };
 
       
   233         if (tmp == 0) then { write(n) } else { skip };
 
       
   234         n  := n + 1
 
       
   235       }}""".replaceAll("\\s+", "")
 
       
   236 
       
   237 eval(Block.parse_all(primes).head)
afl-material