8 // |
8 // |
9 // amm re1.sc all |
9 // amm re1.sc all |
10 // |
10 // |
11 |
11 |
12 |
12 |
13 // regular expressions |
13 // regular expressions (as enum in Scala 3) |
14 abstract class Rexp |
14 enum Rexp { |
15 case object ZERO extends Rexp // matches nothing |
15 case ZERO // matches nothing |
16 case object ONE extends Rexp // matches an empty string |
16 case ONE // matches an empty string |
17 case class CHAR(c: Char) extends Rexp // matches a character c |
17 case CHAR(c: Char) // matches a character c |
18 case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative |
18 case ALT(r1: Rexp, r2: Rexp) // alternative |
19 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence |
19 case SEQ(r1: Rexp, r2: Rexp) // sequence |
20 case class STAR(r: Rexp) extends Rexp // star |
20 case STAR(r: Rexp) // star |
21 |
21 } |
|
22 import Rexp._ |
22 |
23 |
23 // nullable function: tests whether a regular |
24 // nullable function: tests whether a regular |
24 // expression can recognise the empty string |
25 // expression can recognise the empty string |
25 def nullable(r: Rexp) : Boolean = r match { |
26 def nullable(r: Rexp) : Boolean = r match { |
26 case ZERO => false |
27 case ZERO => false |
170 for (i <- 0 to 30 by 5) { |
171 for (i <- 0 to 30 by 5) { |
171 println(f"$i: ${time_needed(2, matcher(BIG, "a" * i))}%.5f") |
172 println(f"$i: ${time_needed(2, matcher(BIG, "a" * i))}%.5f") |
172 } |
173 } |
173 } |
174 } |
174 |
175 |
175 @main |
176 |
176 def all() = { test1(); test2() ; test3() } |
177 |
177 |
178 // Some code for pretty printing regexes as trees |
178 |
179 |
179 |
180 def implode(ss: Seq[String]) = ss.mkString("\n") |
180 |
181 def explode(s: String) = s.split("\n").toList |
|
182 |
|
183 def lst(s: String) : String = explode(s) match { |
|
184 case hd :: tl => implode(" └" ++ hd :: tl.map(" " ++ _)) |
|
185 case Nil => "" |
|
186 } |
|
187 |
|
188 def mid(s: String) : String = explode(s) match { |
|
189 case hd :: tl => implode(" ├" ++ hd :: tl.map(" │" ++ _)) |
|
190 case Nil => "" |
|
191 } |
|
192 |
|
193 def indent(ss: Seq[String]) : String = ss match { |
|
194 case init :+ last => implode(init.map(mid) :+ lst(last)) |
|
195 case _ => "" |
|
196 } |
|
197 |
|
198 def pp(e: Rexp) : String = e match { |
|
199 case ZERO => "0\n" |
|
200 case ONE => "1\n" |
|
201 case CHAR(c) => s"$c\n" |
|
202 case ALT(r1, r2) => "ALT\n" ++ pps(r1, r2) |
|
203 case SEQ(r1, r2) => "SEQ\n" ++ pps(r1, r2) |
|
204 case STAR(r) => "STAR\n" ++ pps(r) |
|
205 } |
|
206 def pps(es: Rexp*) = indent(es.map(pp)) |
|
207 |
|
208 |
|
209 @main |
|
210 def test4() = { |
|
211 println(pp(r2)) |
|
212 println(pp(ders("x".toList, r2))) |
|
213 println(pp(ders("xy".toList, r2))) |
|
214 println(pp(ders("xyz".toList, r2))) |
|
215 } |
|
216 |
|
217 @main |
|
218 def all() = { test1(); test2() ; test3() ; test4() } |
|
219 |
|
220 |
|
221 |
|
222 |
|
223 |
|
224 // partial derivatives produce a set of regular expressions |
|
225 def pder(c: Char, r: Rexp) : Set[Rexp] = r match { |
|
226 case ZERO => Set() |
|
227 case ONE => Set() |
|
228 case CHAR(d) => if (c == d) Set(ONE) else Set() |
|
229 case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2) |
|
230 case SEQ(r1, r2) => { |
|
231 (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++ |
|
232 (if (nullable(r1)) pder(c, r2) else Set()) |
|
233 } |
|
234 case STAR(r1) => { |
|
235 for (pr1 <- pder(c, r1)) yield SEQ(pr1, STAR(r1)) |
|
236 } |
|
237 } |
|
238 |
|
239 def pders(s: List[Char], rs: Set[Rexp]) : Set[Rexp] = s match { |
|
240 case Nil => rs |
|
241 case c::s => pders(s, rs.flatMap(pder(c, _))) |
|
242 } |
|
243 |
|
244 def pders1(s: String, r: Rexp) = pders(s.toList, Set(r)) |
|
245 |
|
246 |