parsers.scala

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

     * @param q a parser that will be executed after `p' (this parser) succeeds
     * @return a `Parser' that -- on success -- returns a `~' (like a Pair, but easier to pattern match on) 
     *         that contains the result of `p' and that of `q'. 
     *         The resulting parser fails if either `p' or `q' fails, this failure is fatal.
     */
    def ~! [U](p: => Parser[U]): Parser[~[T, U]] 
      = OnceParser{ (for(a <- this; b <- commit(p)) yield new ~(a,b)).named("~!") }
        
    /** A parser combinator for alternative composition 
     *
     *<p>`p | q' succeeds if `p' succeeds or `q' succeeds
     *          Note that `q' is only tried if `p's failure is non-fatal (i.e., back-tracking is
     *          allowed).</p>
     * 
     * @param q a parser that will be executed if `p' (this parser) fails (and allows back-tracking)
     * @return a `Parser' that returns the result of the first parser to succeed (out of `p' and `q')
     *         The resulting parser succeeds if (and only if) <ul>
     *           <li> `p' succeeds, <i>or</i>  </li>
     *           <li> if `p' fails allowing back-tracking and `q' succeeds. </li> </ul>
     */
    def | [U >: T](q: => Parser[U]): Parser[U] = append(q).named("|")

    // TODO
    /** A parser combinator for alternative with longest match composition 
     *
     *<p>`p ||| q' succeeds if `p' succeeds or `q' succeeds
     *          If `p' and `q' both succeed, the parser that consumed the most
     *          characters accepts.</p>
     * 
     * @param q a parser that accepts if p consumes less characters.
     * @return a `Parser' that returns the result of the parser consuming the most characteres (out of `p' and `q').
     */
    def ||| [U >: T](q: => Parser[U]): Parser[U] = new Parser[U] {
      def apply(in: Input) = {
        val res1 = Parser.this(in)
        val res2 = q(in)
        
        (res1, res2) match {
          case (s1 @ Success(_, next1), s2 @ Success(_, next2)) => if (next2.pos < next1.pos) s1 else s2
          case (s1 @ Success(_, _), _) => s1
          case (_, s2 @ Success(_, _)) => s2
          case (e1 @ Error(_, _), _) => e1
          case (f1 @ Failure(_, next1), f2 @ Failure(_, next2)) => if (next2.pos < next1.pos) f1 else f2
          case (f1 @ Failure(_, next1), e2 @ Error(_, next2)) => if (next2.pos < next1.pos) f1 else e2
        }
      }
      override def toString = "|||"
    }

    /** A parser combinator for function application 
     *
     *<p>`p ^^ f' succeeds if `p' succeeds; it returns `f' applied to the result of `p'.</p>
     *
     * @param f a function that will be applied to this parser's result (see `map' in `ParseResult').
     * @return a parser that has the same behaviour as the current parser, but whose result is
     *         transformed by `f'.
     */
    def ^^ [U](f: T => U): Parser[U] = map(f).named(toString+"^^")
    

    def ^^^ [U](r: U): Parser[U] = ^^ (x => r)
    
    /** A parser combinator for partial function application 
     *
     *<p>`p ^? (f, error)' succeeds if `p' succeeds AND `f' is defined at the result of `p'; 
     *  in that case, it returns `f' applied to the result of `p'. If `f' is not applicable,
     *  error(the result of `p') should explain why.</p>
     *
     * @param f a partial function that will be applied to this parser's result 
     *          (see `mapPartial' in `ParseResult').
     * @param error a function that takes the same argument as `f' and produces an error message 
     *        to explain why `f' wasn't applicable
     * @return a parser that succeeds if the current parser succeeds <i>and</i> `f' is applicable 
     *         to the result. If so, the result will be transformed by `f'.     
     */
    def ^? [U](f: PartialFunction[T, U], error: T => String): Parser[U] = Parser{ in =>
      this(in).mapPartial(f, error)}.named(toString+"^?")
     
    /** A parser combinator for partial function application 
     *
     *<p>`p ^? f' succeeds if `p' succeeds AND `f' is defined at the result of `p'; 
     *  in that case, it returns `f' applied to the result of `p'.</p>
     *
     * @param f a partial function that will be applied to this parser's result 
     *          (see `mapPartial' in `ParseResult').
     * @return a parser that succeeds if the current parser succeeds <i>and</i> `f' is applicable 
     *         to the result. If so, the result will be transformed by `f'.     
     */
    def ^? [U](f: PartialFunction[T, U]): Parser[U] = ^?(f, r => "Constructor function not defined at "+r)
    
       
    /** A parser combinator that parameterises a subsequent parser with the result of this one
     *
     *<p>
     * Use this combinator when a parser depends on the result of a previous parser. `p' should be
     * a function that takes the result from the first parser and returns the second parser.</p>
     *
     *<p> `p into fq' (with `fq' typically `{x => q}') first applies `p', and then, if `p' successfully  
     *    returned result `r', applies `fq(r)' to the rest of the input. </p>
     *
     *<p> From: G. Hutton. Higher-order functions for parsing. J. Funct. Program., 2(3):323--343, 1992. </p>
     *
     * @param fq a function that, given the result from this parser, returns the second parser to be applied
     * @return a parser that succeeds if this parser succeeds (with result `x') and if then `fq(x)' succeeds
     */
    def into[U](fq: T => Parser[U]): Parser[U] = flatMap(fq)
    
    // shortcuts for combinators:
    
    /** Returns into(fq) */
    def >>[U](fq: T => Parser[U])=into(fq)
    
    
    /** Returns a parser that repeatedly parses what this parser parses
     *
     * @return rep(this) 
     */
    def * = rep(this)
    
    /** Returns a parser that repeatedly parses what this parser parses, interleaved with the `sep' parser.
     * The `sep' parser specifies how the results parsed by this parser should be combined.
     *
     * @return chainl1(this, sep) 
     */    
    def *[U >: T](sep: => Parser[(U, U) => U]) = chainl1(this, sep)
    
    // TODO: improve precedence? a ~ b*(",") = a ~ (b*(","))  should be true 
    
    /** Returns a parser that repeatedly (at least once) parses what this parser parses.
     *
     * @return rep1(this) 
     */      
    def + = rep1(this)
    
    /** Returns a parser that optionally parses what this parser parses.
     *
     * @return opt(this) 
     */       
    def ? = opt(this)
  }

  // TODO: can this implemented in ParseResult, like map?
  /** A helper method for sequential composition of (unit-)parsers
  */
  private def seq[T, U, V](p: => Input => ParseResult[T], q: => Input => ParseResult[U])
                          (compose: (T, U) => V)
                          (in: Input): ParseResult[V] 
    = p(in) match {
      case Success(x, next1) => q(next1) match {
          case Success(y, next2) => Success(compose(x, y), next2)
          case ns: NoSuccess => ns
        }
      case ns: NoSuccess => ns
    }
  
  /** Wrap a parser so that its failures become errors (the | combinator will give up as soon as 
   *  it encounters an error, on failure it simply tries the next alternative) 
   */
  def commit[T](p: => Parser[T]) = Parser{ in =>
    p(in) match{
      case s @ Success(_, _) => s
      case e @ Error(_, _) => e
      case f @ Failure(msg, next) => Error(msg, next)
    }
  }
  
	/*trait ElemFun
  case class EFCons(hd: Elem => ElemFun, tl: ElemFun) extends ElemFun
  case class EFNil(res: Boolean) extends ElemFun*/

   
  /** A parser matching input elements that satisfy a given predicate
   *
   * <p>elem(kind, p) succeeds if the input starts with an element `e' for which p(e) is true.</p>
   *
   * @param  kind   The element kind, used for error messages
   * @param  p      A predicate that determines which elements match.
   * @return 
   */
  def elem(kind: String, p: Elem => Boolean) = acceptIf(p)(inEl => kind+" expected")
   
  /** A parser that matches only the given element `e'
   *
   * <p>elem(e) succeeds if the input starts with an element `e'</p>
   *
   * @param e the `Elem' that must be the next piece of input for the returned parser to succeed
   * @return a `Parser' that succeeds if `e' is the next available input (and returns it).
   */
  def elem(e: Elem): Parser[Elem] = accept(e)
  
  
  /** A parser that matches only the given element `e' 
   *<p>
   * The method is implicit so that elements can automatically be lifted to their parsers. 
   * For example, when parsing `Token's, Identifier("new") (which is a `Token') can be used directly,
   * instead of first creating a `Parser' using accept(Identifier("new")).</p>
   *
   * @param e the `Elem' that must be the next piece of input for the returned parser to succeed
   * @return a `tParser' that succeeds if `e' is the next available input.
   */
   
  implicit def accept(e: Elem): Parser[Elem] = acceptIf(_ == e)("`"+e+"' expected but " + _ + " found")
  
  /** A parser that matches only the given list of element `es'
   *
   * <p>accept(es) succeeds if the input subsequently provides the elements in the list `es'.</p>
   *
   * @param  es the list of expected elements
   * @return a Parser that recognizes a specified list of elements
   */
  def accept[ES <% List[Elem]](es: ES): Parser[List[Elem]] = acceptSeq(es)

  /** 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] = acceptMatch(expected, f)


  def acceptIf(p: Elem => Boolean)(err: Elem => String): Parser[Elem] = Parser { in =>
    if (p(in.first)) Success(in.first, in.rest)
    else Failure(err(in.first), in)
  }
  
  def acceptMatch[U](expected: String, f: PartialFunction[Elem, U]): Parser[U] = Parser{ in => 
    if (f.isDefinedAt(in.first)) Success(f(in.first), in.rest)
    else Failure(expected+" expected", in)
  }
  
  def acceptSeq[ES <% Iterable[Elem]](es: ES): Parser[List[Elem]] = es.foldRight[Parser[List[Elem]]](success(Nil)){(x, pxs) => accept(x) ~ pxs ^^ mkList}

  /** 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) = Parser{ in => Failure(msg, in) }