6 // some regular expressions |
6 // some regular expressions |
7 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") |
7 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") |
8 val DIGIT = RANGE("0123456789") |
8 val DIGIT = RANGE("0123456789") |
9 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) |
9 val ID = SEQ(SYM, STAR(ALT(SYM, DIGIT))) |
10 val NUM = PLUS(DIGIT) |
10 val NUM = PLUS(DIGIT) |
11 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "print") |
11 val KEYWORD = ALTS("skip", "while", "do", "if", "then", "else", "true", "false", "write") |
12 val SEMI: Rexp = ";" |
12 val SEMI: Rexp = ";" |
13 val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!", "<", ">") |
13 val OP: Rexp = ALTS(":=", "=", "-", "+", "*", "!", "<", ">") |
14 val WHITESPACE = PLUS(RANGE(" \n")) |
14 val WHITESPACE = PLUS(RANGE(" \n")) |
15 val RPAREN: Rexp = ")" |
15 val RPAREN: Rexp = ")" |
16 val LPAREN: Rexp = "(" |
16 val LPAREN: Rexp = "(" |
55 type Block = List[Stmt] |
55 type Block = List[Stmt] |
56 case object Skip extends Stmt |
56 case object Skip extends Stmt |
57 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
57 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
58 case class While(b: BExp, bl: Block) extends Stmt |
58 case class While(b: BExp, bl: Block) extends Stmt |
59 case class Assign(s: String, a: AExp) extends Stmt |
59 case class Assign(s: String, a: AExp) extends Stmt |
60 case class Print(s: String) extends Stmt |
60 case class Write(s: String) extends Stmt |
61 |
61 |
62 case class Var(s: String) extends AExp |
62 case class Var(s: String) extends AExp |
63 case class Num(i: Int) extends AExp |
63 case class Num(i: Int) extends AExp |
64 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
64 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
65 |
65 |
102 IdParser ==> Var || |
102 IdParser ==> Var || |
103 NumParser ==> Num |
103 NumParser ==> Num |
104 |
104 |
105 // boolean expressions |
105 // boolean expressions |
106 lazy val BExp: Parser[List[Token], BExp] = |
106 lazy val BExp: Parser[List[Token], BExp] = |
|
107 (T_KWD("true") ==> ((_) => True: BExp)) || |
|
108 (T_KWD("false") ==> ((_) => False: BExp)) || |
|
109 (T_LPAREN ~> BExp <~ T_RPAREN) || |
107 (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || |
110 (AExp ~ T_OP("=") ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z): BExp } || |
108 (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || |
111 (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || |
109 (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || |
112 (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || |
110 (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop(">", x, z): BExp } || |
113 (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } |
111 (T_KWD("true") ==> ((_) => True)) || |
|
112 (T_KWD("false") ==> ((_) => False: BExp)) |
|
113 |
114 |
114 lazy val Stmt: Parser[List[Token], Stmt] = |
115 lazy val Stmt: Parser[List[Token], Stmt] = |
115 (T_KWD("skip") ==> ((_) => Skip: Stmt)) || |
116 (T_KWD("skip") ==> ((_) => Skip: Stmt)) || |
116 (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } || |
117 (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } || |
117 (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==> |
118 (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==> |
118 { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } || |
119 { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } || |
119 (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || |
120 (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } || |
120 (T_KWD("print") ~ IdParser) ==> { case (x, y) => Print(y) } |
121 (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } |
121 |
122 |
122 lazy val Stmts: Parser[List[Token], Block] = |
123 lazy val Stmts: Parser[List[Token], Block] = |
123 (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } || |
124 (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } || |
124 (Stmt ==> ((s) => List(s) : Block)) |
125 (Stmt ==> ((s) => List(s) : Block)) |
125 |
126 |
133 def eval_bexp(b: BExp, env: Env) : Boolean = b match { |
134 def eval_bexp(b: BExp, env: Env) : Boolean = b match { |
134 case True => true |
135 case True => true |
135 case False => false |
136 case False => false |
136 case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
137 case Bop("=", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env) |
137 case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env)) |
138 case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env)) |
138 case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env) |
|
139 case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
139 case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
|
140 case Bop("&&", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env) |
|
141 case Bop("||", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env) |
140 } |
142 } |
141 |
143 |
142 def eval_aexp(a: AExp, env : Env) : Int = a match { |
144 def eval_aexp(a: AExp, env : Env) : Int = a match { |
143 case Num(i) => i |
145 case Num(i) => i |
144 case Var(s) => env(s) |
146 case Var(s) => env(s) |
152 case Assign(x, a) => env + (x -> eval_aexp(a, env)) |
154 case Assign(x, a) => env + (x -> eval_aexp(a, env)) |
153 case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) |
155 case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) |
154 case While(b, bl) => |
156 case While(b, bl) => |
155 if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env)) |
157 if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env)) |
156 else env |
158 else env |
157 case Print(x) => { println(env(x)); env } |
159 case Write(x) => { println(env(x)); env } |
158 } |
160 } |
159 |
161 |
160 def eval_bl(bl: Block, env: Env) : Env = bl match { |
162 def eval_bl(bl: Block, env: Env) : Env = bl match { |
161 case Nil => env |
163 case Nil => env |
162 case s::bl => eval_bl(bl, eval_stmt(s, env)) |
164 case s::bl => eval_bl(bl, eval_stmt(s, env)) |
163 } |
165 } |
164 |
166 |
165 def eval_prog(name: String) : Env = { |
167 def eval_prog(name: String) : Env = { |
166 val tks = Tok.fromFile(name) |
168 val tks = Tok.fromFile(name) |
167 val ast = Stmts.parse_all(tks).head |
169 val ast = Stmts.parse_single(tks) |
168 eval_bl(ast, Map.empty) |
170 eval_bl(ast, Map.empty) |
169 } |
171 } |
170 |
172 |
171 |
173 |
172 //examples |
174 //examples |
173 |
175 |
174 eval_prog("fib.while") |
176 eval_prog("loops.while") |
|
177 //eval_prog("fib.while") |
|
178 |
|
179 |
|
180 |
|
181 |
|
182 |
|
183 |
|
184 |
|
185 |
|
186 |