17 |
17 |
18 |
18 |
19 // Parser combinators |
19 // Parser combinators |
20 // type parameter I needs to be of Seq-type |
20 // type parameter I needs to be of Seq-type |
21 // |
21 // |
22 abstract class Parser[I, T](implicit ev: I => Seq[_]) { |
22 type IsSeq[I] = I => Seq[_] |
|
23 |
|
24 /* |
|
25 abstract class Parser[I, T](using is: I => Seq[_]) { |
|
26 def parse(in: I): Set[(T, I)] |
|
27 |
|
28 def parse_all(in: I) : Set[T] = |
|
29 for ((hd, tl) <- parse(in); |
|
30 if is(tl).isEmpty) yield hd |
|
31 } |
|
32 */ |
|
33 |
|
34 |
|
35 abstract class Parser[I, T](using is: I => Seq[_]) { |
23 def parse(ts: I): Set[(T, I)] |
36 def parse(ts: I): Set[(T, I)] |
24 |
37 |
25 def parse_single(ts: I) : T = |
38 def parse_single(ts: I) : T = |
26 parse(ts).partition(_._2.isEmpty) match { |
39 parse(ts).partition(p => is(p._2).isEmpty) match { |
27 case (good, _) if !good.isEmpty => good.head._1 |
40 case (good, _) if !good.isEmpty => good.head._1 |
28 case (_, err) => { |
41 case (_, err) => { println (s"Parse Error\n${err.minBy(p => is(p._2).length)}") ; sys.exit(-1) } |
29 println (s"Parse Error\n${err.minBy(_._2.length)}") ; sys.exit(-1) } |
|
30 } |
42 } |
31 } |
43 } |
32 |
44 |
33 // convenience for writing grammar rules |
45 // convenience for writing grammar rules |
34 case class ~[+A, +B](_1: A, _2: B) |
46 case class ~[+A, +B](_1: A, _2: B) |
35 |
47 |
36 class SeqParser[I, T, S](p: => Parser[I, T], |
48 // parser combinators |
37 q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, ~[T, S]] { |
49 |
38 def parse(sb: I) = |
50 // alternative parser |
39 for ((head1, tail1) <- p.parse(sb); |
51 class AltParser[I : IsSeq, T](p: => Parser[I, T], |
40 (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2) |
52 q: => Parser[I, T]) extends Parser[I, T] { |
|
53 def parse(in: I) = p.parse(in) ++ q.parse(in) |
41 } |
54 } |
42 |
55 |
43 class AltParser[I, T](p: => Parser[I, T], |
56 // sequence parser |
44 q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] { |
57 class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], |
45 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
58 q: => Parser[I, S]) extends Parser[I, ~[T, S]] { |
|
59 def parse(in: I) = |
|
60 for ((hd1, tl1) <- p.parse(in); |
|
61 (hd2, tl2) <- q.parse(tl1)) yield (new ~(hd1, hd2), tl2) |
46 } |
62 } |
47 |
63 |
48 class FunParser[I, T, S](p: => Parser[I, T], |
64 // map parser |
49 f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] { |
65 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], |
50 def parse(sb: I) = |
66 f: T => S) extends Parser[I, S] { |
51 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
67 def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
52 } |
68 } |
53 |
69 |
54 // convenient combinators |
70 |
55 implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new { |
71 |
56 def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
72 // more convenient syntax for parser combinators |
57 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
73 extension [I : IsSeq, T](p: Parser[I, T]) { |
|
74 def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) |
58 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
75 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
|
76 def map[S](f: => T => S) = new MapParser[I, T, S](p, f) |
59 } |
77 } |
60 |
78 |
61 def ListParser[I, T, S](p: => Parser[I, T], |
79 def ListParser[I, T, S](p: => Parser[I, T], q: => Parser[I, S])(using is: I => Seq[_]): Parser[I, List[T]] = { |
62 q: => Parser[I, S])(implicit ev: I => Seq[_]): Parser[I, List[T]] = { |
80 (p ~ q ~ ListParser(p, q)).map{ case (x:T) ~ (y:S) ~ (z:List[T]) => x :: z } || |
63 (p ~ q ~ ListParser(p, q)) ==> { case x ~ _ ~ z => x :: z : List[T] } || |
81 (p.map[List[T]]{s => List(s)}) |
64 (p ==> ((s) => List(s))) |
|
65 } |
82 } |
66 |
83 |
67 case class TokParser(tok: Token) extends Parser[List[Token], Token] { |
84 case class TokParser(tok: Token) extends Parser[List[Token], Token] { |
68 def parse(ts: List[Token]) = ts match { |
85 def parse(ts: List[Token]) = ts match { |
69 case t::ts if (t == tok) => Set((t, ts)) |
86 case t::ts if (t == tok) => Set((t, ts)) |
70 case _ => Set () |
87 case _ => Set () |
71 } |
88 } |
72 } |
89 } |
73 |
90 |
74 implicit def token2tparser(t: Token) = TokParser(t) |
91 implicit def token2tparser(t: Token) : Parser[List[Token], Token] = TokParser(t) |
75 |
92 |
76 implicit def TokOps(t: Token) = new { |
93 |
|
94 extension (t: Token) { |
77 def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q) |
95 def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q) |
78 def ==>[S] (f: => Token => S) = new FunParser[List[Token], Token, S](t, f) |
96 def map[S] (f: => Token => S) = new MapParser[List[Token], Token, S](t, f) |
79 def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q) |
97 def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q) |
80 } |
98 } |
81 |
99 |
82 case object NumParser extends Parser[List[Token], Int] { |
100 case object NumParser extends Parser[List[Token], Int] { |
83 def parse(ts: List[Token]) = ts match { |
101 def parse(ts: List[Token]) = ts match { |
116 |
134 |
117 // Grammar Rules for the Fun language |
135 // Grammar Rules for the Fun language |
118 |
136 |
119 // arithmetic expressions |
137 // arithmetic expressions |
120 lazy val Exp: Parser[List[Token], Exp] = |
138 lazy val Exp: Parser[List[Token], Exp] = |
121 (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp) ==> |
139 (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp).map{ case _ ~ x ~ _ ~ y ~ _ ~ z => If(x, y, z): Exp } || |
122 { case _ ~ x ~ _ ~ y ~ _ ~ z => If(x, y, z): Exp } || |
140 (M ~ T_SEMI ~ Exp).map{ case x ~ _ ~ y => Sequence(x, y): Exp } || M |
123 (M ~ T_SEMI ~ Exp) ==> { case x ~ _ ~ y => Sequence(x, y): Exp } || M |
|
124 lazy val M: Parser[List[Token], Exp] = |
141 lazy val M: Parser[List[Token], Exp] = |
125 (T_KWD("write") ~ L) ==> { case _ ~ y => Write(y): Exp } || L |
142 (T_KWD("write") ~ L).map{ case _ ~ y => Write(y): Exp } || L |
126 lazy val L: Parser[List[Token], Exp] = |
143 lazy val L: Parser[List[Token], Exp] = |
127 (T ~ T_OP("+") ~ Exp) ==> { case x ~ _ ~ z => Aop("+", x, z): Exp } || |
144 (T ~ T_OP("+") ~ Exp).map{ case x ~ _ ~ z => Aop("+", x, z): Exp } || |
128 (T ~ T_OP("-") ~ Exp) ==> { case x ~ _ ~ z => Aop("-", x, z): Exp } || T |
145 (T ~ T_OP("-") ~ Exp).map{ case x ~ _ ~ z => Aop("-", x, z): Exp } || T |
129 lazy val T: Parser[List[Token], Exp] = |
146 lazy val T: Parser[List[Token], Exp] = |
130 (F ~ T_OP("*") ~ T) ==> { case x ~ _ ~ z => Aop("*", x, z): Exp } || |
147 (F ~ T_OP("*") ~ T).map{ case x ~ _ ~ z => Aop("*", x, z): Exp } || |
131 (F ~ T_OP("/") ~ T) ==> { case x ~ _ ~ z => Aop("/", x, z): Exp } || |
148 (F ~ T_OP("/") ~ T).map{ case x ~ _ ~ z => Aop("/", x, z): Exp } || |
132 (F ~ T_OP("%") ~ T) ==> { case x ~ _ ~ z => Aop("%", x, z): Exp } || F |
149 (F ~ T_OP("%") ~ T).map{ case x ~ _ ~ z => Aop("%", x, z): Exp } || F |
133 lazy val F: Parser[List[Token], Exp] = |
150 lazy val F: Parser[List[Token], Exp] = |
134 (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> |
151 (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN).map |
135 { case x ~ _ ~ z ~ _ => Call(x, z): Exp } || |
152 { case x ~ _ ~ z ~ _ => Call(x, z): Exp } || |
136 (T_LPAREN ~ Exp ~ T_RPAREN) ==> { case _ ~ y ~ _ => y: Exp } || |
153 (T_LPAREN ~ Exp ~ T_RPAREN).map{ case _ ~ y ~ _ => y: Exp } || |
137 IdParser ==> { case x => Var(x): Exp } || |
154 IdParser.map{ case x => Var(x): Exp } || |
138 NumParser ==> { case x => Num(x): Exp } |
155 NumParser.map{ case x => Num(x): Exp } |
139 |
156 |
140 // boolean expressions |
157 // boolean expressions |
141 lazy val BExp: Parser[List[Token], BExp] = |
158 lazy val BExp: Parser[List[Token], BExp] = |
142 (Exp ~ T_OP("==") ~ Exp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || |
159 (Exp ~ T_OP("==") ~ Exp).map{ case x ~ _ ~ z => Bop("==", x, z): BExp } || |
143 (Exp ~ T_OP("!=") ~ Exp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || |
160 (Exp ~ T_OP("!=") ~ Exp).map{ case x ~ _ ~ z => Bop("!=", x, z): BExp } || |
144 (Exp ~ T_OP("<") ~ Exp) ==> { case x ~ _ ~ z => Bop("<", x, z): BExp } || |
161 (Exp ~ T_OP("<") ~ Exp) .map{ case x ~ _ ~ z => Bop("<", x, z): BExp } || |
145 (Exp ~ T_OP(">") ~ Exp) ==> { case x ~ _ ~ z => Bop("<", z, x): BExp } || |
162 (Exp ~ T_OP(">") ~ Exp) .map{ case x ~ _ ~ z => Bop("<", z, x): BExp } || |
146 (Exp ~ T_OP("<=") ~ Exp) ==> { case x ~ _ ~ z => Bop("<=", x, z): BExp } || |
163 (Exp ~ T_OP("<=") ~ Exp).map{ case x ~ _ ~ z => Bop("<=", x, z): BExp } || |
147 (Exp ~ T_OP("=>") ~ Exp) ==> { case x ~ _ ~ z => Bop("<=", z, x): BExp } |
164 (Exp ~ T_OP("=>") ~ Exp).map{ case x ~ _ ~ z => Bop("<=", z, x): BExp } |
148 |
165 |
149 lazy val Defn: Parser[List[Token], Decl] = |
166 lazy val Defn: Parser[List[Token], Decl] = |
150 (T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(IdParser, T_COMMA) ~ T_RPAREN ~ T_OP("=") ~ Exp) ==> |
167 (T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(IdParser, T_COMMA) ~ T_RPAREN ~ T_OP("=") ~ Exp).map{ case _ ~ y ~ _ ~ w ~ _ ~ _ ~ r => Def(y, w, r): Decl } |
151 { case _ ~ y ~ _ ~ w ~ _ ~ _ ~ r => Def(y, w, r): Decl } |
|
152 |
168 |
153 lazy val Prog: Parser[List[Token], List[Decl]] = |
169 lazy val Prog: Parser[List[Token], List[Decl]] = |
154 (Defn ~ T_SEMI ~ Prog) ==> { case x ~ _ ~ z => x :: z : List[Decl] } || |
170 (Defn ~ T_SEMI ~ Prog).map{ case x ~ _ ~ z => x :: z : List[Decl] } || |
155 (Exp ==> ((s) => List(Main(s)) : List[Decl])) |
171 (Exp.map((s) => List(Main(s)) : List[Decl])) |
156 |
172 |
157 |
173 |
158 |
174 |
159 // Reading tokens and Writing parse trees |
175 // Reading tokens and Writing parse trees |
160 |
176 |