parser4.scala
changeset 70 e6868bd2942b
parent 64 2d625418c011
child 71 7717f20f0504
equal deleted inserted replaced
69:cc3f7908b942 70:e6868bd2942b
     1 
     1 
     2 // parser combinators with input type I and return type T
     2 // parser combinators with input type I and return type T
     3 // and memoisation
       
     4 
     3 
     5 case class SubString(s: String, l: Int, h: Int) {
     4 case class SubString(s: String, l: Int, h: Int) {
     6   def low = l
     5   def low = l
     7   def high = h
     6   def high = h
     8   def length = h - l
     7   def length = h - l
    21     for ((head, tail) <- parse(SubString(s, 0, s.length), Nil); if (tail.substring() == "")) yield head
    20     for ((head, tail) <- parse(SubString(s, 0, s.length), Nil); if (tail.substring() == "")) yield head
    22 
    21 
    23   def || (right : => Parser[T]) : Parser[T] = new AltParser(this, right)
    22   def || (right : => Parser[T]) : Parser[T] = new AltParser(this, right)
    24   def ==>[S] (f: => T => S) : Parser [S] = new FunParser(this, f)
    23   def ==>[S] (f: => T => S) : Parser [S] = new FunParser(this, f)
    25   def ~[S] (right : => Parser[S]) : Parser[(T, S)] = new SeqParser(this, right)
    24   def ~[S] (right : => Parser[S]) : Parser[(T, S)] = new SeqParser(this, right)
    26   def ~>[S] (right : => Parser[S]) : Parser[S] = this ~ right ==> (_._2)
       
    27   def <~[S] (right : => Parser[S]) : Parser[T] = this ~ right ==> (_._1)
       
    28 }
    25 }
    29 
    26 
    30 class SeqParser[T, S](p: => Parser[T], q: => Parser[S]) extends Parser[(T, S)] {
    27 class SeqParser[T, S](p: => Parser[T], q: => Parser[S]) extends Parser[(T, S)] {
    31   def parse(sb: SubString, ctxt: Ctxt) = 
    28   def parse(sb: SubString, ctxt: Ctxt) = 
    32     for ((head1, tail1) <- p.parse(sb, ctxt); 
    29     for ((head1, tail1) <- p.parse(sb, ctxt); 
    68     else if (should_trim) new IgnLst(p).parse(sb, (nt, sb)::ctxt)
    65     else if (should_trim) new IgnLst(p).parse(sb, (nt, sb)::ctxt)
    69     else p.parse(sb, (nt, sb)::ctxt)
    66     else p.parse(sb, (nt, sb)::ctxt)
    70   }
    67   }
    71 }
    68 }
    72 
    69 
       
    70 // ambigous grammar
    73 lazy val E: Parser[Int] = 
    71 lazy val E: Parser[Int] = 
    74   new CHECK("E", (E ~ "+" ~ E) ==> { case ((x, y), z) => x + z} || 
    72   new CHECK("E", (E ~ "+" ~ E) ==> { case ((x, y), z) => x + z} || 
    75                  (E ~ "*" ~ E) ==> { case ((x, y), z) => x * z} ||
    73                  (E ~ "*" ~ E) ==> { case ((x, y), z) => x * z} ||
    76                  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y} ||
    74                  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y} ||
    77                  "0" ==> { (s) => 0 } ||
    75                  "0" ==> { (s) => 0 } ||
    78                  "1" ==> { (s) => 1 } ||
    76                  "1" ==> { (s) => 1 } ||
    79                  "2" ==> { (s) => 2 } ||
    77                  "2" ==> { (s) => 2 } ||
    80                  "3" ==> { (s) => 3 })
    78                  "3" ==> { (s) => 3 })
    81 
    79 
    82 println("foo " + E.parse_all("1+2*3"))
    80 println(E.parse_all("1+2*3"))
    83 
    81 
    84 
    82 
    85 // ambiguous grammar
       
    86 
       
    87 lazy val S: Parser[String] = 
       
    88   new CHECK("S", ("1" ~ S ~ S) ==> { case ((x, y), z) => "1" + y + z} || "")
       
    89 
       
    90 lazy val S2: Parser[String] = 
       
    91   new CHECK("S2", (S2 ~ S2 ~ S2) ==> { case ((x, y), z) => x + y + z} || "1" || "")
       
    92 
       
    93 def test2(i: Int) = {
       
    94   val result = E.parse_all("1" * i)
       
    95   print(result.size + " " + result + " ")
       
    96 }
       
    97 
       
    98 def time_needed[T](i: Int, code: => T) = {
       
    99   val start = System.nanoTime()
       
   100   for (j <- 1 to i) code
       
   101   val end = System.nanoTime()
       
   102   (end - start)/(i * 1.0e9)
       
   103 }
       
   104 
       
   105 
       
   106 for (i <- 1 to 10) {
       
   107   print(i + " ")
       
   108   print("%.5f".format(time_needed(1, test2(i))))
       
   109   print("\n")
       
   110 }
       
   111