package combinator
Type Members
-
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). Theflatten*coercions makes it easy to apply ann-argument function to a nested~of depthn-1The
headOptionTailToFunListconverts a function that takes aList[A]to a function that accepts a~[A, Option[List[A]]](this happens when parsing something of the following shape:p ~ opt("." ~ repsep(p, "."))-- wherepis a parser that yields anA). -
trait
JavaTokenParsers extends RegexParsers
JavaTokenParsersdiffers from scala.util.parsing.combinator.RegexParsers by adding the following definitions:JavaTokenParsersdiffers from scala.util.parsing.combinator.RegexParsers by adding the following definitions:identwholeNumberdecimalNumberstringLiteralfloatingPointNumber
-
trait
PackratParsers extends Parsers
PackratParsersis a component that extends the parser combinators provided by scala.util.parsing.combinator.Parsers with a memoization facility (Packrat Parsing).PackratParsersis 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
PackratParsersis very similar to usingParsers:- any class/trait that extends
Parsers(directly or through a subclass) can mix inPackratParsers. Example:object MyGrammar extends StandardTokenParsers with PackratParsers - each grammar production previously declared as a
defwithout formal parameters becomes alazy val, and its type is changed fromParser[Elem]toPackratParser[Elem]. So, for example,def production: Parser[Int] = {...}becomeslazy val production: PackratParser[Int] = {...} - Important: using
PackratParsers is not an all or nothing decision. They can be free mixed with regularParsers in a single grammar.
Cached parse results are attached to the input, not the grammar. Therefore,
PackratsParsers require aPackratReaderas input, which adds memoization to an underlyingReader. Programmers can createPackratReaderobjects either manually, as inproduction(new PackratReader(new lexical.Scanner("input"))), but the common way should be to rely on the combinatorphraseto wrap a given input with aPackratReaderif 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
- any class/trait that extends
-
trait
Parsers extends AnyRef
Parsersis a component that provides generic parser combinators.Parsersis a component that provides generic parser combinators.There are two abstract members that must be defined in order to produce parsers: the type
Elemand scala.util.parsing.combinator.Parsers.Parser. There are helper methods that produce concreteParserimplementations -- see primitive parser below.A
Parsersmay define multipleParserinstances, 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:
- success or failure
- 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
applymethod 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
p1andp2of 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
Parsersand returning aParserprovided 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,errandfailureas examples.- See also
scala.util.parsing.combinator.RegexParsers and other known subclasses for practical examples.
-
trait
RegexParsers extends Parsers
The most important differences between
RegexParsersand scala.util.parsing.combinator.Parsers are:The most important differences between
RegexParsersand scala.util.parsing.combinator.Parsers are:Elemis 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 totrue) and, if true, skip any whitespace before each parser is called. - Protected val
whiteSpacereturns a regex that identifies whitespace.
For example, this creates a very simple calculator receiving
Stringinput: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) } }