|
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") |