lexing: comparison progs/scala/re-annotated2.sc

equal deleted inserted replaced

-:e752d84225ec
+:8bb064045b4e
 case class ACHARSET(bs: Bits, f: Char => Boolean) extends ARexp
 // an abbreviation for binary alternatives
 def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2))
-abstract class Val
-case object Empty extends Val
-case class Chr(c: Char) extends Val
-case class Sequ(v1: Val, v2: Val) extends Val
-case class Left(v: Val) extends Val
-case class Right(v: Val) extends Val
-case class Stars(vs: List[Val]) extends Val
-case class Recd(x: String, v: Val) extends Val
 // some convenience for typing in regular expressions
 def charlist2rexp(s: List[Char]): Rexp = s match {
 case Nil => ONE
 case c::Nil => CHAR(c)
 case c::s => SEQ(CHAR(c), charlist2rexp(s))
 def % = STAR(s)
 def ~ (r: Rexp) = SEQ(s, r)
 def ~ (r: String) = SEQ(s, r)
 def $ (r: Rexp) = RECD(s, r)
 }
-def size(r: Rexp) : Int = r match {
-case ZERO => 1
-case ONE => 1
-case ALT(r1, r2) => 1 + size(r1) + size(r2)
-case SEQ(r1, r2) => 1 + size(r1) + size(r2)
-case STAR(r) => 1 + size(r)
-case RECD(_, r) => 1 + size(r)
-case CHARSET(_) => 1
-}
 // Bitcoded + Annotation
 //=======================
 // example
 // internalise(("a" | "ab") ~ ("b" | ""))
-// decoding of a value from a bitsequence
-// (this is not tail-recursive and therefore a potential bottleneck)
-def vdecode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
-case (ONE, bs) => (Empty, bs)
-case (ALT(r1, r2), Z::bs) => {
-val (v, bs1) = vdecode_aux(r1, bs)
-(Left(v), bs1)
-}
-case (ALT(r1, r2), S::bs) => {
-val (v, bs1) = vdecode_aux(r2, bs)
-(Right(v), bs1)
-}
-case (SEQ(r1, r2), bs) => {
-val (v1, bs1) = vdecode_aux(r1, bs)
-val (v2, bs2) = vdecode_aux(r2, bs1)
-(Sequ(v1, v2), bs2)
-}
-case (STAR(r1), Z::bs) => {
-val (v, bs1) = vdecode_aux(r1, bs)
-val (Stars(vs), bs2) = vdecode_aux(STAR(r1), bs1)
-(Stars(v::vs), bs2)
-}
-case (STAR(_), S::bs) => (Stars(Nil), bs)
-case (RECD(s, r1), bs) =>
-val (v, bs1) = vdecode_aux(r1, bs)
-(Recd(s, v), bs1)
-case (CHARSET(_), C(c)::bs) => (Chr(c), bs)
-}
-def vdecode(r: Rexp, bs: Bits) = vdecode_aux(r, bs) match {
-case (v, Nil) => v
-case _ => throw new Exception("Not decodable")
-}
 // decoding of sequence of string tokens from a bitsequence
-// tail-recursive version using an accumulator (alternative for
+// tail-recursive version using an accumulator
-// vdecode)
 @tailrec
 def sdecode_aux(rs: List[Rexp], bs: Bits, acc: List[String]) : List[String] = (rs, bs) match {
 case (Nil, _) => acc
 case (_, Nil) => acc
 case (ONE::rest, bs) => sdecode_aux(rest, bs, acc)
 case ACHARSET(bs, f) => if(f(c)) AONE(bs :+ C(c)) else AZERO
 }
 // derivative w.r.t. a string (iterates bder)
 @tailrec
-def bders (s: List[Char], r: ARexp) : ARexp = s match {
+def bders(s: List[Char], r: ARexp) : ARexp = s match {
 case Nil => r
 case c::s => bders(s, bder(c, r))
 }
 // main unsimplified lexing function (produces a bitsequence)
 case Nil => if (bnullable(r)) bmkeps(r) else throw new Exception("Not matched")
 case c::cs => blex(bder(c, r), cs)
 }
 // calls blex and decodes the value
-def blexing(r: Rexp, s: String) : Val =
+def blexing(r: Rexp, s: String) =
-vdecode(r, blex(internalise(r), s.toList))
+sdecode(r, blex(internalise(r), s.toList))
 // example by Tudor
 //val reg = (STAR("a") ~ ("b" | "c")).%
 case Nil => if (bnullable(r)) bmkeps(r)
 else throw new Exception("Not matched")
 case c::cs => blex_simp(bsimp(bder(c, r)), cs)
 }
-// blexing_simp decodes a value from the bitsequence (potentially slow)
+// blexing_simp decodes a string-list from the bitsequence
-// blexing2_simp decodes a string-list from the bitsequence
+def blexing_simp(r: Rexp, s: String) : List[String] =
-def blexing_simp(r: Rexp, s: String) : Val =
-vdecode(r, blex_simp(internalise(r), s.toList))
-def blexing2_simp(r: Rexp, s: String) : List[String] =
 sdecode(r, blex_simp(internalise(r), s.toList))
 //println(blexing_simp(reg, "aab"))
-// extracts a string from value
-def flatten(v: Val) : String = v match {
+def size(r: Rexp) : Int = r match {
-case Empty => ""
+case ZERO => 1
-case Chr(c) => c.toString
+case ONE => 1
-case Left(v) => flatten(v)
+case CHARSET(_) => 1
-case Right(v) => flatten(v)
+case ALT(r1, r2) => 1 + size(r1) + size(r2)
-case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+case SEQ(r1, r2) => 1 + size(r1) + size(r2)
-case Stars(vs) => vs.map(flatten).mkString
+case STAR(r) => 1 + size(r)
-}
+case RECD(_, r) => 1 + size(r)
+}
-// extracts an environment from a value
-def env(v: Val) : List[(String, String)] = v match {
+def bsize(r: ARexp) = size(erase(r))
-case Empty => Nil
-case Chr(c) => Nil
-case Left(v) => env(v)
-case Right(v) => env(v)
-case Sequ(v1, v2) => env(v1) ::: env(v2)
-case Stars(vs) => vs.flatMap(env)
-case Recd(x, v) => (x, flatten(v))::env(v)
-}
-def bsize(a: ARexp) = size(erase(a))
 // Some Tests
 //============
 def time_needed[T](i: Int, code: => T) = {
 val start = System.nanoTime()
 for (j <- 1 to i) code
 val end = System.nanoTime()
 (end - start)/(i * 1.0e9)
 }
+val ones = SEQ(SEQ(CHAR('/'), CHAR('*')), SEQ(STAR(CHAR('1')), SEQ(CHAR('*'), CHAR('/'))))
+println("sizes unsimplified")
+println(bsize(bders("/*".toList, internalise(ones))))     // 12
+println(bsize(bders("/*1".toList, internalise(ones))))    // 25
+println(bsize(bders("/*11".toList, internalise(ones))))   // 34
+println(bsize(bders("/*111".toList, internalise(ones))))  // 43
+println(bsize(bders("/*1111".toList, internalise(ones)))) // 52
+println("sizes simplified")
+println(bsize(bsimp(bders("/*".toList, internalise(ones)))))     // 6
+println(bsize(bsimp(bders("/*1".toList, internalise(ones)))))    // 6
+println(bsize(bsimp(bders("/*11".toList, internalise(ones)))))   // 6
+println(bsize(bsimp(bders("/*111".toList, internalise(ones)))))  // 6
+println(bsize(bsimp(bders("/*1111".toList, internalise(ones))))) // 6
+println("ones:")
+for(i <- 0 to 10000 by 1000) {
+println(s"$i: ${time_needed(1, blexing_simp(ones, "/*" ++ "1" * i ++ "*/"))}")
+}
+System.exit(1)
 val evil1 = STAR(STAR("a")) ~ "b"
 val evil2 = STAR(STAR(STAR("a"))) ~ "b"
 val evil3 = STAR("aa" | "a")
-/*
 println("evil1")
 for(i <- 0 to 10000 by 1000) {
-println(time_needed(1, blexing2_simp(evil1, "a"*i ++ "b")))
+println(time_needed(1, blexing_simp(evil1, "a" * i ++ "b")))
 }
-*/
-/*
 println("evil2")
 for(i <- 0 to 10000 by 1000) {
-println(time_needed(1, blexing2_simp(evil2, "a"*i ++ "b")))
+println(time_needed(1, blexing_simp(evil2, "a" * i ++ "b")))
 }
-*/
-/*
 println("evil3")
 for(i <- 0 to 10000 by 1000) {
-println(time_needed(1, blexing2_simp(evil3, "a"*i)))
+println(time_needed(1, blexing_simp(evil3, "a" * i)))
 }
-*/
 // WHILE LANGUAGE
 //================
 def PLUS(r: Rexp) = r ~ r.%
 def RANGE(s: String) = CHARSET(s.toSet)
 ("w" $ WHITESPACE)).%
 // Some Simple While Tests
 //========================
+println("WHILE TESTS")
 val prog0 = """read n"""
 println(s"test: $prog0")
-println(env(blexing_simp(WHILE_REGS, prog0)))
+println(blexing_simp(WHILE_REGS, prog0))
-println(blexing2_simp(WHILE_REGS, prog0))
 val prog1 = """read  n; write n"""
 println(s"test: $prog1")
-println(env(blexing_simp(WHILE_REGS, prog1)))
+println(blexing_simp(WHILE_REGS, prog1))
-println(blexing2_simp(WHILE_REGS, prog1))
 val prog2 = """
 write "Fib";
 read n;
 minus1 := 0;
 write "Result";
 write minus2
 """
 println("lexing fib program (once)")
-println(blexing2_simp(WHILE_REGS, prog2).filter(s => s == "" || !s.startsWith("w")))
+println(blexing_simp(WHILE_REGS, prog2).filter(s => s == "" || !s.startsWith("w")))
 val n = 200
 println(s"lexing fib program ($n times, size ${prog2.length * n})")
-println(time_needed(1, blexing2_simp(WHILE_REGS, prog2 * n)))
+println(time_needed(1, blexing_simp(WHILE_REGS, prog2 * n)))

changeset 361	8bb064045b4e
parent 360	e752d84225ec
child 644	9f984ff20020