equal
deleted
inserted
replaced
1 // A Version with an explicit n-times regular expression; |
1 // A Version of the matcher with an explicit |
|
2 // n-times regular expression |
|
3 // |
2 // this keeps the size of the regular expression in the |
4 // this keeps the size of the regular expression in the |
3 // EVIL1 test-case quite small |
5 // EVIL1 testcase small |
4 // |
6 // |
5 // call the test cases with X = {1,2} |
7 // call the test cases with X = {1,2} |
6 // |
8 // |
7 // amm re2.sc testX |
9 // amm re2.sc testX |
8 // |
10 // |
29 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
31 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
30 case STAR(_) => true |
32 case STAR(_) => true |
31 case NTIMES(r, n) => if (n == 0) true else nullable(r) |
33 case NTIMES(r, n) => if (n == 0) true else nullable(r) |
32 } |
34 } |
33 |
35 |
34 |
|
35 def der(c: Char, r: Rexp) : Rexp = r match { |
36 def der(c: Char, r: Rexp) : Rexp = r match { |
36 case ZERO => ZERO |
37 case ZERO => ZERO |
37 case ONE => ZERO |
38 case ONE => ZERO |
38 case CHAR(d) => if (c == d) ONE else ZERO |
39 case CHAR(d) => if (c == d) ONE else ZERO |
39 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
40 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
52 |
53 |
53 def matcher(r: Rexp, s: String) : Boolean = |
54 def matcher(r: Rexp, s: String) : Boolean = |
54 nullable(ders(s.toList, r)) |
55 nullable(ders(s.toList, r)) |
55 |
56 |
56 |
57 |
|
58 // Test Cases |
|
59 |
57 // the optional regular expression: one or zero times |
60 // the optional regular expression: one or zero times |
58 // this regular expression is still defined in terms of ALT |
61 // this regular expression is still defined in terms of ALT |
59 def OPT(r: Rexp) = ALT(r, ONE) |
62 def OPT(r: Rexp) = ALT(r, ONE) |
60 |
63 |
61 |
|
62 // Test Cases |
|
63 |
64 |
64 // evil regular expressions |
65 // evil regular expressions |
65 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
66 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
66 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
67 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
67 |
68 |
88 @arg(doc = "Test (a*)* b") |
89 @arg(doc = "Test (a*)* b") |
89 @main |
90 @main |
90 def test2() = { |
91 def test2() = { |
91 println("Test (a*)* b") |
92 println("Test (a*)* b") |
92 |
93 |
93 for (i <- 0 to 30 by 2) { |
94 for (i <- 0 to 22 by 2) { |
94 println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f") |
95 println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f") |
95 } |
96 } |
96 } |
97 } |
97 |
98 |
98 // the size of a regular expressions - for testing purposes |
99 // the size of a regular expressions - for testing purposes |