scala.util.parsing.combinator

# PackratParsers

#### trait PackratParsers extends Parsers

`PackratParsers` is a component that extends the parser combinators provided by `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 `PackratParser`s is not an ``all or nothing decision. They can be free mixed with regular `Parser`s in a single grammar.

Cached parse results are attached to the input, not the grammar. Therefore, `PackratsParser`s 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.

Source
  PackratParsers.scala
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
Parsers, AnyRef, Any
Ordering

1. Alphabetic
2. By inheritance

Inherited

1. Hide All
2. Show all

1. PackratParsers
2. Parsers
3. AnyRef
4. Any

Visibility

1. Public
2. All

### Type Members

1. #### 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. Nonetheless, the same principles apply, regardless of the input type.)

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

   Attributes
     abstract
   Definition Classes
     Parsers

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

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

4. #### type Input = Reader[Elem]

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

   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

5. #### class NoSuccess extends ParseResult[Nothing]

   A common super-class for unsuccessful parse results

6. #### trait OnceParser [+T] extends Parser[T]

   A parser whose ~ combinator disallows back-tracking.

7. #### class PackratParser [+T] extends Parser[T]

   The root class of packrat parsers.

8. #### class PackratReader [+T] extends Reader[T]

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

9. #### class ParseResult [+T] extends AnyRef

   A base class for parser results.

10. #### class Parser [+T] extends (Input) ⇒ ParseResult[T]

    The root class of 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.

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

### Value Members

1. #### def != (arg0: AnyRef): Boolean

   Attributes
     final
   Definition Classes
     AnyRef

2. #### def != (arg0: Any): Boolean

   Test two objects for inequality.

   Test two objects for inequality.

   returns

     `true` if !(this == that), false otherwise.

   Attributes
     final
   Definition Classes
     Any

3. #### def ## (): Int

   Equivalent to `x.hashCode` except for boxed numeric types.

   Equivalent to `x.hashCode` except for boxed numeric types. For numerics, it returns a hash value which is consistent with value equality: if two value type instances compare as true, then ## will produce the same hash value for each of them.

   returns

     a hash value consistent with ==

   Attributes
     final
   Definition Classes
     AnyRef → Any

4. #### def == (arg0: AnyRef): Boolean

   Attributes
     final
   Definition Classes
     AnyRef

5. #### def == (arg0: Any): Boolean

   Test two objects for equality.

   Test two objects for equality.

   returns

     `true` if the receiver object is equivalent to the argument; `false` otherwise.

   Attributes
     final
   Definition Classes
     Any

6. #### object NoSuccess extends AnyRef

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

7. #### def OnceParser [T] (f: (Input) ⇒ ParseResult[T]): Parser[T] with OnceParser[T]

   Definition Classes
     Parsers

8. #### def Parser [T] (f: (Input) ⇒ ParseResult[T]): Parser[T]

   Definition Classes
     Parsers

9. #### 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' 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 <code>accept("name", {case Identifier(n) => Name(n)})</code> accepts an <code>Identifier(n)</code> and returns a <code>Name(n)</code>.`

   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 <code>accept("name", {case Identifier(n) => Name(n)})</code> accepts an <code>Identifier(n)</code> and returns a <code>Name(n)</code>.`

   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

10. #### def accept [ES] (es: ES)(implicit arg0: (ES) ⇒ List[Elem]): Parser[List[Elem]]

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

    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

11. #### implicit def accept (e: Elem): Parser[Elem]

    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` Token's, Identifier("new") (which is a `Token') can be used directly, instead of first creating a` Parser' using accept(Identifier("new")).

    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` Token's, 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.

    Attributes
      implicit
    Definition Classes
      Parsers

12. #### def acceptIf (p: (Elem) ⇒ Boolean)(err: (Elem) ⇒ String): Parser[Elem]

    Definition Classes
      Parsers

13. #### def acceptMatch [U] (expected: String, f: PartialFunction[Elem, U]): Parser[U]

    Definition Classes
      Parsers

14. #### def acceptSeq [ES] (es: ES)(implicit arg0: (ES) ⇒ Iterable[Elem]): Parser[List[Elem]]

    Definition Classes
      Parsers

15. #### def asInstanceOf [T0] : T0

    Cast the receiver object to be of type `T0`.

    Cast the receiver object to be of type `T0`.

    Note that the success of a cast at runtime is modulo Scala's erasure semantics. Therefore the expression `1.asInstanceOf[String]` will throw a `ClassCastException` at runtime, while the expression `List(1).asInstanceOf[List[String]]` will not. In the latter example, because the type argument is erased as part of compilation it is not possible to check whether the contents of the list are of the requested type.

    returns

      the receiver object.

    Attributes
      final
    Definition Classes
      Any

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

17. #### 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. 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.`

    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

18. #### 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. 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)`

    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

19. #### def clone (): AnyRef

    Create a copy of the receiver object.

    Create a copy of the receiver object.

    The default implementation of the `clone` method is platform dependent.

    returns

      a copy of the receiver object.

    Attributes
      protected[lang]
    Definition Classes
      AnyRef
    Annotations
      @throws()

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

21. #### def elem (e: Elem): Parser[Elem]

    A parser that matches only the given element `e' elem(e) succeeds if the input starts with an 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

22. #### 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. @return

    Definition Classes
      Parsers

23. #### def eq (arg0: AnyRef): Boolean

    Tests whether the argument (`arg0`) is a reference to the receiver object (`this`).

    Tests whether the argument (`arg0`) is a reference to the receiver object (`this`).

    The `eq` method implements an equivalence relation on non-null instances of `AnyRef`, and has three additional properties:

    - It is consistent: for any non-null instances `x` and `y` of type `AnyRef`, multiple invocations of `x.eq(y)` consistently returns `true` or consistently returns `false`.
    - For any non-null instance `x` of type `AnyRef`, `x.eq(null)` and `null.eq(x)` returns `false`.
    - `null.eq(null)` returns `true`.

    When overriding the `equals` or `hashCode` methods, it is important to ensure that their behavior is consistent with reference equality. Therefore, if two objects are references to each other (`o1 eq o2`), they should be equal to each other (`o1 == o2`) and they should hash to the same value (`o1.hashCode == o2.hashCode`).

    returns

      `true` if the argument is a reference to the receiver object; `false` otherwise.

    Attributes
      final
    Definition Classes
      AnyRef

24. #### def equals (arg0: Any): Boolean

    The equality method for reference types.

    The equality method for reference types. See equals in Any.

    returns

      `true` if the receiver object is equivalent to the argument; `false` otherwise.

    Definition Classes
      AnyRef → Any

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

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

27. #### def finalize (): Unit

    Called by the garbage collector on the receiver object when there are no more references to the object.

    Called by the garbage collector on the receiver object when there are no more references to the object.

    The details of when and if the `finalize` method is invoked, as well as the interaction between `finalize` and non-local returns and exceptions, are all platform dependent.

    Attributes
      protected[lang]
    Definition Classes
      AnyRef
    Annotations
      @throws()

28. #### def getClass (): java.lang.Class[_]

    A representation that corresponds to the dynamic class of the receiver object.

    A representation that corresponds to the dynamic class of the receiver object.

    The nature of the representation is platform dependent.

    returns

      a representation that corresponds to the dynamic class of the receiver object.

    Attributes
      final
    Definition Classes
      AnyRef → Any

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

30. #### def hashCode (): Int

    The hashCode method for reference types.

    The hashCode method for reference types. See hashCode in Any.

    returns

      the hash code value for this object.

    Definition Classes
      AnyRef → Any

31. #### def isInstanceOf [T0] : Boolean

    Test whether the dynamic type of the receiver object is `T0`.

    Test whether the dynamic type of the receiver object is `T0`.

    Note that the result of the test is modulo Scala's erasure semantics. Therefore the expression `1.isInstanceOf[String]` will return `false`, while the expression `List(1).isInstanceOf[List[String]]` will return `true`. In the latter example, because the type argument is erased as part of compilation it is not possible to check whether the contents of the list are of the specified type.

    returns

      `true` if the receiver object is an instance of erasure of type `T0`; `false` otherwise.

    Attributes
      final
    Definition Classes
      Any

32. #### var lastNoSuccess : NoSuccess

    Definition Classes
      Parsers

33. #### def log [T] (p: ⇒ Parser[T])(name: String): Parser[T]

    Definition Classes
      Parsers

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

35. #### def mkList [T] : (~[T, List[T]]) ⇒ List[T]

    Definition Classes
      Parsers

36. #### def ne (arg0: AnyRef): Boolean

    Equivalent to `!(this eq that)`.

    Equivalent to `!(this eq that)`.

    returns

      `true` if the argument is not a reference to the receiver object; `false` otherwise.

    Attributes
      final
    Definition Classes
      AnyRef

37. #### def not [T] (p: ⇒ Parser[T]): Parser[Unit]

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

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

    Definition Classes
      Parsers

38. #### def notify (): Unit

    Wakes up a single thread that is waiting on the receiver object's monitor.

    Wakes up a single thread that is waiting on the receiver object's monitor.

    Attributes
      final
    Definition Classes
      AnyRef

39. #### def notifyAll (): Unit

    Wakes up all threads that are waiting on the receiver object's monitor.

    Wakes up all threads that are waiting on the receiver object's monitor.

    Attributes
      final
    Definition Classes
      AnyRef

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

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

    Attributes
      implicit

42. #### def phrase [T] (p: Parser[T]): PackratParser[T]

    A parser generator delimiting whole phrases (i.

    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 <code>p</code> consumed all the input.`

    Definition Classes
      PackratParsers → Parsers

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

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

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

      "As of 2.9, the p0 call-by-name arguments is evaluated at most once per constructed Parser object, instead of on every need that arises during parsing."

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

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

48. #### 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')`

    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

49. #### 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: <code>repsep(term, ",")</code> 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

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

51. #### def synchronized [T0] (arg0: ⇒ T0): T0

    Attributes
      final
    Definition Classes
      AnyRef

52. #### def toString (): String

    Creates a String representation of this object.

    Creates a String representation of this object. The default representation is platform dependent. On the java platform it is the concatenation of the class name, "@", and the object's hashcode in hexadecimal.

    returns

      a String representation of the object.

    Definition Classes
      AnyRef → Any

53. #### def wait (): Unit

    Attributes
      final
    Definition Classes
      AnyRef
    Annotations
      @throws()

54. #### def wait (arg0: Long, arg1: Int): Unit

    Attributes
      final
    Definition Classes
      AnyRef
    Annotations
      @throws()

55. #### def wait (arg0: Long): Unit

    Attributes
      final
    Definition Classes
      AnyRef
    Annotations
      @throws()

### Inherited from Parsers

### Inherited from AnyRef

### Inherited from Any