equal
deleted
inserted
replaced
56 case r => r |
56 case r => r |
57 } |
57 } |
58 |
58 |
59 |
59 |
60 // derivative w.r.t. a string (iterates der) |
60 // derivative w.r.t. a string (iterates der) |
61 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
61 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
62 case Nil => r |
62 case Nil => r |
63 case c::s => ders(s, simp(der(c, r))) |
63 case c::s => ders(s, simp(der(c, r))) |
|
64 } |
|
65 |
|
66 // derivative w.r.t. a string (iterates der) |
|
67 def dersp(s: List[Char], r: Rexp) : Rexp = s match { |
|
68 case Nil => r |
|
69 case c::s => dersp(s, der(c, r)) |
64 } |
70 } |
65 |
71 |
66 |
72 |
67 // main matcher function |
73 // main matcher function |
68 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
74 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
69 |
75 |
|
76 //tests |
|
77 val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) |
|
78 dersp("x".toList, q) |
|
79 dersp("xy".toList, q) |
|
80 dersp("xyz".toList, q) |
70 |
81 |
71 //one or zero |
82 //one or zero |
72 def OPT(r: Rexp) = ALT(r, ONE) |
83 def OPT(r: Rexp) = ALT(r, ONE) |
73 |
84 |
74 |
85 |