16 |
16 |
17 |
17 |
18 |
18 |
19 case class ~[+A, +B](x: A, y: B) |
19 case class ~[+A, +B](x: A, y: B) |
20 |
20 |
21 // constraint for the input |
21 abstract class Parser[I, T](using is: I => Seq[_]) { |
22 type IsSeq[A] = A => Seq[_] |
22 def parse(in: I): Set[(T, I)] |
23 |
|
24 |
|
25 abstract class Parser[I : IsSeq, T]{ |
|
26 def parse(in: I): Set[(T, I)] |
|
27 |
23 |
28 def parse_all(in: I) : Set[T] = |
24 def parse_all(in: I) : Set[T] = |
29 for ((hd, tl) <- parse(in); |
25 for ((hd, tl) <- parse(in); |
30 if tl.isEmpty) yield hd |
26 if is(tl).isEmpty) yield hd |
31 } |
27 } |
32 |
28 |
33 // parser combinators |
29 // parser combinators |
34 |
30 |
|
31 // alternative parser |
|
32 class AltParser[I, T](p: => Parser[I, T], |
|
33 q: => Parser[I, T])(using I => Seq[_]) extends Parser[I, T] { |
|
34 def parse(in: I) = p.parse(in) ++ q.parse(in) |
|
35 } |
|
36 |
35 // sequence parser |
37 // sequence parser |
36 class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], |
38 class SeqParser[I, T, S](p: => Parser[I, T], |
37 q: => Parser[I, S]) extends Parser[I, ~[T, S]] { |
39 q: => Parser[I, S])(using I => Seq[_]) extends Parser[I, ~[T, S]] { |
38 def parse(in: I) = |
40 def parse(in: I) = |
39 for ((hd1, tl1) <- p.parse(in); |
41 for ((hd1, tl1) <- p.parse(in); |
40 (hd2, tl2) <- q.parse(tl1)) yield (new ~(hd1, hd2), tl2) |
42 (hd2, tl2) <- q.parse(tl1)) yield (new ~(hd1, hd2), tl2) |
41 } |
43 } |
42 |
44 |
43 // alternative parser |
|
44 class AltParser[I : IsSeq, T](p: => Parser[I, T], |
|
45 q: => Parser[I, T]) extends Parser[I, T] { |
|
46 def parse(in: I) = p.parse(in) ++ q.parse(in) |
|
47 } |
|
48 |
|
49 // map parser |
45 // map parser |
50 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], |
46 class MapParser[I, T, S](p: => Parser[I, T], |
51 f: T => S) extends Parser[I, S] { |
47 f: T => S)(using I => Seq[_]) extends Parser[I, S] { |
52 def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
48 def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
53 } |
49 } |
54 |
50 |
55 |
51 |
56 |
52 |
87 // the following string interpolation allows us to write |
83 // the following string interpolation allows us to write |
88 // StrParser(_some_string_) more conveniently as |
84 // StrParser(_some_string_) more conveniently as |
89 // |
85 // |
90 // p"<_some_string_>" |
86 // p"<_some_string_>" |
91 |
87 |
92 implicit def parser_interpolation(sc: StringContext) = new { |
88 extension (sc: StringContext) |
93 def p(args: Any*) = StrParser(sc.s(args:_*)) |
89 def p(args: Any*) = StrParser(sc.s(args:_*)) |
94 } |
90 |
95 |
91 |
96 // more convenient syntax for parser combinators |
92 // more convenient syntax for parser combinators |
97 implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new { |
93 extension [I, T](p: Parser[I, T])(using I => Seq[_]) { |
98 def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) |
94 def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) |
99 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
95 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
100 def map[S](f: => T => S) = new MapParser[I, T, S](p, f) |
96 def mapp[S](f: => T => S) = new MapParser[I, T, S](p, f) |
101 } |
97 } |
|
98 |
102 |
99 |
103 |
100 |
104 |
101 |
105 // the abstract syntax trees for the WHILE language |
102 // the abstract syntax trees for the WHILE language |
106 abstract class Stmt |
103 abstract class Stmt |
126 case class Or(b1: BExp, b2: BExp) extends BExp |
123 case class Or(b1: BExp, b2: BExp) extends BExp |
127 |
124 |
128 |
125 |
129 // arithmetic expressions |
126 // arithmetic expressions |
130 lazy val AExp: Parser[String, AExp] = |
127 lazy val AExp: Parser[String, AExp] = |
131 (Te ~ p"+" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } || |
128 (Te ~ p"+" ~ AExp).mapp[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } || |
132 (Te ~ p"-" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te |
129 (Te ~ p"-" ~ AExp).mapp[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te |
133 lazy val Te: Parser[String, AExp] = |
130 lazy val Te: Parser[String, AExp] = |
134 (Fa ~ p"*" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } || |
131 (Fa ~ p"*" ~ Te).mapp[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } || |
135 (Fa ~ p"/" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa |
132 (Fa ~ p"/" ~ Te).mapp[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa |
136 lazy val Fa: Parser[String, AExp] = |
133 lazy val Fa: Parser[String, AExp] = |
137 (p"(" ~ AExp ~ p")").map{ case _ ~ y ~ _ => y } || |
134 (p"(" ~ AExp ~ p")").mapp{ case _ ~ y ~ _ => y } || |
138 IdParser.map(Var) || |
135 IdParser.mapp(Var) || |
139 NumParser.map(Num) |
136 NumParser.mapp(Num) |
140 |
137 |
141 // boolean expressions with some simple nesting |
138 // boolean expressions with some simple nesting |
142 lazy val BExp: Parser[String, BExp] = |
139 lazy val BExp: Parser[String, BExp] = |
143 (AExp ~ p"==" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } || |
140 (AExp ~ p"==" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } || |
144 (AExp ~ p"!=" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } || |
141 (AExp ~ p"!=" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } || |
145 (AExp ~ p"<" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } || |
142 (AExp ~ p"<" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } || |
146 (AExp ~ p">" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } || |
143 (AExp ~ p">" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } || |
147 (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } || |
144 (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).mapp[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } || |
148 (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } || |
145 (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).mapp[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } || |
149 (p"true".map[BExp]{ _ => True }) || |
146 (p"true".mapp[BExp]{ _ => True }) || |
150 (p"false".map[BExp]{ _ => False }) || |
147 (p"false".mapp[BExp]{ _ => False }) || |
151 (p"(" ~ BExp ~ p")").map[BExp]{ case _ ~ x ~ _ => x } |
148 (p"(" ~ BExp ~ p")").mapp[BExp]{ case _ ~ x ~ _ => x } |
152 |
149 |
153 // a single statement |
150 // a single statement |
154 lazy val Stmt: Parser[String, Stmt] = |
151 lazy val Stmt: Parser[String, Stmt] = |
155 ((p"skip".map[Stmt]{_ => Skip }) || |
152 ((p"skip".mapp[Stmt]{_ => Skip }) || |
156 (IdParser ~ p":=" ~ AExp).map[Stmt]{ case x ~ _ ~ z => Assign(x, z) } || |
153 (IdParser ~ p":=" ~ AExp).mapp[Stmt]{ case x ~ _ ~ z => Assign(x, z) } || |
157 (p"write(" ~ IdParser ~ p")").map[Stmt]{ case _ ~ y ~ _ => Write(y) } || |
154 (p"write(" ~ IdParser ~ p")").mapp[Stmt]{ case _ ~ y ~ _ => Write(y) } || |
158 (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block) |
155 (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block) |
159 .map[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } || |
156 .mapp[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } || |
160 (p"while" ~ BExp ~ p"do" ~ Block).map[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) }) |
157 (p"while" ~ BExp ~ p"do" ~ Block).mapp[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) }) |
161 |
158 |
162 |
159 |
163 // statements |
160 // statements |
164 lazy val Stmts: Parser[String, Block] = |
161 lazy val Stmts: Parser[String, Block] = |
165 (Stmt ~ p";" ~ Stmts).map[Block]{ case x ~ _ ~ z => x :: z } || |
162 (Stmt ~ p";" ~ Stmts).mapp[Block]{ case x ~ _ ~ z => x :: z } || |
166 (Stmt.map[Block]{ s => List(s) }) |
163 (Stmt.mapp[Block]{ s => List(s) }) |
167 |
164 |
168 // blocks (enclosed in curly braces) |
165 // blocks (enclosed in curly braces) |
169 lazy val Block: Parser[String, Block] = |
166 lazy val Block: Parser[String, Block] = |
170 ((p"{" ~ Stmts ~ p"}").map{ case _ ~ y ~ _ => y } || |
167 ((p"{" ~ Stmts ~ p"}").mapp{ case _ ~ y ~ _ => y } || |
171 (Stmt.map(s => List(s)))) |
168 (Stmt.mapp(s => List(s)))) |
172 |
169 |
173 |
170 |
174 // Examples |
171 // Examples |
175 Stmt.parse_all("x2:=5+3") |
172 Stmt.parse_all("x2:=5+3") |
176 Block.parse_all("{x:=5;y:=8}") |
173 Block.parse_all("{x:=5;y:=8}") |