52 // the main matcher function |
52 // the main matcher function |
53 def matcher(r: Rexp, s: String) : Boolean = |
53 def matcher(r: Rexp, s: String) : Boolean = |
54 nullable(ders(s.toList, r)) |
54 nullable(ders(s.toList, r)) |
55 |
55 |
56 |
56 |
|
57 |
|
58 |
|
59 |
57 // some examples from the homework |
60 // some examples from the homework |
58 |
61 |
59 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
62 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
60 der('a', r) |
63 der('a', r) |
61 der('b', r) |
64 der('b', r) |
178 def all() = { test1(); test2() ; test3() } |
181 def all() = { test1(); test2() ; test3() } |
179 |
182 |
180 |
183 |
181 |
184 |
182 // runs with amm2 and amm3 |
185 // runs with amm2 and amm3 |
|
186 |
|
187 def pp(r: Rexp): String = r match { |
|
188 case SEQ(CHAR(a1), SEQ(r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" |
|
189 case SEQ(ONE, SEQ(r1, r2)) => s"1${pp(r1)}${pp(r2)}" |
|
190 case SEQ(ZERO, SEQ(r1, r2)) => s"0${pp(r1)}${pp(r2)}" |
|
191 case SEQ(CHAR(a1), CHAR(a2)) => s"${a1}${a2}" |
|
192 case SEQ(ONE, CHAR(a2)) => s"1${a2}" |
|
193 case SEQ(ZERO, CHAR(a2)) => s"0${a2}" |
|
194 case ZERO => "0" |
|
195 case ONE => "1" |
|
196 case CHAR(a) => a.toString |
|
197 case ALT(r1, r2) => s"(${pp(r1)} + ${pp(r2)})" |
|
198 case SEQ(r1, r2) => s"(${pp(r1)} o ${pp(r2)})" |
|
199 case STAR(r1) => s"(${pp(r1)})*" |
|
200 } |
|
201 |
|
202 |
|
203 val REG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) |
|
204 |
|
205 print(pp(ders("".toList, REG))) |
|
206 print(pp(ders("a".toList, REG))) |
|
207 print(pp(ders("aa".toList, REG))) |
|
208 print(pp(ders("aaa".toList, REG))) |
|
209 |
|
210 size(ders("".toList, REG)) // 6 |
|
211 size(ders("a".toList, REG)) // 12 |
|
212 size(ders("aa".toList, REG)) // 27 |
|
213 size(ders("aaa".toList, REG)) // 55 |
|
214 size(ders("aaaa".toList, REG)) // 98 |
|
215 size(ders("aaaaa".toList, REG)) // 169 |
|
216 size(ders("aaaaaa".toList, REG)) // 283 |
|
217 size(ders(("a" * 7).toList, REG)) // 468 |
|
218 size(ders(("a" * 8).toList, REG)) // 767 |
|
219 size(ders(("a" * 9).toList, REG)) // 1251 |
|
220 size(ders(("a" * 10).toList, REG))// 2034 |
|
221 size(ders(("a" * 11).toList, REG))// 3301 |
|
222 |
|
223 for (i <- (0 to 40)) { |
|
224 println(s"$i:" + size(ders(("a" * i).toList, REG))) |
|
225 } |