Mercurial Mercurial > hg > lexing / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
progs/scala/re.scala
changeset 34 33065bde3bbd
parent 13 62fe79ee2726
child 38 b48939cca0cf
equal deleted inserted replaced
32:fa92e8f089a2 34:33065bde3bbd 
    52   case SEQ(r1, r2) => 1 + size(r1) + size(r2)
 
    52   case SEQ(r1, r2) => 1 + size(r1) + size(r2)
 
    53   case STAR(r) => 1 + size(r)
 
    53   case STAR(r) => 1 + size(r)
 
    54   case RECD(_, r) => 1 + size(r)
 
    54   case RECD(_, r) => 1 + size(r)
 
    55 }
 
    55 }
 
    56 
    56 
       
    57 
    57 // nullable function: tests whether the regular 
    58 // nullable function: tests whether the regular 
    58 // expression can recognise the empty string
 
    59 // expression can recognise the empty string
 
    59 def nullable (r: Rexp) : Boolean = r match {
 
    60 def nullable (r: Rexp) : Boolean = r match {
 
    60   case NULL => false
 
    61   case NULL => false
 
    61   case EMPTY => true
 
    62   case EMPTY => true
 
   105   case Sequ(v1, v2) => env(v1) ::: env(v2)
 
   106   case Sequ(v1, v2) => env(v1) ::: env(v2)
 
   106   case Stars(vs) => vs.flatMap(env)
 
   107   case Stars(vs) => vs.flatMap(env)
 
   107   case Rec(x, v) => (x, flatten(v))::env(v)
 
   108   case Rec(x, v) => (x, flatten(v))::env(v)
 
   108 }
 
   109 }
 
   109 
   110 
   110 
       
   111 def mkeps(r: Rexp) : Val = r match {
 
   111 def mkeps(r: Rexp) : Val = r match {
 
   112   case EMPTY => Void
 
   112   case EMPTY => Void
 
   113   case ALT(r1, r2) => 
   113   case ALT(r1, r2) => 
   114     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
 
   114     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
 
   115   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
 
   115   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
 
   116   case STAR(r) => Stars(Nil)
 
   116   case STAR(r) => Stars(Nil)
 
   117   case RECD(x, r) => Rec(x, mkeps(r))
 
   117   case RECD(x, r) => Rec(x, mkeps(r))
 
   118 }
 
   118 }
 
   119 
   119 
       
   120 
   120 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
 
   121 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
 
   121   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   122   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   122   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
 
   123   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
 
   123   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
 
   124   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
 
   124   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
 
   125   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
 
   125   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
 
   126   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
 
   126   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
 
   127   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
 
   127   case (CHAR(d), Void) => Chr(d) 
   128   case (CHAR(d), Void) => Chr(c) 
   128   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 
   129   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 
   129 }
 
   130 }
 
   130 
       
   131 
   131 
   132 // main lexing function (produces a value)
 
   132 // main lexing function (produces a value)
 
   133 def lex(r: Rexp, s: List[Char]) : Val = s match {
 
   133 def lex(r: Rexp, s: List[Char]) : Val = s match {
 
   134   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
   134   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
   135   case c::cs => inj(r, c, lex(der(c, r), cs))
 
   135   case c::cs => inj(r, c, lex(der(c, r), cs))
 
   136 }
 
   136 }
 
   137 
   137 
   138 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)
 
   138 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)
 
   139 
   139 
   140 
   140 
   141 val r = (("1" $ "a") | (("2" $ "b") | ("3" $ "ab"))).% 
   141 
   142 env(lexing(r, "ba"))
 
   142 // some "rectification" functions for simplification
 
   143 
   143 def F_ID(v: Val): Val = v
 
   144 val r = "a" | "b"
 
   144 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
 
   145 lexing(r,"a")
 
   145 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
 
       
   146 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
 
       
   147   case Right(v) => Right(f2(v))
 
       
   148   case Left(v) => Left(f1(v))
 
       
   149 }
 
       
   150 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
 
       
   151   case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
 
       
   152 }
 
       
   153 def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v))
 
       
   154 def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void))
 
       
   155 def F_RECD(f: Val => Val) = (v:Val) => v match {
 
       
   156   case Rec(x, v) => Rec(x, f(v))
 
       
   157 }
 
       
   158 def F_ERROR(v: Val): Val = throw new Exception("error")
 
       
   159 
       
   160 // simplification of regular expressions returning also an
 
       
   161 // rectification function; no simplification under STAR 
       
   162 def simp(r: Rexp): (Rexp, Val => Val) = r match {
 
       
   163   case ALT(r1, r2) => {
 
       
   164     val (r1s, f1s) = simp(r1)
 
       
   165     val (r2s, f2s) = simp(r2)
 
       
   166     (r1s, r2s) match {
 
       
   167       case (NULL, _) => (r2s, F_RIGHT(f2s))
 
       
   168       case (_, NULL) => (r1s, F_LEFT(f1s))
 
       
   169       case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
 
       
   170                 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
       
   171     }
 
       
   172   }
 
       
   173   case SEQ(r1, r2) => {
 
       
   174     val (r1s, f1s) = simp(r1)
 
       
   175     val (r2s, f2s) = simp(r2)
 
       
   176     (r1s, r2s) match {
 
       
   177       case (NULL, _) => (NULL, F_ERROR)
 
       
   178       case (_, NULL) => (NULL, F_ERROR)
 
       
   179       case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s))
 
       
   180       case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s))
 
       
   181       case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
 
       
   182     }
 
       
   183   }
 
       
   184   case RECD(x, r1) => {
 
       
   185     val (r1s, f1s) = simp(r1)
 
       
   186     (RECD(x, r1s), F_RECD(f1s))
 
       
   187   }
 
       
   188   case r => (r, F_ID)
 
       
   189 }
 
       
   190 
       
   191 def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
 
       
   192   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
       
   193   case c::cs => {
 
       
   194     val (r_simp, f_simp) = simp(der(c, r))
 
       
   195     inj(r, c, f_simp(lex_simp(r_simp, cs)))
 
       
   196   }
 
       
   197 }
 
       
   198 
       
   199 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)
 
       
   200 
   146 
   201 
   147 // Lexing Rules for a Small While Language
 
   202 // Lexing Rules for a Small While Language
 
   148 
   203 
   149 def PLUS(r: Rexp) = r ~ r.%
 
   204 def PLUS(r: Rexp) = r ~ r.%
 
   150 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"
 
   205 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"
 
   191   println((end - start)/1.0e9)
 
   246   println((end - start)/1.0e9)
 
   192   result
 
   247   result
 
   193 }
 
   248 }
 
   194 
   249 
   195 val prog0 = """read n"""
 
   250 val prog0 = """read n"""
 
   196 env (lexing_simp(WHILE_REGS, prog0))
 
   251 env (lexing(WHILE_REGS, prog0))
 
   197 
   252 
   198 println("Next test")
 
   253 println("Next test")
 
   199 /*
 
   254 /*
 
   200 val prog1 = """read  n; write (n)"""
 
   255 val prog1 = """read  n; write (n)"""
 
   201 env (lexing_simp(WHILE_REGS, prog1))
 
   256 env (lexing(WHILE_REGS, prog1))
 
   202 
   257 
   203 val prog2 = """
 
   258 val prog2 = """
 
   204 i := 2;
 
   259 i := 2;
 
   205 max := 100;
 
   260 max := 100;
 
   206 while i < max do {
 
   261 while i < max do {
 
   220   time(lexing_acc(WHILE_REGS, prog2 * i))
 
   275   time(lexing_acc(WHILE_REGS, prog2 * i))
 
   221 }
 
   276 }
 
   222 
   277 
   223 for (i <- 1 to 100 by 10) {
 
   278 for (i <- 1 to 100 by 10) {
 
   224   print(i.toString + ":  ")
 
   279   print(i.toString + ":  ")
 
   225   time(lexing_simp(WHILE_REGS, prog2 * i))
 
   280   time(lexing(WHILE_REGS, prog2 * i))
 
   226 }
 
   281 }
 
   227 */
 
   282 */
lexing