Packages

p

scala.util.parsing

combinator

package combinator

Type Members

  1. trait ImplicitConversions extends AnyRef

    This object contains implicit conversions that come in handy when using the ^^ combinator.

    This object contains implicit conversions that come in handy when using the ^^ combinator.

    Refer to scala.util.parsing.combinator.Parsers to construct an AST from the concrete syntax.

    The reason for this is that the sequential composition combinator (~) combines its constituents into a ~. When several ~s are combined, this results in nested ~s (to the left). The flatten* coercions makes it easy to apply an n-argument function to a nested ~ of depth n-1

    The headOptionTailToFunList converts a function that takes a List[A] to a function that accepts a ~[A, Option[List[A]]] (this happens when parsing something of the following shape: p ~ opt("." ~ repsep(p, ".")) -- where p is a parser that yields an A).

  2. trait JavaTokenParsers extends RegexParsers

    JavaTokenParsers differs from scala.util.parsing.combinator.RegexParsers by adding the following definitions:

    JavaTokenParsers differs from scala.util.parsing.combinator.RegexParsers by adding the following definitions:

    • ident
    • wholeNumber
    • decimalNumber
    • stringLiteral
    • floatingPointNumber
  3. trait PackratParsers extends Parsers

    PackratParsers is a component that extends the parser combinators provided by scala.util.parsing.combinator.Parsers with a memoization facility (Packrat Parsing).

    PackratParsers is a component that extends the parser combinators provided by scala.util.parsing.combinator.Parsers with a memoization facility (Packrat Parsing).

    Packrat Parsing is a technique for implementing backtracking, recursive-descent parsers, with the advantage that it guarantees unlimited lookahead and a linear parse time. Using this technique, left recursive grammars can also be accepted.

    Using PackratParsers is very similar to using Parsers:

    • any class/trait that extends Parsers (directly or through a subclass) can mix in PackratParsers. Example: object MyGrammar extends StandardTokenParsers with PackratParsers
    • each grammar production previously declared as a def without formal parameters becomes a lazy val, and its type is changed from Parser[Elem] to PackratParser[Elem]. So, for example, def production: Parser[Int] = {...} becomes lazy val production: PackratParser[Int] = {...}
    • Important: using PackratParsers is not an all or nothing decision. They can be free mixed with regular Parsers in a single grammar.

    Cached parse results are attached to the input, not the grammar. Therefore, PackratsParsers require a PackratReader as input, which adds memoization to an underlying Reader. Programmers can create PackratReader objects either manually, as in production(new PackratReader(new lexical.Scanner("input"))), but the common way should be to rely on the combinator phrase to wrap a given input with a PackratReader if the input is not one itself.

    Since

    2.8

    See also

    Alessandro Warth, James R. Douglass, Todd Millstein: "Packrat Parsers Can Support Left Recursion." PEPM'08

    Bryan Ford: "Packrat Parsing: Simple, Powerful, Lazy, Linear Time." ICFP'02

  4. trait Parsers extends AnyRef

    Parsers is a component that provides generic parser combinators.

    Parsers is a component that provides generic parser combinators.

    There are two abstract members that must be defined in order to produce parsers: the type Elem and scala.util.parsing.combinator.Parsers.Parser. There are helper methods that produce concrete Parser implementations -- see primitive parser below.

    A Parsers may define multiple Parser instances, which are combined to produced the desired parser.

    The type of the elements these parsers should parse must be defined by declaring Elem (each parser is polymorphic in the type of result it produces).

    There are two aspects to the result of a parser:

    1. success or failure
    2. the result.

    A scala.util.parsing.combinator.Parsers.Parser produces both kinds of information, by returning a scala.util.parsing.combinator.Parsers.ParseResult when its apply method is called on an input.

    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. For example, given p1 and p2 of type scala.util.parsing.combinator.Parsers.Parser:

    p1 ~ p2 // sequencing: must match p1 followed by p2
    p1 | p2 // alternation: must match either p1 or p2, with preference given to p1
    p1.?    // optionality: may match p1 or not
    p1.*    // repetition: matches any number of repetitions of p1

    These combinators are provided as methods on scala.util.parsing.combinator.Parsers.Parser, or as methods taking one or more Parsers and returning a Parser provided in this class.

    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...

    • is equal to some given object (see method accept),
    • satisfies a certain predicate (see method acceptIf),
    • is in the domain of a given partial function (see method acceptMatch)
    • or other conditions, by using one of the other methods available, or subclassing Parser

    Even more primitive parsers always produce the same result, irrespective of the input. See methods success, err and failure as examples.

    See also

    scala.util.parsing.combinator.RegexParsers and other known subclasses for practical examples.

  5. trait RegexParsers extends Parsers

    The most important differences between RegexParsers and scala.util.parsing.combinator.Parsers are:

    The most important differences between RegexParsers and scala.util.parsing.combinator.Parsers are:

    • Elem is defined to be scala.Char
    • There's an implicit conversion from java.lang.String to Parser[String], so that string literals can be used as parser combinators.
    • There's an implicit conversion from scala.util.matching.Regex to Parser[String], so that regex expressions can be used as parser combinators.
    • The parsing methods call the method skipWhitespace (defaults to true) and, if true, skip any whitespace before each parser is called.
    • Protected val whiteSpace returns a regex that identifies whitespace.

    For example, this creates a very simple calculator receiving String input:

    object Calculator extends RegexParsers {
      def number: Parser[Double] = """\d+(\.\d*)?""".r ^^ { _.toDouble }
      def factor: Parser[Double] = number | "(" ~> expr <~ ")"
      def term  : Parser[Double] = factor ~ rep( "*" ~ factor | "/" ~ factor) ^^ {
        case number ~ list => (number /: list) {
          case (x, "*" ~ y) => x * y
          case (x, "/" ~ y) => x / y
        }
      }
      def expr  : Parser[Double] = term ~ rep("+" ~ log(term)("Plus term") | "-" ~ log(term)("Minus term")) ^^ {
        case number ~ list => list.foldLeft(number) { // same as before, using alternate name for /:
          case (x, "+" ~ y) => x + y
          case (x, "-" ~ y) => x - y
        }
      }
    
      def apply(input: String): Double = parseAll(expr, input) match {
        case Success(result, _) => result
        case failure : NoSuccess => scala.sys.error(failure.msg)
      }
    }

Ungrouped