Mercurial Mercurial > hg > afl-material / 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/token.scala
changeset 354 86b2aeae3e98
parent 352 1e1b0fe66107
child 426 0debe6f41396
equal deleted inserted replaced
353:b88670c5d04b 354:86b2aeae3e98 
    10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
    10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
    11 case class STAR(r: Rexp) extends Rexp 
    11 case class STAR(r: Rexp) extends Rexp 
    12 case class RECD(x: String, r: Rexp) extends Rexp
 
    12 case class RECD(x: String, r: Rexp) extends Rexp
 
    13 
    13 
    14 abstract class Val
 
    14 abstract class Val
 
    15 case object Void extends Val
 
    15 case object Empty extends Val
 
    16 case class Chr(c: Char) extends Val
 
    16 case class Chr(c: Char) extends Val
 
    17 case class Sequ(v1: Val, v2: Val) extends Val
 
    17 case class Seq(v1: Val, v2: Val) extends Val
 
    18 case class Left(v: Val) extends Val
 
    18 case class Left(v: Val) extends Val
 
    19 case class Right(v: Val) extends Val
 
    19 case class Right(v: Val) extends Val
 
    20 case class Stars(vs: List[Val]) extends Val
 
    20 case class Stars(vs: List[Val]) extends Val
 
    21 case class Rec(x: String, v: Val) extends Val
 
    21 case class Rec(x: String, v: Val) extends Val
 
    22    
    22    
    74   case c::s => ders(s, der(c, r))
 
    74   case c::s => ders(s, der(c, r))
 
    75 }
 
    75 }
 
    76 
    76 
    77 // extracts a string from value
 
    77 // extracts a string from value
 
    78 def flatten(v: Val) : String = v match {
 
    78 def flatten(v: Val) : String = v match {
 
    79   case Void => ""
 
    79   case Empty => ""
 
    80   case Chr(c) => c.toString
 
    80   case Chr(c) => c.toString
 
    81   case Left(v) => flatten(v)
 
    81   case Left(v) => flatten(v)
 
    82   case Right(v) => flatten(v)
 
    82   case Right(v) => flatten(v)
 
    83   case Sequ(v1, v2) => flatten(v1) + flatten(v2)
 
    83   case Seq(v1, v2) => flatten(v1) + flatten(v2)
 
    84   case Stars(vs) => vs.map(flatten).mkString
 
    84   case Stars(vs) => vs.map(flatten).mkString
 
    85   case Rec(_, v) => flatten(v)
 
    85   case Rec(_, v) => flatten(v)
 
    86 }
 
    86 }
 
    87 
    87 
    88 // extracts an environment from a value
 
    88 // extracts an environment from a value
 
    89 def env(v: Val) : List[(String, String)] = v match {
 
    89 def env(v: Val) : List[(String, String)] = v match {
 
    90   case Void => Nil
 
    90   case Empty => Nil
 
    91   case Chr(c) => Nil
 
    91   case Chr(c) => Nil
 
    92   case Left(v) => env(v)
 
    92   case Left(v) => env(v)
 
    93   case Right(v) => env(v)
 
    93   case Right(v) => env(v)
 
    94   case Sequ(v1, v2) => env(v1) ::: env(v2)
 
    94   case Seq(v1, v2) => env(v1) ::: env(v2)
 
    95   case Stars(vs) => vs.flatMap(env)
 
    95   case Stars(vs) => vs.flatMap(env)
 
    96   case Rec(x, v) => (x, flatten(v))::env(v)
 
    96   case Rec(x, v) => (x, flatten(v))::env(v)
 
    97 }
 
    97 }
 
    98 
    98 
    99 // injection part
 
    99 // injection part
 
   100 def mkeps(r: Rexp) : Val = r match {
 
   100 def mkeps(r: Rexp) : Val = r match {
 
   101   case EMPTY => Void
 
   101   case EMPTY => Empty
 
   102   case ALT(r1, r2) => 
   102   case ALT(r1, r2) => 
   103     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
 
   103     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
 
   104   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
 
   104   case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2))
 
   105   case STAR(r) => Stars(Nil)
 
   105   case STAR(r) => Stars(Nil)
 
   106   case RECD(x, r) => Rec(x, mkeps(r))
 
   106   case RECD(x, r) => Rec(x, mkeps(r))
 
   107 }
 
   107 }
 
   108 
   108 
   109 
   109 
   110 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
 
   110 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
 
   111   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   111   case (STAR(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
 
   112   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
 
   112   case (SEQ(r1, r2), Seq(v1, v2)) => Seq(inj(r1, c, v1), v2)
 
   113   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
 
   113   case (SEQ(r1, r2), Left(Seq(v1, v2))) => Seq(inj(r1, c, v1), v2)
 
   114   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
 
   114   case (SEQ(r1, r2), Right(v2)) => Seq(mkeps(r1), inj(r2, c, v2))
 
   115   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
 
   115   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
 
   116   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
 
   116   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
 
   117   case (CHAR(d), Void) => Chr(c) 
   117   case (CHAR(d), Empty) => Chr(c) 
   118   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 
   118   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 
   119 }
 
   119 }
 
   120 
   120 
   121 // main lexing function (produces a value)
 
   121 // main lexing function (produces a value)
 
   122 def lex(r: Rexp, s: List[Char]) : Val = s match {
 
   122 def lex(r: Rexp, s: List[Char]) : Val = s match {
 
   123   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
   123   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
 
   124   case c::cs => inj(r, c, lex(der(c, r), cs))
 
   124   case c::cs => inj(r, c, lex(der(c, r), cs))
 
   125 }
 
   125 }
 
   126 
   126 
   127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)
 
   127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)
 
       
   128 
       
   129 lexing(("ab" | "ab") ~ ("b" | EMPTY), "ab")
 
   128 
   130 
   129 // some "rectification" functions for simplification
 
   131 // some "rectification" functions for simplification
 
   130 def F_ID(v: Val): Val = v
 
   132 def F_ID(v: Val): Val = v
 
   131 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
 
   133 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
 
   132 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
 
   134 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
 
   133 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
 
   135 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
 
   134   case Right(v) => Right(f2(v))
 
   136   case Right(v) => Right(f2(v))
 
   135   case Left(v) => Left(f1(v))
 
   137   case Left(v) => Left(f1(v))
 
   136 }
 
   138 }
 
   137 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
 
   139 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
 
   138   case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
 
   140   case Seq(v1, v2) => Seq(f1(v1), f2(v2))
 
   139 }
 
   141 }
 
   140 def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v))
 
   142 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 
   141 def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void))
 
   143   (v:Val) => Seq(f1(Empty), f2(v))
 
       
   144 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 
       
   145   (v:Val) => Seq(f1(v), f2(Empty))
 
   142 def F_RECD(f: Val => Val) = (v:Val) => v match {
 
   146 def F_RECD(f: Val => Val) = (v:Val) => v match {
 
   143   case Rec(x, v) => Rec(x, f(v))
 
   147   case Rec(x, v) => Rec(x, f(v))
 
   144 }
 
   148 }
 
   145 def F_ERROR(v: Val): Val = throw new Exception("error")
 
   149 def F_ERROR(v: Val): Val = throw new Exception("error")
 
   146 
   150 
   161     val (r1s, f1s) = simp(r1)
 
   165     val (r1s, f1s) = simp(r1)
 
   162     val (r2s, f2s) = simp(r2)
 
   166     val (r2s, f2s) = simp(r2)
 
   163     (r1s, r2s) match {
 
   167     (r1s, r2s) match {
 
   164       case (NULL, _) => (NULL, F_ERROR)
 
   168       case (NULL, _) => (NULL, F_ERROR)
 
   165       case (_, NULL) => (NULL, F_ERROR)
 
   169       case (_, NULL) => (NULL, F_ERROR)
 
   166       case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s))
 
   170       case (EMPTY, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
 
   167       case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s))
 
   171       case (_, EMPTY) => (r1s, F_SEQ_Empty2(f1s, f2s))
 
   168       case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
 
   172       case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
 
   169     }
 
   173     }
 
   170   }
 
   174   }
 
   171   case RECD(x, r1) => {
 
   175   case RECD(x, r1) => {
 
   172     val (r1s, f1s) = simp(r1)
 
   176     val (r1s, f1s) = simp(r1)
 
   183   }
 
   187   }
 
   184 }
 
   188 }
 
   185 
   189 
   186 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)
 
   190 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList)
 
   187 
   191 
   188 lexing_simp(("a" + "ab") | ("b" + ""), "ab")
 
   192 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab")
 
   189 
   193 
   190 // Lexing Rules for a Small While Language
 
   194 // Lexing Rules for a Small While Language
 
   191 
   195 
   192 def PLUS(r: Rexp) = r ~ r.%
 
   196 def PLUS(r: Rexp) = r ~ r.%
 
   193 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"
 
   197 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"
afl-material