progs/comb2.scala
changeset 172 47b5c91eff47
child 173 7cfb7a6f7c99
equal deleted inserted replaced
171:8db273a410cc 172:47b5c91eff47
       
     1 import scala.language.implicitConversions
       
     2 import scala.language.reflectiveCalls
       
     3 
       
     4 abstract class Parser[I <% Seq[_], T] {
       
     5   def parse(ts: I): Set[(T, I)]
       
     6 
       
     7   def parse_all(ts: I) : Set[T] =
       
     8     for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head
       
     9 }
       
    10 
       
    11 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] {
       
    12   def parse(sb: I) = 
       
    13     for ((head1, tail1) <- p.parse(sb); 
       
    14          (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
       
    15 }
       
    16 
       
    17 class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
       
    18   def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
       
    19 }
       
    20 
       
    21 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
       
    22   def parse(sb: I) = 
       
    23     for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
       
    24 }
       
    25 
       
    26 case class StringParser(s: String) extends Parser[String, String] {
       
    27   def parse(sb: String) = {
       
    28     val (prefix, suffix) = sb.splitAt(s.length)
       
    29     if (prefix == s) Set((prefix, suffix)) else Set()
       
    30   }
       
    31 }
       
    32 
       
    33 case object NumParser extends Parser[String, Int] {
       
    34   val reg = "[0-9]+".r
       
    35   def parse(sb: String) = reg.findPrefixOf(sb) match {
       
    36     case None => Set()
       
    37     case Some(s) => {
       
    38       val (head, tail) = sb.splitAt(s.length)
       
    39       Set((head.toInt, tail)) 
       
    40     }
       
    41   }
       
    42 }
       
    43 
       
    44 
       
    45 implicit def string2parser(s : String) = StringParser(s)
       
    46 
       
    47 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
       
    48   def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
       
    49   def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
       
    50   def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
       
    51 }
       
    52 
       
    53 implicit def StringOps(s: String) = new {
       
    54   def || (q : => Parser[String, String]) = new AltParser[String, String](s, q)
       
    55   def || (r: String) = new AltParser[String, String](s, r)
       
    56   def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)
       
    57   def ~[S](q : => Parser[String, S]) = 
       
    58     new SeqParser[String, String, S](s, q)
       
    59   def ~ (r: String) = 
       
    60     new SeqParser[String, String, String](s, r)
       
    61 }
       
    62 
       
    63 lazy val E: Parser[String, Int] = 
       
    64   (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z} || T  
       
    65 lazy val T: Parser[String, Int] = 
       
    66   (F ~ "*" ~ T) ==> { case ((x, y), z) => x * z} || F
       
    67 lazy val F: Parser[String, Int] = 
       
    68   ("(" ~ E ~ ")") ==> { case ((x, y), z) => y} || NumParser
       
    69 
       
    70 println(E.parse_all("1+2+3"))
       
    71 println(E.parse_all("1+2*3+1"))
       
    72 
       
    73 
       
    74 // no left-recursion allowed
       
    75 lazy val EL: Parser[String, Int] = 
       
    76   ((EL ~ "+" ~ EL) ==> { case ((x, y), z) => x + z} || 
       
    77    (EL ~ "*" ~ EL) ==> { case ((x, y), z) => x * z} ||
       
    78    ("(" ~ EL ~ ")") ==> { case ((x, y), z) => y} ||
       
    79    NumParser)
       
    80 
       
    81 //println(E.parse_all("1+2+3"))
       
    82 
       
    83 
       
    84 // the abstract syntax trees for the WHILE language
       
    85 abstract class Stmt
       
    86 abstract class AExp
       
    87 abstract class BExp 
       
    88 
       
    89 type Block = List[Stmt]
       
    90 
       
    91 case object Skip extends Stmt
       
    92 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
       
    93 case class While(b: BExp, bl: Block) extends Stmt
       
    94 case class Assign(s: String, a: AExp) extends Stmt
       
    95 
       
    96 case class Var(s: String) extends AExp
       
    97 case class Num(i: Int) extends AExp
       
    98 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
       
    99 
       
   100 case object True extends BExp
       
   101 case object False extends BExp
       
   102 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
       
   103 
       
   104 
       
   105 case object IdParser extends Parser[String, String] {
       
   106   val reg = "[a-z][a-z,0-9]*".r
       
   107   def parse(sb: String) = reg.findPrefixOf(sb) match {
       
   108     case None => Set()
       
   109     case Some(s) => Set(sb.splitAt(s.length))
       
   110   }
       
   111 }
       
   112 
       
   113 lazy val AExp: Parser[String, AExp] = 
       
   114   ((Te ~ "+" ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||
       
   115    (Te ~ "-" ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || Te)  
       
   116 lazy val Te: Parser[String, AExp] = 
       
   117   (Fa ~ "*" ~ Te) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || Fa
       
   118 lazy val Fa: Parser[String, AExp] = 
       
   119   (("(" ~ AExp ~ ")") ==> { case ((x, y), z) => y } || 
       
   120    IdParser ==> ((s:String) => Var(s) :AExp) || 
       
   121    NumParser ==> ((i:Int) => Num(i) :AExp))
       
   122 
       
   123 // boolean expressions
       
   124 lazy val BExp: Parser[String, BExp] = 
       
   125   ((AExp ~ "=" ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || 
       
   126    (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 
       
   127    (AExp ~ "<" ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 
       
   128    (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z): BExp } || 
       
   129    ("true" ==> ((_) => True: BExp)) || 
       
   130    ("false" ==> ((_) => False: BExp)) ||
       
   131    ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y})
       
   132 
       
   133 lazy val Stmt: Parser[String, Stmt] =
       
   134   (("skip" ==> ((_) => Skip: Stmt)) ||
       
   135    (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||
       
   136    ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==>
       
   137     { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||
       
   138    ("while" ~ BExp ~ "do" ~ Block) ==> { case (((x, y), z), w) => While(y, w) }) 
       
   139  
       
   140 lazy val Stmts: Parser[String, Block] =
       
   141   (Stmt ~ ";" ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||
       
   142   (Stmt ==> ((s) => List(s) : Block))
       
   143 
       
   144 lazy val Block: Parser[String, Block] =
       
   145   (("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} || 
       
   146    (Stmt ==> ((s) => List(s))))
       
   147 
       
   148 
       
   149 Block.parse_all("x2:=5")
       
   150 Block.parse_all("{x:=5;y:=8}")
       
   151 Block.parse_all("if(false)then{x:=5}else{x:=10}")
       
   152 
       
   153 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}"""
       
   154 
       
   155 Block.parse_all(fib)
       
   156 
       
   157 // an interpreter for the WHILE language
       
   158 type Env = Map[String, Int]
       
   159 
       
   160 def eval_aexp(a: AExp, env : Env) : Int = a match {
       
   161   case Num(i) => i
       
   162   case Var(s) => env(s)
       
   163   case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
       
   164   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)
       
   166 }
       
   167 
       
   168 def eval_bexp(b: BExp, env: Env) : Boolean = b match {
       
   169   case True => true
       
   170   case False => false
       
   171   case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
       
   172   case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
       
   173   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)
       
   175 }
       
   176 
       
   177 def eval_stmt(s: Stmt, env: Env) : Env = s match {
       
   178   case Skip => env
       
   179   case Assign(x, a) => env + (x -> eval_aexp(a, env))
       
   180   case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 
       
   181   case While(b, bl) => 
       
   182     if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
       
   183     else env
       
   184 }
       
   185 
       
   186 def eval_bl(bl: Block, env: Env) : Env = bl match {
       
   187   case Nil => env
       
   188   case s::bl => eval_bl(bl, eval_stmt(s, env))
       
   189 }
       
   190 
       
   191 def eval(bl: Block) : Env = eval_bl(bl, Map())
       
   192 
       
   193 eval(Block.parse_all(fib).head)("result")