afl-material: progs/app5.scala@1a23d87d1700 (annotated)

412 1cef3924f7a2 updated Christian Urban <urbanc@in.tum.de> parents: 399 diff changeset	1	def nullable(r: Rexp) : Boolean = r match {
399 5c1fbb39c93e updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 261 diff changeset	2	case ZERO => false
5c1fbb39c93e updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 261 diff changeset	3	case ONE => true
7 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
412 1cef3924f7a2 updated Christian Urban <urbanc@in.tum.de> parents: 399 diff changeset	10	def der(c: Char, r: Rexp) : Rexp = r match {
399 5c1fbb39c93e updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 261 diff changeset	11	case ZERO => ZERO
5c1fbb39c93e updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 261 diff changeset	12	case ONE => ZERO
5c1fbb39c93e updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 261 diff changeset	13	case CHAR(d) => if (c == d) ONE else ZERO
261 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
412 1cef3924f7a2 updated Christian Urban <urbanc@in.tum.de> parents: 399 diff changeset	21	def ders(s: List[Char], r: Rexp) : Rexp = s match {
261 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
764 6718ef6143b8 updated Christian Urban <christian.urban@kcl.ac.uk> parents: 412 diff changeset	26	def matcher(r: Rexp, s: String) : Boolean =
261 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.urban@kcl.ac.uk>
	Mon, 20 Oct 2025 22:18:21 +0200
changeset 1013	1a23d87d1700
parent 764	6718ef6143b8
permissions	-rw-r--r--