Packages

t

scala.util.parsing.combinator

PackratParsers

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

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

Linear Supertypes
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. PackratParsers
  2. Parsers
  3. AnyRef
  4. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Type Members

  1. abstract type Elem

    the type of input 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.

    the type of input 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.)

    Definition Classes
    Parsers
  2. type Input = Reader[Elem]

    The parser input is an abstract reader of input elements, i.e.

    The parser input is an abstract reader of input elements, i.e. the type of input the parsers in this component expect.

    Definition Classes
    Parsers
  3. abstract class PackratParser [+T] extends Parser[T]

    The root class of packrat parsers.

  4. class PackratReader [+T] extends Reader[T]

    A specialized Reader class that wraps an underlying Reader and provides memoization of parse results.

  5. case class Error (msg: String, next: Input) extends NoSuccess with Product with Serializable

    The fatal failure case of ParseResult: contains an error-message and the remaining input.

    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.

    msg

    An error message string describing the error.

    next

    The parser's unconsumed input at the point where the error occurred.

    Definition Classes
    Parsers
  6. case class Failure (msg: String, next: Input) extends NoSuccess with Product with Serializable

    The failure case of ParseResult: contains an error-message and the remaining input.

    The failure case of ParseResult: contains an error-message and the remaining input. Parsing will back-track when a failure occurs.

    msg

    An error message string describing the failure.

    next

    The parser's unconsumed input at the point where the failure occurred.

    Definition Classes
    Parsers
  7. sealed abstract class NoSuccess extends ParseResult[Nothing]

    A common super-class for unsuccessful parse results.

    A common super-class for unsuccessful parse results.

    Definition Classes
    Parsers
  8. trait OnceParser [+T] extends Parser[T]

    A parser whose ~ combinator disallows back-tracking.

    A parser whose ~ combinator disallows back-tracking.

    Definition Classes
    Parsers
  9. sealed abstract class ParseResult [+T] extends AnyRef

    A base class for parser results.

    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 T which consists of some result (and the rest of the input).

    Definition Classes
    Parsers
  10. abstract class Parser [+T] extends (Input) ⇒ ParseResult[T]

    The root class of parsers.

    The root class of parsers. Parsers are functions from the Input type to ParseResult.

    Definition Classes
    Parsers
  11. case class Success [+T](result: T, next: Input) extends ParseResult[T] with Product with Serializable

    The success case of ParseResult: contains the result and the remaining input.

    The success case of ParseResult: contains the result and the remaining input.

    result

    The parser's output

    next

    The parser's remaining input

    Definition Classes
    Parsers
  12. case class ~ [+a, +b](_1: a, _2: b) extends Product with Serializable

    A wrapper over sequence of matches.

    A wrapper over sequence of matches.

    Given p1: Parser[A] and p2: Parser[B], a parser composed with p1 ~ p2 will have type Parser[~[A, B]]. The successful result of the parser can be extracted from this case class.

    It also enables pattern matching, so something like this is possible:

    def concat(p1: Parser[String], p2: Parser[String]): Parser[String] =
      p1 ~ p2 ^^ { case a ~ b => a + b }
    Definition Classes
    Parsers

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. def OnceParser[T](f: (Input) ⇒ ParseResult[T]): Parser[T] with OnceParser[T]
    Definition Classes
    Parsers
  5. def Parser[T](f: (Input) ⇒ ParseResult[T]): Parser[T]
    Definition Classes
    Parsers
  6. def accept[U](expected: String, f: PartialFunction[Elem, U]): Parser[U]

    The parser that matches an element in the domain of the partial function f.

    The parser that matches an element in the domain of the partial function f.

    If f is defined on the first element in the input, f is applied to it to produce this parser's result.

    Example: The parser accept("name", {case Identifier(n) => Name(n)}) accepts an Identifier(n) and returns a Name(n)

    expected

    a description of the kind of element this parser expects (for error messages)

    f

    a partial function that determines when this parser is successful and what its output is

    returns

    A parser that succeeds if f is applicable to the first element of the input, applying f to it to produce the result.

    Definition Classes
    Parsers
  7. def accept[ES](es: ES)(implicit arg0: (ES) ⇒ List[Elem]): Parser[List[Elem]]

    A parser that matches only the given list of element es.

    A parser that matches only the given list of element es.

    accept(es) succeeds if the input subsequently provides the elements in the list es.

    es

    the list of expected elements

    returns

    a Parser that recognizes a specified list of elements

    Definition Classes
    Parsers
  8. implicit def accept(e: Elem): Parser[Elem]

    A parser that matches only the given element e.

    A parser that matches only the given element e.

    The method is implicit so that elements can automatically be lifted to their parsers. For example, when parsing Tokens, Identifier("new") (which is a Token) can be used directly, instead of first creating a Parser using accept(Identifier("new")).

    e

    the Elem that must be the next piece of input for the returned parser to succeed

    returns

    a tParser that succeeds if e is the next available input.

    Definition Classes
    Parsers
  9. def acceptIf(p: (Elem) ⇒ Boolean)(err: (Elem) ⇒ String): Parser[Elem]

    A parser matching input elements that satisfy a given predicate.

    A parser matching input elements that satisfy a given predicate.

    acceptIf(p)(el => "Unexpected "+el) succeeds if the input starts with an element e for which p(e) is true.

    p

    A predicate that determines which elements match.

    err

    A function from the received element into an error message.

    returns

    A parser for elements satisfying p(e).

    Definition Classes
    Parsers
  10. def acceptMatch[U](expected: String, f: PartialFunction[Elem, U]): Parser[U]

    The parser that matches an element in the domain of the partial function f.

    The parser that matches an element in the domain of the partial function f.

    If f is defined on the first element in the input, f is applied to it to produce this parser's result.

    Example: The parser acceptMatch("name", {case Identifier(n) => Name(n)}) accepts an Identifier(n) and returns a Name(n)

    expected

    a description of the kind of element this parser expects (for error messages)

    f

    a partial function that determines when this parser is successful and what its output is

    returns

    A parser that succeeds if f is applicable to the first element of the input, applying f to it to produce the result.

    Definition Classes
    Parsers
  11. def acceptSeq[ES](es: ES)(implicit arg0: (ES) ⇒ Iterable[Elem]): Parser[List[Elem]]

    A parser that matches only the given scala.collection.Iterable collection of elements es.

    A parser that matches only the given scala.collection.Iterable collection of elements es.

    acceptSeq(es) succeeds if the input subsequently provides the elements in the iterable es.

    es

    the list of expected elements

    returns

    a Parser that recognizes a specified list of elements

    Definition Classes
    Parsers
  12. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  13. def chainl1[T, U](first: ⇒ Parser[T], p: ⇒ Parser[U], q: ⇒ Parser[(T, U) ⇒ T]): Parser[T]

    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.

    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.

    first

    a parser that parses the first element

    p

    a parser that parses the subsequent elements

    q

    a parser that parses the token(s) separating the elements, yielding a left-associative function that combines two elements into one

    Definition Classes
    Parsers
  14. def chainl1[T](p: ⇒ Parser[T], q: ⇒ Parser[(T, T) ⇒ T]): Parser[T]

    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.

    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.

    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

    a parser that parses the elements

    q

    a parser that parses the token(s) separating the elements, yielding a left-associative function that combines two elements into one

    Definition Classes
    Parsers
  15. def chainr1[T, U](p: ⇒ Parser[T], q: ⇒ Parser[(T, U) ⇒ U], combine: (T, U) ⇒ U, first: U): Parser[U]

    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.

    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 combining 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)

    p

    a parser that parses the elements

    q

    a parser that parses the token(s) separating the elements, yielding a right-associative function that combines two elements into one

    combine

    the "last" (left-most) combination function to be applied

    first

    the "first" (right-most) element to be combined

    Definition Classes
    Parsers
  16. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  17. def commit[T](p: ⇒ Parser[T]): Parser[T]

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

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

    Definition Classes
    Parsers
  18. def elem(e: Elem): Parser[Elem]

    A parser that matches only the given element e.

    A parser that matches only the given element e.

    elem(e) succeeds if the input starts with an element e.

    e

    the Elem that must be the next piece of input for the returned parser to succeed

    returns

    a Parser that succeeds if e is the next available input (and returns it).

    Definition Classes
    Parsers
  19. def elem(kind: String, p: (Elem) ⇒ Boolean): Parser[Elem]

    A parser matching input elements that satisfy a given predicate.

    A parser matching input elements that satisfy a given predicate.

    elem(kind, p) succeeds if the input starts with an element e for which p(e) is true.

    kind

    The element kind, used for error messages

    p

    A predicate that determines which elements match.

    Definition Classes
    Parsers
  20. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  21. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  22. def err(msg: String): Parser[Nothing]

    A parser that results in an error.

    A parser that results in an error.

    msg

    The error message describing the failure.

    returns

    A parser that always fails with the specified error message.

    Definition Classes
    Parsers
  23. def failure(msg: String): Parser[Nothing]

    A parser that always fails.

    A parser that always fails.

    msg

    The error message describing the failure.

    returns

    A parser that always fails with the specified error message.

    Definition Classes
    Parsers
  24. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  25. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  26. def guard[T](p: ⇒ Parser[T]): Parser[T]

    A parser generator for guard expressions.

    A parser generator for guard expressions. The resulting parser will fail or succeed just like the one given as parameter but it will not consume any input.

    p

    a Parser that is to be applied to the input

    returns

    A parser that returns success if and only if p succeeds but never consumes any input

    Definition Classes
    Parsers
  27. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  28. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  29. def log[T](p: ⇒ Parser[T])(name: String): Parser[T]

    A helper method that turns a Parser into one that will print debugging information to stdout before and after being applied.

    A helper method that turns a Parser into one that will print debugging information to stdout before and after being applied.

    Definition Classes
    Parsers
  30. def memo[T](p: Parser[T]): PackratParser[T]

    Explicitly convert a given parser to a memoizing packrat parser.

    Explicitly convert a given parser to a memoizing packrat parser. In most cases, client code should avoid calling memo directly and rely on implicit conversion instead.

  31. def mkList[T]: (~[T, List[T]]) ⇒ collection.immutable.List[T]

    Given a concatenation with a repetition (list), move the concatenated element into the list

    Given a concatenation with a repetition (list), move the concatenated element into the list

    Definition Classes
    Parsers
  32. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  33. def not[T](p: ⇒ Parser[T]): Parser[Unit]

    Wrap a parser so that its failures and errors become success and vice versa -- it never consumes any input.

    Wrap a parser so that its failures and errors become success and vice versa -- it never consumes any input.

    Definition Classes
    Parsers
  34. final def notify(): Unit
    Definition Classes
    AnyRef
  35. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  36. def opt[T](p: ⇒ Parser[T]): Parser[Option[T]]

    A parser generator for optional sub-phrases.

    A parser generator for optional sub-phrases.

    opt(p) is a parser that returns Some(x) if p returns x and None if p fails.

    p

    A Parser that is tried on the input

    returns

    a Parser that always succeeds: either with the result provided by p or with the empty result

    Definition Classes
    Parsers
  37. implicit def parser2packrat[T](p: ⇒ Parser[T]): PackratParser[T]

    Implicitly convert a parser to a packrat parser.

    Implicitly convert a parser to a packrat parser. The conversion is triggered by giving the appropriate target type:

    val myParser: PackratParser[MyResult] = aParser
  38. def phrase[T](p: Parser[T]): PackratParser[T]

    A parser generator delimiting whole phrases (i.e.

    A parser generator delimiting whole phrases (i.e. programs).

    Overridden to make sure any input passed to the argument parser is wrapped in a PackratReader.

    p

    the parser that must consume all input for the resulting parser to succeed.

    returns

    a parser that has the same result as p, but that only succeeds if p consumed all the input.

    Definition Classes
    PackratParsersParsers
  39. def positioned[T <: Positional](p: ⇒ Parser[T]): Parser[T]

    positioned decorates a parser's result with the start position of the input it consumed.

    positioned decorates a parser's result with the start position of the input it consumed.

    p

    a Parser whose result conforms to Positional.

    returns

    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.

    Definition Classes
    Parsers
  40. def rep[T](p: ⇒ Parser[T]): Parser[List[T]]

    A parser generator for repetitions.

    A parser generator for repetitions.

    rep(p) repeatedly uses p to parse the input until p fails (the result is a List of the consecutive results of p).

    p

    a Parser that is to be applied successively to the input

    returns

    A parser that returns a list of results produced by repeatedly applying p to the input.

    Definition Classes
    Parsers
  41. def rep1[T](first: ⇒ Parser[T], p0: ⇒ Parser[T]): Parser[List[T]]

    A parser generator for non-empty repetitions.

    A parser generator for non-empty repetitions.

    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)

    first

    a Parser that parses the first piece of input

    p0

    a Parser that is to be applied successively to the rest of the input (if any) -- evaluated at most once, and only when necessary

    returns

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

    Definition Classes
    Parsers
    Annotations
    @migration
    Migration

    (Changed in version 2.9.0) The p0 call-by-name arguments is evaluated at most once per constructed Parser object, instead of on every need that arises during parsing.

  42. def rep1[T](p: ⇒ Parser[T]): Parser[List[T]]

    A parser generator for non-empty repetitions.

    A parser generator for non-empty repetitions.

    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

    a Parser that is to be applied successively to the input

    returns

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

    Definition Classes
    Parsers
  43. def rep1sep[T](p: ⇒ Parser[T], q: ⇒ Parser[Any]): Parser[List[T]]

    A parser generator for non-empty repetitions.

    A parser generator for non-empty repetitions.

    rep1sep(p, q) repeatedly applies p interleaved with q to parse the input, until p fails. The parser p must succeed at least once.

    p

    a Parser that is to be applied successively to the input

    q

    a Parser that parses the elements that separate the elements parsed by p (interleaved with q)

    returns

    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.

    Definition Classes
    Parsers
  44. def repN[T](num: Int, p: ⇒ Parser[T]): Parser[List[T]]

    A parser generator for a specified number of repetitions.

    A parser generator for a specified number of repetitions.

    repN(n, p) uses p exactly n time to parse the input (the result is a List of the n consecutive results of p).

    num

    the exact number of times p must succeed

    p

    a Parser that is to be applied successively to the input

    returns

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

    Definition Classes
    Parsers
  45. def repsep[T](p: ⇒ Parser[T], q: ⇒ Parser[Any]): Parser[List[T]]

    A parser generator for interleaved repetitions.

    A parser generator for interleaved repetitions.

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

    Example: repsep(term, ",") parses a comma-separated list of term's, yielding a list of these terms.

    p

    a Parser that is to be applied successively to the input

    q

    a Parser that parses the elements that separate the elements parsed by p

    returns

    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.

    Definition Classes
    Parsers
  46. def success[T](v: T): Parser[T]

    A parser that always succeeds.

    A parser that always succeeds.

    v

    The result for the parser

    returns

    A parser that always succeeds, with the given result v

    Definition Classes
    Parsers
  47. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  48. def toString(): String
    Definition Classes
    AnyRef → Any
  49. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  50. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  51. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  52. object NoSuccess

    An extractor so NoSuccess(msg, next) can be used in matches.

    An extractor so NoSuccess(msg, next) can be used in matches.

    Definition Classes
    Parsers

Inherited from Parsers

Inherited from AnyRef

Inherited from Any

Ungrouped