5 // |
5 // |
6 // amm comb1.sc |
6 // amm comb1.sc |
7 |
7 |
8 |
8 |
9 // Note, in the lectures I did not show the type bound |
9 // Note, in the lectures I did not show the type bound |
10 // using is: I => Seq[_], which means that the input |
10 // I : IsSeq, which means that the input type 'I' needs |
11 // type 'I' needs to be a sequence. |
11 // to be a sequence that can be tested to be empty. |
12 |
12 |
13 type IsSeq[I] = I => Seq[?] |
13 trait IsSeq[I] { |
14 |
14 extension (i: I) def isEmpty: Boolean |
15 abstract class Parser[I: IsSeq, T](using is: IsSeq[I]) { |
15 } |
|
16 |
|
17 given IsSeq[String] = _.isEmpty |
|
18 given [I]: IsSeq[Seq[I]] = _.isEmpty |
|
19 |
|
20 |
|
21 // parser class |
|
22 //============== |
|
23 |
|
24 abstract class Parser[I : IsSeq, T] { |
16 def parse(in: I): Set[(T, I)] |
25 def parse(in: I): Set[(T, I)] |
17 |
26 |
18 def parse_all(in: I) : Set[T] = |
27 def parse_all(in: I) : Set[T] = |
19 for ((hd, tl) <- parse(in); |
28 for ((hd, tl) <- parse(in); |
20 if is(tl).isEmpty) yield hd |
29 if tl.isEmpty) yield hd |
21 } |
30 } |
22 |
|
23 |
31 |
24 // parser combinators |
32 // parser combinators |
25 |
33 //==================== |
26 |
34 |
27 // alternative parser |
35 // alternative parser |
28 class AltParser[I : IsSeq, T](p: => Parser[I, T], |
36 class AltParser[I : IsSeq, T](p: => Parser[I, T], |
29 q: => Parser[I, T]) extends Parser[I, T] { |
37 q: => Parser[I, T]) extends Parser[I, T] { |
30 def parse(in: I) = p.parse(in) ++ q.parse(in) |
38 def parse(in: I) = p.parse(in) ++ q.parse(in) |
167 println(E.parse("1 + 2 * 3")) |
175 println(E.parse("1 + 2 * 3")) |
168 println(E.parse_all("(1+2)+3")) |
176 println(E.parse_all("(1+2)+3")) |
169 println(E.parse_all("1+2+3")) |
177 println(E.parse_all("1+2+3")) |
170 |
178 |
171 |
179 |
172 // with parser combinators (and other parsing algorithms) |
180 // with parser combinators (and many other parsing algorithms) |
173 // no left-recursion is allowed, otherwise the will loop |
181 // no left-recursion is allowed, otherwise the will loop; |
174 |
182 // newer versions of Scala (3.5) will actually give a warning |
|
183 // about this |
|
184 |
|
185 /* |
175 lazy val EL: Parser[String, Int] = |
186 lazy val EL: Parser[String, Int] = |
176 ((EL ~ p"+" ~ EL).map{ case ((x, y), z) => x + z} || |
187 ((EL ~ p"+" ~ EL).map{ case ((x, y), z) => x + z} || |
177 (EL ~ p"*" ~ EL).map{ case ((x, y), z) => x * z} || |
188 (EL ~ p"*" ~ EL).map{ case ((x, y), z) => x * z} || |
178 (p"(" ~ EL ~ p")").map{ case ((x, y), z) => y} || |
189 (p"(" ~ EL ~ p")").map{ case ((x, y), z) => y} || |
179 NumParserInt) |
190 NumParserInt) |
|
191 */ |
180 |
192 |
181 // this will run forever: |
193 // this will run forever: |
182 //println(EL.parse_all("1+2+3")) |
194 //println(EL.parse_all("1+2+3")) |
183 |
195 |
184 |
196 |