30 case class Chr(c: Char) extends Val |
30 case class Chr(c: Char) extends Val |
31 case class Sequ(v1: Val, v2: Val) extends Val |
31 case class Sequ(v1: Val, v2: Val) extends Val |
32 case class Left(v: Val) extends Val |
32 case class Left(v: Val) extends Val |
33 case class Right(v: Val) extends Val |
33 case class Right(v: Val) extends Val |
34 case class Stars(vs: List[Val]) extends Val |
34 case class Stars(vs: List[Val]) extends Val |
|
35 |
35 |
36 |
|
37 def Pos(v: Val) : Set[List[Int]] = v match { |
|
38 case Empty => Set(Nil) |
|
39 case Chr(c) => Set(Nil) |
|
40 case Left(v) => Set(Nil) ++ Pos(v).map(0::_) |
|
41 case Right(v) => Set(Nil) ++ Pos(v).map(1::_) |
|
42 case Sequ(v1, v2) => Set(Nil) ++ Pos(v1).map(0::_) ++ Pos(v2).map(1::_) |
|
43 case Stars(vs) => Set(Nil) ++ vs.zipWithIndex.map{ case (v, n) => n::Pos(v) } |
|
44 } |
|
45 |
|
46 val v1 = Sequ(Chr('a'), Chr('b')) |
|
47 val ps1 = Pos(v1) |
|
48 |
|
49 val v2 = Left(Sequ(Chr('a'), Chr('b'))) |
|
50 val ps2 = Pos(v2) |
|
51 |
|
52 val v3 = Stars(List(Left(Chr('x')), Right(Left(Chr('y'))))) |
|
53 val v4 = Stars(List(Right(Right(Sequ(Chr('x'), Chr('y')))))) |
|
54 |
|
55 val ps3 = Pos(v3) |
|
56 val ps4 = Pos(v4) |
|
57 |
|
58 def At(v: Val, ps: List[Int]) : Val = (v, ps) match { |
|
59 case (v, Nil) => v |
|
60 case (Left(v), 0::ps) => At(v, ps) |
|
61 case (Right(v), 1::ps) => At(v, ps) |
|
62 case (Sequ(v1, v2), 0::ps) => At(v1, ps) |
|
63 case (Sequ(v1, v2), 1::ps) => At(v2, ps) |
|
64 case (Stars(vs), n::ps) => At(vs(n), ps) |
|
65 } |
|
66 |
|
67 ps1.map(At(v1, _)) |
|
68 ps2.map(At(v2, _)) |
|
69 |
|
70 import scala.math.Ordering.Implicits._ |
|
71 ps1.toList.sorted |
|
72 |
|
73 List(List(1, 1), List(1), List(0, 1)).sorted |
|
74 |
|
75 |
36 // nullable function: tests whether the regular |
76 // nullable function: tests whether the regular |
37 // expression can recognise the empty string |
77 // expression can recognise the empty string |
38 def nullable (r: Rexp) : Boolean = r match { |
78 def nullable (r: Rexp) : Boolean = r match { |
39 case ZERO => false |
79 case ZERO => false |
40 case ONE => true |
80 case ONE => true |