afl-material: progs/app5.scala@1446bc47a294 (annotated)

7 73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	1	def nullable (r: Rexp) : Boolean = r match {
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	2	case NULL => false
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	3	case EMPTY => true
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	4	case CHAR(_) => false
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	5	case ALT(r1, r2) => nullable(r1) \|\| nullable(r2)
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	6	case SEQ(r1, r2) => nullable(r1) && nullable(r2)
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	7	case STAR(_) => true
73cf4406b773 updated Christian Urban <urbanc@in.tum.de> parents: diff changeset	8	}
261 24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	9
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	10	def der (c: Char, r: Rexp) : Rexp = r match {
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	11	case NULL => NULL
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	12	case EMPTY => NULL
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	13	case CHAR(d) => if (c == d) EMPTY else NULL
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	14	case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	15	case SEQ(r1, r2) =>
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	16	if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	17	else SEQ(der(c, r1), r2)
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	18	case STAR(r) => SEQ(der(c, r), STAR(r))
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	19	}
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	20
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	21	def ders (s: List[Char], r: Rexp) : Rexp = s match {
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	22	case Nil => r
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	23	case c::s => ders(s, der(c, r))
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	24	}
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	25
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	26	def matches(r: Rexp, s: String) : Boolean =
24531cfaa36a updated handouts Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 93 diff changeset	27	nullable(ders(s.toList, r))

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Sun, 12 Oct 2014 19:39:55 +0100
changeset 272	1446bc47a294
parent 261	24531cfaa36a
child 399	5c1fbb39c93e
permissions	-rw-r--r--