parsers.scala

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

      
      while(!these.isEmpty && in.first == these.head) {
        these = these.tail
        in = in.rest
      }
       
      if (these.isEmpty) Success((), in)
      else Failure("Expected: '"+these.head+"', found: '"+in.first+"'", in0)
    }
  }    

  /** The parser that matches an element in the domain of the partial function `f'
   *<p>
   * If `f' is defined on the first element in the input, `f' is applied to it to produce 
   * this parser's result.</p>
   *<p>
   * Example: The parser <code>accept("name", {case Identifier(n) => Name(n)})</code> 
   *          accepts an <code>Identifier(n)</code> and returns a <code>Name(n)</code>.</p>
   *
   * @param expected a description of the kind of element this parser expects (for error messages)
   * @param f a partial function that determines when this parser is successful and what its output is
   * @return A parser that succeeds if `f' is applicable to the first element of the input, 
   *         applying `f' to it to produce the result.
   */
  def accept[U](expected: String, f: PartialFunction[Elem, U]): Parser[U] = new Parser[U] {
    def apply(in: Input) =
      if (f.isDefinedAt(in.first)) Success(f(in.first), in.rest)
      else Failure(expected+" expected", in)
  }

  /** A parser that always fails 
   *
   * @param msg The error message describing the failure. 
   * @return A parser that always fails with the specified error message.
   */
  def failure(msg: String) = new Parser[Nothing] {
    def apply(in: Input) = Failure(msg, in)
  }

  /** A unit-parser that always fails 
   *
   * @param msg The error message describing the failure. 
   * @return A parser that always fails with the specified error message.
   */  
  def fail(msg: String) = new UnitParser {
    def apply(in: Input) = Failure(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) = new Parser[T] {
    def apply(in: Input) = Success(v, in)
  }

  /** A unit-parser that always succeeds  */
  def success = new UnitParser {
    def apply(in: Input) = Success((), in)
  }
  
  /** A unit-parser that always succeeds, discarding `p's result
  *
  * @param p The parser whose result is to be discarded
  * @return A parser that always succeeds, with the empty result
  */
  implicit def discard[T](p: => Parser[T]) = new UnitParser {
    def apply(in: Input) = p(in) map {(x) => ()}
  }
  
  
  def log[T](p: => Parser[T])(name: String): Parser[T] = new Parser[T] {
    def apply(in: Input) = {println("trying "+name+" at "+in.pos); val r = p(in); println(name+" --> "+r); r }
  }
  
  def log[Q <% UnitParser](p: => Q)(name: String): UnitParser = new UnitParser {
    def apply(in: Input) = {println("trying "+name+" at "+in.pos); 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 repetitions.
   *  
   * <p> rep(p)   repeatedly uses `p' to parse the input until `p' fails</p>
   *
   * @param p a `Parser' that is to be applied successively to the input
   * @return A parser that repeatedly applies `p' to the input.
   */  
  def rep[Q <% UnitParser](p: => Q): UnitParser = rep1(p) | success
    
  /** 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 `UnitParser' 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.
   */
  def repsep[T, Q <% UnitParser](p: => Parser[T], q: => Q): 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]] = first ~ rep(p) ^^ { case ~(x, xs) => x :: xs }
  
  /* new Parser[List[T]] {
    def apply(in0: Input) = {
      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)
      }
      
      if (!xs.isEmpty) Success(xs.toList, res.next)
      else Failure("TODO", TODO)
    }
  }*/

  /** 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> rep1(p) repeatedly uses `p' to parse the input until `p' fails -- `p' must succeed at least
   *             once</p>
   *
   * @param p a `Parser' that is to be applied successively to the input
   * @return A unitparser that repeatedly applies `p' to the input
   *        (and that only succeeds if `p' matches at least once).
   */
  def rep1[Q <% UnitParser](p: => Q): UnitParser = 
    p ~ rep(p)
  
  /** A parser generator for a specified number of repetitions.
   *  
   * <p> repN(n, p)  uses `p' exactly `n' time to parse the input</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 unitparser that repeatedly applies `p' to the input
   *        (and that only succeeds if `p' matches at exactly `n' times).
   */  
  def repN[Q <% UnitParser](n: Int, p: => Q): UnitParser = 
    if(n==0) success else p ~ repN(n-1, p) 
   
  /** 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 `UnitParser' 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).
   */
  def rep1sep[T, Q <% UnitParser](first: => Parser[T], p: => Parser[T], q: => Q): Parser[List[T]] = 
    first ~ rep(q ~ p) ^^ { case x ~ y => x :: y }

  def rep1sep[T, Q <% UnitParser](p: => Parser[T], q: => Q): Parser[List[T]] = rep1sep(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.
   *
   * <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] = 
    p ~ rep(q ~ p) ^^ {case x ~ xs => xs.foldLeft(x)((a, f_b) => f_b._1(a, f_b._2))}  // ((a, {f, b}) => f(a, b)) 

  /** 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)((a, f_b) => f_b._1(a, f_b._2))}  // ((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)((f_a, b) => f_a._1(f_a._2, b))}  // (({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)


  /** Turns a unit-parser into a boolean-parser that denotes whether the unit-parser succeeded.
   */
  def opt[Q <% UnitParser](q: => Q): Parser[Boolean] = q ^^ true | success(false) 
    
    
  /** `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] = new Parser[T] {
    def apply(in: Input) = p(in) match {
      case Success(t, in1) => Success(if (t.pos == NoPosition) t setPos in.pos else t, in1)
      case ns: NoSuccess => ns
    }
  }

  /** <code>positioned</code> decorates a unit-parser so that it returns the
   *  start position of the input it consumed. 
   * 
   *  @param p a `UnitParser'.
   *  @return  A parser that has the same behaviour as `p', but which returns
   *           the start position of the input it consumed.
   */
  def positioned[Q <% UnitParser](p: => Q) = new Parser[Position] {
    def apply(in: Input) = p(in) match {
      case Success(_, in1) => Success(in.pos, in1) 
      case ns: NoSuccess => ns
    }
  }
  
  /** A parser whose ~ combinator disallows back-tracking.
   */
  trait OnceParser[+T] extends Parser[T] {
    override def ~ [U](q: => Parser[U]): Parser[~[T, U]] = new Parser[~[T, U]] with OnceParser[~[T, U]] {
      def apply(in: Input) = seq(OnceParser.this, commit(q))((x, y) => new ~(x, y))(in)
    }
    override def ~ [Q <% UnitParser](q: => Q): Parser[T] = new Parser[T] with OnceParser[T] {
      def apply(in: Input) = seq(OnceParser.this, commit(q))((x, y) => x)(in)
    }
  }
  
  /** A parser whose ~ combinator disallows back-tracking.
   */
  trait UnitOnceParser extends UnitParser {
    override def ~ [U](q: => Parser[U]): Parser[U] = new Parser[U] with OnceParser[U]{
      def apply(in: Input): ParseResult[U] = seq(UnitOnceParser.this, commit(q))((x, y) => y)(in)
    }
    override def ~ [A <% UnitParser](q: => A): UnitParser = new UnitOnceParser {
      def apply(in: Input): ParseResult[Unit] = seq(UnitOnceParser.this, commit(q))((x, y) => y)(in)
    }
  }
}