1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
package examples;
trait Tree {}
case class Var(n: String) : Tree extends Tree {}
case class Num(n: Int) : Tree extends Tree {}
case class Binop(op: Char, l: Tree, r: Tree): Tree extends Tree {}
module Parse {
trait Parser[p] {
type Result = Option[Pair[p, List[Char]]];
def apply(in: List[Char]): Result;
def filter(p: p => Boolean) = new Parser[p] {
def apply(in: List[Char]): Result = Parser.this.apply(in) match {
case Some(Pair(x, in1)) => if (p(x)) Some(Pair(x, in1)) else None()
case n => n
}
}
def map[b](f: p => b) = new Parser[b] {
def apply(in: List[Char]): Result = Parser.this.apply(in) match {
case Some(Pair(x, in1)) => Some(Pair(f(x), in1))
case None() => None()
}
}
def flatMap[b](f: p => Parser[b]) = new Parser[b] {
def apply(in: List[Char]): Result = Parser.this.apply(in) match {
case Some(Pair(x, in1)) => f(x)(in1)
case None() => None()
}
}
def ||| (def p: Parser[p]) = new Parser[p] {
def apply(in: List[Char]): Result = Parser.this.apply(in) match {
case None() => p(in)
case s => s
}
}
def &&& [b](def p: Parser[b]): Parser[b] =
for (val _ <- this; val result <- p) yield result;
}
def succeed[p](x: p) = new Parser[p] {
def apply(in: List[Char]) = Some(Pair(x, in))
}
def rep[a](p: Parser[a]): Parser[List[a]] =
rep1(p) ||| succeed(List());
def rep1[a](p: Parser[a]): Parser[List[a]] =
for (val x <- p; val xs <- rep(p)) yield x :: xs;
def opt[a](p: Parser[a]): Parser[Option[a]] =
(for (val x <- p) yield Some(x): Option[a]) ||| succeed(None(): Option[a]);
}
module ExprParser {
import Parse._;
def chrWith(p: Char => Boolean) = new Parser[Char] {
def apply(in: List[Char]): Result = in match {
case List() => None()
case (c :: in1) => if (p(c)) Some(Pair(c, in1)) else None()
}
}
def chr(c: Char): Parser[Char] = chrWith(d => d == c);
def letter: Parser[Char] = chrWith(c => c.isLetter);
def digit : Parser[Char] = chrWith(c => c.isDigit);
def ident: Parser[String] =
for (val c <- letter; val cs <- rep(letter ||| digit))
yield ((c :: cs) foldr "") {(c, s) => c+ s}
def number: Parser[Int] =
for (val d <- digit; val ds <- rep(digit))
yield ((d - '0') foldl_: ds) {(x, y) => x * 10 + (y - '0')};
def expr: Parser[Tree] =
for {
val e1 <- expr1;
val es <- rep (
for {
val op <- chr('+') ||| chr('-');
val e <- expr1
} yield (x: Tree => Binop(op, x, e))
)
} yield (e1 foldl_: es) {(x,f) => f(x)}
def expr1: Parser[Tree] =
for {
val e1 <- expr2;
val es <- rep (
for {
val op <- chr('*') ||| chr('/');
val e <- expr2
} yield (x: Tree => Binop(op, x, e))
)
} yield (e1 foldl_: es) {(x,f) => f(x)}
def expr2: Parser[Tree] =
(for { val n <- ident } yield Var(n))
||| (for { val n <- number } yield Num(n))
||| (for { val _ <- chr('('); val e <- expr; val _ <- chr(')') } yield e);
private def applyAll[a](fs: List[a => a], x: a) =
(x foldl_: fs) { (x, f) => f(x) }
}
|
