parsers.scala

来自「JAVA 语言的函数式编程扩展」· SCALA 代码 · 共 741 行 · 第 1/3 页

  /** A parser that results in an error 
   *
   * @param msg The error message describing the failure. 
   * @return A parser that always fails with the specified error message.
   */  
  def err(msg: String) = Parser{ in => Error(msg, in) }


  /** A parser that always succeeds 
   *
   * @param v The result for the parser
   * @return A parser that always succeeds, with the given result `v'
   */
  def success[T](v: T) = Parser{ in => Success(v, in) }

  def log[T](p: => Parser[T])(name: String): Parser[T] = Parser{ in =>
    println("trying "+ name +" at "+ in)
    val r = p(in)
    println(name +" --> "+ r)
    r
  } 

  
  /** A parser generator for repetitions.
   *  
   * <p> rep(p)   repeatedly uses `p' to parse the input until `p' fails (the result is a List 
   *  of the consecutive results of `p') </p>
   *
   * @param p a `Parser' that is to be applied successively to the input
   * @return A parser that returns a list of results produced by repeatedly applying `p' to the input.
   */
  def rep[T](p: => Parser[T]): Parser[List[T]] = rep1(p) | success(List())

  /** A parser generator for interleaved repetitions.
   *  
   * <p> repsep(p, q)   repeatedly uses `p' interleaved with `q' to parse the input, until `p' fails.
   *  (The result is a `List' of the results of `p'.) </p>
   *
   * <p>Example: <code>repsep(term, ",")</code> parses a comma-separated list of term's, 
   *          yielding a list of these terms</p>
   *
   * @param p a `Parser' that is to be applied successively to the input
   * @param q a `Parser' that parses the elements that separate the elements parsed by `p'
   * @return A parser that returns a list of results produced by repeatedly applying `p' (interleaved
   *         with `q') to the input. 
   *         The results of `p' are collected in a list. The results of `q' are discarded.    
   */
  def repsep[T](p: => Parser[T], q: => Parser[Any]): Parser[List[T]] = 
    rep1sep(p, q) | success(List())
  
  /** A parser generator for non-empty repetitions.
   *  
   * <p> rep1(p) repeatedly uses `p' to parse the input until `p' fails -- `p' must succeed at least
   *             once (the result is a `List' of the consecutive results of `p')</p>
   *
   * @param p a `Parser' that is to be applied successively to the input
   * @return A parser that returns a list of results produced by repeatedly applying `p' to the input
   *        (and that only succeeds if `p' matches at least once).
   */
  def rep1[T](p: => Parser[T]): Parser[List[T]] = rep1(p, p)
  
  /** A parser generator for non-empty repetitions.
   *  
   * <p> rep1(f, p) first uses `f' (which must succeed) and then repeatedly uses `p' to 
   *     parse the input until `p' fails 
   *     (the result is a `List' of the consecutive results of `f' and `p')</p>
   *
   * @param first a `Parser' that parses the first piece of input
   * @param p a `Parser' that is to be applied successively to the rest of the input (if any)
   * @return A parser that returns a list of results produced by first applying `f' and then 
   *         repeatedly `p' to the input (it only succeeds if `f' matches).
   */
  def rep1[T](first: => Parser[T], p: => Parser[T]): Parser[List[T]] = Parser{ in0 =>
    val xs = new scala.collection.mutable.ListBuffer[T]
    var in = in0

    var res = first(in)

    while(res.successful) {
      xs += res.get
      in = res.next
      res = p(in)
    }

    // assert(res.isInstanceOf[NoSuccess])

    if (!xs.isEmpty) {
      // the next parser should start parsing where p failed, 
      // since `!p(in).successful', the next input to be consumed is `in'
      Success(xs.toList, in)  // TODO: I don't think in == res.next holds
    }
    else {
      Failure(res.asInstanceOf[NoSuccess].msg, in0)
    }
  }
  
  //= first ~ rep(p) ^^ { case ~(x, xs) => x :: xs }
  

  /** A parser generator for a specified number of repetitions.
   *  
   * <p> repN(n, p)  uses `p' exactly `n' time to parse the input 
   *       (the result is a `List' of the `n' consecutive results of `p')</p>
   *
   * @param p a `Parser' that is to be applied successively to the input
   * @param n the exact number of times `p' must succeed
   * @return A parser that returns a list of results produced by repeatedly applying `p' to the input
   *        (and that only succeeds if `p' matches exactly `n' times).
   */  
  def repN[T](n: Int, p: => Parser[T]): Parser[List[T]] = 
    if(n==0) success(Nil) else p ~ repN(n-1, p) ^^ { case ~(x, xs) => x :: xs }
  
  /** A parser generator for non-empty repetitions.
   *  
   *  <p>rep1sep(first, p, q) starts by using `first', followed by repeatedly uses of `p' interleaved with `q' 
   *                to parse the input, until `p' fails. `first' must succeed (the result is a `List' of the 
   *                consecutive results of `first' and `p')</p>
   *
   * @param first a `Parser' that is to be applied to the first element of input
   * @param p a `Parser' that is to be applied successively to the input
   * @param q a `Parser' that parses the elements that separate the elements parsed by `p' 
   *          (interleaved with `q')   
   * @return A parser that returns a list of results produced by repeatedly applying `p' to the input
   *         (and that only succeeds if `p' matches at least once).
   *         The results of `p' are collected in a list. The results of `q' are discarded.    
   */
  def rep1sep[T](p: => Parser[T], q: => Parser[Any]): Parser[List[T]] = 
    p ~ (q ~ rep1sep(p, q) ^^ { case x ~ y => y } | success(List())) ^^ { case x ~ y => x :: y }
   
  /** A parser generator that, roughly, generalises the rep1sep generator so that `q', which parses the separator,
   * produces a left-associative function that combines the elements it separates.
   *
   * <p> From: J. Fokker. Functional parsers. In J. Jeuring and E. Meijer, editors, Advanced Functional Programming, volume 925 of Lecture Notes in Computer Science, pages 1--23. Springer, 1995.</p>
   *
   * @param p a parser that parses the elements
   * @param q a parser that parses the token(s) separating the elements, yielding a left-associative function that 
   *          combines two elements into one 
   */
  def chainl1[T](p: => Parser[T], q: => Parser[(T, T) => T]): Parser[T]  
    = chainl1(p, p, q)

  /** A parser generator that, roughly, generalises the rep1sep generator so that `q', which parses the separator,
   * produces a left-associative function that combines the elements it separates.
   *
   * @param first a parser that parses the first element
   * @param p a parser that parses the subsequent elements
   * @param q a parser that parses the token(s) separating the elements, yielding a left-associative function that 
   *          combines two elements into one 
   */
  def chainl1[T, U](first: => Parser[T], p: => Parser[U], q: => Parser[(T, U) => T]): Parser[T] 
    = first ~ rep(q ~ p) ^^ {
        case x ~ xs => xs.foldLeft(x){(_, _) match {case (a, f ~ b) => f(a, b)}}
      }
        
  /** A parser generator that generalises the rep1sep generator so that `q', which parses the separator,
   * produces a right-associative function that combines the elements it separates. Additionally,
   * The right-most (last) element and the left-most combinating function have to be supplied.
   * 
   * rep1sep(p: Parser[T], q) corresponds to chainr1(p, q ^^ cons, cons, Nil) (where val cons = (x: T, y: List[T]) => x :: y)
   *
   * @param p a parser that parses the elements
   * @param q a parser that parses the token(s) separating the elements, yielding a right-associative function that 
   *          combines two elements into one 
   * @param combine the "last" (left-most) combination function to be applied
   * @param first   the "first" (right-most) element to be combined
   */
  def chainr1[T, U](p: => Parser[T], q: => Parser[(T, U) => U], combine: (T, U) => U, first: U): Parser[U]
    = p ~ rep(q ~ p) ^^ {
        case x ~ xs => (new ~(combine, x) :: xs).
                            foldRight(first){(_, _) match {case (f ~ a, b) => f(a, b)}}
      }
    
  /** A parser generator for optional sub-phrases.
   *  
   *  <p>opt(p) is a parser that returns `Some(x)' if `p' returns `x' and `None' if `p' fails</p>
   *
   * @param p A `Parser' that is tried on the input
   * @return a `Parser' that always succeeds: either with the result provided by `p' or 
   *         with the empty result
   */
  def opt[T](p: => Parser[T]): Parser[Option[T]] = 
    p ^^ (x => Some(x)) | success(None)

  /** Wrap a parser so that its failures&errors become success and vice versa -- it never consumes any input 
   */
  def not[T](p: => Parser[T]): Parser[Unit] = Parser { in =>
    p(in) match {
      case s @ Success(_, _) => Failure("Expected failure", in)
      case e @ Error(_, _) => Success((), in)
      case f @ Failure(msg, next) => Success((), in)
    }
  }  
  
  
  /** `positioned' decorates a parser's result with the start position of the input it consumed. 
   * 
   * @param p a `Parser' whose result conforms to `Positional'.
   * @return A parser that has the same behaviour as `p', but which marks its result with the 
   *         start position of the input it consumed, if it didn't already have a position.
   */
  def positioned[T <: Positional](p: => Parser[T]): Parser[T] = Parser { in =>
    p(in) match {
      case Success(t, in1) => Success(if (t.pos == NoPosition) t setPos in.pos else t, in1)
      case ns: NoSuccess => ns
    }
  }

  /** <p>
   *    A parser generator delimiting whole phrases (i.e. programs).
   *  </p>
   *  <p>
   *    <code>phrase(p)</code> succeeds if <code>p</code> succeeds and
   *    no input is left over after <code>p</code>.
   *  </p>
   *
   *  @param p the parser that must consume all input for the resulting parser
   *           to succeed.
   *  @return  a parser that has the same result as `p', but that only succeeds
   *           if <code>p</code> consumed all the input.
   */
  def phrase[T](p: Parser[T]) = new Parser[T] {
    lastNoSuccess = null
    def apply(in: Input) = p(in) match {
      case s @ Success(out, in1) =>
        if (in1.atEnd) 
          s
        else if (lastNoSuccess == null || lastNoSuccess.next.pos < in1.pos)
          Failure("end of input expected", in1)
        else 
          lastNoSuccess
      case _ => lastNoSuccess
    }
  }

  def mkList[T] = (_: ~[T, List[T]]) match { case x ~ xs => x :: xs }
  case class ~[+a, +b](_1: a, _2: b) {
    override def toString = "("+ _1 +"~"+ _2 +")"
  }

  /** A parser whose ~ combinator disallows back-tracking.
   */
  trait OnceParser[+T] extends Parser[T] {
    override def ~ [U](p: => Parser[U]): Parser[~[T, U]]
      = OnceParser{ (for(a <- this; b <- commit(p)) yield new ~(a,b)).named("~") }
  }
}