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
116
117
118
119
120
121
122
123
124
125
|
package examples;
abstract class Parsers {
type intype;
trait Parser[a] {
type Result = Option[Pair[a, intype]];
def apply(in: intype): Result;
def filter(pred: a => boolean) = new Parser[a] {
def apply(in: intype): Result = Parser.this.apply(in) match {
case None => None
case Some(Pair(x, in1)) => if (pred(x)) Some(Pair(x, in1)) else None
}
}
def map[b](f: a => b) = new Parser[b] {
def apply(in: intype): Result = Parser.this.apply(in) match {
case None => None
case Some(Pair(x, in1)) => Some(Pair(f(x), in1))
}
}
def flatMap[b](f: a => Parser[b]) = new Parser[b] {
def apply(in: intype): Result = Parser.this.apply(in) match {
case None => None
case Some(Pair(x, in1)) => f(x).apply(in1)
}
}
def ||| (def p: Parser[a]) = new Parser[a] {
def apply(in: intype): 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 x <- p) yield x;
}
def succeed[a](x: a) = new Parser[a] {
def apply(in: intype): Result = 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[List[a]] =
(for (val x <- p) yield List(x)) ||| succeed(List());
}
abstract class CharParsers extends Parsers {
def any: Parser[char];
def chr(ch: char) =
for (val c <- any; c == ch) yield c;
def chr(p: char => boolean) =
for (val c <- any; p(c)) yield c;
}
abstract class Tree{}
case class Id (s: String) extends Tree {}
case class Num(n: int) extends Tree {}
case class Lst(elems: List[Tree]) extends Tree {}
abstract class ListParsers extends CharParsers {
def ident: Parser[Tree] =
for (
val c: char <- chr(Character.isLetter);
val cs: List[char] <- rep(chr(Character.isLetterOrDigit))
) yield Id((c :: cs).mkString("", "", ""));
def number: Parser[Tree] =
for (
val d: char <- chr(Character.isDigit);
val ds: List[char] <- rep(chr(Character.isDigit))
) yield Num(((d - '0') /: ds) ((x, digit) => x * 10 + digit - '0'));
def list: Parser[Tree] =
for (
val _ <- chr('(');
val es <- listElems ||| succeed(List());
val _ <- chr(')')
) yield Lst(es);
def listElems: Parser[List[Tree]] =
for (
val x <- expr;
val xs <- chr(',') &&& listElems ||| succeed(List())
) yield x :: xs;
def expr: Parser[Tree] =
list ||| ident ||| number;
}
class ParseString(s: String) extends Parsers {
type intype = int;
val input = 0;
def any = new Parser[char] {
def apply(in: int): Parser[char]#Result =
if (in < s.length()) Some(Pair(s charAt in, in + 1)) else None;
}
}
object Test {
def main(args: Array[String]): unit =
System.out.println(
if (args.length == 1) {
val ps = new ListParsers with ParseString(args(0));
ps.expr(ps.input) match {
case Some(Pair(list, _)) => System.out.println("parsed: " + list);
case None => "nothing parsed"
}
} else "usage: java examples.Test <expr-string>"
);
}
|
