parsers.scala

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

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2006-2007, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

// $Id: Parsers.scala 13912 2008-02-07 12:40:59Z moors $

package scala.util.parsing.combinatorold

import scala.util.parsing.input._
import scala.collection.mutable.{Map=>MutableMap}

// TODO: better error handling (labelling like parsec's <?>)
// TODO: memoisation (like packrat parsers?) 

/** <p>
 *    <code>Parsers</code> is a component that <i>provides</i> generic
 *    parser combinators.
 *  </p>
 *  <p>
 *    It <i>requires</i> the type of the elements these parsers should parse 
 *    (each parser is polymorphic in the type of result it produces).
 *  </p>
 *  <p>
 *    There are two aspects to the result of a parser: (1) success or failure,
 *    and (2) the result. A <code>Parser[T]</code> provides both kinds of
 *    information, but a <code>UnitParser</code> only signals success/failure.
 *    When composing a `UnitParser' with a normal <code>Parser</code>, the
 *    <code>UnitParser</code> only contributes to whether the combined parser
 *    is successful (i.e., its result is discarded).
 *  </p>
 *  <p>
 *    The term ``parser combinator'' refers to the fact that these parsers
 *    are constructed from primitive parsers and composition operators, such
 *    as sequencing, alternation, optionality, repetition, lifting, and so on.
 *  </p>
 *  <p>
 *    A ``primitive parser'' is a parser that accepts or rejects a single
 *    piece of input, based on a certain criterion, such as whether the
 *    input...
 *  </p><ul>
 *    <li> is equal to some given object, </li>
 *    <li> satisfies a certain predicate, </li>
 *    <li> is in the domain of a given partial function,.... </li>
 *  </ul>
 *  <p>
 *    Even more primitive parsers always produce the same result, irrespective
 *    of the input.
 *  </p>
 *
 * @requires Elem the type of elements the provided parsers consume 
 *              (When consuming invidual characters, a parser is typically called a ``scanner'', 
 *               which produces ``tokens'' that are consumed by what is normally called a ``parser''.
 *               Nonetheless, the same principles apply, regardless of the input type.)</p>
 *<p>
 * @provides Input = Reader[Elem] 
 *              The type of input the parsers in this component expect.</p>
 *<p>
 * @provides Parser[+T] extends (Input => ParseResult[T]) 
 *              Essentially, a `Parser[T]' is a function from `Input' to `ParseResult[T]'.</p>
 *<p>
 * @provides ParseResult[+T] is like an `Option[T]', in the sense that it is either
 *              `Success[T]', which consists of some result (:T) (and the rest of the input) or
 *              `Failure[T]', which provides an error message (and the rest of the input).</p>
 *
 * @author Martin Odersky, Iulian Dragos, Adriaan Moors 
 */
trait Parsers {
  /** the type of input elements */
  type Elem

  /** The parser input is an abstract reader of input elements */
  type Input = Reader[Elem]

  /** A base class for parser results. 
   *  A result is either successful or not (failure may be fatal, i.e.,
   *  an Error, or not, i.e., a Failure)
   *  On success, provides a result of type <code>T</code>. 
   */
  sealed abstract class ParseResult[+T] {
    /** Functional composition of ParseResults
     * 
     * @param `f' the function to be lifted over this result
     * @return `f' applied to the result of this `ParseResult', packaged up as a new `ParseResult'
     */
    def map[U](f: T => U): ParseResult[U]
    
    /** Partial functional composition of ParseResults
     * 
     * @param `f' the partial function to be lifted over this result
     * @param error a function that takes the same argument as `f' and produces an error message 
     *        to explain why `f' wasn't applicable (it is called when this is the case)
     * @return <i>if `f' f is defined at the result in this `ParseResult',</i>
     *         `f' applied to the result of this `ParseResult', packaged up as a new `ParseResult'.
     *         If `f' is not defined, `Failure'.
     */
    def mapPartial[U](f: PartialFunction[T, U], error: T => String): ParseResult[U]   
    
    def isEmpty = !successful
    
    /** Returns the embedded result */
    def get: T
    
    def getOrElse[B >: T](default: => B): B = 
        if (isEmpty) default else this.get
    
    val next: Input
    
    val successful: Boolean
  }

  /** The success case of ParseResult: contains the result and the remaining input.
   *
   *  @param result The parser's output 
   *  @param next   The parser's remaining input
   */
  case class Success[+T](result: T, override val next: Input) extends ParseResult[T] {
    def map[U](f: T => U) = Success(f(result), next)
    def mapPartial[U](f: PartialFunction[T, U], error: T => String): ParseResult[U] 
       = if(f.isDefinedAt(result)) Success(f(result), next) 
         else Failure(error(result), next)

    def get: T = result
    
    /** The toString method of a Success */
    override def toString = "["+next.pos+"] parsed: "+result
    
    val successful = true
  }

  /** A common super-class for unsuccessful parse results
   */
  sealed abstract class NoSuccess(val msg: String, override val next: Input) extends ParseResult[Nothing] { // when we don't care about the difference between Failure and Error
    val successful = false

    def map[U](f: Nothing => U) = this
    def mapPartial[U](f: PartialFunction[Nothing, U], error: Nothing => String): ParseResult[U] = this

    def get: Nothing = error("No result when parsing failed")
  }
  
  /** The failure case of ParseResult: contains an error-message and the remaining input.
   * Parsing will back-track when a failure occurs.
   *
   *  @param msg    An error message string describing the failure.
   *  @param next   The parser's unconsumed input at the point where the failure occurred.
   */
  case class Failure(override val msg: String, override val next: Input) extends NoSuccess(msg, next) {
    /** The toString method of a Failure yields an error message */
    override def toString = "["+next.pos+"] failure: "+msg+"\n\n"+next.pos.longString
  }
  
  /** The fatal failure case of ParseResult: contains an error-message and the remaining input.
   * No back-tracking is done when a parser returns an `Error' 
   *
   *  @param msg    An error message string describing the error.
   *  @param next   The parser's unconsumed input at the point where the error occurred.
   */
  case class Error(override val msg: String, override val next: Input) extends NoSuccess(msg, next) {
    /** The toString method of an Error yields an error message */
    override def toString = "["+next.pos+"] error: "+msg+"\n\n"+next.pos.longString
  }
  
  /** The root class of parsers. 
   *  Parsers are functions from the Input type to ParseResult 
   */
  abstract class Parser[+T] extends (Input => ParseResult[T]) {
    /** An unspecified method that defines the behaviour of this parser.
     */
    def apply(in: Input): ParseResult[T]

                                      
    // the operator formerly known as +++, ++, &, but now, behold the venerable ~
    // it's short, light (looks like whitespace), has few overloaded meaning (thanks to the recent change from ~ to unary_~)
    // and we love it!
                                      
    /** A parser combinator for sequential composition 
     *
     * <p> `p ~ q' succeeds if `p' succeeds and `q' succeeds on the input
     *          left over by `p'.</p>
     * 
     * @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.
     */
    def ~ [U](q: => Parser[U]): Parser[~[T, U]] = new Parser[~[T, U]] {
      def apply(in: Input) = seq(Parser.this, q)((x, y) => new ~(x,y))(in)
      override def toString = "~"
    }
   
     /* not really useful: V cannot be inferred because Parser is covariant in first type parameter (V is always trivially Nothing)
    def ~~ [U, V](q: => Parser[U])(implicit combine: (T, U) => V): Parser[V] = new Parser[V] {
      def apply(in: Input) = seq(Parser.this, q)((x, y) => combine(x,y))(in)
    }  */   
     
    /** A parser combinator for sequential composition with a unit-parser 
     *
     * <p> `p ~ q' succeeds if `p' succeeds and `q' succeeds on the input
     *          left over by `p'.</p>
     *
     * @param q a parser (convertible to a UnitParser) that will be executed after `p' (this parser)
     *          succeeds
     * @return a `Parser' that -- on success -- returns the result of `p'.
     *         The resulting parser fails if either `p' or `q' fails.
     */ 
    def ~ [Q <% UnitParser](q: => Q): Parser[T] = new Parser[T] {
      def apply(in: Input) = seq(Parser.this, q)((x, y) => x)(in)
      override def toString = "~"
    }
    
    /** A parser combinator for non-back-tracking sequential composition 
     *
     *<p>`p ~! q' succeeds if `p' succeeds and `q' succeeds on the input
     *          left over by `p'. In case of failure, no back-tracking is performed 
     *          (in an earlier parser produced by the | combinator).</p>
     * 
     * @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](q: => Parser[U]): Parser[~[T, U]] = new Parser[~[T, U]] with OnceParser[~[T, U]] {
      def apply(in: Input) = seq(Parser.this, commit(q))((x, y) => new ~(x,y))(in)
      override def toString = "~!"
    }
    
    /** A parser combinator for non-back-tracking sequential composition with a unit-parser
     *
     *<p>`p ~! q' succeeds if `p' succeeds and `q' succeeds on the input
     *          left over by `p'. In case of failure, no back-tracking is performed 
     *          (in an earlier parser produced by the | combinator).</p>
     * 
     * @param q a parser that will be executed after `p' (this parser) succeeds
     * @return a `Parser' that -- on success -- returns the result of `p'.
     *         The resulting parser fails if either `p' or `q' fails, this failure is fatal.
     */
    def ~! [Q <% UnitParser](q: => Q): Parser[T] = new Parser[T] with OnceParser[T] {
      def apply(in: Input) = seq(Parser.this, commit(q))((x, y) => x)(in)
      override def toString = "~!"
    }

    /** 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] = new Parser[U] {
      def apply(in: Input) = Parser.this(in) match {
        case s1 @ Success(_, _) => s1
        case e1 @ Error(_, _) => e1
        case f1 @ Failure(_, next1) => q(in) match {
              case s2 @ Success(_, _) => s2
              case f2 @ Failure(_, next2) => if (next2.pos < next1.pos) f1 else f2
              case e2 @ Error(_, next2) => if (next2.pos < next1.pos) f1 else e2
        }
      }
      override def toString = "|"
    }
    
    /** 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] = new Parser[U] {
      def apply(in: Input) = Parser.this(in).map(f)
      override def toString = Parser.this.toString+"^^"
    }    
    
    /** 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'.