lexing: progs/scala/re-bit.scala@4e00dd2398ac (annotated)

3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	1	import scala.language.implicitConversions
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	2	import scala.language.reflectiveCalls
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	3	import scala.annotation.tailrec
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	4
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	5	abstract class Rexp
156 6a43ea9305ba updated implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 81 diff changeset	6	case object ZERO extends Rexp
6a43ea9305ba updated implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 81 diff changeset	7	case object ONE extends Rexp
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	8	case class CHAR(c: Char) extends Rexp
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	9	case class ALT(r1: Rexp, r2: Rexp) extends Rexp
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	10	case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	11	case class STAR(r: Rexp) extends Rexp
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	12
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	13	abstract class ARexp
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	14	case object AZERO extends ARexp
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	15	case class AONE(bs: List[Boolean]) extends ARexp
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	16	case class ACHAR(bs: List[Boolean], c: Char) extends ARexp
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	17	case class AALT(bs: List[Boolean], r1: ARexp, r2: ARexp) extends ARexp
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	18	case class ASEQ(bs: List[Boolean], r1: ARexp, r2: ARexp) extends ARexp
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	19	case class ASTAR(bs: List[Boolean], r: ARexp) extends ARexp
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	20
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	21	abstract class Val
156 6a43ea9305ba updated implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 81 diff changeset	22	case object Empty extends Val
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	23	case class Chr(c: Char) extends Val
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	24	case class Sequ(v1: Val, v2: Val) extends Val
13 62fe79ee2726 fixed the scala implementation Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 3 diff changeset	25	case class Left(v: Val) extends Val
62fe79ee2726 fixed the scala implementation Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 3 diff changeset	26	case class Right(v: Val) extends Val
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	27	case class Stars(vs: List[Val]) extends Val
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	28
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	29	// some convenience for typing in regular expressions
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	30	def charlist2rexp(s : List[Char]): Rexp = s match {
156 6a43ea9305ba updated implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 81 diff changeset	31	case Nil => ONE
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	32	case c::Nil => CHAR(c)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	33	case c::s => SEQ(CHAR(c), charlist2rexp(s))
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	34	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	35	implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	36
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	37	implicit def RexpOps(r: Rexp) = new {
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	38	def \| (s: Rexp) = ALT(r, s)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	39	def % = STAR(r)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	40	def ~ (s: Rexp) = SEQ(r, s)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	41	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	42
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	43	implicit def stringOps(s: String) = new {
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	44	def \| (r: Rexp) = ALT(s, r)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	45	def \| (r: String) = ALT(s, r)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	46	def % = STAR(s)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	47	def ~ (r: Rexp) = SEQ(s, r)
81 7ac7782a7318 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 78 diff changeset	48	def ~ (r: String) = SEQ(s, r)
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	49	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	50
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	51	// translation into ARexps
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	52	def fuse(bs: List[Boolean], r: ARexp) : ARexp = r match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	53	case AZERO => AZERO
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	54	case AONE(cs) => AONE(bs ++ cs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	55	case ACHAR(cs, c) => ACHAR(bs ++ cs, c)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	56	case AALT(cs, r1, r2) => AALT(bs ++ cs, r1, r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	57	case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	58	case ASTAR(cs, r) => ASTAR(bs ++ cs, r)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	59	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	60
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	61	def internalise(r: Rexp) : ARexp = r match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	62	case ZERO => AZERO
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	63	case ONE => AONE(Nil)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	64	case CHAR(c) => ACHAR(Nil, c)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	65	case ALT(r1, r2) => AALT(Nil, fuse(List(false), internalise(r1)), fuse(List(true), internalise(r2)))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	66	case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	67	case STAR(r) => ASTAR(Nil, internalise(r))
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	68	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	69
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	70	internalise(("a" \| "ab") ~ ("b" \| ""))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	71
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	72
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	73	def decode_aux(r: Rexp, bs: List[Boolean]) : (Val, List[Boolean]) = (r, bs) match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	74	case (ONE, bs) => (Empty, bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	75	case (CHAR(c), bs) => (Chr(c), bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	76	case (ALT(r1, r2), false::bs) => {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	77	val (v, bs1) = decode_aux(r1, bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	78	(Left(v), bs1)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	79	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	80	case (ALT(r1, r2), true::bs) => {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	81	val (v, bs1) = decode_aux(r2, bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	82	(Right(v), bs1)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	83	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	84	case (SEQ(r1, r2), bs) => {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	85	val (v1, bs1) = decode_aux(r1, bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	86	val (v2, bs2) = decode_aux(r2, bs1)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	87	(Sequ(v1, v2), bs2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	88	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	89	case (STAR(r), false::bs) => {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	90	val (v, bs1) = decode_aux(r, bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	91	val (Stars(vs), bs2) = decode_aux(STAR(r), bs1)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	92	(Stars(v::vs), bs2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	93	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	94	case (STAR(r), true::bs) => (Stars(Nil), bs)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	95	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	96
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	97	def decode(r: Rexp, bs: List[Boolean]) = decode_aux(r, bs) match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	98	case (v, Nil) => v
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	99	case _ => throw new Exception("Not decodable")
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	100	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	101
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	102	// nullable function: tests whether the aregular
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	103	// expression can recognise the empty string
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	104	def nullable (r: ARexp) : Boolean = r match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	105	case AZERO => false
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	106	case AONE(_) => true
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	107	case ACHAR(_,_) => false
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	108	case AALT(_, r1, r2) => nullable(r1) \|\| nullable(r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	109	case ASEQ(_, r1, r2) => nullable(r1) && nullable(r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	110	case ASTAR(_, _) => true
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	111	}
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	112
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	113	def mkepsBC(r: ARexp) : List[Boolean] = r match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	114	case AONE(bs) => bs
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	115	case AALT(bs, r1, r2) =>
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	116	if (nullable(r1)) bs ++ mkepsBC(r1) else bs ++ mkepsBC(r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	117	case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	118	case ASTAR(bs, r) => bs ++ List(true)
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	119	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	120
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	121	// derivative of a regular expression w.r.t. a character
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	122	def der (c: Char, r: ARexp) : ARexp = r match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	123	case AZERO => AZERO
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	124	case AONE(_) => AZERO
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	125	case ACHAR(bs, d) => if (c == d) AONE(bs) else AZERO
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	126	case AALT(bs, r1, r2) => AALT(bs, der(c, r1), der(c, r2))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	127	case ASEQ(bs, r1, r2) =>
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	128	if (nullable(r1)) AALT(bs, ASEQ(Nil, der(c, r1), r2), fuse(mkepsBC(r1), der(c, r2)))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	129	else ASEQ(bs, der(c, r1), r2)
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	130	case ASTAR(bs, r) => ASEQ(bs, fuse(List(false), der(c, r)), ASTAR(Nil, r))
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	131	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	132
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	133	// derivative w.r.t. a string (iterates der)
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	134	@tailrec
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	135	def ders (s: List[Char], r: ARexp) : ARexp = s match {
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	136	case Nil => r
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	137	case c::s => ders(s, der(c, r))
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	138	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	139
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	140	// main unsimplified lexing function (produces a value)
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	141	def lex(r: ARexp, s: List[Char]) : List[Boolean] = s match {
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	142	case Nil => if (nullable(r)) mkepsBC(r) else throw new Exception("Not matched")
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	143	case c::cs => lex(der(c, r), cs)
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	144	}
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	145
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	146	def lexing(r: Rexp, s: String) : Val = decode(r, lex(internalise(r), s.toList))
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	147
1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	148	// Some Tests
1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	149	//============
75 f95a405c3180 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 74 diff changeset	150
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	151	def time_needed[T](i: Int, code: => T) = {
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	152	val start = System.nanoTime()
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	153	for (j <- 1 to i) code
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	154	val end = System.nanoTime()
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	155	(end - start)/(i * 1.0e9)
75 f95a405c3180 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 74 diff changeset	156	}
f95a405c3180 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 74 diff changeset	157
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	158
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	159
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	160
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	161	val r0 = ("a" \| "ab") ~ ("b" \| "")
1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	162	println(lexing(r0, "ab"))
75 f95a405c3180 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 74 diff changeset	163
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	164	val r1 = ("a" \| "ab") ~ ("bcd" \| "cd")
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	165	println(lexing(r1, "abcd"))
78 279d0bc48308 updated the Isabelle theories with the totality proof Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 77 diff changeset	166
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	167	println(lexing((("" \| "a") ~ ("ab" \| "b")), "ab"))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	168	println(lexing((("" \| "a") ~ ("b" \| "ab")), "ab"))
4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	169	println(lexing((("" \| "a") ~ ("c" \| "ab")), "ab"))
78 279d0bc48308 updated the Isabelle theories with the totality proof Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 77 diff changeset	170
279d0bc48308 updated the Isabelle theories with the totality proof Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 77 diff changeset	171
81 7ac7782a7318 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 78 diff changeset	172
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	173	// Two Simple Tests for the While Language
1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	174	//========================================
78 279d0bc48308 updated the Isabelle theories with the totality proof Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 77 diff changeset	175
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	176	// Lexing Rules
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	177
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	178	def PLUS(r: Rexp) = r ~ r.%
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	179	val SYM = "a" \| "b" \| "c" \| "d" \| "e" \| "f" \| "g" \| "h" \| "i" \| "j" \| "k" \| "l" \| "m" \| "n" \| "o" \| "p" \| "q" \| "r" \| "s" \| "t" \| "u" \| "v" \| "w" \| "x" \| "y" \| "z"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	180	val DIGIT = "0" \| "1" \| "2" \| "3" \| "4" \| "5" \| "6" \| "7" \| "8" \| "9"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	181	val ID = SYM ~ (SYM \| DIGIT).%
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	182	val NUM = PLUS(DIGIT)
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	183	val KEYWORD : Rexp = "skip" \| "while" \| "do" \| "if" \| "then" \| "else" \| "read" \| "write" \| "true" \| "false"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	184	val SEMI: Rexp = ";"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	185	val OP: Rexp = ":=" \| "==" \| "-" \| "+" \| "*" \| "!=" \| "<" \| ">" \| "<=" \| ">=" \| "%" \| "/"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	186	val WHITESPACE = PLUS(" " \| "\n" \| "\t")
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	187	val RPAREN: Rexp = ")"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	188	val LPAREN: Rexp = "("
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	189	val BEGIN: Rexp = "{"
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	190	val END: Rexp = "}"
41 4f8a9ed0f26d updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 38 diff changeset	191	val STRING: Rexp = "\"" ~ SYM.% ~ "\""
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	192
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	193	val WHILE_REGS = (KEYWORD \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	194	ID \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	195	OP \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	196	NUM \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	197	SEMI \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	198	LPAREN \| RPAREN \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	199	BEGIN \| END \|
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	200	WHITESPACE).%
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	201
94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	202
38 b48939cca0cf slightly polished the scala file re.scala Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 34 diff changeset	203	println("prog0 test")
b48939cca0cf slightly polished the scala file re.scala Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 34 diff changeset	204
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	205	val prog0 = """read n"""
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	206	println(lexing(WHILE_REGS, prog0))
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	207
38 b48939cca0cf slightly polished the scala file re.scala Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 34 diff changeset	208	println("prog1 test")
b48939cca0cf slightly polished the scala file re.scala Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 34 diff changeset	209
3 94824659f6d7 added all toy implementations Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	210	val prog1 = """read n; write (n)"""
158 4e00dd2398ac added bit-coded version Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 157 diff changeset	211	println(lexing(WHILE_REGS, prog1))
157 1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	212
1fe44fb6d0a4 cleaned up scala code Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 156 diff changeset	213

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Fri, 01 Apr 2016 16:29:33 +0100
changeset 158	4e00dd2398ac
parent 157	progs/scala/re-simp.scala@1fe44fb6d0a4
child 159	940530087f30
permissions	-rw-r--r--